Задач с применением деревьев

Понятие красно-черного дерева

Свойства красно-черных деревьев

Основные операции над красно-черными деревьями

Литература: [3, с. 254-271]

Вопросы для самоконтроля

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 При работе со стеком или очередью доступны позиции ограниченного числа элементов. Возможна ли ситуация записи новых элементов стека или очереди на уже занятые собственными элементами участки памяти (запись себя поверх себя)? Ответ обоснуйте.

27 С какой целью в программах выполняется удаление стека и очереди по окончании работы с ними? Как изменится работа программы, если операцию удаления не выполнять?

28 Какую структуру данных называют очередью?

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

30 На основании чего в красно-черном дереве самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу?

31 Куда может быть добавлен элемент в красно-черное дерево? Вид дерева при этом должен сохраниться.

32 Каким образом при удалении элемента из красно-черного дерева перекрашиваются узлы?

33 Почему существует большое количество алгоритмов сортировок?

34 С какой целью используются простые сортировки, если они характеризуются малой эффективностью?

35 Чем отличается принцип сортировки по неубыванию (невозрастанию) от сортировки по возрастанию (убыванию)?

36 На каких наборах исходных данных проявляется эффективность алгоритмов простых сортировок по сравнению друг с другом?