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

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

Вариант 2196105302.


Ваше имя*:


Вопрос 1

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

  1.  
    Check-me-animated.gif Решено: Ssyrovatkin 13:11, 8 ноября 2024 (UTC)
    Задача зарезервирована: Ssyrovatkin 07:27, 24 октября 2024 (UTC)
  2.  
  3.  
  4.  

Вопрос 2

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

- Пусть n - это число элементов в массиве

- В процессе сортировки массива происходит порядка уровней

- На каждом уровне происходит порядка действий

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

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

  4.  Сортировка кучей

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

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

Вопрос 5

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

  1.  57

  2.  56
  3.  58
  4.  2**6 - 4

Вопрос 6

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

I. если даже .

II. для любых .

III. для любых .


  1.  I, II, III

  2.  Только I, II
  3.  Только II, III
  4.  Только I

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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


Вопрос 9

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

I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

II. DFS на ориентированном графе с вершинами и, по крайней мере, ребрами гарантированно найдет хотя бы одно обратное ребро.

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

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


Вопрос 10

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

  1.  

  2.  
  3.  
  4.