Варіанти індивідуальних завдань

1. 1) послідовність структур, що мають поля: < Назва товару >, < Індекс > – впорядкування за індексами; 2) симетричний справа наліво; 3) визначити кількість вузлів у лівому і правому піддеревах; вилучити корінь того з піддерев, у якого кількість вузлів більша, – на місце вилученого перенести лівий дочірній вузол (якщо він є) і під’єднати праворуч решту вузлів; перевірити, чи змінилася висота цього піддерева; 4) нижній (від листків) зліва направо; 5) формування дерева.

2. 1) послідовність координат (x, y) точок площини, впорядкування за віддалю від точки початку координат (розробити окрему функцію для обчислення віддалі і зберігати це значення в структурі даних); 2) нижній (від листків) справа наліво; 3) 3.1) визначити відсоток точок, віддаль яких від точки початку координат перевищує задане значення MD; 3.2) вилучити з дерева вузол, який є коренем лівого піддерева, підтягнувши на його місце один з дочірніх вузлів та коректно під’єднавши інший; 4) прямий (від кореня) зліва направо; 5) друк дерева.

3. 1) символьні рядки з 16-ми кодами цілих беззнакових чисел, впорядкування за значеннями чисел (розробити окрему функцію для обчислення десяткового значення 16-го числа і зберігати це значення в структурі даних); 2) прямий (від кореня) справа наліво; 3) 3.1) з клавіатури ввести декілька нових кодів; якщо таких кодів у дереві немає, то, доповнити дерево новими елементами; 3.2) надрукувати таблицю всіх 16-х кодів та їхніх десяткових значень; 4) симетричний зліва направо; 5) додавання нового вузла.

4. 1) послідовність структур, що мають поля: < Ключ >, < Текст > – впорядку­вання за ключами; 2) прямий (від кореня) справа наліво; 3) видалити з дерева всі вузли, в текстах яких є задане слово, і вказати кількість видалень; 4) симетричний зліва направо; 5) витирання всього дерева.

5. 1) послідовність символьних рядків з датами у формі dd.mm.rr – впорядкування у дереві календарне; 2) нижній (від листків) справа наліво; 3) 3.1) надрукувати список дат, які потрапляють до заданого часового проміжку D1.. D2 та вказати їхню кількість; 3.2) вилучити всі вузли, які є листками дерева; 4) симетричний зліва направо; 5) пошук і друк дат зі заданого часового проміжку.

6. 1) послідовність структур, що мають поля: < Країна Європи >, < Кількість жителів > – впорядкування за назвами країн; 2) прямий (від кореня) зліва направо; 3) 3.1) з клавіатури ввести назви декількох країн і знайти їхнє населення (або зазначити, що даних про таку країну нема); 3.2) якщо в дереві є два суміжні вузли (батьківський і дочірній), що не мають правих нащадків, то дочірній вузол треба перенести (підняти) на місце батьківського, а батьківський зробити його правим листком; 4) нижній (від листків) справа наліво; 5) пошук країни в дереві.

7. 1) послідовність слів, впорядкування за довжинами слів (якщо довжини збігаються, то за абетковим порядком); 2) нижній (від листків) зліва направо; 3) вилучити з дерева всі вузли, в яких записані слова, що складаються з NL та більше літер; 4) симет­рич­ний справа наліво; 5) вилу­чення вузлів з довгими словами.

8. 1) послідовність символьних рядків, впорядкування за лексико-графічним порядком (кодами символів); 2) симетричний зліва направо; 3) 3.1) з клавіатури ввести певну кодову комбінацію символів; надрукувати ті рядки, які містять цю комбінацію; 3.2) вивести інформацію про дерево (всі його вузли) у формі таблиці: < корінь >, < кількість вузлів лівого піддерева >, < кількість вузлів правого піддерева >; 4) нижній (від листків) справа наліво; 5) пошук рядків із заданою кодовою комбінацією.

9. 1) послідовність структур, що мають поля: < Індекс товару >, < Кількість > – впорядкування за індексами; 2) прямий (від кореня) зліва направо; 3) 3.1) видалити вузол дерева з даними, що мають найменший індекс (якщо він має праві дочірні вузли, то під’єднати їх до батька цього вузла); 3.2) надрукувати інформацію про товари, індекси яких починаються заданою двосимвольною комбінацією; 4) симетричний справа наліво; 5) видален­ня найменшого вузла.

