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

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

Вариант 1705741995.


Прошло 00:00:02.
Ваше имя*:


Вопрос 1

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

  • I.
  • II.

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

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

Вопрос 5

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

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.  

Вопрос 6

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

  • Пусть n — это число элементов в массиве
  • В процессе сортировки массива происходит порядка уровней
  • На каждом уровне происходит порядка действий

Для какого алгоритма сортировки все утверждения являются верными?

  1.  Сортировка кучей
  2.  Сортировка слиянием
  3.  Сортировка выбором
  4.  Сортировка пузырьком

Вопрос 7

Существует несколько способов определить порядок умножения матриц A, B, C, D: (A(BC)D), A(B(CD)), (AB)(CD), ((AB)C)D), A((BC)D)

Эффективность умножения зависит от числа скалярных произведений, для (A(BC))D получится:

Для (A(B(CD))):

Какие размерности у матриц A, B, C, D соответственно?

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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