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

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

Вариант 1548857618.


Ваше имя*:


Вопрос 1

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

  1.  Данное соотношение подходит для случая 3 Master теоремы
  2.  Master теорема не может быть применена, поскольку не является константой
  3.  Данное соотношение подходит для случая 2 Master теоремы
  4.  Данное соотношение подходит для случая 1 Master теоремы

Вопрос 2

Запустим алгоритм Дейкстры, начиная с вершины S, чтобы найти кратчайший путь T, и рассмотрим следующие утверждения:

  • I. Алгоритм Дейкстры возвращает кратчайший путь с минимальным общим весом.
  • II. Алгоритм Дейкстры возвращает кратчайший путь с минимальным количеством ребер.

Какие из данных утверждений верны?

  1.  Только I
  2.  Только II
  3.  Оба
  4.  Ни одно

Вопрос 3

Пусть и что из ниже перечисленного является верным?

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

Рассмотрим следующее AVL-дерево: [svg]

Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

Сколько остовных деревьев имеет данный граф (все ребра имеют одинаковый вес)?

[svg]

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

Вопрос 9

Сколько вершин имеет дерево с 57 ребрами?

  1.  58
  2.  56
  3.  57
  4.  2**6 — 4

Вопрос 10

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

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