Очередь

Стек

Обязательные: добавление элемента в стек, удаление элемента из стека. Дополнительные: проверка заполнения стека, проверка пустоты стека, неразрушающее чтение элемента с вершины стека.

Очередь

Обязательные: добавление элемента в очередь, удаление элемента из очереди. Дополнительные: неразрушающее чтение элемента из головы очереди, проверка заполнения очереди, проверка пустоты очереди.

Дек

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

Дек с ограниченным входом или выходом

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

Варианты заданий

Вариант № 1 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента к концу списка, просмотр списка, поиск записи по указанному критерию, удаление последнего элемента из списка. Поля записей: язык программирования (паскаль / бейсик / си), длина программы, количество встречающихся в программе операторов {:=, case, repeat…until, with} / {input, print, do… loop, gosub} / {if, switch, do…while, return}, время выполнения. Критерий поиска – язык программирования. 2. Элементами дека являются натуральные числа. Удалите из дека элементы, оставив только простые числа. Расположите их в порядке неубывания. (структура данных – дек).

Вариант № 2 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: вставка элемента после n-го элемента списка, просмотр списка в прямом и обратном порядке, удаление первого элемента списка. Поля записей: слово, часть речи (существительное {склонение, падеж, число (если единственное, то род)} / прилагательное {разряд (если качественное, то форма), падеж, число (если единственное, то род)} / глагол {спряжение, наклонение (если изъявительное, то время), число( если единственное, то лицо)}), начальная форма. 2. Напишите программу для моделирования работы конвейера по упаковке молока в бутылки. Бутылки, заполненные не менее номинального объема, закупориваются и отправляются на склад, отбракованные снимаются с конвейера, и молоко возвращается в цех розлива (структура данных – дек с ограниченным входом слева).

Вариант № 3 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента к началу списка, просмотр списка, поиск и удаление элементов списка, удовлетворяющих критерию. Поля записей: название геометрической фигуры (квадрат {длина_диагонали}/прямоугольник {длины_сторон}/круг {радиус}), координаты точки привязки (х, у), цвет контура, цвет заливки. Критерий поиска – точка привязки. 2. Напишите программу, которая считывает символьную строку, содержащую три набора скобок: круглые (), угловые <> и квадратные [],- и определяет, правильно ли расставлены в этой строке скобки (структура данных – стек).

Вариант № 4 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в упорядоченный список с сохранением упорядоченности, просмотр списка, удаление n-го элемента из списка. Поля записей: тип посуды (кастрюля {объем}/ сковорода {диаметр, антипригарное покрытие}), материал, цена. 2. Фирма по хранению и сбыту бытовых инструментов получает грузы с оборудованием по различным ценам и продает их затем с 20%-ной надбавкой, причем товары, полученные позднее, продаются в первую очередь (структура данных – стек). Напишите программу, считывающую записи о торговых операциях двух типов: операции по закупке и операции по продаже. Запись о продаже содержит префикс “S” и количество товара. Запись о закупке содержит префикс “R”, количество товара и стоимость одного изделия. После считывания записи о закупке напечатайте ее с указанием стоимости всей партии. После считывания записи об операции продажи напечатайте, сколько изделий было продано, цену одного изделия в каждой продаваемой партии, стоимость каждой партии и суммарную стоимость всей сделки. Например, если фирмой были проданы 200 единиц оборудования, в которые входили 50 единиц с закупочной ценой 1.25$ и 150 единиц с закупочной ценой 1.1$, то напечатаны должны быть три строки: 50 штук по 1.50$ каждый на сумму 75.00$ 150 штук по 1.32$ каждый на сумму 198.00$ Всего продано на сумму 273.00$ Если на складе отсутствует требуемое в заказе число изделий, то продайте все имеющиеся, а затем напечатайте сообщение об отсутствии остальной части изделий на складе.

Вариант № 5 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: вставка элемента после n-го элемента списка, просмотр списка, поиск и удаление элементов списка, удовлетворяющих критерию. Поля записей: марка автомобиля, модификация кузова, цвет кузова, новый {на_гарантии(да, нет)} / подержанный {год выпуска, пробег}. Критерий поиска – марка автомобиля. 2. Некая программа может получать входные данные от пользователя и изредка от другой программы, причем данные, предоставляемые другой программой , имеют более высокий приоритет в сравнении с пользователем. Напишите программу для моделирования потоков данных в описанном процессе (структура данных – дек с ограниченным выходом справа)

