Алгоритмы и анализ сложности ЧелГУ (1 сем) ответы (Итоговый тест + промежуточные)
Институт информационных технологий ЧелГу
Алгоритмы и анализ сложности ЧелГУ (1 сем) ответы (Итоговый тест + промежуточные)
Итоговый тест 90% + промежуточные тесты около 90-100% каждый пройден.
Покупая данные ответы нет полной гарантии что все вопросы совпадут с вашими! Но явно часть из них будет такая же как в ответах у меня.
Часть вопросов из файлов перечислена ниже:
Какая структура данных соответствует принципу: LIFO?
a. В-дерево
b. Стек
c. Очередь
d. Односвязные циклические списки
Если символы ‘1’, ‘2’, ‘3’, ‘4’ помещены в очередь по порядку и затем будут по одному удалены, в каком порядке это произойдет?
a. 1234
b. 1243
c. 4231
d. 4321
Какие операции необходимо произвести над стеком?
a. push, pop
b. insert, pop
c. push, delete
d. add, delete
e. нет правильных вариантов
f. put, extract
Дан стек, в котором хранятся следующие значения:
Что останется в стеке после выполнения ряда операций?
if IsEmpty(): Push(5);
Push(2);
Top();
Pop();
Известны элементы некоторой структуры данных:
После выполнения некоторых операций с этой структурой получили:
Что это за структура данных?
a. Такой структуры не существует
b. Дерево
c. LIFO
d. Очередь
e. Стек
Какова сложность алгоритма "Быстрая сортировка" в худшем случае.
a. O(n^2)
b. O(n*log(n^2))
c. O(2*n*log(n))
d. O(n*log(n))
Задан массив X[1..N]. Определите временную сложность алгоритма:
for i:=1 to N-1 do
for j:=N-1 doiwnto i do
if A[j]>A[j+1] then
Swap(A[j], A[j+1]);
a. O(2^N)
b. O(log N)
c. O(N^3)
d. O(N^2)
e. O(N)
Пусть T(n) = O (g(n)), где O – это…
a. Нижняя оценка функции
b. Порядок роста функции
c. Верхняя оценка функции
Укажите два наилучших алгоритма по критерию трудоемкости
a. алгоритм с линейной скоростью роста
b. алгоритм с логарифмической скоростью роста
c. алгоритм с квадратичной скоростью роста
d. алгоритм с линейно-логарифмической скоростью роста
Имеется двоичное дерево (не являющееся деревом поиска), содержащее произвольные символы. Восходящий просмотр дерева даёт следующий результат: B, +, #, 3, f, k. Какой узел является корнем дерева?
Какое положение будет верно относительно B-дерева (B-Tree)?
a. Все нелистовые узлы имеют одинаковое число потомков
b. Все узлы имеют одинаковое количество записей
c. Все записи узла больше чем или равняются записям узлов-потомков
d. Все листья находятся на нижнем уровне
Элемент дерева j, на который нет ссылок называется
a. Корнем
b. Промежуточным элементом
c. Терминальным (лист)
Существуют следующие методы сортировки. Найдите ошибку.
Выберите один ответ:
a. динамические
b. улучшенные
c. строгие
В процессе сортировки выполняется поиск наименьшего элемента. По какому алгоритму выполняется эта сортировка?
a. Вставками
b. Быстрая
c. Пузырьковая
d. Шелла
e. Выбором
Что из перечисленных ниже понятий является одним из типов сортировки?
a. сортировка данных
b. внутренняя сортировка
c. сортировка по возрастанию
d. сортировка по убыванию
Какое из следующих высказываний наилучшим образом характеризует пузырьковую сортировку?
a. Ищет наименьший или наибольший элемент
b. Выполняет наименьшее число операций
c. Не подходит для 1-мерных массивов
d. Считается самой быстрой
e. Считается самой простой
Какие виды Хеш-таблиц (из нижеперечисленных) существуют?
a.Хеш-таблица с закрытой адресацией
b. С замкнутой адресацией
c. Хеш-таблица с цепочками
d. С невозможной адресацией
e. Хеш-таблица с открытой адресацией
f. С опциональной адресацией
g. С прямой адресацией
Что такое универсальное хеширование?
a. Вид хеширования, при котором хеш-функция отображает каждый ключ из набора во множество целых чисел без коллизий.
b. Хеширование, при котором хеш-функция может выполнять деление входных данных на полином по модулю два.
c. Вид хеширования, при котором хеш-функция выбирается случайно для каждой хэш-таблицы и не зависит от набора ключей, с которыми работает.
d. Хеширование, при котором хеш-функция может вычислять «хеш» как остаток от деления входных данных
Можно ли вывести элементы хеш-таблицы в определенном порядке?
a. Да, потому что в хеш-таблицу данные заносятся как в массив, следовательно, мы можем отсортировать элементы в заданном порядке
b. Нет, так как хеш-таблица является неупорядоченной коллекцией
Что из перечисленного может быть ключом хеш-таблицы?
Выберите один или несколько ответов:
a. Указатель
b. Число
c. Ничего из перечисленного. Он задается автоматически
d. Строка
Дана хеш-функция h(x, i) = (x + 3i) mod 10. Напишите через запятую индексы (без пробелов), которые будет выдавать эта функция при x=5, подставляя i от 0 до 9
Неориентированное дерево это: (выбрать верные утверждения)
a. связный граф, содержащий n вершин и n-1 ребер
b. граф без циклов, в котором полустепень захода каждой вершины, за исключением одной (начальной вершины x1), равна единице.
c. граф, в котором каждая пара вершин соединена несколькими простыми цепями
d. связный граф, не имеющий циклов
Определите какой шаг пропущен для поиска в ширину. 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная (и заносится в очередь). 2. ??? 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные. Варианты ответов:
a. Выбирается следующая вершина и помечается как не посещенная. Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.
b. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.
c. Для последней помеченной как посещенная вершины выбирается смежная вершина, являющаяся первой помеченной как не посещенная, и ей присваивается значение посещенная. Если таких вершин нет, то берется предыдущая помеченная вершина
Какими алгоритмами из перечисленных решается задача нахождения кратчайшего пути?
a. Крускала
b. Дейкстры
c. Прима
d. Буровки
e. Беллмана–Форда
f. Форда-Фалкерсона
Какая из матриц инцидентности является правильной для графа, показанного на рисунке. рисунок)
Какой граф изображён на рисунке?
В алгоритме быстрой сортировки количество сравнений во время каждого прохода равно n в…
Что может привести к переполнению стека при использовании быстрой сортировки?
У вас имеется сортирующее дерево, которое хранится в массиве. Какое число может быть в этой последовательности вместо звездочек: 25, 14, 24, ***, 6, 21,22, 3,4,5?
Алгоритм какой сортировки может быть разделен на две фазы?
В каком алгоритме происходит увеличение упорядоченной серии чисел ровно в 2 раза?
Алгоритмы внутренней сортировки работают с данными, которые
Последовательность элементов, упорядоченную по ключу называют…
Алгоритмы внешней сортировки отличает … доступ к элементам последовательности:
Пусть имеется ключ k1 = 26 и хеш-функция для хеш-таблицы вычисляется по формуле h(x)=x mod 11. При каком минимальном значении ключа k2 возникнет коллизия на ключах k1 и k2?
В таблице с прямой адресацией её размер совпадает с…
Время выполнения операция в таблице прямой адресации:
Универсальным хэшированием называется такой подход, когда...
Средняя длина цепочки в хеш-таблице размера m, в которую добавлено n элементов будет составлять:
Все операции в хеш-таблице с цепочками в среднем будут выполняться за время:
Пусть имеется хеш-таблица размерностью на 1000 элементов. В нее добавлено 5466 элементов. Какая возможна минимальная длина цепочки элементов, ассоциированной с некоторой ячейкой хеш-таблицы?
Пусть имеется хеш-таблица, элементы в которую добавляются согласно методу линейного исследования (m=15). В какую ячейку хеш-таблицы (при условии, что она свободная) добавится элемент с ключом k=63 при третьей попытке записи в таблицу?
Алгоритм обхода с помощью поиска в ширину использует динамическую структуру данных:
Чтобы свести задачу поиска кратчайшего расстояния до задачи поиска минимального количества ребер между вершинами, необходимо полагать веса ребер:
Алгоритм Форда-Беллмана работает со взвешенным графом, у которого все веса ребер:
Пусть имеется исходный граф с n вершинами и m ребрами, тогда в остовном графе вершин будет:
Пусть имеется исходный граф с n вершинами и m ребрами, тогда в остовном графе ребер будет:
Для потока, протекающего по любому ребру в графе верна формула:
Какие из перечисленных структур данных являются динамическими?
a. Массивы
b. Деревья
c. Стек
d. Множества
Выберите правильные утверждения
a. размер динамической структуры данных ограничивается только доступным объемом памяти компьютера
b. размер динамической структуры данных фиксирован и задается во время её инициализации
c. при изменении логической последовательности элементов динамической структуры (удалении, добавлении элемента), создается новая структура данных, а старая удаляется, высвобождая память компьютера
Первым шагом разработки алгоритма является:
a. Выбор математической модели
b. Выбор абстрактного типа данных
c. Выбор языка программирования
d. Выбор структуры данных
Что характерно для статического типа данных?
a. Характер взаимосвязи между элементами структуры не изменен
b. Количество элементов структуры может не фиксироваться
c. Количество элементов структуры заранее определено
d. В процессе выполнения программы может меняться характер взаимосвязи между элементами структуры
e. Не требуется дополнительной памяти
При объявлении одномерного массива постоянной длины определяется
a. тип элементов, имя массива
b. тип элементов, количество элементов, имя массива
c. тип элементов, нижнюю границу массива, верхнюю границу массива, имя массива, шаг для индекса массива
d. тип элементов, нижнюю границу массива, верхнюю границу массива, имя массива, индекс массива
Какие операции применимы к списку?
a. Поиск конкретного элемента
b. Добавление\Удаление элементов
c. Проверка на пустоту
Из каких позиций списка можно удалять звенья (выделенного ведущего звена нет)?
a. Из любой позиции
b. Из любой позиции, кроме последнего звена
c. Только из ведущего звена
d. Только из конца списка
e. Из любой позиции, кроме ведущего звена
Показанная на рисунке структура данных является
a. 1-связным линейным списком
b. 1-связным кольцевым списком
c. 2-связным линейным списком
d. Стеком
e. 2-связным кольцевым списком
Выберите правильные утверждения
a. в списке указатели могут ссылаться как на предыдущее, так и на последующее звенья списка
b. длина списка постоянна и задается при его инициализации
c. списки относятся к динамической структуре данных
d. вся информация о списке хранится в динамической памяти
Какие виды списков существуют?
a. пирамидальный
b. ненаправленный
c. линейный
d. цилиндрический
e. кольцевой
Какие операции из перечисленных являются стандартными для стека?
a. put, extract
b. push, delete
c. insert, pop
d. add, delete
e. push, pop
Из каких позиций стека можно извлекать элементы?
a. Только из вершины
b. Из любой позиции, кроме вершины стека
c. Только со дна стека
d. Из любой позиции, кроме дна стека
e. Из любой позиции
В чем особенность структуры данных «стек»?
a. Открыт с одной стороны на вставку и удаление
b. Доступен любой элемент
c. Открыт с обеих сторон на вставку и удаление
По какому принципу работает стек?
a. OIFO
b. FIFO
c. Как в очереди
d. LIFO
С какими проблемами можно столкнуться при реализации очереди с помощью списка?
a. «хвост» съедает «голову»
b. переполнение очереди
c. выделение дополнительной памяти для каждого элемента
d. необходима связь каждого элемента очереди с последующим и предыдущим элементами
По какому принципу работает очередь?
a. LIFO
b. FIFO
c. OIFO
d. Как в стеке
В чем особенность структуры данных «очереди»?
a. Доступен любой элемент
b. Открыта с обеих сторон
c. Открыта с одной стороны на вставку и удаление
Какие операции из перечисленных являются стандартными для очереди?
a. add, delete
b. push, delete
c. insert, pop
d. enqueue, dequeue
e. push, pop
Сколько и какие указатели необходимы при инициализации очереди?
a. 0 – ничего не нужно
b. 3 – head, top, tail
c. 1 – top
d. 2 – head, tail
Вычислительная сложность – это
a. это количественная характеристика алгоритма, характеризуемая количеством шагов и времени выполнения каждого шага
b. максимальное количество шагов, которое производит алгоритм на всех наборах входных данных, соответствующих мере N
c. количественная характеристика алгоритма, которая определяется максимальным количеством памяти, необходимым для реализации алгоритма на вычислительной системе
Алгоритм перебора элементов массива относится к классу сложности…
a. Логарифмический
b. Полиномиальный
c. Линейный логарифм
d. Линейный
Время выполнения операторов присваивания, чтения, сравнения считают равным…
Алгоритмы какого класса имеют бо`льшую скорость роста?
На рисунке представлено k-позиционное дерево, где k=…
Листом дерева называется….
a. Вершина, имеющая ровно 1 потомка
b. Верхняя вершина
c. Вершина, не имеющая потомков
d. Произвольная вершина
Если в коде Прюффера N чисел, то количество вершин в исходном дереве…
a. N
b. N+2
c. N+1
d. N-2
e. N-1
Недостатками реализации корневого дерева с помощью списков являются…
a. Нехватка памяти
b. Быстрая скорость прохода по дереву
c. Дополнительная память для указателей
d. Простои памяти
e. Гибкость структуры
Если корневое k-позиционное дерево хранить в массиве, то для вершины с индексом s потомками будут вершины с индексами
a. k+s, k+s+1,…,k+s+s
b. ks+1, ks+2,…, ks+k
c. k, k+1, …, s
d. k^s, k^s+1,…, k^s+k
В памяти компьютера двоичное дерево удобно представлять в виде:
a. Связанных линейных списков
b. Связанных нелинейных списков
c. Массивов
Имеется идеально сбалансированное двоичное дерево поиска, содержащее целые числа. Просмотр дерева даёт следующий результат: 2, 4, 6, 8, 10, 12, 14. Какой способ просмотра дерева использовался?
Имеется двоичное дерево (не являющееся деревом поиска), содержащее целые числа. Восходящий просмотр дерева даёт следующий результат: 2, 4, 6, 8, 10, 12, 14. Какой узел является корнем дерева?
Какие из операций над двоичными деревьями поиска наиболее затратны по памяти компьютера? (оценивается сложность алгоритма)
Дано красно-черное дерево: Какой примет вид дерево после добавления 50?
Операция «правого/левого вращения» служит для …
a. Нахождения самого правого/левого узла
b. Перекрашивания вершин
c. Выравнивания высот поддеревьев
d. Удаления вершины
В красно-черном дерево должно выполняться
a. «Красная» и «черная» высота могут различаться не более чем на 1
b. Равенство «черных» высот
c. Равенство «красных» высоты
d. «Красная» и «черная» могут различаться не более чем в 2 раза
В красно-черном дереве фиктивные потомки могут быть следующих цветов…
Какие операции в КЧ-дереве могут привести к его перестройке?
Алгоритм, где на каждом проходе производится увеличение в два раза частично упорядоченных последовательностей, называется…
Шейкерная сортировка является модификацией…
Если последовательность в сортировке вставкой – связный список, то вставка приводит…
