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

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

Вариант 2565529683.


Прошло 00:00:02.
Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

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

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

Вопрос 4

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?

  1.  
  2.  
  3.  
  4.  

Вопрос 5

Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

Рассмотрим следующие выражения:

  • I.
  • II.

Какие утверждения верные, а какие нет?

  1.  I-TRUE, II-False
  2.  I-False, II-False
  3.  I-TRUE, II-TRUE
  4.  I-False, II-TRUE

Вопрос 9

Дан неориентированный граф G = (V, E) и положительное целое число K, имеет ли G K вершин, которые образуют полный подграф, и если да, то каково минимальное значение K?

  1.  4
  2.  3
  3.  Ничего и перечисленного
  4.  2

Вопрос 10

Рассмотрим следующие выражения:

  • I. Диграф — это граф, имеющий ровно 2 вершины.
  • II. Остовное дерево в графе всегда должно содержать как минимум ребер.
  • III. Алгоритм сортировки ребер для решения задачи коммивояжера всегда дает оптимальный результат.

Какие утверждения верные, а какие нет?

  1.  I, III
  2.  I, II
  3.  II, III
  4.  Только II