Структуры и алгоритмы обработки данных

Ввести символы, формируя из них


q       Ввести символы, формируя из них стек.
 Варианты :
1.Поменять местами первый и последний элементы стека.
2.Развернуть стек, т.е. "дно" стека сделать вершиной, а вершину - "дном".
3.Удалить элемент, который находится в середине стека, если нечетное число элементов, а если четное, то два средних.
4.Удалить каждый второй элемент стека.
5.Вставить символ '*' в середину стека, если четное число элементов, а если нечетное, то после среднего элемента.
6.Найти минимальный элемент и вставить после него 0.
7.Найти максимальный элемент и вставить после него 0.
8.Удалить минимальный элемент.
9.Удалить все элементы, равные первому.
10.Удалить все элементы, равные последнему.
11.Удалить максимальный элемент.


12.Найти минимальный элемент и вставить на его место 0.
q       Вывести полученный стек на экран.
q       Распечатать полученный стек.


Варианты :
1. Написать программу передвижения элемента на n позиций.
2. Создать копию списка.
3. Добавить элемент в начало списка.
4. Склеить два списка.
5. Удалить n-ый элемент из списка.
6. Вставить элемент после n-го элемента списка.
7. Создать список содержащий элементы общие для двух списков.
8. Упорядочить элементы в списке по возрастанию.
9. Удалить каждый второй элемент списка.
10. Удалить каждый третий элемент списка.
11. Упорядочить элементы списка по убыванию.
12. Очистить список.


Варианты:
1) Дан кольцевой список, содержащий 20 фамилий игроков футбольной    команды. Разбить игроков на 2 группы по 10 человек. Во вторую группу попадает каждый 12-й человек.
 2) Даны 2 кольцевых списка, содержащие фамилии спортсменов 2-х фехтовальных команд. Произвести жеребьевку. В первой  команде выбирается каждый n-й игрок, а во второй - каждый m-й.
 3) Задача Джозефуса.
 4) Даны 2 кольцевых списка, содержащие фамилии участников лотереи и наименования призов. Выиграет N человек (каждый К-й). Число для пересчета призов - t.
 5) Даны 2 списка, содержащих фамилии учащихся и номера экзаменационных билетов. Число пересчета для билетов - Е, для учащихся - К. Определить номера билетов, вытащенных  учащимися.
 6) Дан список содержащий перечень товаров. Из элементов 1-го списка (товары изготовленные фирмой SONY) создать новый список.
 7) Даны 2 списка, содержащие фамилии студентов 2-х групп. Перевести L студентов из 1-й группы во вторую. Число пересчета -К.
 8) Даны 2 списка, содержащие перечень товаров, производимых Концернами BOSH и FILIPS. Создать список товаров, выпускаемых как одной так и другой фирмой.
 9) Даны 2 списка, содержащие фамилии футболистов основного состава команды и запасного. Произвести К замен.
 10) Даны 2 списка, содержащие фамилии солдат 1-го и 2-го взводов. Во время атаки М человек из 1-го взвода погибли. Произвести пополнение солдатами 2-го взвода.
 11) Даны 2 списка, содержащие перечень товаров и фамилии покупателей. Каждый N-й покупатель покупает М-й товар. Вывести список покупок.
 12) Даны 2 списка, содержащие наименования товаров, выпускаемых фирмами SONY и SHARP. Создать список товаров, конкурирующих между собой товаров.


Общее задание для всех.
    Пусть имеется обслуживающая система из  n  обслуживающих аппаратов. Работа этой системы разбита на такты. В  течение   одного  такта может одна заявка стать в очередь  и  одна заявка приступить к обслуживанию, (разумеется, если аппарат свободен).   Вероятность заявки поступить на обслуживание Р(A),  вероятность  обслужить заявку P(B), вероятность заявки покинуть  очередь  после Т тактов Р(С).   После каждых  L  тактов  давать  информацию о длине очереди и  число тактов, в  течении  которых  обслуживающий аппарат простаивал.  Четным вариантам реализовать  обслуживающую систему  c неограниченной очередью, нечетным  вариантам с  конечной очередью (т.е. если в очереди будет стоять К заявок, то  следующая  заявка получает отказ в обслуживании).
 
