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

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

Вариант 1512835938.


Ваше имя*:


Вопрос 1

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

  1.   и соответственно
  2.   и соответственно
  3.   и соответственно
  4.   и соответственно

Вопрос 2

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

  1.  1101, 111, 1101
  2.  1100, 1101, 111
  3.  1101, 1100, 111

  4.  1100, 10, 0

Вопрос 3

Пусть неориентированный граф, какие утверждения ниже являются верными?

I. Если является деревом, то между двумя любыми вершинами существует единственный уникальный путь.

II. Если является связным, и , тогда является деревом.

III. Удаление ребра из цикла не может сделать граф несвязным.

  1.  I, II, III

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

Вопрос 4

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

I. Подсчет медианы из элементов занимает времени для любого алгоритма, основанного на сравнении элементов.

II. Пусть является минимальным остовным деревом для графа . Тогда для любой пары вершин и кратчайший путь между ними в является кратчайшим путем между ними в .

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

  1.  I–False, II–False

  2.  I–False, II–TRUE
  3.  I–TRUE, II–TRUE
  4.  I–TRUE, II–False

Вопрос 5

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

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

Вопрос 6

Какие из представленных ниже утверждений являются верными?

1)

2)

3), - константа

4)

  1.  i,ii,iv
  2.  ii,iii
  3.  i,ii

  4.  i,ii,iii

Вопрос 7

Предположим, что - это связный неориентированный граф, ребра которого имеют положительные веса. Пусть - минимальное остовное дерево этого графа. Мы модифицируем граф, добавляя "6" к весу каждого ребра, какое из следующих утверждений верно?

  1.  Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Прима, изменится.
  2.  Ничего из вышеперечисленного.

  3.  Модификация добавляет к общему весу всех остовных деревьев.
  4.  Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Крускала, изменится.

Вопрос 8

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

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

  1.  3

  2.  0
  3.  1
  4.  2

Вопрос 9

Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:

I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

II. DFS на ориентированном графе с вершинами и, по крайней мере, ребрами гарантированно найдет хотя бы одно обратное ребро.

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

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

  4.  Только I

Вопрос 10

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

  1.  
  2.  
  3.  
  4.