1. Составить программу, которая вставляет в список L новый элемент F за каждым вхождением элемента E.
2. Составить программу, которая вставляет в список L новый элемент F перед первым вхождением элемента E, если E входит в L.
3. Составить программу, которая вставляет в непустой список L, элементы которого упорядочены по неубыванию, новый элемент E так, чтобы сохранилась упорядоченность.
4. Составить программу, которая удаляет из списка L всеэлементы E, если такие есть.
5. Составить программу, которая удаляет из списка L за каждым вхождением элемента E один элемент, если такой есть и он отличен от E.
6. Составить программу, которая удаляет из списка L все отрицательные элементы.
7. Составить программу, которая проверяет, есть ли в списке L хотя бы два одинаковых элемента.
8. Составить программу, которая переносит в конец непустого списка L его первый элемент.
9. Составить программу, которая вставляет в список L за первым вхождением элемента E все элементы списка L, если E входит в L.
10. Составить программу, которая переворачивает список L, т.е. изменяет ссылки в этом списке так, чтобы его элементы оказались расположенными в обратном порядке.
11. Составить программу, которая в списке L из каждой группы подряд идущих одинаковых элементов оставляет только один.
12. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят одновременно в оба списка L1 и L2.
13. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2.
14. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входит в другой из них.
15. Многочлен
с целыми коэффициентами можно представить в виде списка, причем если ai=0, то соответствующее звено не включается в список.
P
Þ
n
an
Þ
n – 1
an–1
Þ
¼
Þ
a1
Þ
a0
nil
Ниже показано представление многочлена S(x) = 52x40 – 3x8 + x.
S
Þ
Þ
–3
Þ
nil
Описать тип данных, соответствующий такому представлению многочленов, и определить следующие процедуры и функции для работы с этими списками-многочленами:
15.1. Логическую функцию Ravno(P, Q), проверяющую на равенство многочлены P и Q.
15.2. Функцию Znach(P, x), вычисляющую значение многочлена P в целочисленной точке x.
15.3. Процедуру Diff(P, Q), которая строит многочлен Q — производную многочлена P.
15.4. Процедуру Slozh(P, Q, R), которая строит многочлен R — сумму многочленов Q и P.
15.5. Процедуру Print(P, v), которая печатает многочлен P как многочлен от переменной, однобуквенное имя которой является значением литерного параметра v; например, для указанного выше многочлена S процедура Print(S, 'y') должна напечатать 52y40 – 3y8 + y.
15.6. Процедуру Vvod(P), которая считывает из входного файла безошибочную запись многочлена (см. 15.5) (за ней — пробел) и формирует соответствующий список-многочлен P.
15.7. Дан многочлен P(x) степени n. Получить многочлен P2(x).
15.8. Дан многочлен P(x) степени n. Получить многочлен P(x+1) – P(x). Какова степень этого многочлена?
16. Составить программу упорядочения в порядке возрастания элементов однонаправленного списка.
Составить программу, заполняющую список последовательностью случайных различных целых чисел и суммирующую те его элементы, которые расположены между минимальным и максимальным элементом (если минимальный элемент предшествует максимальному).
18. Дан список, содержащий целые числа. Сформировать другой список из элементов данного, абсолютные величины которых являются простыми числами.
19. Дан список, содержащий натуральные числа. Удалить те его элементы, которые кратны заданному числу k.
20. Дан список, элементами которого являются векторы
(Const NMax = 200; Type Vector = Array [1..NMax] Of Real;).
Сформировать список из длин этих векторов.
21. Элементами списка являются слова — имена существительные, записанные в именительном падеже (строки длиной не более 15 символов). Составить программу, которая добавляет за каждым словом все его падежи.
22. Дан список, содержащий целые числа. Определить количество различных элементов этого списка.
23. Даны упорядоченные списки L1 и L2. Вставить элементы списка L2 в список L1, не нарушая его упорядоченности.
24. Дан список, содержащий запись неотрицательных целых чисел в двоичной системе счисления. Заменить каждый элемент списка на его запись в шестнадцатеричной системе счисления.
25. Дан список, содержащий обыкновенные дроби вида , (P — целое, Q — натуральное). Составить программу суммирования модулей этих дробей. Ответ представить в виде обыкновенной несократимой дроби.
26. Программа должна находить среднее арифметическое элементов непустого однонаправленного списка вещественных чисел, заменять все вхождения числа x на число y, менять местами первый и последний элементы, проверить, упорядочены ли числа в списке по возрастанию.
27. Дан список вещественных чисел. Написать следующие функции:
а) проверить, есть ли в нем два одинаковых элемента;
б) перенести в начало его последний элемент;
в) перенести в конец его первый элемент;
г) вставить список сам в себя вслед за первым вхождением числа x.
28. Дан список строк. Написать следующие подпрограммы:
а) обращение списка (изменить ссылки в списке так, чтобы элементы оказались расположены в противоположном порядке);
б) из каждой группы подряд идущих элементов оставить только один;
в) оставить в списке только первые вхождения одинаковых элементов.
29. Даны два списка L1 и L2 пар вещественных чисел. Написать подпрограммы, возвращающие новый список L, включающий
а) пары списка L1, первая координата которых встречается как вторая координата у пар списка L2;
б) пары (x, y) списка L1 встречающиеся в виде (y, x) в списке L2;
в) пары (x, y), где x < y списка L1.
30. Даны два списка L1 и L2 вещественных чисел. Написать подпрограммы, возвращающие новый список L, включающий по одному разу числа, которые
а) входят одновременно в оба списка;
б) входят хотя бы в один из списков;
в) входят в один из списков L1 и L2, но в то же время не входят в другой из них;
г) входят в список L1, но не входят в список L2.
31. Целое «длинное» число представляется строкой цифр. Написать программу, упорядочивающую числа по неубыванию.
32. Дан список слов, среди которых есть пустые. Написать подпрограмму,
а) переставляющую местами первое и последнее непустые слова;
б) печатающую текст из первых букв непустых слов;
в) удаляющую из непустых слов первые буквы;
г) определяющую количество слов в непустом списке, отличных от последнего.
33. Описать рекурсивную функцию или процедуру, которая
а) определяет, входит ли элемент Е в список L;
б) подсчитывает число вхождений элемента Е в список L;
в) находит максимальный элемент непустого списка;
г) печатает в обратном порядке элементы списка;
д) заменяет в списке L все вхождения Е1 на Е2;
е) удаляет из списка L первое вхождение элемента Е, если такое есть;
ж) удаляет из списка L все вхождения элемента Е;
з) строит L1 — копию списка L;
и) удваивает каждое вхождение элемента Е в список L;
к) находит среднее арифметическое всех элементов непустого списка L;
л) однонаправленный простой список L преобразует в кольцевой и возвращает адрес минимального элемента этого списка;
м) отрицательные элементы списка L переставляет в начало списка, не меняя их порядок;
н) из целочисленного списка удаляет все элементы, имеющие в своей записи цифру k;
о) список строк сохраняет в обратном порядке в текстовом файле;
п) проверяет, упорядочены ли элементы списка, содержащего строки, по алфавиту.
34. Описать процедуру, которая в списке L заменяет первое вхождение списка L1 (если такое есть) на список L2.
35. Пусть L обозначает кольцевой (циклический) двунаправленный список с заглавным звеном и пусть Е обозначает величину типа элементов, входящих в список. Описать функцию или процедуру, которая
а) определяет, является ли список L пустым;
б) печатает в обратном порядке элементы непустого списка L;
в) подсчитывает количество элементов списка L, у которых равные «соседи»;
г) определяет, есть ли в списке L хотя бы один элемент, который равен следующему за ним (по кругу) элементу;
д) в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если Е входит в L не менее двух раз;
е) удаляет из списка L первый отрицательный элемент, если такой есть;
ж) из списка L, содержащего не менее двух элементов, удаляет все элементы, у которых одинаковые «соседи» (первый и последний элементы считать соседями);
з) добавляет в конец списка L новый элемент Е;
и) в списке L удваивает каждое вхождение элемента Е;
к) строит список L по однонаправленному списку L1;
л) в конец непустого списка L добавляет все его элементы, располагая их в обратном порядке (например, по списку из элементов 1, 2, 3 требуется построить список из элементов 1, 2, 3, 3, 2, 1);
м) проверяет симметричность участка списка с i-го по j-й элемент (i < j).
Стек
1. Подсчитать количество элементов в стеке.
2. Сформировать стек и сохранить его содержимое в текстовом файле.
3. Восстановить стек из текстового файла.
4. Вычислить среднее арифметическое элементов стека.
5. Написать процедуру присоединения стека S2 к стеку S1.
6. Определить симметричность произвольного текста любой длины, используя два стека.
7. Слить два стека, содержащих возрастающую последовательность целых положительных чисел, в третий стек так, чтобы его элементы располагались также в порядке возрастания.
8. В данном тексте проверить соответствие открытия и закрытия скобок.
9. Напечатать содержимое текстового файла, выписывая символы каждой его строки в обратном порядке.
10. Проверить, является ли строка палиндромом.
11. Проверить, является ли содержимое текстового файла правильной записью формулы следующего вида:
где знаки ù, Ù и Ú обозначают соответственно отрицание, конъюнкцию и дизъюнкцию. Вычислить (как boolean) значение этого выражения.
Двоичные деревья поиска
1. Написать рекурсивную числовую функцию, подсчитывающую сумму элементов дерева.
2. Написать функцию, которая находит наибольший элемент дерева.
3. Написать функцию, которая находит наименьший элемент дерева.
4. Напишите процедуру, которая удаляет из дерева все четные элементы.
5. Написать рекурсивную процедуру, которая определяет число вхождений заданного элемента в дерево.
6. Написать рекурсивную процедуру, которая печатает элементы из всех листьев дерева.
7. Написать рекурсивную функцию, которая определяет глубину заданного элемента на дереве и возвращает –1, если такого элемента нет.
8. Написать процедуру, которая печатает (по одному разу) все вершины дерева.
9. Написать процедуру, которая по заданному n считает число всех вершин глубины n в заданном дереве.
10. Написать процедуру, которая определяет глубину дерева.
11. Отсортировать массив путем включения его элементов в дерево и скопировать отсортированные данные обратно в массив.
12. Задана последовательность слов. Определить частоту вхождения каждого из слов в последовательность. Указание. Для решения задачи любое слово ищется в дереве, которое на начальном этапе пусто. Если слово найдено, то счетчик его вхождений увеличивается на единицу, если нет, то слово включается в дерево с единичным значением счетчика.
13. Составить программу, которая печатает все элементы дерева по уровням: сначала — из корня дерева, затем (слева направо) — из вершин, дочерних по отношению к корню, затем (также слева направо) — из вершин, дочерних по отношению к этим вершинам, и т.д.
14. Составить программу, которая находит в непустом дереве длину (число ветвей) пути от корня до ближайшей вершины с элементом Е;если Е не входит в дерево, за ответ принять –1.
15. Составить программу, которая подсчитывает число вершин на n-ом уровне непустого дерева (корень считать вершиной нулевого уровня).
16. Составить программу, которая заменяет в дереве все отрицательные элементы на их абсолютные величины.
17. Описать рекурсивную функцию или процедуру, которая:
а) определяет, входит ли элемент Е в дерево;
б) определяет число вхождений элемента Е в дерево;
в) вычисляет сумму элементов непустого дерева;
г) находит величину наибольшего элемента непустого дерева;
д) определяет максимальную глубину непустого дерева, т.е. число ветвей в самом длинном из путей от корня дерева до листьев;
е) по текстовому файлу, содержащему числовые элементы (среди которых могут быть и одинаковые), строит дерево поиска;
ж) добавляет в дерево поиска новый элемент Е, если его не было в дереве.
18. Вершина двоичного дерева содержит массив целых и два указателя — на правое и левое поддеревья. Массив целых в каждом элементе упорядочен, дерево в целом также упорядочено. Функция включает в дерево целую переменную с сохранением упорядоченности. (На рисунке приведён пример такого дерева.)
19. Сформировать двоичное дерево по следующему принципу: указать элемент и количество его вхождений в дерево, т.е. если элемент включается в дерево повторно, просто счетчик его вхождений увеличивается на 1.
20. Составить программу, которая удаляет из дерева L всеэлементы E, если такие есть.
21. Составить программу, которая удаляет из дерева L все отрицательные элементы.
22. Составить программу, которая проверяет, есть ли в дереве L хотя бы два одинаковых элемента.
23. Составить программу, которая в дереве L из каждой группы подряд идущих одинаковых элементов оставляет только один.
24. Составить программу, которая формирует дерево L, включив в него по одному разу элементы, которые входят одновременно в оба дерева L1 и L2.
25. Составить программу, которая формирует дерево L, включив в него по одному разу элементы, которые входят в дерево L1, но не входят в дерево L2.
26. Составить программу, которая формирует дерево L, включив в него по одному разу элементы, которые входят в один из деревьев L1 и L2, но в то же время не входит в другое из них.
27. Определить количество различных элементов дерева.
, (P — целое, Q — натуральное). Составить программу суммирования модулей этих дробей. Ответ представить в виде обыкновенной несократимой дроби.