Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Бінарне дерево пошуку
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2009
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Структура даних "Бінарне дерево пошуку"
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 7
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Львів – 2009
Методичні вказівки до лабораторної роботи "Структура даних "Бінарне дерево пошуку"" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2009 – 12 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Опир Ю.М., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач.
2. ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.
2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.
3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого текстового редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.
4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати.
5. Написати контрольне опитування по темі.
6. Оформити звіт по роботі.
Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.
3. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
Постановка задачі:
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку та підрахувати:
кількість вершин дерева при проходженні його у прямому порядку;
кількість листків дерева при проходженні його у зворотньому порядку;
кількість вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне завдання згідно з варіантом.
Варіанти завдань:
Cтворити дзеркальне до заданого дерево.
Вилучити з дерева всi листки.
Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка.
Вилучити з дерева всi вузли, що мають двох синів.
Додати до дерева листки так, щоб воно стало строго бінарним деревом.
Побудувати два бінарних дерева пошуку та визначити, чи є вони дзеркальним відображенням одне одного.
Побудувати два бінарних дерева пошуку та визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї з його вершин.
Знайти середнє арифметичне значення всіх вузлів дерева.
Знайти середнє арифметичне значення всіх листків дерева.
Добудувати дерево до строго бінарного дерева.
Добудувати дерево до повного бінарного дерева.
Визначити, чи побудоване дерево є строго бінарним деревом.
Визначити, чи побудоване дерево є повним деревом.
Визначити, чи заданий вузол дерева є коренем, або листком, або вершиною.
Знайти найближчого спільного предка двох заданих вузлів дерева.
Знайти рівень заданого вузла дерева.
Знайти вузли, у яких кількість нащадків у лівому піддереві не дорівнює кількості нащадків у правому піддереві.
Знайти вузли, для яких висота лівого поддерева не дорівнює висоті правого піддерева.
Знайти довжину мінімального шляху між листами.
Знайти максимальний шлях між вузлами дерева.
4. ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
№ варіанта = [(день народження студента) * (місяць народження студента) ] % 20 + 1
5. ЗМІСТ ЗВІТУ
I. Оформити титульну сторінку звіту стандартного зразка, на якій вказати назву лабораторної роботи, її номер та номер варіанту.
II. В звіті мають бути відображені наступні пункти:
1. Мета роботи.
2. Постановка задачі.
3. Алгоритм розв’язання задачі.
4. Схематичні зображення бінарного дерева пошуку до та після змін у ньому.
5. Реалізація бінарного дерева пошуку на базі масиву розмірністю N=15 (намалювати масиви до та після змін у бінарному дереві пошуку).
6. Результати виконання програми (обов’язково відобразити на екрані монітора бінарне дерево до змін та після змін у ньому).
Висновки.
Додатки (тексти програм з коментарями).
6. КОНТРОЛЬНІ ЗАВДАННЯ
1. Для заданого на Мал.1 бінарного дерева (БД) дайте відповіді на наступні питання:
Кількість вузлів БД.
Глибина БД.
Степінь БД.
Степінь вузла 6.
Рівень вузла 2.
Всі вузли 3 рівня.
Корінь БД .
Всі листки БД.
Всі вершини БД.
Безпосередні нащадки вузла 4.
Нащадки вузла 4.
Безпосередні предки вузла 6.
Предки вузла 8.
Батько вузла 2.
Сини вузла 4.
Брат вузла 6.
2. Запишіть послідовність вузлів при проходження БД :
у прямому порядку,
у симетричному порядку,
у зворотньому порядку.
3. Домалюйте це БД до найближчого строго БД.
4. Домалюйте це БД до найближчого повного БД.
5. Домалюйте це БД до найближчого майже повного строго БД.
6. Перемалюйте це БД після вилучення з нього вузла 4.
7. Для заданого на Мал.1 БД намалюйте його представлення на базі масиву розмірністю n=15.
8. Побудуйте бінарне дерево пошуку , згідно заданої послідовності.
5 , 1 , 8 , 3 , 8 , 9 , 6 , 0 , 7 , 1 , 4 , 6 , 2 , 0 , 1 , 7 , 9 , 5 .
7. НАВЧАЛЬНО-МЕТОДИЧНІ МАТЕРІАЛИ
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
ЗМІСТ
Мета роботи……………………………………..……………………………………………3
Порядок виконання роботи….………………………………………………………….…. .3
Завдання на лабораторну роботу ....………………………………………..……..………...3
Вибір індивідуального завдання ……………………………………………………………4
Зміст звіту....................................………...…………………………………………………. 4
Контрольні завдання................………..……………………………………………………. 5
Навчально-методичні матеріали………...…………………………………………………. 5
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи
"Структура даних "Бінарне дерево пошуку" "
з дисципліни
“Програмування. Частина IIІ. Структури даних та алгоритми"
для підготовки студентів напрямку
6.0915 “Комп’ютерна інженерія
Укладач Т.А.Лисак, ст. викладач каф.ЕОМ
Редактор
Комп’ютерне складання
Підписано до друку 2008 р.
Формат 70 х 100 1/16. Папір офсетний.
Друк на різографі. Умовн. друк. арк. ...... Обл.-вид. арк. ......
Наклад ..... прим. Зам.
Поліграфічний центр
Видавництва Національного університету “Львівська політехніка”
вул. Колесси, 2, 79000, Львів
24.03.2013 13:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора