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

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

Вариант 3528065127.


Ваше имя*:


Вопрос 1

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

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

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

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

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

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

  4.  Сортировка выбором

Вопрос 2

Существует несколько способов определить порядок умножения матриц : , , , ,

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

Для :

Какие размерности у матриц соответственно?

  1.  , , ,
  2.  , , ,

  3.  , , ,
  4.  , , ,

Вопрос 3

Дан неориентированный граф и положительное целое число , имеет ли m>G</m> m>K</m> вершин, которые образуют полный подграф, и если да, то каково минимальное значение ?

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

  3.  2
  4.  4

Вопрос 4

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

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

  1.  3

  2.  0
  3.  2
  4.  1

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

  4.  Сохранять элемент в отсортированном массиве и применять бинарный поиск.

Вопрос 7

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

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

Вопрос 8

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

  1.  Ничего из вышеперечисленного.

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

Вопрос 9

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

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

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

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

  1.  Ни одно

  2.  Только II
  3.  Оба
  4.  Только I

Вопрос 10

Каково минимальное и максимальное количество узлов, которые может содержать в себе куча на минимум/максимум высотой ?

  1.   и соответственно
  2.   и соответственно
  3.   и соответственно
  4.   и соответственно