Контрольная работа №3 Лабораторная работа 5




Скачать 84.61 Kb.
НазваниеКонтрольная работа №3 Лабораторная работа 5
Дата21.12.2012
Размер84.61 Kb.
ТипКонтрольная работа

Контрольная работа № 3

Лабораторная работа 5



Тема – списки.

Цель лабораторной работы – освоить основные способы работы со стеками и очередями;

Связный список – структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом логически с помощью указателей, хранящихся в самих элементах.

Простейшие связные списки:

  • односвязный (один указатель);

  • двусвязный (два).

В односвязном списке каждый элемент состоит из двух полей: содержательного и поля указателя.

Содержательное поле хранит данные (в общем случае это запись).

Поле указателя хранит адрес следующего элемента списка. По указателю получаем доступ к следующему элементу, от него – к очередному и т.д. Поле указателя последнего элемента должно содержать специальный признак нулевого или пустого указателя, свидетельствующего о конце списка (0 в нашем примере).

Кроме того, должен быть указатель начала списка. Он является частью его логической структуры.

Кольцевой связный список. В односвязном списке для доступа к желаемому элементу необходимо просматривать список с самого начала. Это неудобно и занимает много времени. Если замкнуть элементы списка в кольцо, т.е. в последний элемент списка поместить указатель на первый элемент, то просмотр списка можно начинать с любого элемента и просмотреть весь список. Такой список называется кольцевым.

Линейный двусвязный список. Нередко при просмотре линейного списка возникает необходимость продвижения в любом направлении по цепочке элементов: как к концу списка, так и к его началу. Такую возможность обеспечивает линейный двусвязный список. Каждый элемент такого списка содержит два указателя:

  1.  прямой – на следующий элемент списка;

  2.  обратный – на предыдущий элемент списка.

Кроме указателя на начало списка в структуру двусвязного списка должен быть включен указатель на конец списка (т.е. на последний элемент).

Варианты заданий к лабораторной работе


  1. В списке целых чисел удалить из каждой группы подряд идущих одинаковых элементов все, кроме одного.

  2. Два списка упорядоченных по возрастанию целых чисел объединить в один так, чтобы результирующий список был упорядочен.

  3. Составить программу, которая из кольцевого списка из n элементов удаляет в порядке просмотра кольца каждый k-й элемент до тех пор, пока в списке не останется один элемент. Распечатать номера удаленных элементов.

  4. Составить программу, которая в кольцевой список из n элементов добавляет m новых элементов так, чтобы новый элемент вставлялся через k элементов кольца.

  5. Массив целых чисел представлен в виде динамического списка. Изменить последовательность указателей так, чтобы отрицательные числа находились в начале списка.

  6. Последовательность символов, ограниченную точкой, занести в два списка, содержащих гласные и согласные. Вывести на экран оба списка.

  7. Из динамического списка, содержащего последовательность символов, удалить все одинаковые символы, кроме одного.

  8. Текст, заканчивающийся точкой, занести в динамический кольцевой список. Вывести на экран монитора текст из кольцевого списка n раз. n ввести с клавиатуры.

  9. Создать список, содержащий целые числа. Перенести последний элемент списка в его начало.

  10. В связном списке, содержащем целые числа, удалить все нулевые элементы списка.



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


  1. Отличие динамических структур от статических и полустатических.

  2. Основные операции, выполняемые над списками.

  3. Что такое кольцевой список?



Лабораторная работа 6



Тема – деревья.

Цель лабораторной работы – освоить основные способы представления деревьев в оперативной памяти ЭВМ и практически реализовать алгоритмы работы с деревьями.

Деревом называется структура, которая характеризуется следующими свойствами:

  1. существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем;

  2. каждый элемент связан с несколькими элементами следующего уровня иерархии. Эти элементы могут быть в свою очередь деревьями (поддеревьями);

  3. каждый элемент промежуточного уровня порожден только одним элементом более высокого уровня.

Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т.е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами.

Таким образом, дерево отражает иерархически упорядоченную структуру данных, в которой прослеживаются связи между элементами предыдущего (верхнего) уровня или предками и элементами следующего уровня – потомками.

Узлы располагаются по уровням. Корень – нулевой уровень и т.д. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.

Число непосредственных потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.

Большую роль в прикладных задачах играют упорядоченные деревья второй степени. Они называются бинарными деревьями или двоичными. Бинарное дерево – это конечное множество элементов (узлов), каждый из которых либо пуст (не связан с нижним уровнем, не имеет потомков, т.е. лист), либо является корнем (или узлом) с двумя различными бинарными поддеревьями – левым и правым.

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

