Структуры и алгоритмы компьютерной обработки данных - тест 41

Упражнение 1:

---

Номер 1

Дана последовательность чисел: 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 8. Нумерация элементов начинается с нуля. Элемент с каким номером будет найден методом бинарного поиска по ключу key=5?

Ответ:

---

Номер 2

Дана последовательность чисел: 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 8, 8. Нумерация элементов начинается с нуля. Элемент с каким номером будет найден методом бинарного поиска по ключу key=8?

Ответ:

---

Номер 3

Дана последовательность n вещественных чисел. Необходимо найти число по ключу key с точностью e алгоритмом бинарного поиска. Оцените время выполнения алгоритма

Ответ:

---

Упражнение 2:

---

Номер 1

Дан программный код. Какое значение возвращает функция Search?
		
int Search(int *x, int k, int key){
  int i;
  for (i = k-1; i >=0 ; i--)
    if ( x[i] == key )
      break;
  return i > 0 ? i : -1;
}
		
		

Ответ:

---

Номер 2

Дан программный код. Какое значение возвращает функция Search?
		
int Search(int *x, int k, int key){
    x = (int *)realloc(x,(k+1)*sizeof(int));
    x[k] = key;
    int i = 0;
    while ( x[i] != key )
        i++;
    return i < k ? i : -1;
}
		
		

Ответ:

---

Номер 3

Дан программный код. Какое значение возвращает функция Search?
		
int Search(int *x, int k, int key){
  bool found = false;
  int high = k - 1, low = 0;
  int middle = (high + low) / 2;
  while ( !found && high >= low ){
    if (key == x[middle])
      found = true;
    else if (key < x[middle])
      high = middle - 1;
    else 
      low = middle + 1;
      middle = (high + low) / 2;
  } 
  return found ? middle : -1 ;
}
		
		

Ответ:

---

Упражнение 3:

---

Номер 1

Размер хеш-таблицы HashTableSize =7. Определите хеш-коды для первых пяти простых чисел, сформированные функцией Hash
		
int Hash(int Key, int HashTableSize) {
    return Key % HashTableSize;
}
		
		

Ответ:

---

Номер 2

Хеш-таблица формируется методом середин квадратов. Определите хеш-коды для первых пяти двузначных простых чисел, сформированные функцией Hash
		
int Hash(int Key) {
    return ((Key*Key)/10)%10 ;
}
		
		

Ответ:

---

Номер 3

Хеш-таблица формируется методом поразрядного сложения двузначных представлений цифр числа с последующим переводом результата в десятичное число. Определите хеш-коды для первых пяти двузначных составных чисел, сформированные функцией хеширования

Ответ:

---

Упражнение 4:

---

Номер 1

Технология данного метода хеширования состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. О каком методе хеширования идет речь?

Ответ:

---

Номер 2

При данном методе хешировании в хеш-таблице хранятся непосредственно сами элементы, а не заголовки списков элементов. Поэтому в каждой записи (сегменте) может храниться только один элемент. О каком методе хеширования идет речь?

Ответ:

---

Номер 3

Если осуществляется попытка поместить элемент х в сегмент с номером h(x), который уже занят другим элементом, то в соответствии с данной методикой выбирается последовательность других номеров сегментов h1(x),h2(x),..., куда можно поместить элемент х. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное. О какой методике хеширования идет речь?

Ответ:

---

Упражнение 5:

---

Номер 1

Укажите, на какую позицию произойдет второе смещение начала подстроки при поиске в тексте по алгоритму Кнута, Морриса и Пратта. Строка: АВСКВАВСМКВ, подстрока: ВСМ. Нумерация в строке начинается с нуля

Ответ:

---

Номер 2

Составьте таблицу смещений при поиске подстроки в строке по алгоритму Бойера и Мура. Строка: АВВОМРАВАВМАВ, подстрока: ВАВ. Нумерация в строке начинается с нуля

Ответ:

---

Номер 3

Укажите, на какую позицию произойдет пятое смещение начала подстроки при поиске в тексте по алгоритму Бойера и Мура. Строка: АВСССКВАВСМВВВК, подстрока: ВСМ. Нумерация в строке начинается с нуля

Ответ:

---

Упражнение 6:

---

Номер 1

Дано случайное дерево поиска. Укажите примеры входных последовательностей, которые могли бы сформировать данное дерево
		
		

Ответ:

---

Номер 2

На схеме показано вращение АВЛ-дерева. Определите вид вращения
		
		

Ответ:

---

Номер 3

Дано упорядоченное бинарное дерево. Укажите позицию вставки элемента с ключом 3 в это дерево, чтобы соблюдалась балансировка дерева
		
		

Ответ:

---

Упражнение 7:

---

Номер 1

Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите код символа 'е'. Считать, что очередной бит кода начинает формироваться с единицы
		
a
b
c
d
e
0,4
0,15
0,22
0,05
0,18
		

Ответ:

---

Номер 2

Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите среднюю длину кодового слова, которая равна сумме произведений вероятности на длину кода каждого символа соответственно. Считать, что очередной бит кода начинает формироваться с единицы
		
a
b
c
d
e
0,4
0,15
0,22
0,05
0,18
		

Ответ:

---

Номер 3

Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите длину кода символа 'b'. Считать, что очередной бит кода начинает формироваться с единицы
		
a
b
c
d
e
0,4
0,15
0,22
0,05
0,18
		

Ответ:

---

Упражнение 8:

---

Номер 1

Определите коэффициент сжатия текста "abcaabbaac", к которому применено сжатие по методу Хаффмана. Размер входной последовательности на 1 байт больше ее длины

Ответ:

---

Номер 2

Выполните кодирование текста "abcaabbaac", к которому применено сжатие по методу Хаффмана. Считать, что очередной бит кода начинает формироваться с единицы

Ответ:

---

Номер 3

Дано кодовое дерево. Каким из представленных строк оно соответствует?
		
		

Ответ:

---