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

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

Вариант 924848931.


Ваше имя*:


Вопрос 1

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

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.  

Вопрос 2

Для какой из изображенных ниже куч на минимум будут получены элементы массива в порядке возрастания, если для кучи применяется обход preorder traversal?

  1.  [svg]

  2.  [svg]
  3.  [svg]
  4.  [svg]

Вопрос 3

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

  • I.
  • II.

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

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

Вопрос 4

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

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

Вопрос 5

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

  • 1)
  • 2)
  • 3),  — константа
  • 4)
  1.  i, ii, iii —
  2.  ii, iii
  3.  i, ii
  4.  i, ii, iv

Вопрос 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

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

  1.   —
  2.  
  3.  
  4.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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