Во многих задачах, связанных с деревьями, требуется осуществлять систематический перебор всех их узлов в определенном порядке. Такой просмотр называется обход дерева. Существует три способа обхода деревьев, которые называются соответственно обходом сверху, обходом слева направо и обходом снизу.

Над деревьями выполняются такие операции: пройти все узлы в определенном порядке, найти узел с заданным свойством, определить отца данного узла, определить сыновей данного узла, удалить определенный узел (поддерево), добавить новый узел и т.д.

Для представления деревьев в памяти ЭВМ используются последовательный и связанный методы хранения.

Последовательное хранение произвольного дерева получается на основе какого-нибудь из его линейных представлений, т.е. задания дерева в "строку".

Связанная стандартная форма хранения деревьев состоит в том, что задается связь от отца к сыновьям, поэтому в каждом узле дерева степени N необходимо иметь N указателей на его сыновей. Отсутствие какого-либо сына обозначается указателем со значением Nil.

Допускается обратная форма связного хранения графа, которая состоит в задании связей от сыновей к отцу; здесь для каждого узла достаточно иметь один указатель на отца. Как правило, эта форма хранения используется для неупорядоченных деревьев.

Варианты заданий к лабораторной работе


  1. Используя очередь или стек, напишите программу, определяющую число вхождений элемента Е в дерево Т.

  2. Вычислить среднее арифметическое всех элементов непустого двоичного дерева Т.

  3. Подсчитать число вершин на n-ом уровне непустого дерева T (корень считать вершиной нулевого уровня).

  4. Напишите программу, определяющую число вхождений элемента Е в дерево Т.

  5. Напишите программу, находящую величину наибольшего элемента дерева Т.

  6. Напишите программу, определяющую максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.

  7. Разработать программу, которая определяет, равны ли два бинарных дерева.

  8. Напишите программу, определяющую самое большое число на n-ом уровне непустого дерева Т (корень считать вершиной нулевого уровня).

  9. Разработать программу, формирующую динамическую структуру данных для хранения генеалогического дерева. Каждая вершина дерева должна содержать следующую информацию: имя и год рождения.

  10. В непустом дереве T найти длину пути (число ветвей) от корня до ближайшей вершины с элементом Е. Если элемент Е не входит в Т, то за ответ принять "-1".

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


  1. Степень дерева.

  2. Бинарное дерево.

  3. Основные операции, выполняемые над бинарными деревьями.

  4. Обход двоичного дерева.

  5. Сильно ветвящиеся деревья.

Контрольная работа № 4

Лабораторная работа 7



Тема – графы.

Цель лабораторной работы – освоить способы представления графов в оперативной памяти ЭВМ, научиться практически реализовывать основные алгоритмы работы с графами – поиск в глубину и в ширину, построение эйлерова и гамильтонова пути, а также построение кратчайшего пути на графах, имеющих различные свойства.

Будем обозначать граф



где V - множество вершин, а E - множество ребер, причем

– для ориентированного графа и

– для неориентированного графа.

Будем использовать также обозначения | V | = n, | E | = m (мощность множества).

В теории графов классическим способом представления графа является матрица инциденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (x, y)E, содержит "+1" в строке, соответствующей вершине x, "-1" в строке, соответствующей вершине y, и нули во всех остальных строках. Петлю, т.е. дугу вида (x, x), удобно представлять другим значением, например, 2, в строке x. Для неориентированного графа столбец, соответствующий ребру {x, y}, содержит 1 в строках, соответствующих x и y, и 0 - во всех остальных строках.

Второй способ представления графа – с помощью матрицы смежности размера n x n, где = 1, если существует ребро из x и y, и = 0 в противном случае. При этом подразумевается, что ребро {x, y} неориентированного графа идет как от x к y, так и от y к x. Поэтому матрица смежности для неориентированного графа всегда симметрична.

Более экономным в отношении памяти (особенно для неплотных графов, когда m гораздо меньше ) является способ представления графа с помощью списка пар, соответствующих его ребрам. Пара (x, y) соответствует дуге (x, y), если граф ориентированный, и ребру {x, y}, если граф неориентированный.

Лучшим решением во многих случаях является структура данных, которую назовем списками инцидентности. Она содержит для каждой вершины список вершин u, между которыми существуют дуги (v, u) для ориентированного графа, и ребра {v, u} – для неориентированного графа.