10. 1) послідовність символьних рядків, кожен з яких задає час певної події у формі години: хвилини: секунди (наприклад, 5:13:08), впорядкування за часом – розробити окрему функцію для порівняння двох часових рядків; 2) си­мет­­ричний справа наліво; 3) 3.1) знайти найдовший шлях від кореня до листка дерева і надрукувати вузли, які він включає (якщо довгих шляхів декілька, то можна вказати тільки один); 3.2) визначити часовий діапазон дерева – різницю часу в секундах між значеннями крайнього правого і лівого вузлів; 4) нижній (від листків) зліва направо; 5) обчислення часового діапазону дерева.

11. 1) послідовність символьних рядків, що задають дати у формі: < День Місяць > (наприклад, 5 березня) – впорядкування за календарем (розробити окрему функцію для порівняння двох дат); 2) прямий (від кореня) справа наліво; 3) 3.1) кількість дат, які пов’язані зі заданим місяцем; 3.2) перевірити, чи дерево збалансоване; якщо ні, то вказати корінь піддерева, в якому різниця кількості вузлів у лівому й правому піддеревах найбільша; 4) симетричний зліва направо; 5) пошук дат для заданого місяця.

12. 1) послідовність дійсних чисел (дві цифри в цілій частині, одна в дробовій) – впорядкування за значеннями чисел; 2) нижній (від листків) зліва направо; 3) 3.1) обчислити середнє значення всіх елементів дерева; 3.2) надрукувати вузли, розташовані на кожному з рівнів дерева; 4) прямий (від кореня) справа наліво; 5) обчислення середнього значення всіх вузлів.

13. 1) послідовність структур, що мають поля: < Код >, < Повідомлення > – впорядкування за кодами; 2) симетричний зліва направо; 3) 3.1) перевірити, чи є в дереві повідомлення із заданим кодом, якщо так, то надрукувати його; 3.2) визначити відсоток вузлів, які мають лише один дочірній елемент і вивести їхні коди; 4) нижній (від листків) справа наліво; 5) пошук вузлів з одним дочірнім елементом.

14. 1) послідовність структур, що мають поля: < Термін >, < № сторінки > – впорядкування за термінами; 2) прямий (від кореня) зліва направо; 3) 3.1) з клавіатури ввести номер сторінки і надрукувати всі терміни, записані на цій сторінці, або вказати, що таких немає; 3.2) створити нове дерево, коренем якого має стати крайній правий вузол лівого піддерева – до нового дерева можна під’єднати цілі піддерева початкового дерева та наприкінці коректно долучити його корінь; 4) симетричний справа наліво; 5) пошук термінів за номером сторінки.

15. 1) послідовність структур, що мають поля: < Кількість > (дійсне число), < Рік > – впорядкування за роками; 2) симетричний зліва направо; 3) знайти піддерево, яке має більшу висоту; корінь цього піддерева зробити новим коренем усього дерева, під’єднавши до його листка інше піддерево; перевірити і вказати, як змінилася висота обох піддерев; 4) нижній (від листків) справа наліво; 5) обчислення висоти дерева.

16. 1) прізвища та ініціали учасників конкурсу, впорядкування за абеткою; 2) нижній (від листків) зліва направо; 3) 3.1) визначити кількість листків сформованого дерева; 3.2) вилучити кореневий вузол дерева – на його місце має бути перенесений найбільший елемент лівого піддерева (якщо цей елемент має своє ліве піддерево, то його треба під’єднати на місце елемента, що стає коренем дерева); 4) прямий (від кореня) справа наліво; 5) знаходження кількості вузлів, що є листками.

17. 1) послідовність дійсних чисел (одна-дві цифри в цілій частині та дві цифри в дробовій), впорядкування за значеннями чисел; 2) нижній (від листків) справа наліво; 3) 3.1) знайти півсуму значень найбільшого та найменшого (двох крайніх) елементів сформованого дерева; 3.2) видалити всі листки, розташовані на найнижчому рівні дерева; 4) прямий (від кореня) зліва направо; 5) витирання всього дерева.

18. 1) послідовність структур, що мають поля: < Слово >, < Переклад інозем­ною мовою > – впорядкування за словами; 2) симетричний справа наліво; 3) визначити кількість вузлів у лівому і правому піддеревах; вилучити корінь того з піддерев, у якого кількість вузлів більша, – на місце вилученого перенести правий дочірній вузол (якщо він є) і коректно під’єднати решту вузлів; перевірити, чи змінилася висота цього піддерева; 4) прямий (від кореня) зліва направо; 5) обчислення кількості вузлів дерева.

