Задачи по программированию  

Структуры данных и их применение

к содержанию задачника

1. Многочлен \(P(x)=a_nx^n+a_{n-1}x^{n-1}+…+a_1x+a_0\) с целыми коэффициентами можно представить в виде списка. При этом, если \(a_i=0\), то соответствующий элемент не включается в список. На рисунке показано общее представление многочлена и пример для \(S(x)=-5x^6+3x^2-x+7\):
   Необходимо описать тип данных, соответствующий предложенному представлению многочленов, а также разработать процедуру Add(P,Q,R) вычисления суммы многочленов Q и R, результат – многочлен P.
2. Задача связности. Предположим, что имеется последовательность пар целых чисел (пара p-q интерпретируется в значении “р связано с q“). Если р связано с q, a q связано с r, то р связано с r. Задача состоит в написании программы для исключения лишних пар из набора: когда программа получает очередную пару р-q, она должна добавлять эту пару только в том случае, если из предыдущих пар не следует, что что р связано с q.  Пример: 3-4, 4-9, 8-0, 2-3, 5-6. К данному списку 2-9 не добавляем, так как 2-3-4-9.
3. Создать список из заданного количества элементов. Выполнить циклический сдвиг этого списка на N элементов вправо или влево.
4. Реализовать с помощью однонаправленного линейного списка операцию умножения длинного целого числа на N (целую цифру, то есть целое число от 0 до 9).
5. Исходный файл содержит два набора положительных значений, между наборами стоит отрицательное значение. Построить два списка С1 и С2, элементы которых содержат значение из наборов 1 и 2 соответственно. Элементы расположить по возрастанию. Выполнить соединение списков
6. Создать два стека и поменять информацию местами.
7. Исходный файл содержит наименование некоторых объектов. Построить список, элементы которого содержат наименование и шифры данных объектов, причем элементы списка должны быть упорядочены по возрастанию значений шифров. Выполнить «сжатие» списка, удалив продублированные наименования объектов.
8. Задано множество точек на двухмерной плоскости. Найти три разные точки, которые составляют треугольник наибольшего периметра. Структуру данных “множество” реализовать в виде класса.
9. Задано множество точек на двухмерной плоскости. Найти такую точку, от которой сумма расстояние к другим точкам наименьшая.  Структуру данных “множество” реализовать в виде класса.
10. На плоскости заданы N множеств по M точек в каждой. Найти среди точек первого множества такую точку, которая принадлежит наибольшему количеству множеств. Структуру данных “множество” реализовать в виде класса.
11. Создать список из стихов одного автора. Выполнить сортировку списка по возрастанию размера стихов.
12. Ввести некоторое число и записать его цифры в стек. Вывести число, у которого цифры идут в обратном порядке. Предусмотреть возможность введения произвольного количества чисел.
13. Система состоит из трех процессоров P1, P2, P3, очереди F, стека S и распределителя задач R. В систему поступают запросы на выполнение задач трёх типов – T1, T2 и T3, каждая для своего процессора.Поступающие запросы ставятся в очередь. Если в начале очереди находится задача Ti и процессор Pi свободен, то распределитель R ставит задачу на выполнение в процессор Pi, а если процессор Pi занят, то распределитель R отправляет задачу в стек и из очереди извлекается следующая задача. Если в вершине стека находится задача, процессор которой в данный момент свободен, то эта задача извлекается и отправляется на выполнение. Осуществить моделирование работы данной системы.
14. Задано два списка, которые содержат результаты N-измерений тока (I) и напряжения (U) на неизвестном сопротивлении (R). Найти приближенное значение R методом наименьших квадратов.
15. Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования начального хеш-адреса использовать метод деления, а затем при возникновении коллизии процедуру квадратичного исследования.
16. Написать программу, определяющую является ли двоичное дерево деревом поиска.
17. Имеется дерево, корень которого соответствует основателю рода. Сыновья каждой вершины задают сыновей и дочерей соответствующего человека. Указываются имена двух человек (например, А и В) . Сообщить, какая из следующих ситуаций имеет место:
    1) А предок В;
    2) В предок А;
    3) А и В имееют ближайшего общего предка С.
