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

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

Вариант 3372295761.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

Каково число подстрок любой длины, за исключением пустой строки, может быть получено из заданной строки длиной n?

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

Вопрос 7

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

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

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

Вопрос 8

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

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

Вопрос 9

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

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

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

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

Вопрос 10

Рассмотрим следующий код:

y = y + z
for i in range(1, n + 1):
    k = k + 2;
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = x + 1;

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

  1.  
  2.  
  3.  
  4.