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

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

Вариант 3475270895.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

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

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

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

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.  

Вопрос 5

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

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

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

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

Вопрос 6

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

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

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

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

Вопрос 7

Сколько раз происходит обращение ко всем вершинам в графе G(V, E) в процессе работы алгоритма поиска в глубину?

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

Рассмотрим следующие утверждения (h(k) — хэш-функция):

  • I. если даже .
  • II. для любых .
  • III. для любых .
  1.  I, II, III
  2.  Только I
  3.  Только II, III
  4.  Только I, II

Вопрос 10

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

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