Вычислить как целое число значение выражения (без переменных), записанного в постфиксной форме в текстовом файле postfix.

2. Создать программу, которая отыскивает проход по лабиринту.

Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице.

Программа находит проход через лабиринт, двигаясь от заданного входа. После отыскания прохода программа выводит найденный путь в виде координат квадратов.

Алгоритм.

Выражение просматривается слева направо. Если встречается операнд (число), то его значение (как целое) заносится в стек, а если встречается знак операции, то из стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция, и ее результат записывается в стек. В конце концов, в стеке останется только одно число – значение всего выражения.

· Перевести выражение, записанное в обычной (инфиксной) форме в текстовом файле infix, в постфиксную форму. Записать его в текстовый файл postfix.

4. Алгоритм.

В стек записывается открывающая скобка, и выражение просматривается слева направо. Если встречается операнд (число или переменная), то он сразу переносится в файл postfix. Если встречается открывающая скобка, то она заносится в стек, а если встречается закрывающая скобка, то из стека извлекаются находящиеся там знаки операций до ближайшей открывающей скобки, которая также удаляется из стека, и все эти знаки (в порядке их извлечения) записываются в файл postfix. Когда же встречается знак операции, то из конца стека извлекаются (до ближайшей скобки, которая сохраняется в стеке) знаки операций, старшинство которых больше или равно старшинству данной операции, и они записываются в файл postfix, после чего рассматриваемый знак заносится в стек. В заключение выполняются такие же действия, как если бы встретилась закрывающая скобка.

Напечатать в обычной (инфиксной) форме выражение, записанное в постфиксной форме в текстовом файле postfix. Лишние скобки желательно не печатать.

Двусвязные списки

1. Дан двусвязный список:

a) вывести количество элементов в списке;

b) вставить перед (после) данным элементом списка новый элемент;

c) добавить в начало списка новый элемент, а в конец – другой новый элемент;

d) добавить набор чисел после (перед) i-го элемента;

e) продублировать в списке первый и последний элементы (новые элементы добавлять перед (после) существующими элементами с такими же значениями);

f) продублировать в списке все элементы с нечетными номерами (новые элементы добавлять перед существующими элементами с такими же значениями);

g) удалить из списка i-ый элемент;

h) удалить из списка все элементы с нечетными номерами;

i) удалить из списка все элементы с нечетными значениями;

j) удалить из списка n элементов и вывести их значения;

k) переместить i-ый элемент в начало (конец) списка;

l) переместить в списке i-ый элемент на k позиций вперед (назад);

m) перегруппировать элементы списка, переместив все элементы с нечетными (четными) номерами (значениями) в конец (начало) списка;

n) преобразовать список в циклический, связав его последний элемент с первым, а первый элемент - с последним;

o) преобразовать список в два циклических списка, разбив изначальный на равное количество элементов;

p) осуществить циклический сдвиг элементов списка на K позиций вперед (назад) (то есть в направлении от начала к концу списка). Для выполнения циклического сдвига преобразовать исходный список в циклический;

q) присвоить нулевые значения элементам исходного списка с нечетными номерами и вывести количество элементов в списке;

r) вывести все четные значения элементов исходного списка, просматривая список с конца. Вывести также количество элементов в списке.

2. Дано два двусвязных списка.

a) добавить один из списков, в конец другого. Вывести полученный список;

b) переместить заданный элемент одного списка в другой на заданную позицию;

c) объединить исходные списки, поместив все элементы первого списка (в том же порядке) перед (после) данным (-го) элементом (-а) второго списка.

Двусвязные списки с барьерным элементом

1. Дан двусвязный список. Барьерный элемент должен иметь значение 0 и быть связан с первым и последним элементом исходного списка.

a) Разбить список на два, перенеся во второй список все элементы от текущего до последнего и добавив ко второму списку барьерный элемент. Если текущий элемент исходного списка является барьерным элементом, то второй список должен быть пустым (то есть состоять только из барьерного элемента);

b) Добавить в конец исходного списка данный набор чисел (в том же порядке (в обратном порядке)) и вывести адрес текущего элемента полученного списка.

2. Даны два двусвязных списка. Барьерный элемент должен иметь значение 0 и быть связан с первым и последним элементом исходного списка. Объединить исходные списки, связав конец первого и начало второго списка (барьерным элементом объединенного списка должен остаться барьерный элемент первого (второго) списка).

