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

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

Вариант 3585402309.


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


Вопрос 1

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

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

Вопрос 2

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

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

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

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

Вопрос 6

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

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

Вопрос 7

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

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

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

Вопрос 8

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для вычисления медианы данного массива?

  1.  
  2.  
  3.  
  4.  

Вопрос 9

Существует несколько способов определить порядок умножения матриц 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.  , , ,

Вопрос 10

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

  1.  
  2.  
  3.  
  4.