Вариант № 6 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента к концу списка, просмотр списка в прямом и обратном порядке, удаление двух последних элементов из списка. Поля записей: название театра, дата, название спектакля, взрослый {жанр} /детский {возраст ребенка}. 2. Фирма по хранению и сбыту бытовых инструментов получает грузы с оборудованием по различным ценам и продает их затем с 20%-ной надбавкой, причем товары, полученные ранее, продаются в первую очередь (структура данных – очередь). Напишите программу, считывающую записи о торговых операциях двух типов: операции по закупке и операции по продаже. Запись о продаже содержит префикс “S” и количество товара. Запись о закупке содержит префикс “R”, количество товара и стоимость одного изделия. После считывания записи о закупке напечатайте ее с указанием стоимости всей партии. После считывания записи об операции продажи напечатайте, сколько изделий было продано, цену одного изделия в каждой продаваемой партии, стоимость каждой партии и суммарную стоимость всей сделки. Например, если фирмой были проданы 200 единиц оборудования, в которые входили 50 единиц с закупочной ценой 1.25$ и 150 единиц с закупочной ценой 1.1$, то напечатаны должны быть три строки: 50 штук по 1.50$ каждый на сумму 75.00$ 150 штук по 1.32$ каждый на сумму 198.00$ Всего продано на сумму 273.00$ Если на складе отсутствует требуемое в заказе число изделий, то продайте все имеющиеся, а затем напечатайте сообщение об отсутствии остальной части изделий на складе.