Типичные задачи, связанные с графами, – это сравнение графов (скажем, чертежей при распознавании изображений), нахождение кратчайшего пути по карте дорог, составление совместной системы уравнений по электронной цепи, нахождение критического ребра в графе, удаление которого приведет к расщеплению графа на две отдельные, не связанные между собой области.

Варианты заданий к лабораторной работе


  1. Проверьте, содержит ли граф, заданный с помощью списков инцидентности, вершину, в которую входят дуги от всех остальных вершин графа, но из которой не исходит ни одна дуга.

  2. Напишите и используйте в программе процедуру поиска в глубину в графе, заданном списками инцидентности. Выведите на экран номера вершин в том порядке, в котором они просматриваются процедурой.

  3. Напишите и используйте в программе процедуру поиска в ширину в графе, заданном списками инцидентности. Выведите на экран номера всех вершин в порядке очередности просмотра.

  4. Напишите и используйте в программе процедуру, реализующую метод, отличающийся от поиска в ширину только тем, что вновь достигнутая вершина помещается не в очередь, а в стек.

  5. С помощью метода поиска в глубину найдите стягивающее дерево для произвольного связного неориентированного графа, заданного списками инцидентности.

  6. Используя метод поиска в ширину, найдите стягивающее дерево для произвольного связного неориентированного графа, заданного списками инцидентности.

  7. Используя метод поиска в ширину, найдите кратчайший путь от начальной до любой произвольной вершины связного неориентированного графа, заданного списками инцидентности (веса всех ребер примите равными единице).

  8. Используя алгоритм поиска в глубину, найдите множество фундаментальных циклов связного неориентированного графа, заданного списками инцидентности.

  9. Найдите эйлеров цикл в графе, не содержащем вершин нечетной степени и заданном списками инцидентности.

  10. Найдите эйлеров путь в графе, содержащем две вершины нечетной степени и заданном списками инцидентности.

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


  1. Представление графов в памяти ЭВМ.

  2. Что такое эйлеров путь?

  3. Что такое гамильтонов путь?

  4. Что такое стягивающее дерево?

Похожие:

Контрольная работа №3 Лабораторная работа 5 iconКонтрольная работа по немецкому языку Контрольная работа предназначена для проверки знаний лексики, грамматики, умения читать и извлекать информацию из немецких текстов
...
Контрольная работа №3 Лабораторная работа 5 iconКонтрольная работа №1 по документоведению
Лабораторная работа на тему «Документ его функции. Способы документирования»
Контрольная работа №3 Лабораторная работа 5 iconЛабораторная работа Установка и настройка 6 Лабораторная работа Демонстрационный проект 7 Упражнение 1: Работа с основной схемой проекта 7 Упражнение 2: Работа со схемой «Резервуарный парк»
Разработка систем диспетчерского контроля и управления с использованием Infinityscada 4
Контрольная работа №3 Лабораторная работа 5 iconКонтрольная работа по текстам му уо контрольная работа по математике 11 класс 16. 11. 2011г. Контрольная работа по русскому языку 11 класс 18. 11. 2011г
Входные контрольные работы по линии администрации школы (предметы инвариантной части учебного плана) (график контрольных работ) 3...
Контрольная работа №3 Лабораторная работа 5 iconКонтрольная работа 2 курс Контрольная работа 1 Контрольная работа 2 рекомендуемая литература введение контрольные работы по дисциплине «Практический курс основного иностранного языка»
Они отражают требования государственного образовательного стандарта высшего профессионального образования – специальность 050303...
Контрольная работа №3 Лабораторная работа 5 iconПорядок ведения и оформления тетрадей по русскому языку и литературе
Например: Проверочная работа. Самостоятельная работа. Контрольная работа. Работа над ошибками. Изложение. Сочинение
Контрольная работа №3 Лабораторная работа 5 iconЛабораторная работа. Получение и свойства оксидов, гидроксидов и солей
Лабораторная работа. Ряд напряжений металлов. Гальванические элементы. Электролиз юююююю
Контрольная работа №3 Лабораторная работа 5 iconКонтрольная работа по теме «Производная функции одной переменной» для студентов тэс
Данная контрольная работа должна позволить и студенту, и преподавателю оценить уровень усвоения указанной темы. Работа рассчитана...
Контрольная работа №3 Лабораторная работа 5 iconТематическое планирование биология, 6 класс
Морфология листа (лабораторная работа) 12. Строение растительного организма. Клетки и ткани 13. Типы растительных тканей (Лабораторная...
Контрольная работа №3 Лабораторная работа 5 iconКонтрольная работа по дисциплине «Информационные системы и сети»
Контрольная работа состоит из трех заданий: одно задание теоретическое, два задания практические
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница