Варианты практических заданий для 106 группы (2004 г.)

2-3 деревья

Теоретическая часть

Краткий теоретический материал по 2-3 деревьям

Постановка задачи

Во входном текстовом файле PROCS.TXT содержится таблица со сведениями о современных микропроцессорах. Каждая запись таблицы занимает в файле одну строку следующего вида:

ключ записи, название процессора, тактовая частота, размер кеш-памяти, частота системной шины,
результат теста SPECint, результат теста SPECfp

где

ключ записи — натуральное число < maxint;
название процессора — строка длиной не более 30 символов (название не содержит запятых!);
тактовая частота (в ГГц) — положительное вещественное число, представимое real;
размер кеш-памяти (в Кб) — неотрицательное целое < maxint;
частота системной шины (в ГГц) — положительное вещественное число, представимое real;
результаты тестов — натуральные числа < maxint. Данные в файле записаны без ошибок. Программа считывает содержимое файла и строит 2-3 дерево, в листьях которого содержатся записи таблицы. После этого она ждет от пользователя команду и выполняет ее. Команды (буквы в командах латинские малые или заглавные):

L — вывести на экран вершины дерева, как определено вариантом задания. Для листовой вершины выводится ключ. Для остальных вершин выводится один ключ и символ «-» (если у вершины 2 сына), либо оба ключа (если у вершины 3 сына).
D n — (где n — ключ записи) удалить из дерева запись с ключом n, если такой записи нет, предупредить об этом пользователя;
A n — (где n — ключ записи) добавить в дерево запись с ключом n, если запись с таким ключом уже есть, предупредить об этом пользователя. Содержимое полей записи программа запрашивает у пользователя.
S — записать в файл PROCS.TXT все записи из дерева.
E — выйти из программы.

После выполнения одной команды ожидается следующая, и так до тех пор, пока не будет выполнена команда E (выход).

Варианты

В каком порядке печатать вершины (цифра варианта):

Печатать вершины по уровням слева направо, начиная с нижнего уровня.
Печатать вершины по уровням слева направо, начиная с верхнего уровня.
Порядок печати: левое поддерево, среднее поддерево, правое поддерево (если есть), а затем корень. Правило печати применяется рекурсивно ко всем поддеревьям в дереве.
Порядок печати: корень, левое поддерево, среднее поддерево, правое поддерево (если есть). Правило печати применяется рекурсивно ко всем поддеревьям в дереве.
См. вариант 3) + для каждой вершины выводится дополнительная информация — номер уровня дерева, на котором расположена вершина.
См. вариант 4) + для каждой вершины выводится дополнительная информация — номер уровня дерева, на котором расположена вершина.

Ограничения на реализацию обхода дерева при печати (буква варианта):

Р) можно использовать рекурсивные вызовы процедур и/или функций;
С) рекурсивные вызовы запрещены, использовать стек.

Пример

Пример входного файла PROCS.TXT и дерева, построенного по нему:

2, Intel Pentium 4, 2.0, 256, 0.400, 664, 734
5, Intel Itanium, 0.800, 96, 0.266, 365, 701
6, AMD Athlon XP, 1.6, 256, 0.266, 701, 634
1, IBM Power 4, 1.3, 16384, 0.400, 814, 1169

(данные взяты с www.parallel.ru)

Дерево, построенное по приведённому примеру.

Распечатка дерева по варианту 1:

1, 2, 5, 6,
2 -, 6 -,
5 -

Распечатка дерева по варианту 3:

1, 2, 2 -, 5, 6, 6 -, 5 -

Распечатка дерева по варианту 6:

5 - (уровень 1), 2 - (уровень 2), 1 (уровень 3), 2 (уровень 3), 6 - (уровень 2), 5 (уровень 3), 6 (уровень 3)