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

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

Вариант 1391183683.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

[svg]

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

Вопрос 3

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

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.  

Вопрос 4

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

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

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  
  3.  
  4.   

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

  • I.
  • II.

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

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