Тест по Computer Science — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по Computer Science, подготовил Участник:Ssyrovatkin

Вариант 2317196748.


Ваше имя*:


Вопрос 1

Для какой из изображенных ниже куч на минимум будут получены элементы массива в порядке возрастания, если для кучи применяется обход preorder traversal?

  1.  [svg]
  2.  [svg]
  3.  [svg]
  4.  [svg]

Вопрос 2

Рассмотрим следующие утверждения (h(k) — хэш-функция):

  • I. если даже .
  • II. для любых .
  • III. для любых .
  1.  Только I, II
  2.  Только II, III
  3.  I, II, III
  4.  Только I

Вопрос 3

Пусть имеется два отсортированных списка размера K и L соответственно. Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера K + L, состоящий из элементов этих списков?

  1.  
  2.  
  3.  
  4.  

Вопрос 4

Хэш функция с линейным зондированием используется для вставки ключей 37, 38, 72, 68, 98, 11, 74 в хэш-таблицу с индексом (0-6). Какой индекс соответствует ключу 74?

  1.  1
  2.  4
  3.  2
  4.  3

Вопрос 5

Пусть структура данных поддерживает операцию `foo`, таким образом, что последовательность из n операций `foo` занимает времени в худшем случае. Каково амортизационное время операции `foo`?

  1.  
  2.  
  3.  
  4.  

Вопрос 6

Чтобы выполнить поиск элемента в dynamic set, какой из следующих методов является асимптотически наиболее эффективным по времени в наихудшем случае для операции поиска?

  1.  Сохранять элемент в отсортированном массиве и применять бинарный поиск.
  2.  Все вышеперечисленное.
  3.  Сохранять элемент в хэш-таблице и использовать хэширование.
  4.  Сохранять элемент в несортированном массиве и применять линейный поиск.

Вопрос 7

Какой будет временная сложность печати всех ключей дерева бинарного поиска в отсортированном порядке?

  1.  
  2.  
  3.  
  4.  

Вопрос 8

Сколько существует различных бинарных деревьев с 8 узлами?

  1.  248
  2.  128
  3.  64
  4.  256

Вопрос 9

Какое из следующих рекуррентных соотношений не может быть использовано для алгоритма быстрой сортировки?

  1.  
  2.  
  3.   
  4.  

Вопрос 10

Предположим, что символы a,b,c,d,e встречаются с частотами . Какие получатся коды Хаффмана для букв a,b,c соответственно?

  1.  1101, 1100, 111
  2.  1101, 111, 1101
  3.  1100, 10, 0
  4.  1100, 1101, 111