Как сумма длин путей всех его узлов
Сортировки
Теория графов
Рекурсия и итерация
Теория чисел
Списки
Деревья
Хэш-таблицы
Стеки и очереди
1. Вам надо отсортировать массив из 6 элементов. Быстрей всего это выполнит?
BubbleSort (сортировка пузырьком)++
HeapSort (пирамидальная сортировка)
Сортировка обменом
Сортировка вставкой
QuickSort (быстрая сортировка Хоара)
2. Что верно об алгоритме поиска в глубину (DFS)?
В нём используется структура данных "очередь"
Он применяется для обхода вершин графа++
Наиболее естественная реализация этого алгоритма рекурсивна++
Наиболее удалённые вершины обходятся в самую последнюю очередь
Варианты 2 и 4
3. Гиперграф это?
обобщённый вид графа, в котором вершины могут быть инцидентными, не соединяясь при этом ребром
обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин++
обобщённый вид графа, который содержит одновременно ориентированные и неориентированные ребра
такого понятия не существует
Варианты 1 и 3
4. Отметьте истинные утверждения:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.++
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.++
|
|
|
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком++
5. Что вычисляет следующая рекурсивная функция для произвольного аргумента n?
F(n)
1 if n=0
2 then return 0
3 else return 1 + F(n & (n-1))
количество цифр в двоичном представлении n
количество нулей в двоичном представлении n
количество единиц в двоичном представлении n++
количество чисел в двоичном представлении n
ничего из вышеперечисленного
6. Выберите все правильные реализации алгоритма: y = -1, если x < 0; y = 0, если x = 0; y = 1, если x > 0.
if (x <= 0) if (x > 0) y = 1; else y = 0; else y = -1;
if (x < 0) y = -1; else if (x > 0) y = 1; else y = 0;++
if (x > 0) y = 1; else if (x < 0) y = -1; else y = 0;++
if (x >= 0) if (x > 0) y = 1; else y = 0; else y = -1;++
if (x <= 0) if (x > 0) y = 1; else y = 1; else y = -1;
7. Что называют динамическим программированием?
Если решение задачи разбивается на блоки: ввод данных, алгоритм решения, вывод
Если реализация алгоритма использует динамическое выделение памяти
Программирование с использованием динамических языков (JavaScript, Python, Ruby)
Метод решения задач, в котором оптимальное решение подзадач меньшей размерности дает решение основной задачи+++
Если решение задачи разбивается на блоки: ввод данных, вывод
|
|
|
8. Необходимо присвоить переменной R значение 10, если все три переменные: X, Y, Z равны друг другу. Укажите верную реализацию алгоритма:
IF (X=Y) OR (Y=Z) THEN R=10; END IF
IF (X=Y) XOR (Y=Z) THEN R=10; END IF
IF (X=Y) AND (Y=Z) THEN R=10; END IF++
IF (X=Y=Z) THEN R=10; END IF
IF (X=Y) THEN IF (Y=Z) THEN R=10; END IF END IF++
9. Какой из следующих случаев входных данных является наихудшим для алгоритма быстрой сортировки при выборе первого элемента в качестве опорного?
массив отсортированный в обратном порядке
массив отсортированный в нужном порядке++
массив в котором каждый второй элемент больше предыдущего и следующего (например, 1 3 2 5 4 ...)
массив отсортированный в прямом порядке
произвольный массив
10. Укажите минимальное число ребер, которые должны быть удалены из полного графа K6 таким образом, чтобы оставшийся граф был планарным.
2
3++
4
6
10
11. Какие переменные-указатели используются при реализации операций с динамическим стеком
+основной указатель на вершинный элемент
+дополнительный указатель на добавляемый в стек элемент
+дополнительный указатель на удаляемый из стека элемент
вспомогательный указатель на элемент, находящийся на дне стека
основной указатель на удаляемый элемент
|
|
|
12. Чем отличается NP-трудная задача от NP-полной?
Задача NP-полна, если к ней сводится любая задача из NP.
Задача NP-трудна, если она лежит в NP и NP-трудна.
Задача NP-трудна, если к ней сводится любая задача из NP.
Задача NP-полна, если она лежит в NP и NP-трудна.++
Задача NP-трудна, если существует подсказка, размер которой с точностью до полинома не превышает размер входа, и существует полиномиальный алгоритм решающий задачу по данной подсказке.
Задача NP-полна, если она лежит в NP и NP-трудна.
Задача NP-полна, если к ней сводится любая задача из NP.
Задача NP-трудна, если она лежит в NP.
13. Задачу о Ханойской башне (оптимальная последовательность перекладываний) обычно решают с помощью ... (Выберите все подходящие варианты.)
динамического программирования++
массива констант
Итерации++
формулы
рекурсии++
теории графов
14. Выберите алгоритмы устойчивой сортировки (при которой порядок одинаковых элементов не меняется)
Шелла
быстрая
Слиянием++
Пузырьковая++
пирамидальная
15. Какой алгоритм сортировки (до 10 элементов) на практике является самым быстрым (при этом используется генератор случайных чисел и производится не менее 100 тестов для более объективной оценки)?
|
|
|
Гномья сортировка
Сортировка Шелла
Сортировка вставками++
Шейкерная сортировка
Пузырьковая сортировка
16. Что означает f(n) = O(g(n))
Найдется константа C, что для любого n, начиная с некоторого n0, справедливо f(n) > C*g(n)
Для любого C, найдется N, что для любого n > N справедливо f(n) > C*g(n)
Для любого C, найдется N, что для любого n > N справедливо f(n) < C*g(n)
Найдется константа C, что для любого n, начиная с некоторого n0, справедливо f(n) < C*g(n)++
Для любого C, найдется N, что для любого n < N справедливо f(n) < C*g(n)
17. Для решения каких из этих задач может использоваться нахождение знака векторного произведения?
Построение выпуклой оболочки++
Проверка на колинеарность векторов++
Определения пересекаются ли два отрезка++
Вычисление угла между векторами
Вычисление угла между отрезками
18. Какие правила обхода дерева являются основными
+обход в прямом порядке
+обход в обратном порядке
обход в диагональном порядке
+симметричный обход
круговой обход
19. Какую задачу позволяет решить алгоритм Дейкстры?
Данный алгоритм осуществляет обход графа, при этом проходит по каждой из вершин исключительно один раз
Данный алгоритм формирует матрицу достижимости для каждой вершины
Данный алгоритм находит кратчайшее расстояние из заданной вершины во все остальные++
Данный алгоритм осуществляет обход графа, при этом проходит по каждой из вершин по несколько раз
Данный алгоритм формирует матрицу достижимости для одной вершины
20. Какое максимальное расстояние между двумя узлами в сбалансированном двоичном дереве из n элементов?
около log2n
около 2*log2n++
около 4*log2n
около n
около n/2
21. data - циклический массив из N элементов и last - индекс в этом массиве, какая формула индекса следующего послеlast элемента?
last % (1 + N)
(last % 1) + N
last + (1 % N)
(last + 1) % N++
(last 1%) + N
22. Если куча реализована с использованием одномерного массива data с n элементами (n > 0), где будет находится элемент с наибольшим значением?
data[2*n + 1]
data[n-1]
data[0]++
data[n]
data[n+1]
23. Какой тип списка предпочтительнее всего использовать если нужно получить элемент, находящийся на позиции n?
Двусвязный и односвязный списки одинаково подходят
Список, реализованный как массив++
Односвязный список
Двусвязный список
Варианты 1 и 2
24. Каких методов в представленном шаблоне класса не существует для бинарного дерева поиска?
Template<typedef X> class BinaryTreeSearch
{
node<X>* head;
public:
void insert_node(node<X>* currentNode); //1
void left_rotate(node<X>* rotateNode); //2
void right_rotate(node<X>* rotateNode); //3
void delete_node(node<X>* deleteNode); //4
void inorder_tree_walk(node<X>* walkNode); //5
node<X>* tree_search(X data); //6
};
все существуют
2, 3++
5, 6
5
6
3
25. Какая структура данных соответствует принципу: FIFO?
Очередь
Стек
B-дерево++
Односвязные циклические списки
Список
26. По какому принципу работает Стек?
LIFO++
FIFO
OIFO
Как в очереди
Как в списке
27. Одномерный массив A имеет индексы 1..75. Элементы массива - строки и каждая занимает три единицы(слота) памяти. Массив начинается в области памяти со смещением 1120. Укажите стартовый адрес элемента A[49]:
1264++
1164
1169
1267
1265
28. В чем главное преимущество хеш-таблиц над остальными структурами данных?
Быстрая вставка и удаление
Меньшее потребление памяти++
Быстрый поиск
Простота реализации
Быстрая сортировка
29. Какие виды Хэш-таблиц (из нижеперечисленных) существуют?
Хеш-таблица с открытой адресацией++
Хеш-таблица с цепочками++
Хеш-таблица с закрытой адресацией++
Хэш-таблица с прямой адресацией++
Хэш-таблица с опциональной адресацией
Хэш-таблица с замкнутой адресацией
Хэш-таблица с необычной адресацией
30. Какая структура данных позволяет производить вставку и удаление элемента с обоих концов?
стек
очередь++
дек
список
дерево
31. Возможно ли отсортировать произвольный массив за время O(N)?
Да. Массив любого размера и любого типа.
Нет. Это невозможно ни для какого массива.
Это возможно для массивов определённых размеров.
Это возможно для массивов некоторых типов.++
Это возможно для массивов определённых размеров и любого типа.
32. Термин, которым называют ситуацию, когда совершается попытка удаления данных из пустой структуры называется _____.
переполнение (Overflow)
опустошение++
null
сборка мусора (garbagecollection)
варианты 1 и 3
33. Какие из указанных структур данных могут хранить в себе одновременно элементы различных (произвольных) типов?
Объединение++
Массив
Куча
Дерево
Пересечение
34. Какой тип инициализации нужно сделать для хеш-таблицы с цепочками (chainedhashtable)?
Никакой
Каждый элемент массива ключа должен быть инициализирован
Голова каждой цепочки должна быть установлена в NULL++
Каждый элемент массива ключа не должен быть инициализирован
Варианты 2 и 3
35. В каких связных списках при обходе элементов первый узел может быть достигнут после перемещения ко второму узлу? (Выберите все возможные варианты)
Односвязный список
Кольцевой связный список++
Двусвязный список++
Многосвязный список
Варианты 1 и 4
36. В какой структуре данных вставка и удаление происходят на одном конце?
Дерево
Стек++
Связный список стеков
Связный список
Очередь
37. Какие из перечисленных операций более затратны (по времени) для реализации списка через массив относительно реализации через динамически создаваемый связный список?
Удаление++
Обход
Вставка++
Поиск
Замена
38. Дано AVL-дерево с балансом узла -1. Какие из следующих утверждений корректны?
Левое поддерево больше чем правое
Правое поддерево больше чем левое++
Дерево сбалансировано по высоте++
AVL-дерева с балансом -1 не существует
Варианты 1 и 4
39. Возможно ли отсортировать произвольный массив за время O(N)?
Да. Массив любого размера и любого типа.
Нет. Это невозможно ни для какого массива.
Это возможно для массивов определённых размеров.
Это возможно для массивов некоторых типов.++
Варианты 2 и 3
40. Линейный список, в котором доступен только последний элемент, называется...
стеком++
очередью
деком
массивом
деревом
41. Какая из указанных структур данных имеет сбалансированное состояние?
Двусвязный список
Стек
AVL-дерево++
Дек (двусторонняя очередь)
Односвязный список
42. В какой структуре данных вставка и удаление происходят на одном конце?
Связный список стеков
Стек++
Связный список
Дерево
Очередь
43. Какое минимальное количество узлов в заполненном бинарном дереве глубины 3?
4
8
11
15
7++
44. При объявлении одномерного массива постоянной длины определяется:
тип элементов, имя массива
тип элементов, нижнюю границу массива, верхнюю границу массива, имя массива, индекс массива
тип элементов, нижнюю границу массива, верхнюю границу массива, имя массива, шаг для индекса массива
тип элементов, количество элементов, имя массива++
варианты 1 и 2
45. Если символы 'D', 'C', 'B', 'A' помещены в очередь по порядку и затем будут по одному удалены, в каком порядке это произойдет?
DCBA++
ABDC
DCAB
ABCD
CABD
46. В каких связных списках при обходе элементов первый узел может быть достигнут после перемещения ко второму узлу? (Выберите все возможные варианты)
Односвязный список
Двусвязный список++
Кольцевой связный список++
Многосвязный список
Трехсвязный список
47. Какие ситуации возможны при удалении вершины из дерева поиска
+удаляемая вершина не имеет потомков
+удаляемая вершина имеет только одного потомка
+удаляемая вершина имеет двух потомков
удаляемая вершина имеет трех потомков
удаляемая вершина имеет более трех потомков
48. Какие операции из перечисленных являются стандартными для структуры данных стек?
put, extract
push, delete
insert, pop
push, pop++
extract, put
49. Какой тип инициализации нужно сделать для хеш-таблицы с цепочками (chainedhashtable)?
Никакой
Каждый элемент массива ключа должен быть инициализирован
Голова каждой цепочки должна быть установлена в NULL++
Первый элемент массива ключа должен быть инициализирован
Варианты 2 и 3
50. В чем отличие циклического списка от линейного?
Их нет
В том, что в списке нет пустых указателей++
Нет указателей на последний элемент.
Нет указателей на первый элемент.
Нет указателей на серединный элемент.
51. Какие виды Хэш-таблиц (из нижеперечисленных) существуют?
Хеш-таблица с открытой адресацией++
Хеш-таблица с цепочками++
Хеш-таблица с закрытой адресацией++
Хэш-таблица с прямой адресацией++
Хэш-таблица с опциональной адресацией
Хэш-таблица с замкнутой адресацией
Хэш-таблица с необычной адресацией
52. Дано AVL-дерево с балансом узла -1. Какие из следующих утверждений корректны?
Левое поддерево больше чем правое
AVL-дерева с балансом -1 не существует
Правое поддерево больше чем левое++
Дерево сбалансировано по высоте++
Дерево сбалансировано по ширине
53. Какой тип списка предпочтительнее всего использовать если нужно получить элемент, находящийся на позиции n?
Односвязный список
Двусвязный список
Список, реализованный как массив++
Список, реализованный как стек
Двусвязный и односвязный списки одинаково подходят
54. Какая формула точнее всего оценивает глубину кучи из n элементов?
lg(n)
sqrt(n)
log2(n)++
n
sqr(n)
55. Какие из перечисленных операций более затратны (по времени) для реализации списка через массив относительно реализации через динамически создаваемый связный список?
Поиск
Обход
Удаление++
Вставка++
Обмен
56. Для чего предназначен циклический алгоритм?
для того, чтобы избежать дублирования кода
для постоянного выполнения идентичных операций
для повторения идентичных операций определённое количество раз++
для постоянного выполнения операций разветвления
57. Выберите задачи, которые относятся к NP-полным
Задача о коммивояжере++
Определение наличия в графе Гамильтонова цикла++
Определение наличия в графе Эйлерова цикла
Задача о сумме подмножества++
Определение наличия в графе
58. Какой алгоритм сортировки является фактически худшим?
Bogosort++
Блинная сортировка
Глупая сортировка
Пузырьковая сортировка
Сортировка обменом
59. Сколько условных операторов типа if-else следует использовать для реализации алгоритма: y = 1, если x > 0 y = 0, если x = 0 y = -1, если x < 0
два++
три
четыре
пять
один
60. Что верно о NP-полных задачах?
Для них не существует алгоритмов решения
Для их решения в настоящий момент не разработаны алгоритмы с полиномиальным временем работы++
Их невозможно реализовать на классическом компьютере
Они относятся к задачам по теории чисел
61. Что вычисляет следующая рекурсивная функция для произвольного аргумента n?
F(n)
1 if n=0
2 then return 0
3 else return 1 + F(n & (n-1))
количество цифр в двоичном представлении n
количество нулей в двоичном представлении n
количество единиц в двоичном представлении n++
ничего из вышеперечисленного
все вышеперечисленное
62. Для чего применяется алгоритм Евклида?
Раскладывает число на простые множители
Проверяет число на простоту
Ищет наименьшее общее кратное (НОК) для двух чисел
Ищет наибольший общий делитель (НОД) для двух чисел++
Ищет наименьший общий делитель (НОД) для двух чисел
63. Укажите минимальное число ребер, которые должны быть удалены из полного графа K6 таким образом, чтобы оставшийся граф был планарным.
2
3++
4
6
1
64. Какова асимптотическая оценка для быстрого алгоритма возведения числа в целочисленную степень n, применяя только операцию умножения?
O(log2n)++
O(2n)
O(n2)
O(n)
O(1)
65. Какова сложность алгоритма "Быстрая сортировка" в худшем случае.
O(n*log(n))
O(2*n*log(n))++
O(n*log(n^2)) (n в квадрате)
O(n^2) (n в квадрате)
O(n+log(n))
66. Что верно о алгоритме поиска в ширину (BFS)?
Он применяется для обхода вершин графа++
Зачастую реализация этого алгоритма рекурсивная
В нём используется структура данных "стэк"
Наиболее удалённые вершины обходятся в самую последнюю очередь++
В нём используется структура данных "очередь"++
67. Сколько условных операторов if-else нужно использовать для вычисления y = f(x), если область определения функции (-oo< x< +oo) состоит из четырёх вложенных областей и в каждой из них f(x) различна?
один
два++
три
четыре
пять
68. В чём разница между расширенным алгоритмом Евклида и обычным?
Расширенный алгоритм работает быстрее, но более сложный в реализации
Между ними нет существенной разницы
Расширенный алгоритм Евклида позволяет извлечь дополнительную информацию++
Расширенный алгоритм работает быстрее, удобен в реализации
Ничего из вышеперечисленного
69. Выберите алгоритмы сортировки для которых асимптотическая оценка в наихудшем случае O(n2)
Быстрая++
слиянием
Шелла
Пузырьковая++
Выбором++
70. Термин, которым называют ситуацию, когда совершается попытка удаления данных из пустой структуры называется _____.
Опустошение++
Сборка мусора (garbagecollection)
переполнение (Overflow)
null
nullnull
71. По какому принципу работает Стек?
LIFO++
FIFO
OIFO
Как в очереди
Как в стеке
72. При объявлении одномерного массива постоянной длины определяется:
тип элементов, имя массива
тип элементов, нижнюю границу массива, верхнюю границу массива, имя массива, индекс массива
тип элементов, нижнюю границу массива, верхнюю границу массива, имя массива, шаг для индекса массива
тип элементов, количество элементов, имя массива++
количество элементов,тип элементов
73. Какая из следующих строк кода удалит два последовательных элемента связного линейного списка (с более чем двумя элементами) после элемента X? (Здесь 'LINK[X]' означает поле адреса элемента X)
LINK[X]:=LINK[LINK[LINK[X]]]++
LINK[LINK[X]]:=X
X:=LINK[LINK[X]]
LINK[X]:=LINK[LINK[X]]
LINK[LINK[X]]:= LINK[X]
74. Если куча реализована с использованием одномерного массива data с n элементами (n > 0), где будет находится элемент с наибольшим значением?
data[n-1]
data[0]++
data[n]
data[2*n + 1]
data[n+1]
75. При каком методе разрешения коллизий хеш-таблица может оказаться заполненной, делая невозможной вставку новых элементов?
открытая адресация++
метод цепочек
метод поиска
закрытая адресация
всевышеперечисленное
76. Какое минимальное количество узлов в заполненном бинарном дереве глубины 3?
8
11
15
4
7++
77. Какие из перечисленных операций более затратны (по времени) для реализации списка через массив относительно реализации через динамически создаваемый связный список?
Поиск
Обход
Вставка++
Удаление++
Обмен
78. Какое максимальное расстояние между двумя узлами в сбалансированном двоичном дереве из n элементов?
около n/2
около log2n
около 2*log2n++
около 4*log2n
около n
79. Какой фактор может замедлить операции хеш-таблицы?
Вычисление сложной хеш-функции при каждой операции++
Хеш-коллизии++
Организация таблицы как массива цепочек
Вычисление простой хеш-функции при каждой операции
Ничего из вышеперечисленного
80. Линейный список, в котором доступен только последний элемент, называется...
стеком++
очередью
деком
массивом
деревом
81. Какое положение будет верно относительно B-дерева (B-Tree)?
Все нелистовые узлы имеют одинаковое число потомков
Все листья находятся на нижнем уровне++
Все записи узла больше чем или равняются записям узлов-потомков
Все узлы имеют одинаковое количество записей
Все листья находятся на верхнем уровне
82. Какой тип списка предпочтительнее всего использовать если нужно получить элемент, находящийся на позиции n?
Двусвязный список
Односвязный список
Двусвязный и односвязный списки одинаково подходят
Многосвязный список
Список, реализованный как массив ++
83. Какие утверждения справедливы по отношению к простейшим методам сортировки массивов
эти методы имеют квадратичную скорость роста трудоемкости
+эти методы следует использовать при небольших объемах входных данных
+эти методы имеют простую программную реализацию
эти методы обеспечивают высокую скорость сортировки
эти методы обеспечивают низкую скорость сортировки
84. Структура данных представляет собой
набор правил и ограничений, определяющих связи между отдельными элементами и группами данных++
набор правил и ограничений, определяющих связи между отдельными элементами данных
набор правил и ограничений, определяющих связи между отдельными группами данных
некоторую иерархию данных
некоторое дерево данных
85. Линейный список, в котором доступен только последний элемент, называется
Стеком
очередью
деком
массивом
кольцом
86. Структура данных работа с элементами которой организована по принципу FIFO (первый пришел - первый ушел) это –
Стек
Дек
Очередь
Список
Массив
87. Линейный последовательный список, в котором включение исключение элементов возможно с обоих концов, называется
стеком
очередью
Деком
кольцевой очередью
массив
88. Какую дисциплину обслуживания принято называть FIFO ?
стек
Очередь
дек
массив
таблица
89. Чем отличается кольцевой список от линейного ?
в кольцевом списке последний элемент является одновременно и первым;
в кольцевом списке указатель последнего элемента пустой;
в кольцевых списках последнего элемента нет ;
в кольцевом списке указатель последнего элемента не пустой.
в кольцевом списке указатель первого элемента пустой;
90. Дерево называется полным бинарным, если степень исходов вершин равна:
2 ++
1
М или 0
M
0++
91. Какой из критериев эффективности сортировки определяется формулой M=0,01*n*n+10*n ?
число сравнений (верный)
время, затраченное на написание программы
количество перемещений
время, затраченное на сортировку
время, затраченное на сравнения
92. Как называется сортировка, происходящая в оперативной памяти?
сортировка таблицы адресов;
полная сортировка;
сортировка прямым включением;
внутренняя сортировка (верный);
внешняя сортировка.
93. Где эффективен линейный поиск ?
в списке; +
в массиве; +
в стеке.
в очереди
в дереве
94. Где наиболее эффективен метод транспозиций ?
встеках
в массивах++
в списках++
в очередях
в таблицах
95. Как определяется длина пути дерева
как сумма длин путей всех его узлов
как количество ребер от узла до вершины
как количество ребер от листа до вершины
как максимальное количество ребер
как максимальное количество листьев
Дата добавления: 2018-05-12; просмотров: 2866; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!