МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
УПРАВЛЕНИЕ ОБРАЗОВАНИЯ
МОГИЛЕВСКОГО ОБЛАСТНОГО ИСПОЛНИТЕЛЬНОГО КОМИТЕТА
УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ
«МОГИЛЕВСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ»
УТВЕРЖДАЮ
Директор колледжа
_________ С.Н.Козлов
___________________
СТРУКТУРЫ И АЛГОРИТМЫ
ОБРАБОТКИ ДАННЫХ
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
ПО ИЗУЧЕНИЮ УЧЕБНОЙ ДИСЦИПЛИНЫ,
ЗАДАНИЯ НА ДОМАШНЮЮ КОНТРОЛЬНУЮ РАБОТУ
ДЛЯ УЧАЩИХСЯ ЗАОЧНОЙ ФОРМЫ ОБУЧЕНИЯ
ПО СПЕЦИАЛЬНОСТИ 2-40 01 01
“ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ”
2016
2
Автор: Вайнилович Ю.В., Атрощенко И.С., преподаватели учреждения образования «Могилевский государственный политехнический
колледж»
Рецензент: Сенькевич Е.А., преподаватель учреждения образования «Могилевский государственный политехнический колледж»
Разработано на основе типовой учебной программы по учебной
дисциплине «Структуры и алгоритмы обработки данных», утвержденной Министерством образования Республики Беларусь, 23.05.2016.
Обсуждено и одобрено
на заседании цикловой комиссии
спецдисциплин специальности
«Программное обеспечение
информационных технологий»
Протокол № ______ от _______________
Согласовано с цикловой комиссией
стандартизации
Протокол № ______ от _______________
3
Пояснительная записка
Целью изучения учебной дисциплины «Структуры и алгоритмы
обработки данных» является изучение применяемых в программировании (и информатике) структур данных, их спецификации и реализации,
алгоритмов обработки данных и анализа этих алгоритмов, взаимосвязь
алгоритмов и структур данных.
Задачами учебной дисциплины являются:
формирование базовых теоретических понятий, лежащих в основе процесса разработки алгоритмов и структур данных;
формирование представлений и знаний об основных классах,
используемых в них структурах данных и общих схемах решения задач
на их основе;
знакомство с типовыми алгоритмами, принципами и методами
построения программ;
формирование основ конструирования и использования сложных (динамических) структур данных на базе модели абстрактного типа
данных (спецификация+представление+реализация);
приобретение навыков программирования типовых алгоритмов,
структур данных и их модификаций на языке высокого уровня;
развитие у учащихся алгоритмического мышления, умений проектировать структуры данных на основе анализа условия задачи, выделять стандартные алгоритмы, обобщать, делать выводы;
развитие навыков исследовательской работы при решении нестандартных задач и умения работать в команде;
воспитание логической последовательности суждений при анализе условий задач.
В результате изучения учащийся должен знать:
– базовые структуры данных, их достоинства, недостатки и основные сферы использования;
– определения, свойства и классификацию абстрактных типов
данных;
– основные алгоритмы обработки данных, такие как поиск, сортировка и пр., характеристики их сложности;
– способы реализации структур данных, таких как хеш-таблицы,
бинарные деревья, связные списки и пр.;
учащийся должен уметь:
– проводить сравнительный анализ различных структур данных;
4
– обоснованно проектировать структуры данных в создаваемых
приложениях;
– осознанно выбирать правильную структуру данных и алгоритм
обработки, наиболее эффективные для решения конкретной задачи и
аргументировано обосновать свой выбор;
– проектировать и реализовывать структуры данных для конкретной задачи как суперпозицию базовых структур данных, если это требуется сутью решаемой задачи;
– реализовывать основные алгоритмы обработки данных на одном
из языков высокого уровня.
Материал учебной дисциплины опирается на отдельные темы
учебных дисциплин «Математика», «Основы алгоритмизации и программирования».
Знания и умения, полученные при изучении учебной дисциплины,
являются необходимыми для усвоения учебного программного материала учебной дисциплины «Конструирование программ и языки программирования».
5
Общие методические рекомендации по выполнению домашней
контрольной работы
Учащиеся заочного отделения выполняют одну домашнюю контрольную работу. Домашняя контрольная работа ставит своей задачей
проверить, как учащийся усвоил материал изучаемой учебной дисциплине.
Номера задач выбираются в соответствии с двумя последними
цифрами шифра учащегося, на пересечении соответствующей строки с
соответствующим столбцом из таблицы 1.
Каждый вариант состоит из четырех заданий.
Первым и вторым заданиями являются теоретические вопросы, на
которые нужно дать развернутый ответ, сопровождаемый рисунками,
схемами. Привести примеры. Объем – около четырех страниц.
Остальные два задания – практические задания, в которых нужно
составить программу на языке высокого уровня Паскаль.
Перед выполнением задания рекомендуется ознакомиться с методическими рекомендациями по выполнению домашней контрольной
работы и соответствующими тематическими разделами в рекомендуемой литературе.
При оформлении домашней контрольной работы следует придерживаться следующих требований:
- работа выполняется на листах А4 машинописным способом
(шрифт 12-14, межстрочный интервал - одинарный). Следует пронумеровать страницы и оставить на них поля: справа – не менее 3 см
для замечаний преподавателя, остальные поля – 2,5 см;
- на титульном листе указываются: учебная дисциплина и номер
работы, номер группы, шифр, группа, фамилия, имя, отчество учащегося;
- ответ на теоретический вопрос следует начинать с номера и полного названия вопроса;
- каждую задачу следует начинать с новой страницы;
- решение задач желательно располагать в порядке номеров, указанных в задании;
- перед решением задачи указать ее номер и условие;
- для каждой задачи привести распечатку листинга программного
кода и результатов работы программы (скриншоты).
Требования к оформлению исходного текста программы:
структурирование текста программы (отступы, разделители, заголовки, пустые строки и т.д.);
6
программа должна быть снабжена комментариями для пояснения ее работы, интерфейса процедур и логики работы. Комментарии не
должны (!) сопровождать каждую строку, а выделять блоки программы,
процедуры и их параметры.
К пояснительной записке прикладывается диск, на котором для
каждой задачи записаны исходные и исполняемые файлы программы.
Имена файлам даются по номеру задачи.
7
Критерии оценки домашней контрольной работы
Домашняя контрольная работа признается преподавателем удовлетворительной и оценивается словом «зачтено» если:
выполнено минимум одно практическое задание верно, а в другом имеются незначительные недочеты;
содержание теоретического вопроса соответствует теме;
при изложении теоретического вопроса соблюдена логика изложения и терминологическая четкость;
соблюдены требования к оформлению домашней контрольной
работы.
Домашняя контрольная работа не может быть зачтена, если в ней
поверхностно раскрыт вопрос, допущены принципиальные ошибки, а
также при условии механически переписанного материала из учебников
или другой литературы.
Также работа не зачтена, если выполнена не по варианту, не
выполнено или есть существенные ошибки, приводящие к неверному
результату хотя бы в одном практическом задании.
8
Программа учебной дисциплины
Введение
Основные понятия структур данных. Классификация структур
данных
Основные операции над структурами данных: формирование; просмотр; вставка (включение); добавление (дополнение); извлечение; удаление (исключение); сдвиг; изменение содержимого элемента; сортировка
Элементарные данные: числовые типы; символьный тип; логический тип; тип указатель
Анализ сложности и эффективности алгоритмов и структур данных
Литература: [6], с. 346-362; [9], c.11-28
Раздел 1 Алгоритмы поиска и сортировки
Тема 1.1 Массивы. Поиск элемента в массиве
Массивы: одномерные и двумерные, статические и динамические
Постановка задачи поиска элемента в массиве. Последовательный
поиск. Двоичный поиск
Литература: [6], c. 220-234
Тема 1.2 Алгоритмы внутренней сортировки
Постановка задачи сортировки массива
Простые алгоритмы сортировки: обменная сортировка, сортировка
вставками, сортировка выбором
Быстрые алгоритмы сортировки: быстрая сортировка, пирамидальная сортировка, карманная сортировка
Сравнение методов сортировки
Литература: [6], c. 234-271
Тема 1.3 Алгоритмы внешней сортировки
Особенности задачи сортировки файлов
Алгоритмы внешней сортировки: метод прямого слияния, метод
естественного слияния
Литература: [4], c. 72-75
9
Вопросы для самоконтроля
1 Что такое массив?
2 Как реализуется алгоритм сортировки массива обменом?
3 Как реализуется алгоритм сортировки массива вставками?
4 Как реализуется алгоритм сортировки массива методом выбора?
5 Как реализуется алгоритм сортировки массива методом прямого
слияния?
6 Почему в программах размер памяти под статические переменные должен быть определен на этапе компиляции?
7 За счет каких ресурсов выделяется память под динамические
структуры?
8 Как располагаются в памяти динамические величины?
9 Как осуществляется доступ к динамическим структурам из программного кода?
10 Как связываются между собой элементы динамической структуры?
11 Какого типа может быть поле данных в динамической структуре?
12 Почему для обращения к динамической структуре достаточно
хранить в памяти адрес ее первого элемента?
Раздел 2 Линейные структуры данных
Тема 2.1 Линейные списки
Линейные списки. Линейный однонаправленный список. Реализация списка в виде массива и динамических указателей. Операции с однонаправленным списком: вставка, удаление, поиск элемента, формирование и просмотр списка
Линейный двунаправленный список. Операции с двунаправленным списком: вставка, удаление, поиск элемента, формирование и просмотр списка
Кольцевой однонаправленный список. Кольцевой двунаправленный список. Особенности выполнения операции с кольцевыми списками
Литература: [6], c. 348-354; [9], c. 89-143
Тема 2.2 Стеки
Стек. Реализация стека в виде массива и динамических указателей
10
Операции со стеком: включение, исключение элемента. Алгоритмы поиска элемента, формирования и просмотра стека
Формы записи арифметических выражений: инфиксная, постфиксная, префиксная. Использование стека для вычисления арифметических выражений
Литература: [6], c. 362-372; [9], c. 89-143
Тема 2.3 Очереди
Очередь. Реализация очереди в виде массива и динамических указателей
Операции с очередью: включение, исключение элемента. Алгоритмы поиска элемента, формирования и просмотра очереди
Литература: [6], c. 372-383; [9], c. 89-143
Вопросы для самоконтроля
1 Какую структур данных называют списком?
2 В чем отличие первого элемента однонаправленного (двунаправленного) списка от остальных элементов этого же списка?
3 В чем отличие последнего элемента однонаправленного (двунаправленного) списка
от остальных элементов этого же списка?
4 Почему при работе с однонаправленным списком необходимо
позиционирование на первый элемент списка?
5 Почему при работе с двунаправленным списком не обязательно
позиционирование на первый элемент списка?
6 В чем принципиальные отличия выполнения добавления (удаления) элемента на первую и любую другую позиции в однонаправленном списке?
7 В чем принципиальные отличия выполнения основных операций
в однонаправленных и двунаправленных списках?
8 С какой целью в программах выполняется проверка на пустоту
однонаправленного (двунаправленного) списка?
9 С какой целью в программах выполняется удаление однонаправленного (двунаправленного) списка по окончании работы с ним?
Как изменится работа программы, если операцию удаления списка не
выполнять?
10 Какую структуру данных называют стеком?
11 На базе каких структур может быть организован стек?
11
12 В чем преимущества и недостатки организации структур в виде
стека?
13 В чем преимущества и недостатки организации структур в виде
очереди?
14 Для моделирования каких реальных задач удобно использовать
стек? А для каких очередь?
15 Какое значение хранит указатель на стек?
16 Какое значение хранит указатель на очередь?
17 Какие существуют ограничения на тип информационного поля
стеки и очереди?
18 С какой целью в программах выполняется проверка на пустоту
стека и очереди?
19 При работе со стеком или очередью доступны позиции ограниченного числа элементов. Возможна ли ситуация записи новых элементов стека или очереди на уже занятые собственными элементами участки памяти (запись себя поверх себя)? Ответ обоснуйте.
20 С какой целью в программах выполняется удаление стека и
очереди по окончании работы с ними? Как изменится работа программы, если операцию удаления не выполнять?
21 Какую структуру данных называют очередью?
Раздел 3 Множества и графы
Тема 3.1 Множества
Множество. Математическое определение множества
Операции над множествами: объединение, пересечение, разность
множеств, проверка равенства множеств, очистка множества, проверка
принадлежности элемента, включение элемента, исключение элемента,
поиск минимального и максимального элемента
Реализация с помощью двоичных векторов, связанного списка
Литература: [6], c. 234-242
Тема 3.2 Граф. Обходы графа
Граф: основные понятия и терминология
Реализация с помощью матриц и списков смежности
Обходы графа: поиск в глубину, поиск в ширину
Литература: [1], c. 436-453; [6], c. 385-392
12
Тема 3.3 Поиск кратчайших путей в графе
Постановка задачи о кратчайших путях между парой вершин и
всеми вершинами в орграфе. Алгоритмы Дейкстры, Флойда
Литература: [1], c. 479-523; [4], c. 124-136; [7], c. 161-166
Тема 3.4 Поиск минимального остовного дерева графа
Постановка задачи поиска минимального остовном дерева графа
Жадные алгоритмы. Алгоритмы Прима и Крускала
Литература: [5], c. 250-259; [7], c. 144-150
Тема 3.5 Максимальный поток в сети
Постановка задачи о максимальном потоке
Алгоритм Форда - Фалкерсона нахождения максимального потока
Поиск минимального разреза
Литература: [1], c. 535-552; [7], c.186-195
Вопросы для самоконтроля
1 Дайте определение графа и его основным компонентам.
2 Дайте определение матрице смежности. Как формируется матрица? Примеры
3 Дайте определение матрице инцидентности. Как формируется
матрица? Примеры
4 Дайте определение матрице расстояний. Как формируется матрица? Примеры
5 С какими видами графов работают алгоритмы Дейкстры,
Флойда и переборные алгоритмы?
6 Как от представления графа зависит эффективность алгоритма
его обхода?
7 За счет чего поиск в ширину является достаточно ресурсоемким алгоритмом?
8 В чем преимущества алгоритмов обхода графа в ширину?
Раздел 4 Организация поиска
Тема 4.1 Деревья. Бинарные деревья. Обходы деревьев
Деревья: основные определения
13
Обходы деревьев: прямой обратный, симметричный
Бинарные деревья. Особенности их обходов. Реализация бинарных
деревьев с помощью массива родителей, с помощью списков сыновей, с
помощью указателей
Деревья выражений
Литература: [6], c. 397-411; [9], c. 149-197
Тема 4.2 Бинарные поисковые деревья
Бинарные поисковые деревья
Операции над бинарными поисковыми деревьями: поиск элемента, добавление элемента, удаление элемента
Литература: [2], c. 386-401; [6], c. 397-411; [9], c. 149-197
Тема 4.3 Сбалансированные деревья
Сбалансированные деревья: преимущества и недостатки
АВЛ-деревья: определение, методы балансировки. Операции с
АВЛ-деревьями: поиск, добавление и удаление элемента
Красно-черные деревья: определение, методы балансировки. Операции с красно-черными деревьями: поиск, добавление и удаление элемента
Литература: [1], c. 254-271; [6], c. 413-427
Тема 4.4 Структуры данных, основанные на хеш-таблицах.
Открытое хеширование
Хеширование и хеш-таблицы. Функции хеширования
Открытое хеширование. Операции добавления, удаления и поиска
элемента
Литература: [4], c. 90-95; [8], c. 567-597
Тема 4.5 Закрытое хеширование. Методы разрешения коллизий хеширования
Закрытое хеширование. Операции добавления, удаления и поиска
элемента
Методы разрешения коллизий хеширования
Реструктуризация открытых и закрытых хеш-таблиц
Литература: [4], c.90-95; [8], c. 567-597
14
Вопросы для самоконтроля
1 Что такое дерево?
2 Какую роль выполняет корень дерева?
3 Какую роль играет понятие поддерева по отношению к дереву?
4 Что такое путь на дереве? Глубина дерева?
5 Как можно классифицировать деревья?
6 Что представляют из себя бинарные деревья?
7 Что такое вырожденное дерево?
8 Что такое полное дерево?
9 Какие операции считаются основными для бинарного дерева?
10 Из каких базовых действий строится алгоритм обхода дерева?
11 Чем отличаются друг от друга прямой, обратный и симметричный обходы дерева?
12 Что такое свойство упорядоченности?
13 Как осуществляется программная реализация бинарного дерева?
14 Что должен содержать узел бинарного дерева?
15 Какие операции над узлами дерева можно отнести к основным?
16 На основании чего в красно-черном дереве самая длинная ветвь
от корня к листу не более чем вдвое длиннее любой другой ветви от
корня к листу?
17 Куда может быть добавлен элемент в красно-черное дерево?
Вид дерева при этом должен сохраниться.
18 Каким образом при удалении элемента из красно-черного дерева перекрашиваются узлы?
19 Каков принцип построения хеш-таблиц?
20 Существуют ли универсальные методы построения хештаблиц? Ответ обоснуйте.
21 Почему возможно возникновение коллизий?
22 Каковы методы устранения коллизий? Охарактеризуйте их эффективность в различных ситуациях.
23 Назовите преимущества открытого и закрытого хеширования.
24 В каком случае поиск в хеш-таблицах становится неэффективен?
25 Как выбирается метод изменения адреса при повторном хешировании?
26 В чем заключается суть каждого метода для разрешения коллизии?
15
Список используемых источников
1 Алгоритмы: построение и анализ / пер. с англ. под ред. А. Шейя.
– М.:МЦНМО, 2002. – 960 с.
2 Кнут, Д. Искусство программирования. Т.1 / Д. Кнут. – М.: Вильямс, 2001. - 976 с.
3 Кнут, Д. Искусство программирования. Т.2 / Д. Кнут. – М.: Вильям, 2001. - 988 с.
4 Красиков, И. В. Алгоритмы. Просто, как дважды два / И. В. Красиков, И. Е. Красикова. – М.:Эксмо, 2007. – 256 с.
5 Макконнелл, Дж. Основы современных алгоритмов / Дж. Макконнелл. – М: Техносфера, 2004. – 368 с.
6 Окулов, С. М. Основы программирования / С. М. Окулов. – М.:
БИНОМ. Лаборатория знаний, 2008. – 341 с.
7 Окулов, С. М. Программирование в алгоритмах / С. М. Окулов.
– М.: БИНОМ. Лаборатория знаний, 2002. – 341 с.
8 Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/ Сортировка/Поиск / пер. с англ. / Роберт Седжвик. – К: Издательство «ДиаСофт», 2001. – 688 с.
9 Хусаинов, Б. С. Структуры и алгоритмы обработки данных.
Примеры на языке Си: учеб. пособие / Б. С. Хусаинов. – М.:Финансы и
статистика, 2004. – 464 с.
16
Задания на домашнюю контрольную работу по учебной
дисциплине «Структуры и алгоритмы обработки данных»
Теоретические вопросы
1 Опишите одномерные и двумерные массивы. Опишите основные
понятия и операции.
2 Опишите обменную сортировку массива: описание алгоритма и
поясняющие примеры.
3 Опишите сортировку массива вставками: описание алгоритма и
поясняющие примеры.
4 Опишите сортировку массива выбором: описание алгоритма и
поясняющие примеры.
5 Опишите быструю сортировку массива: описание алгоритма и
поясняющие примеры.
6 Опишите пирамидальную сортировку массива: описание алгоритма и поясняющие примеры.
7 Опишите карманную сортировку массива: описание алгоритма и
поясняющие примеры.
8 Опишите алгоритмы внешней сортировки: метод прямого слияния, метод естественного слияния.
9 Дайте понятие термину «структура данных». Классификация
структур данных.
10 Опишите статические и динамические структуры данных.
11 Дайте определение указателя. Опишите базовые операции с
указателями в языке Паскаль.
12 Опишите структуру данных «стек»: определение, основные
операции – создание, добавление элемента, удаление элемента. Опишите алгоритм преобразования выражения в обратную польскую запись.
13 Опишите структуру данных «односвязный список»: определение, основные операции – создание, добавление элемента, удаление
элемента.
14 Опишите структуру данных «двусвязные список»: определение,
основные операции – создание, добавление элемента, удаление элемента.
15 Опишите структуру данных «очередь»: определение, основные
операции – создание, добавление элемента, удаление элемента.
16 Опишите структуру данных «кольцо»: определение, основные
операции – создание, добавление элемента, удаление элемента.
17
17 Опишите структуру данных «бинарное дерево»: определение,
основные операции над бинарным деревом – создание, добавление элемента, удаление элемента.
18 Опишите алгоритмы поиска по ключу и полного обхода в бинарном дереве.
19 Опишите структуру данных «красно-черное бинарное дерево»:
определение, основные свойства, создание, размещение очередного
элемента.
20 Дайте определение множества. Опешите математическое определение множества.
21 Дайте определение операции над множествами: объединение,
пересечение, разность множеств, проверка равенства множеств, очистка
множества, проверка принадлежности элемента, включение элемента,
исключение элемента, поиск минимального и максимального элемента.
22 Дайте определение понятию графа. Опишите основные свойства графов.
23 Опишите способы представления графов в памяти компьютера.
24 Опишите вычислительную схему алгоритма поиска в глубину
на графе.
25 Опишите вычислительную схему алгоритма поиска в ширину
на графе.
26 Опишите вычислительную схему алгоритма поиска кратчайшего пути между двумя вершинами на графе.
27 Опишите понятие «сеть». Дайте определение понятию максимального потока на сети.
28 Опишите алгоритм нахождения максимального потока методом
Форда-Фанкерсона.
29 Опишите алгоритм нахождения потока минимальной стоимости.
30 Опишите принципы работы алгоритма жадного выбора.
31 Опишите применение жадного алгоритма в задаче о поиске
кратчайшего пути между двумя вершинами графа.
32 Опишите применение жадного алгоритма в задаче о ранце.
33 Опишите применение жадного алгоритма в задаче о сумме элементов подмножества.
34 Опишите вычислительную схему алгоритма Хоффмана.
35 Опишите основные определения, связанные с темой «Деревья».
36 Опишите обходы деревьев: прямой обратный, симметричный.
37 Опишите основные определения, связанные с темой «Бинарные
деревья». Расскажите про особенности их обходов.
18
38 Опишите основные определения, связанные с темой «Бинарные
поисковые деревья». Опишите операции над бинарными поисковыми
деревьями.
39 Опишите основные определения, связанные с темой «Сбалансированные деревья». Расскажите про преимущества и недостатки.
40 Дайте определение хеш-функции и хеш-таблицы.
41 Опишите методы хеширования: метод деления, метод середины
квадратов, метод свертывания.
42 Расскажите про коллизии при хешировании. Опишите методы
разрешения коллизий.
Практические задания
1 Задания 43-54. Дан одномерный массив целых чисел. Реализуйте алгоритм сортировки указанным методом.
43 Реализуйте алгоритм сортировки массива методом простого
выбора по возрастанию.
44 Отсортируйте методом простого обмена элементы, стоящие на
нечетных местах по убыванию.
45 Реализуйте алгоритм сортировки массива методом вставок по
возрастанию.
46 Отсортируйте четные элементы массива методом простого выбора по убыванию.
47 Реализуйте алгоритм сортировки массива методом простого
обмена по возрастанию.
48 Отсортируйте методом простого выбора элементы, стоящие на
нечетных местах по убыванию.
49 Реализуйте алгоритм сортировки массива методом вставок по
убыванию.
50 Отсортируйте отрицательные элементы массива методом простого выбора по возрастанию.
51 Реализуйте алгоритм сортировки массива методом простого
выбора по убыванию.
52 Отсортируйте методом вставок элементы, стоящие на нечетных
местах по возрастанию.
53 Реализуйте алгоритм сортировки массива методом простого
обмена по убыванию.
54 Отсортируйте четные элементы массива методом простого выбора по возрастанию.
19
2 Задания 55-81. Условие вида «дана матрица размера М х М
означает, что вначале дается фактический размер двумерного массиваматрицы (количество строк М и количество столбцов N), а затем приводятся элементы этого массива (количество элементов равно M*N).
Если в задании явно не указывается, какие значения могут принимать
размеры исходной матрицы, то предполагается, что и число строк, и
число столбцов может меняться в пределах от 2 до 10. Порядковые номера начальной строки и начального столбца матрицы считаются равными 1.
Ввод и вывод элементов матрицы осуществляются по строкам.
Организуйте ввод матрицы как с клавиатуры, так и из файла.
Используя алгоритм полного перебора решите поставленную задачу.
55 Дана целочисленная матрица размера M х N. Найдите номер
первой из ее строк, содержащих равное количество положительных и
отрицательных элементов (нулевые элементы матрицы не учитываются). Если таких строк нет, то вывести 0.
56 Дана целочисленная матрица размера M х N. Найдите номер
последнего из ее столбцов, содержащих равное количество положительных и отрицательных элементов (нулевые элементы матрицы не
учитываются). Если таких столбцов нет, то вывести 0.
57 Дана целочисленная матрица размера М х N. Найдите номер
последней из ее строк, содержащих только четные числа. Если таких
строк нет, то вывести 0.
58 Дана целочисленная матрица размера М х N. Найдите номер
первого из ее столбцов, содержащих только нечетные числа. Если таких
столбцов нет, то вывести 0.
59 Дана целочисленная матрица размера М х N, элементы которой
могут принимать значения от 0 до 100. Различные строки матрицы
назовем похожими, если совпадают множества чисел, встречающихся в
этих строках. Найдите количество строк, похожих на первую строку
данной матрицы.
60 Дана целочисленная матрица размера М х N, элементы которой
могут принимать значения от 0 до 100. Различные столбцы матрицы
назовем похожими, если совпадают множества чисел, встречающихся в
этих столбцах. Найдите количество столбцов, похожих на последний
столбец данной матрицы.
61 Дана целочисленная матрица размера M х N. Найдите количество ее строк, все элементы которых различны.
20
62 Дана целочисленная матрица размера M х N. Найдите количество ее столбцов, все элементы которых различны.
63 Дана целочисленная матрица размера M х N. Найдите номер
последней из ее строк, содержащих максимальное количество одинаковых элементов.
64 Дана целочисленная матрица размера M х N. Найдите номер
первого из ее столбцов, содержащих максимальное количество одинаковых элементов.
65 Дана матрица размера M х N. Найдите количество ее строк,
элементы которых упорядочены по возрастанию.
66 Дана матрица размера M х N. Найдите количество ее столбцов,
элементы которых упорядочены по убыванию.
67 Дана матрица размера M х N. Найдите минимальный среди
элементов тех строк, которые упорядочены либо по возрастанию, либо
по убыванию. Если упорядоченные строки в матрице отсутствуют, то
вывести 0.
68 Дана матрица размера М х N. Найдите максимальный среди
элементов тех столбцов, которые упорядочены либо по возрастанию,
либо по убыванию. Если упорядоченные столбцы в матрице отсутствуют, то вывести 0.
69 Дана целочисленная матрица размера M х N. Найдите элемент,
являющийся максимальным в своей строке и минимальным в своем
столбце. Если такой элемент отсутствует, то вывести 0.
70 Дана матрица размера M х N. В каждой строке матрицы найдите минимальный элемент и максимальный элемент среди этих минимальных.
71 Дана матрица размера M х N. В каждом столбце матрицы
найдите максимальный элемент и минимальный среди этих максимальных.
72 Дана матрица размера M х N. Найдите номер ее строки с
наибольшей суммой элементов и вывести данный номер, а также значение наибольшей суммы. Среди этих наибольших сумм найдите
наименьшую.
73 Дана матрица размера M х N. Найдите номер ее столбца с
наименьшим произведением элементов и вывести данный номер, а также значение наименьшего произведения.
74 Дана матрица размера M х N. Найдите максимальный среди
минимальных элементов ее строк.
75 Дана матрица размера M х N. Найдите минимальный среди
максимальных элементов ее столбцов.
21
76 Дана матрица размера M х N. В каждой ее строке найдите количество элементов, меньших среднего арифметического всех элементов этой строки.
77 Дана матрица размера M х N. В каждом ее столбце найдите количество элементов, больших среднего арифметического всех элементов этого столбца.
78 Дана целочисленная матрица размера M х N. Найдите номер
последней из ее строк, содержащих равное количество положительных
и отрицательных элементов (нулевые элементы матрицы не учитываются). Если таких строк нет, то вывести 0.
79 Дана целочисленная матрица размера M х N. Найдите номер
первого из ее столбцов, содержащих равное количество положительных
и отрицательных элементов (нулевые элементы матрицы не учитываются). Если таких столбцов нет, то вывести 0.
80 Дана матрица размера M х N. Найдите максимальный среди
элементов тех строк, которые упорядочены либо по возрастанию, либо
по убыванию. Если упорядоченные строки в матрице отсутствуют, то
вывести 0.
81 Дана матрица размера М х N. Найдите минимальный среди
элементов тех столбцов, которые упорядочены либо по возрастанию,
либо по убыванию. Если упорядоченные столбцы в матрице отсутствуют, то вывести 0.
3 Задания 82-114. В задачах требуется обработать заданную динамическую структуру данных. Элементы исходной структуры данных
вводятся с клавиатуры. Результат выводится на экран.
82 Информационное поле элемента стека - числовое. Разбейте стек
на два стека - из положительных и отрицательных элементов.
83 Задан массив чисел. Скопируте элементы массива в информационное поле элементов стека.
84 Информационное поле элемента стека - числовое. Найдите
максимальный элемент стека и поменять его местами с первым элементом стека.
85 Информационное поле элемента стека - числовое. Найдите минимальный и максимальный элементы стека и поменять их местами.
86 Выбросить из стека повторяющиеся элементы, идущие подряд.
87 Информационное поле элемента стека - числовое. Выбросите
из стека отрицательные числа, идущие подряд.
22
88 Информационное поле элемента стека - числовое. Вычислите
среднее арифметическое элементов стека и выбросите из стека элементы, превышающие среднее арифметическое.
89 Информационное поле элемента стека - числовое. Удалите из
стека нулевые элементы.
90 Подсчитайте количество элементов списка, у которых "соседи"
равны между собой.
91 Информационное поле элемента списка - числовое. Подсчитайте и выведите на экран элементы списка не равные нулю.
92 Объедините два списка в один, присоединив хвост второго
списка к голове первого.
93 Объедините два списка в один, чередуя элементы первого и
второго списка.
94 Информационное поле элемента списка - числовое. Разбейте
список на два списка - из положительных и отрицательных элементов.
95 Информационное поле элемента списка - числовое. Найдите
максимальный элемент списка и поменять его местами с первым элементом списка.
96 Информационное поле элемента списка - числовое. Найдите
минимальный и максимальный элементы списка и поменять их местами.
97 Выбросите из списка повторяющиеся элементы, идущие подряд.
98 Информационное поле элемента списка - числовое. Выбросите
из списка отрицательные числа, идущие подряд.
99 Информационное поле элемента списка - числовое. Вычислите
среднее арифметическое элементов списка и выбросите из списка элементы, превышающие среднее арифметическое.
100 Информационное поле элемента списка - числовое. Удалите
из списка нулевые элементы.
101 Подсчитайте количество элементов очереди, у которых "соседи" равны между собой.
102 Информационное поле элемента очереди - числовое. Подсчитайте и выведите на экран элементы очереди, не равные нулю.
103 Информационное поле элемента очереди - числовое. Разбейте
очередь на две очереди - из положительных и отрицательных элементов.
104 Информационное поле элемента очереди - числовое. Найдите
максимальный элемент очереди и поменяйте его местами с первым
элементом очереди.
23
105 Информационное поле элемента очереди - числовое. Найдите
минимальный и максимальный элементы очереди и поменяйте их местами.
106 Выбросите из очереди повторяющиеся элементы, идущие
подряд.
107 Информационное поле элемента очереди - числовое. Выбросите из очереди отрицательные числа, идущие подряд.
108 Информационное поле элемента очереди - числовое. Вычислите среднее арифметическое элементов очереди и выбросите из очереди элементы, превышающие среднее арифметическое.
109 Информационное поле элемента очереди - числовое. Удалите
из очереди нулевые элементы.
110 Информационное поле двоичного упорядоченного дерева содержит целое число. Выведите на экран среднее арифметическое этих
чисел, а также наибольшее и наименьшее из них.
111 Информационное поле двоичного упорядоченного дерева содержит целое число. Удалите из дерева все узлы, информационное поле
которое превышает некоторое вводимое пользователем число.
112 Информационное поле двоичного упорядоченного дерева содержит целое число. Удалите из дерева нулевые элементы, а также подсчитайте их количество.
113 Информационное поле двоичного упорядоченного дерева содержит целое число. Выбросите из дерева повторяющиеся элементы.
114 Информационное поле двоичного упорядоченного дерева содержит целое число. Подсчитайте количество элементов, больших
среднего арифметического всех элементов дерева.
4 Задания 115-143. Во всех задачах под термином "граф" понимается: (а) "неориентированный граф"; (б) "ориентированный граф" (организовать выбор). Ввод должен осуществляться либо с клавиатуры,
либо из файла (организовать выбор пользователя).
115 Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей смежностей.
Указание. Найдите сумму чисел в строке матрицы смежности, соответствующей данной вершине.
116 Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей инцидентности.
24
117 Посчитайте количество ребер в графе, заданном матрицей
смежности вершин. Указание. Найдите сумму элементов, стоящих на и
выше главной диагонали матрицы смежности.
118 . Проверьте, есть ли в графе, заданном матрицей смежности
ребер, кратные ребра. Указание. Проверьте наличие в матрице смежности элементов >1. Если такие элементы есть, то номера этих элементов
соответствуют вершинам, имеющим кратные ребра.
119 Проверьте, имеет ли граф, заданный матрицей смежности
вершин, петли. Указание. Проверьте наличие на главной диагонали
матрицы смежности элементов, не равных 0.
120 Посчитайте количество кратных ребер в графе, заданном матрицей смежности вершин.
121 В графе, заданном матрицей смежности вершин, определите
количество петель.
122 Определите максимальную кратность ребер в графе, заданном
матрицей смежности вершин. Указание. Найдите максимальный элемент в матрице смежности.
123 Посчитайте число вершин в графе (граф задан матрицей
смежности вершин), от которых отходит более m ребер. Указание.
Найдите количество сумм строк в матрице смежности, больших m.
124 Напишите программу, определяющую существуют ли в графе, заданном матрицей смежности вершин, изолированные вершины?
Указание. Суммы строк в матрице смежности равны 0.
125 Определите, каково максимальное (минимальное) количество
ребер, выходящих от одной вершины в графе, заданном матрицей
смежности? Указание. Найдите максимум сумм строк в матрице смежности.
126 Напишите программу, определяющую среднее количество
ребер в графе, заданном матрицей смежности вершин? Указание. Среднее арифметическое элементов матрицы смежности.
127 Установите, является ли граф, заданный матрицей смежности
вершин, регулярным (в регулярном графе степень всех вершин одинакова)? Указание. Суммы в строках матрицы смежности одинаковы.
128 Установите, является ли граф, заданный матрицей смежности
вершин, полным (в полном графе любые две вершины смежны)? Указание. Все элементы матрицы смежности равны 1.
129 Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей инцидентности.
25
130 Посчитайте количество ребер в графе, заданном матрицей
инцидентности.
131 Проверьте, есть ли в графе, заданном матрицей инцидентности, кратные ребра.
132 Проверьте, имеет ли граф, заданный матрицей инцидентности, петли.
133 Посчитайте количество кратных ребер в графе, заданном матрицей инцидентности.
134 В графе, заданном матрицей инцидентности, определите количество петель.
135 Определите максимальную кратность ребер в графе, заданном
матрицей инцидентности.
136 Посчитайте число вершин в графе (граф задан матрицей инцидентности), от которых отходит более m ребер.
137 Определите, существуют ли в графе, заданном матрицей инцидентности, изолированные вершины?
138 Определите, каково максимальное (минимальное) количество
ребер, отходящих от одной вершины в графе, заданном матрицей инцидентности?
139 Определите, каково минимальное количество ребер, отходящих от одной вершины, в графе, заданном матрицей инцидентности?
140 Определите, является ли граф, заданный матрицей инцидентности, регулярным (в регулярном графе степень всех вершин одинакова)?
141 Определите, является ли граф, заданный матрицей инцидентности, полным (в полном графе любые две вершины смежны)?
142 Определите, является ли граф, заданный матрицей инцидентности, звездой (звезда - граф, у которого одна вершина соединена со
всеми, а у остальных степень равна 1)?
143 Определите, является ли граф, заданный матрицей инцидентности, кольцом (кольцо - связный граф, степень каждой вершины которого равна 2)?
26
Методические рекомендации по оформлению практического
задания
Найдите площадь фигуры ограниченной заданными функциями
методом правых прямоугольников. Заданные функции: f = sin x / x2,
x1 = 1, x2 = 3.
Описание метода
Разделим отрезок [a; b] на n равных частей, т.е. на n элементарных
отрезков. Длина каждого элементарного отрезка
. Точки деления
будут: x0=a; x1=a+h; x2=a+2× h, ... , xn-1=a+(n-1)× h; xn=b. Эти числа будем называть узлами. Вычислим значения функции f(x) в узлах, обозначим их y0, y1, y2, ... , yn. Cтало быть, y0=f(a), y1=f(x1), y2=f(x2), ... , yn=f(b).
Числа y0, y1,y2, ... , yn являются ординатами точек графика функции, соответствующих абсциссам x0, x1, x2, ... , xn (рисунок 1). Площадь криволинейной трапеции приближенно заменяется площадью многоугольника, составленного из n прямоугольников. Таким образом, вычисление
определенного интеграла сводится к нахождению суммы n элементарных прямоугольников.
Формула правых прямоугольников:
Рисунок 1 – Геометрическая интерпретация
Текст программы:
Program RP;
var x1,x2,h,S1,x,y:real;
begin
S1:=0;
27
x1:=1;
x2:=3;
h:=(x2-x1)/100;
x:=x1;
while x<x2 do
begin
y:=sin(x)/sqr(x);
S1:=S1+(y)*h;
x:=x+h;
end;
writeln(S1);
end.
Результаты работы программы представлены на рисунке 2.
Рисунок 2 – Результат работы программы
28
Таблица 1 – Варианты домашней контрольной работы по учебной дисциплине «Структуры и алгоритмы
обработки данных»
Предпоследняя цифра
шифра
0
1
2
3
4
5
6
7
8
9
Последняя цифра номера шифра
0
1
2
3
4
5
6
7
8
9
1, 17,
43, 93
11, 27,
53, 103
21, 37,
63, 113
31, 5,
73, 123
41, 15,
83, 133
9, 25,
93, 143
19, 35,
103, 52
29, 3,
113, 62
39, 13,
123, 72
7, 23,
133, 82
2, 18,
44, 94
12, 28,
54, 104
22, 38,
64, 114
32, 6,
74, 124
42, 16,
84, 134
10, 26,
94, 43
20, 36,
104, 53
30, 4,
114, 63
40, 14,
124, 73
8, 24,
134, 83
3, 19,
45, 95
13, 29,
55, 105
23, 39,
65, 115
33, 7,
75, 125
1, 17,
85, 135
11, 27,
95, 44
21, 37,
105, 54
31, 5,
115, 64
41, 15,
125, 74
9, 25,
135, 84
4, 20,
46, 96
14, 30,
56, 106
24, 40,
66, 116
34, 8,
76, 126
2, 18,
86, 136
12, 28,
96, 45
22, 38,
106, 55
32, 6,
116, 65
42, 16,
126, 75
10, 26,
136, 85
5, 21, 47,
97
15, 31,
57, 107
25, 41,67,
117
35, 9, 77,
127
3, 19, 87,
137
13, 29,
97, 46
23, 39,
107, 56
33, 7,
117, 66
1, 17,
127, 76
11, 27,
137, 86
6, 22,
48, 98
16, 32,
58, 108
26, 42,
68, 118
36, 10,
78, 128
4, 20,
88, 138
14, 30,
98, 47
24, 40,
108, 57
34, 8,
118, 67
2, 18,
128, 77
12, 28,
138, 87
7, 23,
49, 99
17, 33,
59, 109
27, 1,
69, 119
37, 11,
79, 129
5, 21,
89, 139
15, 31,
99, 48
25, 41,
109, 58
35, 9,
119, 68
3, 19,
129, 78,
13, 29,
139, 88
8, 24,
50, 100
18, 34,
60, 110
28, 2,
70, 120
38, 12,
80, 130
6, 22,
90, 140
16, 32,
100, 49
26, 42,
110, 59
36, 10,
120, 69
4, 20,
130, 79
14, 30,
140, 89
9, 25,
51, 101
19, 35,
61, 111
29, 3,
71, 121
39, 13,
81, 131
7, 23,
91, 141
17, 33,
101, 50
27, 1,
111, 60
37, 11,
121, 70
5, 21,
131, 80
15, 31,
141, 90
10, 26,
52, 102
20, 36,
62, 112
30, 4,
72, 122
40, 14,
82, 132
8, 24,
92, 142
18, 34,
102, 51
28, 2,
112, 61
38, 12,
122, 71
6, 22,
132, 81
16, 32,
142, 91
