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

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

Вариант 349342820.


Ваше имя*:


Вопрос 1

Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

Вопрос 3

Какова временная сложность выполнения алгоритма Беллмана-Форда на K-регулярном графе ()?

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

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

Вопрос 5

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

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

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

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

Вопрос 6

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

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

Вопрос 7

Алгоритм Беллмана-Форда решает задачу кратчайшего пути из вершины в случае, когда веса ребер могут быть отрицательными, какова временная сложность выполнения алгоритма Беллмана-Форда?

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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

Вопрос 9

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

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

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

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

Вопрос 10

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

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

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