Normal 0 false false false RU X-NONE X-NONE MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Обычная таблица"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman","serif";}

ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПО КУРСУ СиАОД

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.                Бинарное дерево поиска. Привести пример построения.

37.                Сбалансированное бинарное дерево. Сравнить с идеально сбалансированным. Привести пример таких деревьев.

38.                Вставка элемента в АВЛ-дерево. Привести пример.

39.                Основные определения ориентированных графов: вершина, дуга, путь, цикл. Помеченный орграф. Привести примеры.

40.                Представление орграфов с помощью матриц смежности. Пример.

41.                Нахождение кратчайшего пути на орграфе с помощью алгоритма Дейкстры, пояснить примером.

42.                Нахождение кратчайших путей на орграфе между парами вершин с помощью алгоритма Флойда, пояснить примером.

43.                Нахождение центра орграфа, пояснить примером.

44.                Обход орграфа поиском в глубину, пояснить примером.

45.                Модель вычислений, использующих внешнюю память.

46.                Ускорение операций с файлами. Хешированные файлы.

47.                Ускорение операций с файлами. Индексированные файлы. Пример.

48.                Ускорение операций с файлами. Несортированные файлы с плотным индексом. Пример.

49.                Внешние деревья. Поиск записей в В-дереве. Пример.

50.                Внешние деревья. Вставка записей в В-дерево. Пример.

51.                Внешние деревья. Удаление записей  из В-дерева.  Пример.