19. 1) послідовність слів, впорядкування за абетковим порядком; 2) прямий (від кореня) справа наліво; 3) 3.1) перевірити, чи створене дерево збалансоване, якщо ні, то вказати корінь піддерева, в якому різниця кількості вузлів у лівому й правому піддеревах найбільша; 3.2) визначити кількість вузлів, розташованих на заданому рівні, і надрукувати ці вузли; 4) нижній (від листків) зліва направо; 5) друк вузлів, розташованих на заданому рівні.

20. 1) послідовність структур, що мають поля: < Код >, < Адреса > – впорядкування за кодами; 2) нижній (від листків) зліва направо; 3) 3.1) знайти й надрукувати всі львівські адреси; 3.2) видалити всі вузли, розташовані на найнижчому рівні дерева; 4) симетричний справа наліво; 5) видалення найнижчих листків.

21. 1) послідовність структур, що мають поля: < Ключ >, < Кодова комбінація > (ключ – одна літера, код – символьний рядок) – впорядкування за ключами; 2) симетричний зліва направо; 3) знайти і надрукувати всі кодові комбінації, в яких ключ повторюється понад 3 рази та вилучити їхні вузли з дерева; 4) нижній (від листків) справа наліво; 5) видалення всього дерева.

22. 1) послідовність структур, що мають поля: < Шифр >, < Час > (шифр – трисимвольна комбінація, час – рядок виду 13:44) – впорядкування за шифрами; 2) прямий (від кореня) зліва направо; 3) 3.1) надрукувати шифри всіх елементів, поле < Час > яких потрапляє у задані межі Т1.. Т2; 3.2) знайти найкорот­ший шлях від кореня до одного з листків і надрукувати вузли, які входять у цей шлях (якщо таких шляхів декілька, то вказати всі); 4) симетричний справа наліво; 5) друк усього дерева.

23. 1) послідовність слів, впорядкування за абетковим порядком; 2) нижній (від листків) справа наліво; 3) 3.1) вивести інформацію про дерево (всі його вузли) у формі таблиці: < корінь >, < кількість вузлів лівого піддерева >, < кількість вузлів правого піддерева >; 3.2) вилучити найменший вузол правого піддерева (якщо він має праві дочірні вузли, то їх треба під’єднати до батька цього вузла); 4) прямий (від кореня) зліва направо; 5) обчислення кількості вузлів дерева.

24. 1) послідовність координат (x, y, z) просторових точок, впорядкування за координатою x (у разі збігу – за координатою y, а в останню чергу – за z); 2) симетричний справа наліво; 3) 3.1) визначити точку, найближчу до початку координат; 3.2) вилучити з дерева всі вузли, які мають тільки один дочірній елемент; 4) нижній (від листків) зліва направо; 5) визначення точки, найближчої до початку координат.

25. 1) послідовність структур, що мають поля: < Рік >, < Подія > – впорядкування за роками; 2) прямий (від кореня) справа наліво; 3) 3.1) знайти кількість подій, що відбулися після 1990 року; 3.2) створити нове дерево, коренем якого має стати найменший вузол правого піддерева (до нового дерева треба під’єднати ліве і праве піддерево початкового дерева і коректно долучити його корінь); 4) симетричний зліва направо; 5) витирання всього дерева.

26. 1) послідовність структур, що мають поля: < Шифр книги >, < № книгар­ні > – впорядкування за шифрами; 2) прямий (від кореня) справа наліво; 3) 3.1) знайти всі книги, завезені у задану книгарню; 3.2) перевірити, чи створене дерево збалансоване; якщо ні, то вказати корені усіх незбалансованих піддерев; 4) нижній (від листків) зліва направо; 5) пошук книг за номером книгар­ні.

27. 1) послідовність слів, які є назвами столиць, – впорядкування за абеткою; 2) симет­рич­ний зліва направо; 3) 3.1) вивести інформацію про дерево (всі його вузли) у формі таблиці: < Вузол >, < Кількість елементів у його дереві (піддереві) >; 3.2) видалити крайній правий вузол дерева (якщо він має лівий дочірній вузол, то під’єднати цей вузол до батька видаленого вузла); 4) прямий (від кореня) справа наліво; 5) знаходження кількості вузлів у заданому дереві.

