Тест по дисциплине «Структуры и алгоритмы обработки данных»

>Вопрос 1

Какие операции характерны при использовании очереди

добавление элемента в конец очереди

удаление элемента из начала очереди

добавление элемента в любое место очереди

удаление любого элемента из очереди

Вопрос 2

Что характерно для статической реализации структур данных

использование массивов как основы реализации

распределение памяти под элементы структуры во время компиляции программы

использование адресных переменных (указателей) для связывания элементов структуры

возможность выделения памяти для элементов структуры во время выполнения программы

Вопрос 3

Какие объявления необходимы для статической реализации кольцевой очереди

массив для хранения элементов очереди

переменная-индекс для указания ячейки массива с первым элементом очереди

переменная-индекс для указания ячейки массива с последним элементом очереди

переменная-указатель размещения в памяти первого элемента очереди

Вопрос 4

В чем состоит отличие элемента двунаправленного списка от элемента обычного списка

наличие двух связующих полей для адресации левого и правого соседа

каждый элемент двунаправленного списка имеет указатели на начало и конец списка

каждый элемент двунаправленного списка кроме основного указателя на следующий элемент имеет указатель на отдельно хранящуюся информационную часть

никаких отличий между элементами нет

Вопрос 5

Какие утверждения относительно динамической реализации списков являются правильными

каждому элементу списка во время выполнения программы выделяется своя область памяти

каждый элемент списка имеет специальное поле с адресом следующего элемента

логический порядок следования элементов в списке может не совпадать с физическим размещением элементов в памяти

максимальное число элементов в списке должно быть известно заранее

Вопрос 6

Какие правила обхода дерева являются основными

обход в прямом порядке

обход в обратном порядке

симметричный обход

круговой обход

Вопрос 7

Какие высказывания относятся к рекурсивному определению дерева

дерево может быть пустым

дерево — это вершина и связанное с ней конечное число поддеревьев

дерево всегда содержит хотя бы одну корневую вершину

дерево — это вершина и связанное с ней единственное поддерево

Вопрос 8

В чем суть правила симметричного обхода дерева

сначала обрабатывается корень поддерева, потом — левое поддерево, потом — правое поддерево

сначала обрабатывается левое поддерево, потом — корень поддерева, потом — правое поддерево

сначала обрабатывается правое поддерево, потом — левое поддерево, потом — корень поддерева

сначала обрабатывается корень поддерева, потом — правое поддерево, потом — левое поддерево

Вопрос 9

Как выполняется удаление вершины из дерева поиска, если эта вершина имеет двух потомков

удаление такой вершины невозможно

определяется вершина-заменитель, которая подставляется на место удаляемой

соответствующий указатель в родительской вершине устанавливается в адрес левого потомка удаляемой вершины

соответствующий указатель в родительской вершине устанавливается в адрес правого потомка удаляемой вершины

Вопрос 10

Какое дерево называется идеально сбалансированным

если для каждой вершины число вершин в левом и правом поддеревьях отличается не более чем на 1

если для корневой вершины число вершин в левом и правом поддеревьях отличается не более чем на 1

если для каждой вершины число вершин в левом и правом поддеревьях совпадают

если для каждой вершины высота левого и правого поддерева одинаковы

Вопрос 11

Что происходит при удалении вершины с терминальной страницы Б-дерева

удаление элемента из страничного массива

уменьшение счетчика числа вершин

проверка допустимого числа вершин

поиск вершины-заменителя

Вопрос 12

Какие утверждения справедливы относительно процедуры поиска заданного ключа в Б-дереве

поиск начинается с корневой страницы

поиск заканчивается как неудачный при попытке перехода к несуществующей дочерней странице

поиск реализуется перебором всех страниц дерева

поиск всегда заканчивается на терминальной странице

Вопрос 13

Какие утверждения справедливы относительно страничного массива Б-дерева порядка m

массив имеет размерность 2m

элементами массива являются записи-структуры

массив может изменять свою размерность

в массиве всегда заняты все ячейки

Вопрос 14

Какие ситуации могут возникать при добавлении новой вершины как потомка заданной вершины в недвоичном дереве

отсутствие в массиве указателей у заданной вершины свободного места

наличие у заданной вершины потомков

отсутствие у заданной вершины потомков

отсутствие заданной вершины в дереве

Вопрос 15

Какие утверждения справедливы относительно представления графа с помощью матрицы смежности

в этом представлении используются двухмерные массивы

данное представление рекомендуется использовать для графов с фиксированным числом вершин

данное представление имеет простую программную реализацию

данное представление позволяет легко изменять набор вершин в графе

Вопрос 16

В каких случаях поиск в методе цепочек дает положительный результат

если ячейка массива, определяемая значением хеш-функции, содержит искомый ключ

если в процессе просмотра ячеек массива по определенному правилу будет обнаружена ячейка с искомым ключом

если один из элементов списка, связанного с исходной ячейкой, содержит искомый ключ

если хеш-функция для искомого ключа дает положительное значение

Вопрос 17

Какие вспомогательные списки будут созданы при размещении десяти ключей ( 15, 19, 77, 33, 12, 35, 54, 14, 20, 10 ) в семиэлементной хеш-таблице

(33, 12, 54)

(35, 14)

(77, 35, 14, 20)

(19, 35)

Вопрос 18

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

такой поиск обеспечивает более равномерное распределение ключей по массиву

такой поиск не обеспечивает обход всех ячеек массива

такой поиск требует использования датчика случайных чисел

такой поиск требует минимальных затрат памяти по сравнению с остальными

Вопрос 19

Укажите два наилучших алгоритма по критерию трудоемкости

алгоритм с логарифмической скоростью роста

алгоритм с линейной скоростью роста

алгоритм с линейно-логарифмической скоростью роста

алгоритм с квадратичной скоростью роста

Вопрос 20

Сколько раз выполняется внешний цикл в программах простой сортировки

n-1

n

1

n+1

Вопрос 21

Какие достоинства имеет пирамидальная сортировка по сравнению с другими методами

пирамидальная сортировка при любых входных данных сохраняет трудоемкость порядка O(n*log n)

пирамидальная сортировка эффективна при поиске нескольких первых наименьших элементов

пирамидальная сортировка требует существенно меньше памяти

пирамидальная сортировка имеет наиболее простую программную реализацию

Вопрос 22

Какой шаг выполняется самым первым при начале обработки очередного подмассива

выбор опорного элемента

поиск в подмассиве минимального элемента

поиск в подмассиве максимального элемента

поиск медианного элемента

Вопрос 23

Что выполняется на основном этапе сортировки файлов естественным слиянием

распределение объединенных серий по выходным вспомогательным файлам

сортировка отдельных серий методами сортировки массивов

сортировка серий с помощью Б-дерева

попарное объединение серий из входных вспомогательных файлов

Вопрос 24

Какие условия необходимы для применения поразрядной сортировки

наличие в процессоре специальных поразрядных команд

возможность преобразования строковых ключей в целые числа

все ключи — целые числа

все ключи имеют заранее известную разрядность