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

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

Вариант 2094530287.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

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

Вопрос 3

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

[svg]

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

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

Вопрос 8

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

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

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

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

Вопрос 9

Алгоритм Беллмана-Форда решает задачу кратчайшего пути из вершины в случае, когда веса ребер могут быть отрицательными, какова временная сложность выполнения алгоритма Беллмана-Форда?

  1.  
  2.  
  3.  
  4.  

Вопрос 10

Какова временная сложность выполнения алгоритма Беллмана-Форда на K-регулярном графе ()?

  1.  
  2.  
  3.  
  4.