УНИВЕРСИТЕТ УПРАВЛЕНИЯ "ТИСБИ" Тест Алгоритмы обработки данных

УНИВЕРСИТЕТ УПРАВЛЕНИЯ "ТИСБИ"

Номер семестра 3

Наименование предмета Алгоритмы обработки данных

Преподаватель Таренко Л.Б.

Балл 77 (Проходной 67). См. Демо файл!

ВОПРОСЫ:

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

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

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

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

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

2. Какие утверждения справедливы относительно общего понятия "древовидная структура"

дерево - это разветвляющаяся (нелинейная) структура

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

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

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

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

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

обработка удаляемого элемента

исключение элемента из списка

удаление элемента из массива

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

выделение памяти для размещения новой записи и заполнение полей этой записи

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

занесение в адресное поле нового элемента списка адреса созданной записи

включение нового элемента в список

5. Как реализуется проход в прямом направлении по динамическому двунаправленному списку с заголовком

pCurrent := pHead^.Right; while pCurrent<>pHead do pCurrent := pCurrent^.Right;

pCurrent := pHead; while pCurrent<>nil do pCurrent := pCurrent^.Right;

pCurrent := 0; while pCurrent<>pHead do pCurrent := pCurrent + 1;

pCurrent := pHead^.Left; while pCurrent<>pHead do pCurrent := pCurrent^.Left;

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

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

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

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

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

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

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

отсутствие элементов в списке

отсутствие удаляемого элемента

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

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

поиск оформляется как функция, которая возвращает либо адрес найденного элемента, либо пустой адрес

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

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

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

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

основной указатель на первый элемент

основной указатель на последний элемент

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

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

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

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

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

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

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

11. Какие утверждения справедливы относительно внутренних методов поиска

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

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

эти методы должны учитывать особенности взаимодействия с внешней памятью

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

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

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

проверка числа вершин, оставшихся на странице, с которой был взят элемент-заменитель

проверка числа вершин, оставшихся на нетерминальной странице

удаление элемента из массива нетерминальной страницы

13. Что происходит при попытке добавления новой вершины на полностью заполненную страницу Б-дерева

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

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

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

отказ в выполнении операции добавления

14. Какие данные должна содержать страница Б-дерева

счетчик числа вершин на странице

указатель на левого потомка

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

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

15. Какие утверждения справедливы относительно спискового представления графов

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

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

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

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

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

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

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

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

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

17. Какие утверждения справедливы относительно операции добавления вершины в дерево поиска

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

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

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

новую вершину можно добавить в любое место дерева

18. Какие утверждения относительно переменных-указателей являются правильными

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

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

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

указатели реализованы только в языке Си

19. Что необходимо задать при объявлении переменных-указателей

имя переменной

адресуемый тип данных

размер адресуемых данных

адрес размещения данных в памяти

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

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

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

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

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

21. Имеется набор данных [28, 22, 29, 05, 11, 88, 44, 100, 99, 01, 02]. Какой вид он будет иметь после первого этапа сортировки слиянием

[22, 28, 29, 05, 11, 44, 88, 100, 01, 02, 99]

[05, 11, 22, 28, 29, 44, 88, 100, 01, 02, 99]

[01, 02. 05, 11, 22, 28, 29, 44, 88, 99, 100]

[28, 22, 05, 29, 44, 11, 88, 99, 01, 02, 100]

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

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

ключи - целые числа со значениями от 1 до m

в основе метода - комбинированная структура типа "Динамический список списков"

метод имеет квадратичную оценку трудоемкости

23. Дан массив с элементами ( 35, 08, 10, 15, 20, 11, 18, 25, 23, 30, 40 ). Какой массив будет получен после просеивания первого элемента ( 35 )

08, 15, 10, 23, 20, 11, 18, 25, 35, 30, 40

08, 35, 10, 15, 20, 11, 18, 25, 23, 30, 40

08, 15, 10, 35, 20, 11, 18, 25, 23, 30, 40

08, 10, 11, 15, 18, 20, 23, 25, 30, 35, 40

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

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

поиск медианы равносилен сортировке массива

медианный элемент всегда находится в середине массива

медиана - это среднее арифметическое всех элементов массива

25. Какие утверждения справедливы относительно программной реализации сортировки обменами

реализация включает двойной цикл

оба цикла - с известным числом повторений

внутренний цикл - с шагом (-1)

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

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

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

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

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

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

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

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

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

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

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

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

массив динамических списков

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

дерево поиска

двухмерный массив

29. Какие базовые операции составляют основу хеш-поиска

вычисление индекса размещения ключа в массиве

обращение в ячейки массива по индексам, вычисленным на основе входных ключей

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

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

30. Что необходимо объявить для реализации спискового представления недвоичного дерева

структуру элементов подсписков потомков

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

переменную-указатель первого элемента основного списка родителей

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