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

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

Вариант 3916479217.


Ваше имя*:


Вопрос 1

Пусть структура данных поддерживает операцию `foo`, таким образом, что последовательность из n операций `foo` занимает времени в худшем случае. Каково амортизационное время операции `foo`?

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

[svg]

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

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

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

Вопрос 5

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

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

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

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

Вопрос 6

Чтобы выполнить поиск элемента в dynamic set, какой из следующих методов является асимптотически наиболее эффективным по времени в наихудшем случае для операции поиска?

  1.  Сохранять элемент в хэш-таблице и использовать хэширование.
  2.  Все вышеперечисленное.
  3.  Сохранять элемент в несортированном массиве и применять линейный поиск.
  4.  Сохранять элемент в отсортированном массиве и применять бинарный поиск.

Вопрос 7

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

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

Вопрос 8

Какие из следующих алгоритмов используют подход Разделяй и Властвуй?

  1.  Сортировка слиянием
  2.  Быстрая сортировка
  3.  Бинарный поиск и умножение Штрассена
  4.  Все выше перечисленные

Вопрос 9

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

  • I. Подсчет медианы из n элементов занимает времени для любого алгоритма, основанного на сравнении элементов.
  • II. Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.

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

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

Вопрос 10

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

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