- •1 Билет.
- •2 Билет.
- •3 Билет.
- •4 Билет.
- •5 Билет.
- •6 Билет. Способы описания языков программирования: бнф-нотации, синтаксические диаграммы.
- •7 Билет.
- •8 Билет. Переменные, область действия, время жизни, класс памяти.
- •10 Билет.
- •19 Билет. Ввод/вывод данных на c.
- •21 Билет. Производные типы данных, массивы, работа с массивами.
- •26 Билет. Файлы прямого и последовательного доступа к данным. Форматизированный и неформатизированный ввод/вывод.
- •28 Билет. Понятие подпрограммы, назначение подпрограммы, использование подпрограмм.
- •30 Билет. Передача параметров в подпрограмму. Параметры входные и выходные, параметры передаваемые по значению и по адресу.
- •1) По значению.
- •2) По адресу.
- •31 Вопрос. Использование подпрограмм. Параметры формальные, локальные, глобальные, обращение к подпрограммам, фактические параметры.
- •32 Билет. Передача параметров-массивов в подпрограмму. Примеры.
- •33 Билет. Передача параметров-функций в подпрограмму.
- •34 Билет. Рекурсивные функции. Примеры.
- •35 Билет. Понятие структурного программирования, этап проектирования - композиция и декомпозиция, понятие статической и динамической структуры программы, спецификация программы.
- •36 Билет. Понятие частичной и полной корректности программы, правила вывода - общий вид, правила консеквенции.
- •2 Способа создания динамической переменной:
- •42. Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.
- •43. Использование динамических переменных для представления и работы со стеком.
- •44. Очередь, реализация очереди массивом.
- •45. Очередь, представление и реализация основных операций с помощью динамических переменных.
- •46. Реализация основных операций со списком: добавление, удаление, поиск.
- •47. Деревья, основные операции над деревьями, представление дерева массивом.
- •48. Двусвязные линейные списки, построение и обход бинарного дерева.
- •49. Операции поиска и удаления в бинарном дереве.
47. Деревья, основные операции над деревьями, представление дерева массивом.
Древовидная структура с базовым типом Т – это либо пустая структура, либо узел типа Т, с которым связано конечное количество древовидных структур с базовым типом Т, называемых поддеревьями. Это рекурсивное определение, следуя которому, можно сказать, что линейный список – дерево, а у каждого узла – одно поддерево. Существуют различные графические способы представления:
Дерево – это неориентированный связный граф без циклов.
Дерево – это неориентированный связный граф с n вершинами и n-1 ребром.
Дерево – это конечное множество элементов, называемых узлами, таких, что:
- между узлами существует связь «исходный-порожденный». Узел у, который находится непосредственно под узлом х, называется непосредственным потомком (сыном) х, а х – предок (отец) у. если х находиться на уровне i, то у на уровне i+1.
- лишь один узел не имеет исходного (отца), он называется корнем дерева. Максимальный уровень элемента дерева называется высотой или глубиной дерева.
- остальные узлы имеют только одного отца и могут иметь ноль или более потомков. Если узел не имеет потомков, то он называется листом дерева или терминальным узлом, а остальные узлы – внутренние (если не лист и не корень), а количество непосредственных потомков узла называется его степенью. Количество ветвей или ребер, которые необходимо пройти от корня дерева к некоторому узлу называется длиной пути к этому узлу.
Исходя из этого определения можно сказать, что рисунки 1,2, и 3 учитывают связи между узлами и положение корня.
48. Двусвязные линейные списки, построение и обход бинарного дерева.
Линейный связанный список - это конечное множество компонент, каждая из которых состоит из двух частей:
Информационной ( info ) и указующей ( link )
info может содержать произвольнок количество любого типа данных.
link содержит адреса других компонент этого же списка.
Если указующая часть содержит два адреса то это двусвязный список.
Обход бинарного дерева.
3 Способа обхода дерева;соотв 3 формата записи выражения
1) +ab 2)a+b 3)ab+
49. Операции поиска и удаления в бинарном дереве.
Поиск в дереве узла с заданным значением некоторого поля:
Представим дерево с помощью массива ( комб. тип)
(a+b/c)*(d-e*f)
для двоичного дерева 2 поля указывают на левое и правое поддерево, а остальные поля информационные.
struct T{char info;
int left,right;
}tree[11]
Представление дерева массивом позволяет легко найти путь от корня к узлу если значением каждого элемента A[i] является указатель на родителя узла i. Корень не ссылается ни на кого или на себя.