Варианты:
1) L=50, после окончания  работы системы  выдать информацию, сколько    заявок покинуло систему без обслуживания.
2) L=55, после окончания  работы системы  выдать информацию, сколько    заявок обслуживалось больше 2 тактов.
3)  L=100, после окончания  работы системы  выдать информацию, сколько  тактов очередь была пустой.
4) L=75 , после окончания  работы системы  выдать информацию, сколько заявок обслуживалось один такт.
5)  L=25 , после окончания  работы системы  выдать информацию, сколько заявок первого приоритета приступили к обслуживанию.
6)  L=40 , после окончания работы системы выдать информацию о среднем приращении очереди.
7) L=80 , после окончания  работы системы  выдать информацию, сколько заявок обслуживалось 2 такта.
8)  L=100, после окончания  работы системы  выдать информацию, заявок обслужилось.
9) L=70 , после окончания  работы системы выдать информацию, на каком такте была самая длинная очередь.
10) L=50, после окончания  работы системы посчитать практическую вероятность простоя аппарата по формуле s/n, где s- число тактов простоя аппарат, n- общее число тактов.
11) L=65, после окончания  работы системы  выдать информацию, сколько заявок второго приоритета поступили на обслуживания.
12) L=30, после окончания  работы системы  выдать информацию, сколько заявок обслуживалось 2 или 3 такта.


 
Варианты:
1.Описать процедуру или функцию, которая:
        a) присваивает параметру Е запись из самого левого листа непустого дерева Т (лист-вершина, из которого не выходит ни одной ветви);
        b) определяет число вхождений записи Е в дерево Т.
2. Вершины дерева вещественные числа. Описать процедуру или функцию, которая:
        a) вычисляет среднее арифметическое всех вершин дерева;
        b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции).
3. Записи вершин дерева - вещественные числа. Описать процедуру, которая удаляет все вершины с отрицательными записями.
4. Записи вершин дерева - вещественные числа. Описать процедуру или функцию, которая:
        a) находит максимальное или минимальное значение записей вершин непустого дерева;
        b) печатает записи из всех листьев дерева.
5. Описать процедуру или функцию, которая:
      a) определяет, входит ли вершина с записью Е в дерево Т;
      b) если такая запись не найдена, то она добавляется.
6. Описать процедуру или функцию, которая:
      a) находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с записью Е; если Е не входит в Т, то за ответ принять -1.
      b) определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.
7. Описать процедуру СОРY(Т,Т1), которая строит Т1 -  копию дерева Т.
8. Описать процедуру ЕQUAL(T1,T2), проверяющую на равенство деревья Т1 и Т2 (деревья равны, если ключи и записи вершин одного дерева равны соответственно ключам и записям  другого дерева).
9. Описать процедуру или функцию, которая:
      a) печатает узлы непустого дерева при обходе слева направо;
      b) удаляет все листья исходного дерева;
      c) печатает модифицированное дерево.
10. Описать процедуру, которая:
      a) присваивает переменной b типа char значение:
           К - если вершина - корень,
           П - если вершина - промежуточная вершина,
           Л - если вершина - лист;
      b) распечатывает атрибуты всех вершин дерева.
11. Описать процедуру или функцию, которая:
      а) вставляет узел с записью Е в дерево, если ранее такой не было;
      b) удалить ее, если она уже существует.
12. Описать процедуру или функцию, которая:
      а) печатает дерево, встречающееся в дереве один раз;
      b) печатает запись, встречающееся в дереве максимальное число раз.


 
В ремонтной мастерской находятся несколько (N) машин. О них имеются следующие сведения: номер, марка, имя владельца, дата последнего ремонта (число, месяц, год), день, к которому машина должна быть отремонтирована (число, месяц, год).
Требуется (согласно варианту) :
1.Расположить по алфавиту имена владельцев и, соответственно, вывести информацию об их машинах.
2.Исходя из того, что машина, дата окончания ремонта которой раньше, должна ремонтироваться в первую очередь, вывести порядок ремонта автомобилей.
3.Вывести по убыванию количество всех предыдущих ремонтов машин марки "Жигули".
4.Вывести по убыванию номера тех машин, количество предыдущих ремонтов которых равно 2.
5.Вывести по возрастанию даты конца ремонта всех машин, которые ранее не ремонтировались.
6.Вывести по алфавиту в обратном порядке владельцев автомобилей марки "Мерседес"
7.Вывести по алфавиту марки машин, которые должны быть отремонтированы раньше всех (дата конца ремонта меньше 01.08.96).
8.Вывести по возрастанию номера машин марки "Жигули".
9.Вывести по алфавиту имена владельцев, чьи машины не ремонтировались с прошлого года.
10.Вывести машины, которые надо отремонтировать к следующему месяцу по возрастанию даты их последнего ремонта.
11. Вывести по алфавиту в обратном порядке имена владельцев, количество предыдущих ремонтов машин которых больше трех.
12. Вывести по убыванию номера машин марки "Мерседес".
 

 


 
Создать  группу  из  N  студентов.  Ввести  их:  фамилия,  имя,  год рождения,  оценки  по  предметам: стр. и алг.данных, высш. математика, физика,   программирование,   общий  балл  сдачи  сессии;  Разработать программу   с  использованием  метода  "прямого  выбора",  которая  бы осуществляла сортировку (согласно варианту) :
 1. Фамилий студентов по алфавиту.
 2. Фамилий студентов по алфавиту в обратном порядке.
 3. Студентов по старшинству (начиная со старшего).
 4. Студентов по старшинству (начиная с младшего).
 5. Студентов по общему баллу (по возрастанию).
 6. Студентов по общему баллу (по убыванию).
 7. Студентов по результатам 1-го экзамена (по возрастанию).
 8. Студентов по результатам 2-го экзамена (по убыванию).
 9. Студентов по результатам 3-го экзамена (по возрастанию).
 10. Студентов по результатам 4-го экзамена (по убыванию).
 11. Имен в алфавитном порядке.
 12. Имен в обратном алфавитном порядке.


