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

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

Вариант 1915734291.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  • I. Подсчет медианы из n элементов занимает времени для любого алгоритма, основанного на сравнении элементов.
  • II. Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.

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

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

Вопрос 5

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

  • I.
  • II.

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

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

Вопрос 6

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

for (i = n; i > 0; i/= 2){
    for (int j = 1; j < n; j * = 2){
        for (int k = 0; k < n; k + = 2){
        sum + = (i + j * k);
        }
    }
}
  1.  
  2.  
  3.  
  4.  

Вопрос 7

Какое из представленных ниже регулярных выражений задает строки вида , где m, p, n больше либо равно 2.

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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

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

Вопрос 9

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

[svg]

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

Вопрос 10

Пусть имеется два отсортированных списка размера K и L соответственно. Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера K + L, состоящий из элементов этих списков?

  1.  
  2.  
  3.  
  4.