Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Очередь

Стек

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

Очередь

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

Дек

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

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

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

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

Вариант № 1 1. Поля данных: название игрушки, цена, количество, возрастные границы, например от 2 до 5. Вывести названия игрушек, которые подходят детям определенного возраста и стоят не больше определенной суммы. Получить сведения о самом дорогом конструкторе. 2. Элементами дека являются натуральные числа. Удалите из дека элементы, оставив только простые числа. Расположите их в порядке неубывания. (Структура данных – дек).

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

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

Вариант № 4 1. Поля данных: название растения, время (месяц) высадки, количество семян в упаковке, стоимость одной упаковки. Вывести названия растений, семена которых можно высаживать с марта по май. Провести корректировку цены для семян определенного названия. 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. Поля данных: название животного, природная зона, затраты на корм за один день. Вывести количество животных определенной природной зоны, находящихся в зоопарке, и определить, сколько денег тратится на содержание определенного животного в месяц. 2. Некая программа может получать входные данные от пользователя и изредка от другой программы, причем данные, предоставляемые другой программой, имеют более высокий приоритет в сравнении с пользователем. Напишите программу для моделирования потоков данных в описанном процессе (структура данных – дек с ограниченным выходом)

Вариант № 6 1. Поля данных: марка автомобиля, страна-производитель, год выпуска, объем двигателя, расход бензина на 100 км, цена, количество экземпляров. Скорректировать данные об определенном автомобиле при изменении на него цены. Вывести марку автомобиля с определенным объемом двигателя и наименьшим расходом бензина. 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. Поля данных: страна, город, название отеля, класс отеля, стоимость проживания за один день, стоимость проезда в оба конца. Вывести сведения об отелях определенного класса, где стоимость проживания за неделю наименьшая. Определить среднюю стоимость тура на неделю в определенный класс отеля, включая стоимость проживания и стоимость проезда. 2. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

Вариант № 8 1. Поля данных: название, символическое обозначение, массу атома, заряд ядра. Вывести сведения о химическом элементе по его символическому названию. Найти элемент с самой большой массой. 2. Многочлены вида , где e 1> e 2>…> e n³0, можно представить в виде очереди, где каждый элемент имеет два поля: одно – для коэффициента ci, второе – для показателя степени ei. Для описанного представления многочленов напишите программу их дифференцирования.

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

Вариант № 10 1. Поля данных: фамилия автора, название, издательство, год издания, тематика книги. Вывести названия книг определенного автора, изданных после 2000 года. Определить долю книг в библиотеке по теме «Программирование» от общего количества экземпляров. 2. Многочлены вида , где e 1> e 2>…> e n³0, можно представить в виде очереди, где каждый элемент имеет два поля: одно – для коэффициента ci, второе – для показателя степени ei. Напишите программу сложения многочленов, представленных описанным образом.

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

Вариант № 12 1. Поля данных: наименование товара, страна-импортер и объем поставляемой партии в штуках. Вывести страны, в которые экспортируется определенный товар и общий объем его экспорта. 2. Многочлены вида , где e 1> e 2>…> e n³0, можно представить в виде очереди, где каждый элемент имеет два поля: одно – для коэффициента ci, второе – для показателя степени ei. Для описанного представления многочленов написать программу вычисления значения р (х) при заданном х.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

12. Что такое дескриптор списка?

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

14. Какие операции применимы к стекам?

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

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

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

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

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

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

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

22. Что такое дек? Какие операции применимы к декам?

23. В чем различие между конкатенацией двух стеков и конкатенацией двух очередей?

24. Какая структура данных описывается аббревиатурой LIFO?

25. Какая структура данных описывается аббревиатурой FIFO?

26. От чего зависит выбор структуры хранения для реализации структуры данных?