Варианты:
1. Составить программу вывода на экран самого большого  (самого малого) элемента массива А.
2. Составить программу сортировки массива А по убыванию величин его элементов.
3. В массиве А находятся элементы. Составить программу, которая сформирует массив В, в  котором расположить элементы масива В в порядке убывания.
4. Дан упорядоченный массив А - числа, расположенные в порядке возрастания, и число а, которое необходимо вставить в массив А, так,  чтобы упорядоченность массива сохранилась.
5. Составить программу для быстрой перестройки данного массива А, в котором элементы расположены в порядке возрастания, так, чтобы  после перестройки эти же элементы оказались расположенными в порядке убывания.
6. Дан массив А, содержащий как отрицательные, так и положительные числа. Составить программу исключения из него  всех отрицательных чисел, а оставшиеся положительные расположить в порядке их  возрастания.
7. Составить программу, которая будет из массива А брать одно число за другим и формировать  из  них массив В, располагая числа в порядке возрастания.
8. Дан список авторов в форме массива А. Составить программу формирования указателя авторов в алфавитном порядке и вывести его на экран.
9. Имеется n абонентов телефонной  станции. Составить программу, в которой формируется  список  по форме: номер телефона, фамилия (номера идут в порядке возрастания).
10. Имеется n слов  различной  длины, все  они занесены в массив А. Составить программу упорядочения слов по возрастанию их длин.
11. Составить программу для сортировки массива А по возрастанию и убыванию модулей его  элементов.
12. В  отсортированный  массив А между  каждой соседней парой элементов вставить число больше левого и меньше правого элемента в массиве и вывести полученный массив на экран.
 


 
Вариант 1: На заводе выпустили детали со следующими серийными номерами : 45, 56, 13, 75, 14, 18, 43, 11, 52, 12, 10, 36, 47, 9. Детали с четными номерами поступают на склад №1, а с нечетными на слад №2. Требуется отсортировать детали на складе №1.
Вариант 2 : Угнали автомобиль. Свидетель запомнил, что первой цифрой номера была 4. В базе угнанных автомобилей в этот день были следующие номера : 456, 124, 786, 435, 788, 444, 565, 127, 458, 322, 411, 531, 400, 546, 410. Нужно составить список номеров начинающихся на 4 и упорядочить его по возрастанию.
Вариант 3 : За неделю езды в транспорте накопились билеты с номерами  124512, 342351, 765891, 453122, 431350, 876432, 734626, 238651, 455734, 234987.  Нужно отобрать "счастливые" билеты и расположить их по возрастанию.
Вариант 4 : Дан список людей с указанием их возраста. Для составления графика ухода сотрудников на пенсию требуется составить новый список новый список в том порядке, в каком они будут уходить на пенсию.
Вариант 5 : Студенты сдали пять экзаменов. Нужно отсортировать список студентов по возрастанию общего балла по результатам сданных экзаменов.
Вариант 6 :  В городе был один автобусный парк, куда приезжали автобусы с номерами : 11, 32, 23, 12, 6, 52, 47, 63, 69, 50, 43, 28, 35, 33, 42, 56, 55, 101. После строительства второго автопарка решили перевести туда автобусы с нечетными номерами. Для того чтобы составить расписание их движения нужно организовать список номеров автобусов второго парка, упорядочив их по убыванию.
Вариант 7 : Была составлена ведомость по зарплате, представленная в виде : Иванов - 166000, Сидоров - 180000, ... Требуется упорядочить этот список таким образом, чтобы размер зарплаты уменьшался.
Вариант 8 : На стоянке стоят автомобили со следующими номерами : 1212, 3451, 7694, 4512, 4352, 8732, 7326, 2350, 4536, 2387, 5746, 6776, 4316, 1324. Для статистики необходимо составить список автомобилей с такими номерами, сумма первых двух цифр которых равна сумме двух последних цифр, так чтобы каждый следующий номер был меньше предыдущего.