18. При запуске программы в консоли должно открыться меню с выбором “Работа со списками” или “Работа с деревьями”. При выборе какого-либо из пунктов должно открыться подменю. Подменю “Работа со списками” должно включать в себя пункты: “Включить новый элемент после i-ого по номеру элемента”, “Исключить элемент после i-ого по номеру элемента”, “Поменять местами i-ый и i-ый+1 по номерам элементы”. Подменю “Работа с деревьями” должно выполнять следующие действия: создание бинарного дерева (дерева поиска) в диалоге с пользователем (способ формирования дерева: с учётом значений ключа), обход бинарного дерева каждым из трёх способов с выдачей на экран содержимого информационных полей, включение элемента в бинарное дерево (согласно алгоритму формирования дерева), удаление заданного узла из дерева (без поддерева), удаление дерева с освобождением памяти, вывод дерева на экран. А так же определить количество листьев на заданном уровне дерева, определить количество узлов (не листьев) бинарного дерева.
19. Составить программу  для построения и обработки дерева общего вида или упорядоченного двоичного дерева, содержащего узлы целого типа. После того как дерево, создано с ним можно выполнять следующие действия:
    Добавление нового узла (для двоичного дерева положение нового узла определяется в соответствии с требованием сохранения порядка, для дерева общего вида должен задаваться путь до добавляемого узла, добавляемый узел становится младшим сыном).
    Текстовая визуализация дерева (значение каждого узла выводится на отдельной строке, с отступом пропорциональным глубине узла (шаг отступа равен двум пробелам), в порядке старшинства узлов).
    Удаление узла (двоичное дерево перестраивается в соответствии с требованием сохранения целостности и порядка; для дерева общего вида удаляется все поддерево, исходящее из удаляемого узла; должно быть предусмотрено корректное освобождение памяти). Определение числа вершин, степень которых совпадает со степенью дерева.
20. Задан граф (орграф) в виде матрицы смежности. Составить программу
    а) проверки, есть ли в графе петли;
    б) поиска в графе изолированной вершины (не смежной с дру­гими);
    в) определения степени графа;
    г) получения последовательности ребер.
21. Запрограммировать структуры данных и операции над ними для представления графа в виде
    а) последовательности ребер (дуг),
    б) векторов смежности,
    в) матрицы смежности,
    г) списков смежности,
    д) матрицы весов,
    е) сети,
    ж) матрицы инцидентности,
    з)списковой структуры.
    Необходимые детали представления уточнить  самостоятельно.
22. Дан граф (орграф). Составить описание данных для его представления и фрагмент программы
    а) получения кратчайших путей и расстояний между всеми вер­шинами по алгоритму Флойда и вывода кратчайшего пути от вершины А до вершины В.
    б) получения матрицы связности по алгоритму Уоршалла и вывода номеров вершин каждой компоненты связности графа.
23. Разработать программу, выполняющую обработку данных на основе рекурсивных алгоритмов.
    Дано \(N\) городов и известны расстояния между ними. Не все города связаны друг с другом дорогой. Найти все возможные маршруты из города А в город В (ни в один город не заходить дважды). Определить самый длинный и самый короткий маршрут.
24. Система двусторонних дорог такова, что для любой пары городов можно указать соединяющий их путь. Найдите такой город, сумма расстояний от которого до остальных городов минимальна.
25. Для заданной системы двусторонних дорог определите, можно ли, закрыв какие-нибудь три дороги, запретить перемещение из города А в город Б.
26. Дана система двусторонних дорог. \(N\)-периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше \(N\). Для данного \(N\) определите \(N\)-периферию.
27. Определите, можно ли в данной системе двусторонних дорог проехать из города А в город B так, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.
28. За проезд по каждой дороге взымается некоторая пошлина. Найдите путь из города А в город B с минимальной величиной \(S+P\), где \(S\) – сумма длин дорог пути, а \(P\) – сумма пошлин проезжаемых дорог.
29. Найдите медиану графа, то есть такую его вершину, что сумма расстояний от нее до остальных вершин минимальна.
30. Разработать класс B-дерево для хранения объектов, обладающих ключом с операцией сравнения. При реализации следует пользоваться статическим полиморфизмом на основе шаблонов.