3. Разряженную матрицу, содержащую незначительное количество ненулевых элементов, представить в виде трех одномерных массивов, в которых хранятся соответственно номера строк, номера столбцов и ненулевые значения исходной матрицы. Матрицу задать вручную.

Деревья

Уровень сложности

1. Построить в динамической памяти двоичное дерево и выполнить следующие действия:

a) найти в непустом дереве длину пути (число ветвей) от корня до ближайшей вершины с заданным элементом; если заданный элемент не входит в дерево, то за ответ принять -1;

b) найти величину наибольшего элемента непустого дерева;

c) найти кратчайший путь в дереве от корня до вершины с заданным информационным полем;

d) найти длиннейший путь в дереве от корня до вершины с заданным информационным полем;

e) найти путь заданной длины от корня до вершины с заданным информационным полем;

f) найти кратчайший путь в дереве от вершины с заданным информационным полем до вершины с другим заданным информационным полем;

g) найти длиннейший путь в дереве от вершины с заданным информационным полем до вершины с другим заданным информационным полем;

h) найти длины всех корневых ветвей – от корня дерева до каждого листа;

i) найти длину ветви (т.е. от i-й к j-й ветви);

j) найти, на какой глубине в дереве находится каждый лист;

k) посчитать число вершин дерева;

l) посчитать число листьев дерева;

m) посчитать число вершин на i-ом уровне непустого дерева (корень считать вершиной 0 уровня);

n) посчитать число листьев в поддереве, корнем которого является заданная вершина исходного дерева;

o) поменять местами максимальный и минимальный элементы непустого дерева, все элементы которого различны;

p) вычислить среднее арифметическое (произведение) всех элементов непустого дерева;

q) заменить в дереве все отрицательные элементы на их абсолютные величины;

r) определить, есть ли в дереве хотя бы два одинаковых элемента;

s) определить число вхождений элемента в дерево.

2. Построить в динамической памяти двоичные деревья T1 и T2. Проверить на равенство эти деревья.

3. Построить деревья (n- целое положительное число):

a) b)

4. Построить в динамической памяти двоичное дерево Т, а затем расформировать его.

5. Задано некоторое простое выражение:

a) вывести прямую польскую запись выражения, вычислив его;

b) вывести обратную польскую запись выражения, вычислив его.

6. Построить в динамической памяти двоичное дерево Т, затем преобразовать дерево так, чтобы для каждой вершины левое и правое поддерево поменялись местами.

Уровень сложности

1. В некоторой древовидной структуре опытным путем измеряется частота обращения к

каждому из элементов. По прошествии некоторого времени дерево изменяется:

a) построить дерево, сделав заданную вершину корнем;

b) построить дерево, автоматически его сбалансировав.

2. В некоторой файловой системе справочник файлов организован в виде упорядоченного двоичного дерева. Каждой вершине соответствует некоторый файл: здесь содержится имя файла, его размер, расширение, дата последнего обращения к нему, закодированная целым числом.

a) удалить все файлы, последнее обращение к которым происходило до некоторой определенной даты;

b) удалить все файлы с заданным расширением;

c) удалить все файлы с заданным именем;

d) удалить все файлы, размер которых превосходит некоторое заданное значение.

3. Построить в динамической памяти двоичное дерево и выполнить следующие действия:

a) удалить из дерева элементы с заданным информационным полем;

b) удалить крайний левый элемент k-го уровня, если он есть;

c) удалить крайний правый элемент k-го уровня, если он есть.

d) вставить дерево, сделав его продолжением i-го уровня;

e) найти все вершины, которые имеют одну дочернюю, и вставить туда недостающую вершину;

f) вставить дерево, состоящее из i уровней и j вершин, которое будет продолжением существующего дерева, начиная с k-ой вершины.

4. Дано АВЛ-дерево.

a) включить новую вершину с заданным ключом;

b) исключить вершину с заданным ключом;

c) найти вершину с заданным ключом.

5. Дано ДБ-дерево (2-3-дерево)

a) включить новую вершину с заданным ключом;

b) исключить из ДБ-дерева (2-3-дерева) вершину с заданным ключом.

Уровень сложности

1. Построить частотный словарь.

2. Формулу вида

< формула>:: =< терминал> |(< формула> < знак> < формула> )

< знак>:: = + | - | *

< терминал>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

можно представить в виде двоичного дерева (" дерева-формулы" ) согласно следующим правилам: формула из одного терминала (цифры) представляется деревом из одной вершины с этим терминалом, а формула вида (f1 s f2) – деревом, в котором корень – это знак s, а левое и правое поддеревья – это соответствующие представления формул f1 и f2.