Варианты:
1.Найти наименьший элемент в массиве А с помощью линейного поиска.
2.Поиск элементов в массиве А, которые больше 30.
3.Вывести на экран все числа массива А кратные 3 (3,6,9,...) с помощью линейного поиска.
4.Найти все элементы, модуль которых больше 20 и меньше 50, с помощью линейного поиска.
5.Вывести на экран все числа массива А кратные 4 (4,8,...) с помощью линейного поиска.
6.Вывести на экран сообщение, каких чисел больше относительно 50, с помощью линейного поиска.
7.Найти элемент в массиве А и найти число сравнений с помощью линейного поиска.
8.Поиск элементов случайным образом с помощью бинарного поиска.
9.Дан список номеров машин (345, 368, 876, 945, 564, 387, 230), найти, на каком месте стоит машина с заданным номером, бинарный поиск.
10.Поиск каждого второго элемента в списке и число сравнений.
11.Найти элемент с заданным ключом с помощью бинарного поиска.


Дан массив целых чисел. Составить процедуры метода транспозиции и перестановки в начало. Решить заданную задачу и переставить найденный в задаче элемент обоими методами в начало списка.
ВАРИАНТ 1. Найти максимальный элемент массива.
ВАРИАНТ 2. Найти минимальный элемент массива.
ВАРИАНТ 3. Найти число, нацело делящееся на 11 ( если таких чисел несколько, то найти максимальное; если таких чисел нет - выдать сообщение ).
ВАРИАНТ 4. Найти число, нацело делящееся на 11 ( если таких чисел несколько, то найти максимальное; если таких чисел нет - выдать сообщение ).
ВАРИАНТ 5. Найти элемент, разность соседних элементов которого не меньше 72. Если таких элементов несколько, выбрать максимальный. Если таких элементов нет, выдать сообщение.
ВАРИАНТ 6. Найти элемент, частное соседних элементов которого четное число. Если таких элементов несколько, выбрать максимальный или минимальный элемент. Если таких элементов нет, выдать сообщение.
ВАРИАНТ 7. Найти элемент, разность соседних элементов которого четное число. Если таких элементов несколько, выбрать максимальный или минимальный элемент. Если такого элемента нет, выдать сообщение.
ВАРИАНТ 8. Найти элемент, среднее арифметическое элементов, находящихся до этого элемента равно 12. Если таких элементов нет, выдать сообщение.
ВАРИАНТ 9. Найти максимальный элемент, делящийся на 10. Если такого элемента нет, выдать сообщение.
ВАРИАНТ 10. Найти элемент, разность соседних элементов которого четное число и делится на 3. Если такого элемента нет, выдать сообщение.
ВАРИАНТ 11. Найти элемент, среднее квадратичное элементов, находящихся после этого элемента меньше 10. Если таких элементов несколько, выбрать максимальный элемент. Если таких элементов нет, выдать сообщение.
ВАРИАНТ 12. Найти значение tg (x) от каждого элемента и переставить на 1 место элемент, значение функции от которого максимально.
 


Используя  генератор  случайных  чисел  сформировать бинарное дерево, состоящее из  5 элементов  (предусмотреть ручной ввод элементов).  Причем числа должны лежать в диапазоне от -99 до 99. Произвести поиск с вставкой    элементов в соответствии со следующими вариантами заданий:                
1. Числа кратные N.                                                    
2. Нечетные числа.                                                       
3. Числа > N.                                                           
4. Простые числа.                                                       
5. Числа по выбору.                                                     
6. Случайное число.                                                     
7. Составные числа.                                                     
8. Числа в интервале от X до Y.                                         
9. Числа, сумма цифр (по модулю) которого > N.                          
10. Числа, сумма цифр (по модулю) которого < N.                         
11. Числа, сумма цифр (по модулю) которого лежит в интервале от X до Y. 
 12. Числа, взятые по модулю, квадратный корень которых целое число.      
 где: N, X, Y  - задается преподавателем.


Используя  генератор  случайных  чисел  сформировать бинарное дерево, состояшее из 15 элементов  (предусмотреть ручной ввод элементов).  Причем числа должны лежать в диапазоне от -99 до 99. Произвести поиск с удалением  элементов в соответствии со следую-щими вариантами заданий:
1. Числа кратные N.
2. Нечетные числа.
3. Числа > N.
4. Числа < N.
5. Числа по выбору.
6. Простые числа.
7. Составные числа.
8. Числа в интервале от X до Y.
9. Числа, сумма цифр (по модулю) которого > N.
10. Числа, сумма цифр (по модулю) которого < N.
11. Числа, сумма цифр (по модулю) которого лежит в интервале от X до Y.
12. Числа, взятые по модулю, квадратный корень которых целое число.
где: N, X, Y  - задается преподавателем.

Содержание раздела