28. 1) послідовність координат (x, y, z) просторових точок, впорядкування за віддалю від точки початку координат (розробити окрему функцію для обчислення віддалі і зберігати це значення в структурі даних); 2) ниж­ній (від листків) справа наліво; 3) вилучити з дерева всі вузли, корди­ната z яких потрапляє у заданий діапазон z_min.. z_max, і вказати їхню кількість; 4) прямий (від кореня) зліва направо; 5) друк всього дерева.

29. 1) символьні рядки з п’ятірковими кодами цілих беззнакових чисел, впорядкування за значеннями чисел (розробити окрему функцію для обчислення десяткового значення числа, заданого п’ятірковим кодом, – це значення має зберігатися в структурі даних); 2) прямий (від кореня) зліва направо; 3) 3.1) надрукувати таблицю п’ятіркових кодів чисел та їхніх десяткових значень за порядком спадання; 3.2) якщо в дереві є два суміжні вузли (батьківський і дочірній), що не мають лівих нащадків, то дочірній вузол треба перенести на місце батьківського, а батьківський зробити його лівим нащадком; 4) симетричний справа наліво; 5) по­шук та переставлення суміжних вузлів, які не мають лівих нащадків.

30. 1) символьні рядки з 2-10-ми кодами цілих чисел, впорядкування за значеннями чисел (розробити окрему функцію для обчислення десяткового значення числа, заданого 2-10-м кодом, – це значення має зберігатися в структурі даних); 2) нижній (від листків) справа наліво; 3) 3.1) з клавіатури ввести декілька десяткових чисел; перевірити, чи є такі числа в дереві – якщо так, то надрукувати їхні 2-10-ві коди; 3.2) знайти і вказати всі вузли, розташовані на заданому рівні дерева; 4) симетричний зліва направо; 5) пошук вузлів зі заданим значенням.

СПИСОК ЛІТЕРАТУРИ

1. Шпак З.Я. Програмування мовою С. – Львів: Вид-во Львівської політехніки, 2011. – 436 с.

2. Шилдт Г. Полный справочник по С: Пер. с англ. – М.: Вильямс, 2009. – 704 с.

3. Кочан С. Программирование на языке Си: Пер. с англ. – К.: Диалектика-Вильямс, 2007. – 496 с.

4. Хэзфилд Р., Кирби Л. Искусство программирования на Си. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста: Пер. с англ. – К.: Изд-во “ДиаСофт”, 2001. – 736 с.

5. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – СПб.: Невский диалект, 2008. – 352 с.

6. Скиена С. Алгоритмы. Руководство по разработке: Пер. с англ. – СПб.: БХВ-Петербург, 2011. – 720 с.

7. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы: Пер. с англ. – М.: Вильямс, 2009. – 400 с.

8. Прата С. Язык программирования С. Лекции и упражнения: Пер. с англ. – М.: Изд. дом “Вильямс”, 2010. – 960 с.

9. Кнут Д. Искусство программирования. Т.1. Основные алгоритмы: Пер. с англ. – М.: Вильямс, 2010. – 720 с.

10. Кнут Д. Искусство программирования. Т.2. Получисленные алгоритмы: Пер. с англ. – М.: Вильямс, 2010. – 832 с.

11. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск: Пер. с англ. – М.: Вильямс, 2008. – 824 с.

12. Керниган Б., Ритчи Д. Язык программирования Си: Пер. с англ. – М.: Вильямс, 2009. – 304 с.

13. Джонс Б., Эйткен П. Освой самостоятельно С за 21 день: Пер. с англ. – М.: Изд. дом “Вильямс”, 2005. – 800 с.

14. Гукин Д. Язык программирования Си для чайников: Пер. с англ. – М.: Диалектика, 2006. – 352 с.

15. Кормен Т. и др. Алгоритмы: построение и анализ: Пер. с англ. – М.: Вильямс, 2011. – 1296 с.

16. Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке Си. Управление ресурсами. – Минск: Вышэйшая школа, 1992. – 432 с.

17. Абраш М. Таинства программирования графики. Пер. с англ. – К.: ЕвроСИБ, 1996. – 548 с.

18. Шикин Е.В., Боресков А.В. Компьютерная графика. – М.: Диалог-МИФИ, 1995. – 288 с.

19. Аммерал Л. Машинная графика на языке С. В 4-х томах. Пер. с англ. – М.: СолСистем, 1992.