Вариант № 7 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: вставка элемента перед n-м элементом списка, просмотр списка в прямом и обратном порядке, удаление из списка каждого второго элемента. Поля записей: тип издания (книга {автор} / журнал {номер}, название, год издания, издательство. 2. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

Вариант № 8 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента к началу списка, просмотр списка в прямом и обратном направлении, перемещение элемента с конца списка в его начало. Поля записей: ткань, тип одежды (рубашка {рукав длинный/ короткий} / брюки / платье {рукав есть/нет}), размер ({рост, охват шеи для рубашки} / {рост, охват бедер для брюк} / {рост, охват груди, охват бедер для платья}), цена. 2. Многочлены вида , где можно представить в виде очереди, где каждый элемент имеет два поля: одно – для коэффициента ci, второе – для показателя степени ei. Для описанного представления многочленов напишите программу их дифференцирования.

Вариант № 9 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в упорядоченный список с сохранением упорядоченности, просмотр списка в прямом и обратном направлении, удаление первого элемента списка. Поля записей: ФИО, год рождения, образование (высшее {вуз, номер диплома, ученая степень (да, нет)} /неполное_высшее {вуз, оконченный курс}/ среднее {школа, номер аттестата} /неполное_среднее {школа, оконченный класс}). 2. Элементами дека являются натуральные числа. Удалите из дека элементы, являющиеся простыми числами. Расположите оставшиеся элементы в порядке убывания.

Вариант № 10 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: вставка элемента после n-го элемента списка, просмотр списка в прямом и обратном направлении, поиск элемента по заданному критерию. Поля записей: тип покрытия (линолеум {толщина, наличие утеплителя, ширина}/ ламинат{класс, площадь в 1 упаковке} / паркет{вид (паркетная доска, штучный), площадь в 1 упаковке}), цвет, цена 1 квадратного метра. Критерий поиска – тип покрытия. 2. Многочлены вида , где можно представить в виде очереди, где каждый элемент имеет два поля: одно – для коэффициента ci, второе – для показателя степени ei. Напишите программу сложения многочленов, представленных описанным образом.

Вариант № 11 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в список, просмотр списка, удаление произвольного элемента из списка, поиск элемента по заданному критерию. Поля записей: номер группы, имя ребенка, дата рождения (запись: число, месяц, год), домашний адрес (запись: улица, дом, квартира). Найти детей, посещающих ясли (младше 3 лет на начало текущего учебного года). 2. Напишите программу для моделирования работы конвейера по упаковке кофе в банки. Банки, заполненные не менее номинального объема, закупориваются и отправляются на склад, отбракованные снимаются с конвейера, и кофе возвращается в развесочный автомат (структура данных – дек с ограниченным входом справа).

Вариант № 12 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в конец списка, поэлементный просмотр списка с возможностью редактирования элемента, удаление из списка каждого второго элемента, поиск элементов по номеру дня диеты. Поля записей: номер дня диеты, завтрак {1 блюдо, 2 блюдо, напиток} / обед {салат, суп, основное блюдо, напиток}/ полдник {1 блюдо, напиток}/ ужин {салат, основное блюдо, напиток}, пищевая и энергетическая ценность. 2. Многочлены вида , где можно представить в виде очереди, где каждый элемент имеет два поля: одно – для коэффициента ci, второе – для показателя степени ei. Для описанного представления многочленов написать программу вычисления значения р(х) при заданном х.

Вариант № 13 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в конец списка, просмотр списка, перемещение элемента с первой позиции на n позиций вперед по списку. Поля записей: страна, номинал, монета {металл, вес, диаметр}/ купюра {размеры, цвет, изображение}, год выпуска. 2. Многочлены вида , где можно представить в виде очереди, где каждый элемент имеет два поля: одно – для коэффициента ci, второе – для показателя степени ei. Напишите программу вычитания многочленов, представленных описанным образом.

Вариант № 14 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в упорядоченный список с сохранением упорядоченности, просмотр списка, удаление двух элементов списка, начиная с текущего. Поля записей: тип мебели (мягкая {материал основы, материал обивки, наполнитель} / корпусная {материал, наличие и тип дверец, наличие стеклянных элементов}), наименование, цвет, габаритные размеры. 2. Напишите программу для моделирования Т-образного сортировочного узла на железной дороге, позволяющего разделять на два направления состав, состоящий из вагонов двух типов (на каждое направление формируется состав из вагонов одного типа) (структура данных – стек).

Вариант № 15 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: вставка элемента перед последним элементом списка, просмотр списка, удаление последнего элемента списка. Поля записей: тип изделия (пирог {тесто, начинка}/ пирожное {тесто, тип крема, пропитка}), вес, калорийность, цена. 2. Некая программа может получать входные данные от пользователя и изредка от другой программы, причем данные, предоставляемые другой программой, имеют более высокий приоритет в сравнении с пользователем. Напишите программу для моделирования потоков данных в описанном процессе (структура данных – дек с ограниченным выходом слева).

Вариант № 16 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: вставка элемента в начало списка, просмотр списка в прямом и обратном порядке, удаление из списка каждого третьего элемента. Поля записей: название произведения, автор, скульптура {материал} / картина {основа, краски}. 2. Напишите программу для моделирования работы буфера ввода данных. Пользователь имеет возможность удалять последние введенные значения, пока они не переданы программе (структура данных – дек с ограниченным входом слева)

Вариант № 17 1. Используя списковую структуру хранения, напишите программу для обработки последовательности записей, позволяющую осуществлять следующие действия: добавление элемента в конец списка, просмотр списка, перемещение элемента с текущей позиции на n позиций назад по списку. Поля записей: наименование овощей, их сорт, количество, поставщик: название, адрес, телефон. 2. Написать программу для отыскания прохода по лабиринту (структура данных – стек). Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице. После отыскания прохода программа печатает найденный путь в виде координат квадратов.

Контрольные вопросы

1. Что такое структура и структурный тип?

2. Как осуществляется доступ к элементам структур?

3. Что такое объединение? Чем объединение отличается от структуры и что у них общего?

4. Что такое абстрактный тип данных?

5. Объясните разницу между понятиями «структура данных» и «структура хранения».

6. Что такое полустатическая структура данных?

7. Что такое список как структура данных?

8. Что такое связанный список как структура хранения?

9. Какие виды списков Вы знаете?

10. Какие методы применимы к спискам?

11. Какие методы реализации списков Вы знаете?

12. Что такое стек?

13. Какие методы применимы к стекам?

14. Каков механизм заполнения стека? Что понимают под понятием «дно» стека?

15. Что такое очередь?

16. Какие методы применимы к очередям?

17. Каков механизм заполнения очереди?

18. Что такое дек?

19. Какие виды деков Вы знаете?

20. Как определить количество элементов в списке, стеке и очереди?