Задачи по теме «Динамические структуры данных»

1. Составить программу, которая вставляет в список L новый элемент F за каждым вхождением элемента Е.

2. Составить программу, которая вставляет в список L новый элемент F перед первым вхождением элемента Е, если Е входит в L.

3. Составить программу, которая вставляет в непустой список L, элементы которого упорядочены по неубыванию, новый элемент Е так, чтобы сохранилась упорядоченность.

4. Составить программу, которая удаляет из списка L все элементы Е, если таковые имеются.

5. Составить программу, которая удаляет из списка L за каждым вхождением элемента Е один элемент, если таковой имеется и он отличен от Е.

6. Составить программу, которая удаляет из списка L все отрицательные элементы.

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

8. Составить программу, которая переносит в конец непустого списка L его первый элемент.

9. Составить программу, которая вставляет в список L за первым вхождением элемента Е все элементы списка L, если Е входит в L.

10. Составить программу, которая переворачивает список L, т.е. изменяет ссылки в этом списке так, чтобы его элементы оказались расположенными в обратном порядке.

11. Составить программу, которая в списке L из каждой группы подряд идущих одинаковых элементов оставляет только один.

12. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят одновременно в оба списка L1 и L2.

13. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2.

14. Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входят в другой.

15. Многочлен

с целыми коэффициентами можно представить в виде списка, причем если аi = 0, то соответствующее звено не включается в список.

Ниже показано представление многочлена S(x) = 52x40— 3х8 + х.

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

15.1. Логическую функцию Ravno (P, Q), проверяющую на равенство многочлены Р и Q.

15.2. Функцию Znach(P,x), вычисляющую значение многочлена Р в целочисленной точке х.

15.3. Процедуру Diff(P,Q), которая строит многочлен Q — производную многочлена Р.

15.4. Процедуру Slozh(P,Q,R), которая строит многочлен R — сумму многочленов Q и Р.

15.5. Процедуру Print(P,v), которая печатает многочлен Р как многочлен от переменной, однобуквенное имя которой является значением литерного параметра v; например, для указанного выше многочлена S процедура Print (S, 'у') должна напечатать 52у↑40-Зу↑8+у.

15.6. Процедуру Vvod(Р), которая считывает из входного файла безошибочную запись многочлена (за ней — пробел) и формирует соответствующий список-многочлен Р.

15.7. Дан многочлен Р(х) степени п. Получить многочлен Р2(х).

15.8. Дан многочлен Р(х) степени п. Получить многочлен Р(х + 1) — Р(х). Какова степень этого многочлена?

16. Составить программу для упорядочения в порядке возрастания элементов однонаправленного списка.

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

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

19. Дан список, содержащий натуральные числа. Удалить те его элементы, которые кратны заданному числу k.

20. Дан список, элементами которого являются векторы

(Const NMax=200;

Type Vector=Array[l..NMax] Of Real;).

Сформировать список из длин этих векторов.

21. Элементами списка являются слова — имена существительные, записанные в именительном падеже (строки длиной не более 15 символов). Составить программу, которая добавляет за каждым словом все его падежные формы.

22. Дан список, содержащий целые числа. Определить количество различных элементов этого списка.

23. Даны упорядоченные списки L1 и L2. Вставить элементы списка L2 в список L1, не нарушая его упорядоченности.

24. Дан список, содержащий запись неотрицательных целых чисел в двоичной системе счисления. Заменить каждый элемент списка на его запись в шестнадцатеричной системе счисления.

25. Дан список, содержащий обыкновенные дроби вида

, (Р — целое, Q — натуральное). Составить программу для суммирования модулей этих дробей. Ответ представить в виде обыкновенной несократимой дроби.

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

27. Дан список вещественных чисел. Написать следующие функции:

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

б) переноса в начало его последнего элемента;

в) переноса в конец его первого элемента;

г) вставки списка самого в себя вслед за первым вхождением числа х.

28. Дан список строк. Написать следующие подпрограммы:

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

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

в) оставить в списке только первые вхождения одинаковых элементов.

29. Даны два списка L1 и L2 пар вещественных чисел. Написать подпрограммы, возвращающие новый список L, включающий в себя:

а) пары списка L1, первая координата которых встречается как вторая координата у пар списка L2,

б) пары (х, у) списка L1, встречающиеся в виде (у, х) в списке L2,

в) пары (х,у), где х < у списка L1.

30. Даны два списка L1 и L2 вещественных чисел. Написать подпрограммы, возвращающие новый список L, включающий по одному разу числа, которые:

а) входят одновременно в оба списка;

б) входят хотя бы в один из списков;

в) входят в один из списков L1 и L2, но в то же время не входят в другой из них;

г) входят в список L1, но не входят в список L2.

31. Целое длинное число представляется строкой цифр. Написать программу, упорядочивающую числа по неубыванию.

32. Дан список слов, среди которых есть пустые. Написать подпрограмму, выполняющую следующее действие:

а) перестановку первого и последнего непустых слов;

б) печать текста из первых букв непустых слов;

в) удаление из непустых слов первых букв;

г) определение количества слов в непустом списке, отличных от последнего.