ВУЗ:
Составители:
Рубрика:
Изучите способ представления деревьев и лесов в виде бинарных деревьев. Рассмотрите лес из двух де-
ревьев и получите соответствующее ему бинарное дерево. Посредством выполнения этой процедуры в обрат-
ном порядке убедитесь в том, что всякому бинарному дереву соответствует единственный лес. Изучите прямой,
обратный и концевой порядки прохождения лесов, полученные, исходя из указанного соответствия. Для пони-
мания значения этих трех методов прохождения лесов рассмотрите представление дерева с помощью вложен-
ных скобок и установите связь такого представления с прямым, обратным и концевым порядками прохождения.
Познакомьтесь с представлениями деревьев при последовательном распределении памяти и акцентируйте
свое внимание на случаях, когда такой способ распределения является наиболее подходящим. Исследуйте один
из простых способов представления деревьев и лесов, в котором левые связи явно не указаны, и рассмотрите
наиболее интересные свойства такого представления.
Выясните, что для полной спецификации всякого ориентированного дерева или леса достаточно знания
только всех восходящих связей. Рассмотрите важное приложение этого подхода к построению дерева или леса,
называемое обработкой соотношений эквивалентности. Изучите алгоритм E решения такой задачи, опробуйте
его вручную для некоторой входной информации и по полученным выходным данным нарисуйте лес, каждое
дерево которого определяет свое множество эквивалентных элементов.
Познакомьтесь с использованием понятия дерева при анализе вычислительных алгоритмов. Рассмотрите
систематический метод обнаружения независимых неизвестных в задаче определения количества реализаций
каждого шага алгоритма. Для лучшего понимания этого метода используйте его при решении конкретного
примера и проанализируйте полученные результаты.
Вопросы для самопроверки
1. Что такое информационная структура, структурные отношения, список, узел списка, указатель узла спи-
ска, пустая связь и переменная связи?
2. Какой список называется линейным и какие операции могут быть выполнены с линейными списками?
3. Какие специальные названия имеют линейные списки, в которых включение и исключение производят-
ся в первом или последнем узлах?
4. Каким образом организовано последовательное распределение памяти машины при хранении линейно-
го списка?
5. Какие операции и в какой последовательности необходимо выполнить, чтобы поместить новый эле-
мент в стек и исключить элемент из стека?
6. Каким образом организовано представление очереди и какие операции необходимо выполнить для
включения элемента в конец очереди и исключения начального узла?
7. Как можно обойти проблему выхода очереди за пределы памяти?
8. Что понимается под ситуациями "переполнение" и "нехватка", и как должны быть описаны операции
включения и исключения узлов для стека и очереди с учетом этих ситуаций?
9. Каким образом могут хорошо сосуществовать вместе в одной области памяти два списка переменного
размера, и почему это невозможно для трех и более списков переменного размера?
10. Что понимается под перепаковкой памяти, и с какими способами перепаковки Вы знакомы?
11. Каким образом организуется связанное распределение памяти при хранении линейных списков?
12. В чем заключаются преимущества и недостатки последовательного и связанного распределения памя-
ти?
13. Что понимается под списком свободного пространства и пулом памяти?
14. Каким образом организован список свободного пространства, и какие операции необходимо выполнить
для включения и исключения узлов при работе с этим списком?
15. В чем заключается метод, позволяющий использовать минимально возможный пул памяти?
16. Каким образом реализуются наиболее распространенные операции со связанными стеками и очередя-
ми?
17. Какой смысл вкладывается в понятие топологической сортировки, и как можно решить эту задачу про-
стым способом?
18. Каким образом решает задачу топологической сортировки машинно-ориентированный алгоритм Т
?
19. Что обычно понимается под циклическим списком, и каковы особенности такого списка?
20. Как реализуются операции включения и исключения узлов из циклического списка, очистки цикличе-
ского списка, включения одного циклического списка в другой циклический список, расщепления одного цик-
лического списка на два циклических списка?
21. Каким образом циклические списки используются в алгоритме А сложения двух многочленов?
22. Как организованы линейные списки с двумя связями, и какие действия необходимо выполнить для
включения и исключения информации на левом и правом концах таких списков?
23. Почему представление двусвязного списка с головным узлом является более предпочтительным, чем
представление такого списка без этого узла?
24. Каким образом организуется последовательное распределение памяти при хранении массивов, имею-
щих полную прямоугольную структуру и структуру треугольной матрицы?
25. Как можно использовать линейную адресацию при плотном упаковывании вместе двух треугольных
матриц одинакового размера в одну прямоугольную матрицу?
26. Каким способом организуется связанное распределение памяти для массивов информации и, в частно-
сти, разреженных матриц?
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