Пример: (5*(3+8))

a) по формуле из текстового файла построить соответствующее дерево-формулу;

b) вычислить (как целое число) значение дерева-формулы;

c) распечатать дерево-формулу в инфиксной форме;

d) распечатать дерево-формулу в префиксной форме;

e) распечатать дерево-формулу в постфиксной форме.

Построить дерево-пирамиду, т.е. дерево, обладающее следующими признаками: во-первых, значение элемента в любом узле < = значений его “сыновей” (корень – наименьший элемент дерева), во-вторых, концевые узлы расположены не более, чем на двух уровнях, причем, нижний уровень сдвинут влево насколько это возможно. В дереве нет " дырок".

Формулу вида

< формула>:: =< терминал> |(< формула> < знак> < формула> )

< знак>:: = + | - | *

< терминал>:: =< цифра> |< переменная>

< цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

< переменная>:: =a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

можно представить в виде двоичного дерева (" дерева-формулы" ) согласно следующим правилам: формула из одного терминала представляется деревом из одной вершины с этим терминалом, а формула вида (f1 s f2) – деревом, в котором корень – это знак s, а левое и правое поддеревья – это соответствующие представления формул f1 и f2.

a) Упростить дерево-формулу T, заменяя в нем все поддеревья, соответствующие формулам (f+0), (0+f), (f-0), (f*1), (1*f), на поддеревья, соответствующие формуле f, а поддеревья, соответствующие формулам (f*0) и (0*f), – на вершину с 0.

b) Преобразовать дерево-формулу T, заменяя в нем

поддеревья, соответствующие формуле	на поддеревья, соответствующие формуле
((f1+f2)*f3)	((f1f3)+(f2f3))
((f1-f2)*f3)	((f1f3)-(f2f3))
(f1*(f2+f3))	((f1f2)+(f1f3))
(f1*(f2-f3))	((f1f2)-(f1f3))

c) Преобразовать дерево-формулу T, заменяя в нем

поддеревья, соответствующие формуле	на поддеревья, соответствующие формуле
((f1f3)+(f2f3))	((f1+f2)*f3)
((f1f3)-(f2f3))	((f1-f2)*f3)
((f1f2)+(f1f3))	(f1*(f2+f3))
((f1f2)-(f1f3))	(f1*(f2-f3))

4. Составить программу, которая содержит текущую информацию о книгах в библиотеке.

Сведения о книгах включает: номер УДК, фамилия и инициалы автора, название, год издания, количество экземпляров данной книги в библиотеки.

Программа должна обеспечивать:

начальное формирование данных обо всех книгах в библиотеке в виде двоичного дерева,
добавление данных о книгах, вновь поступающих в библиотеку, удаление данных о списываемых книгах,
по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания.

Составить программу, которая содержит текущую информацию о заявках на авиабилеты.

Каждая заявка включает: пункт назначения, номер рейса, фамилию и инициалы пассажира, желаемую дату вылета. Программа должна обеспечивать:

хранение всех заявок в виде двоичного дерева,
добавление и удаление заявок,
по заданному номеру рейса и дате вылета вывод заявок с их последующем удалением,
вывод всех заявок.

5. Англо-русский словарь построен в виде двоичного дерева. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Первоначальное дерево формируется в порядке английского алфавита. В процессе эксплуатации словаря при каждом обращении к компоненте к счетчику обращений прибавляется единица. Написать программу, которая:

Обеспечивает начальный ввод словаря с конкретными значениями счетчиков обращений;
Формирует новое представление словаря в виде двоичного дерева по следующему алгоритму:

a) в старом словаре ищется компонента с наибольшим значением счетчика обращений;

b) найденная компонента заносится в новый словарь и удаляется из старого;

c) переход к п.а) до исчерпания исходного словаря.

Производит вывод исходного и нового словаря.

6. На международной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована в виде двоичного дерева.

Написать программу, которая:

обеспечивает начальное формирование картотеки в виде двоичного дерева;
производит вывод всей картотеки;
вводит номер телефона и время разговора;
выводит извещение на оплату телефонного разговора.

7. Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные в информационной системе организованы в виде двоичного дерева. Написать программу, которая:

обеспечивает первоначальный ввод данных в информационную систему и формирование двоичного дерева;
производит вывод всего дерева;
вводит номер поезда и выводит все данные об этом поезде;
вводит название станции назначения и выводит данные обо всех поездах, следующих до этой станции.

⇐ Предыдущая 1 2 34