Структуры данных и прикладные алгоритмы
для специальности 090105 (075500)
Кафедра КИБЭВС
Мещеряков Р.В.
Томск-2005

№ 1
Очередь нельзя организовать на базе одного стека.

№ 2
В понятии реализации одного исполнителя на другом мощнее:
• Дек.

№ 3
Для реализации дека необходимо
• три исполнителя типа “стек”.

№ 4
Для реализации стека необходим
• один исполнитель типа “дек”.

№ 5
Используя исполнители типа “дек”, множество реализовать невозможно.

№ 6
Невозможно реализовать стек при исполнителях типа “множество”.

№ 7
Один исполнитель типа «последовательность» необходим для реализации стека.

№ 8
Наиболее мощной (в понятии реализации одного исполнителя на другом) является структура -
• Л2-список.

№ 9
Для реализации вектора необходим
• один исполнитель типа “матрица”.

№ 10
Для реализации матрицы -
• один исполнитель типа “вектор”.

№ 11,12
Граф может быть без ребер и/или узлов.

№ 13
Граф можно реализовать с помощью матрицы.

№ 14
Цикл в графе не может быть длиной менее 1.

№ 15
Однa матрица смежности необходима для построения матрицы инциденций.

№ 16
Сколько циклов допустимо в графе типа дерево.
• Ни одного.

№ 17
У отца в бинарном дереве может быть
• два сына.

№ 18
В полном двоичном дереве высоты 4
• 31 узел.

№ 19
Минимальная единица информации.
• Бит.

№ 20
Каким образом будет храниться число 677645(16), для хранения которого выделено 2 байта.
• 45 76 67 00.

№ 21
Соответствие числа 137 в BCD формате.
• 0001 0011 0111.

№ 22
Максимальное число со знаком, которое можно представить с помощью 1 байта.
• 127.

№ 23
Для представления всех символов алфавита русского языка достаточно
• 6 бит.

№ 24
Максимальная длина строки при хранении строки со счетчиком, базовым элементом для хранения которой является байт.
• 255.

№ 25
Не возможно сразу определить длину строки при хранении с использованием строки с признаком конца строки.

№ 26
Условия, при соблюдении которых возможна сортировка.
• Трихотомии.
• Транзитивность.

№ 27,28
Сортировки, наиболее эффективные в общем случае по времени и/или по количеству перестановок.
• Примерно одинаковы.

№ 29
Особенность внешней сортировки.
• Данные расположены во внешней памяти.

№ 30
Узкое место во внешней сортировке в самом общем случае.
• Операции чтения/записи.

№ 31
У различных значений файла может быть одинаковое значение хеш-функции.

№ 32
Простой поиск быстрее поиска с использованием хеш-функции, если:
• Kоличество значений в искомом файле мало, а время на вычисление хеш-функции значительно.

№ 33
Бинарные деревья можно использовать для ускорения поиска.

№ 34
Для сортировки методом Шелла массива 10 элементов требуется
• 4 прохода.

№ 35
Нельзя сортировать элементы “1”, “время”, “time”, true
• потому что нельзя упорядочить.

№ 36
Для представления одного нагруженного дерева необходимо
• две матрицы.

№ 37
Деревьев в лесу может быть
• сколько угодно.

№ 38
Скорости прямого, обратного и симметричного обхода дерева одинаковы.

№ 39
Какой обход дерева приведен ниже?
Процедура Обход (Х)
Занести в список Х
Если Х – не лист, то Обход (Левый сын(Х)), Обход (Правый сын (Х))
Конец процедуры
• Прямой.

№ 40
Можно обойти дерево, состоящее из одного узла.

№ 41
Сколько матриц смежности необходимо для представления ориентированного графа.
• Одна.

№ 42
Максимальное количество перестановок для метода выбора 15 элементов.
• 14.

№ 43
Карманный вид сортировки наиболее быстрый в самом общем случае.

№ 44
Для организации сортировки типа пузырек необходимо
• три исполнителя типа “стек”.

№ 45
Сколько циклов может быть в графе типа “лес”.
• Hи одного.

№ 46
В динамическом векторе может быть
• сколько угодно элементов.

№ 47
Лучше задать дерево с помощью структуры данных:
• Л1-список.

№ 48
Отсортировать множество не имеет смысла.

№ 49
Сколько множеств необходимо для представления графа.
• Hельзя представить.

№ 50
Максимальное число сравнений методом пузырька массива из 32 элементов.
• 496.