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

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

Вариант 3985388748.


Ваше имя*:


Вопрос 1

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

  1.   —
  2.  
  3.  
  4.  

Вопрос 2

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

  1.   —
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.   —
  3.  
  4.  

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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.  

Вопрос 8

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

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

Вопрос 9

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

  • I. Если G является деревом, то между двумя любыми вершинами G существует единственный уникальный путь.
  • II. Если G = (V, E) является связным, и E = V - 1, тогда G является деревом.
  • III. Удаление ребра из цикла не может сделать граф несвязным.
  1.  Только III
  2.  I, II, III —
  3.  Только I, II
  4.  Только II

Вопрос 10

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

  1.  
  2.   —
  3.  
  4.