Завдання до виконання

1. Побудувати дерево, яке містить:

a) 5 вершин;

b) 8 вершин;

c) 8 ребер;

d) 10 листків;

e) 5 нащадків;

f) 2 батька, 5 синів;

g) 4 предків, 12 нащадків;

h) висоту 3;

i) висоту 4.

До кожного з побудованих дерев записати список суміжності та массив його елементів.

2. Які з наведених нижче графів є деревами?

3. Побудувати ліс, який містить:

a) 2 дерева;

b) 4 дерева;

c) 7 дерев;

d) 10 вершин;

e) 10 ребер.

4. Дати відповідь на запитання щодо дерева, зображеного на рисунку.

a) Яка вершина являє собою корінь?

b) Які вершини внутрішні?

c) Які вершини являють собою листки?

d) Які вершини — сини вершини b?

e) Яка вершина — батько вершини k?

f) Які вершини — предки вершини p?

g) Які вершини — нащадки вершини d?

5. Для кореневого орієнтованого дерева:

a) знайти нащадків вершини v ₃;

b) знайти предків вершини v ₈;

c) знайти батька вершини v ₅;

d) знайти рівень вершини v ₆;

e) знайти синів вершини v ₃;

f) знайти висоту дерева;

g) знайти листки дерева;

h) визначити чи є це дерево бінарним?

6. Намалюйте генеалогічне дерево, починаючи з одного свого прапрадіда.

7. Скільки ребер містить ліс, який складається з k дерев та містить n вершин?

9. Скільки ребер містить ліс, який складається з k дерев та містить i внутрішніх вершин та l листків?

10. Що називають зв'язним графом без простих циклів?

a) контур;

b) кущ;

c) дерево;

d) простий граф.

11. Нехай дерево T має п вершин. Які твердження вірні:

a) граф T містить n простих циклів і має (n -1) ребро;

b) граф Т зв’язний і має (n -1) ребро;

c) довільні дві вершини графа Т з'єднані точно одним простим шляхом;

d) граф Т зв'язний, але вилучення довільного ребра робить його незв'язним;

12. Піддерево з коренем у вершині, яка являє собою лівого сина вершини v, називають

a) внутрішнім;

b) батьком;

c) правим піддеревом у цій вершині;

d) лівим піддеревом у цій вершині.

13. Скільки вершин міститьповне m-арне дерево з і внутрішніми вершинами?

a) n = m·і - 1;

b) n = m·і + 1;

c) n = m·і;

d) n = m + 1.

14. Скільки ребер має дерево з 1000 вершинами?

15. Скільки вершин має повне 5-арне дерево зі 100 внутрішніми вершинами?

16. Скільки ребер має повне бінарне дерево з 1000 внутрішніх вершин?

17. Скільки листків має повне 3-арне дерево зі 100 вершинами?

18. Чи існує повне m-арне деревоT, яке має 84 листки та висоту З?

19. Побудувати завершене бінарне дерево висотою 4 та завершене 3-арне дерево висотою 3.

20. Записати послідовності вершин упорядкованих кореневих дерев, наведених нижче, в разі їх обходу в прямому, зворотному та внутрішньому порядку.

21. Побудувати кореневі дерева, які відповідають виразам

a) ;

b) ;

c) ;

d) ;

e) ;

Записати ці вирази в інфіксній, префіксній та постфіксній формах.

22. Побудувати кореневі дерева, які відповідають виразам

a) ;

b) ;

c) ;

d) ;

e) .

Записати ці вирази в інфіксній, префіксній та постфіксній формах.

23. Зобразити впорядковане кореневе дерево, яке відповідає кожному з виразів, записаних у префіксній формі. Записати їх у постфіксній формі:

а) ; б) ; в) ;

г) ; д) ; е) ;

24. Обчислити значення виразів, записаних у префіксній формі:

а) ; б) ;

в) ; г) .

25. Обчислити значення виразів, записаних у постфіксній формі:

а) ; б) ;

в) .

26. Побудувати впорядковане кореневе дерево, обхід якого в прямому порядку дає послідовність , причому вершина a має чотирьох си­нів, c – трьох, j – двох, b та e – по одному, а решта вершин – листки.

27. Використати бектрекінг для відшукання гамільтонових циклів у графах.

28. Використовуючи бектрекінг, розфарбувати в три кольори графи із задач 28.

29. Використовуючи бектрекінг, розв'язати задачу про n ферзів для значень n, що дорівнюють 3, 4, 5, 6, 7, 20.

30. Використовуючи бектрекінг, знайти підмножину (якщо вона існує):

множи­ни {27, 24, 19, 14, 11, 8} із зазначеною сумою: а) 20; 6)41; в) 60;

множи­ни {7, 4, 45, 65, 18, 34} із зазначеною сумою: а) 40; 6)41; в) 117;

множи­ни {20, 21, 57, 84, 31, 81} із зазначеною сумою: а) 22; 6)98; в) 63;

множи­ни {2, 4, 49, 74, 77, 18} із зазначеною сумою: а) 8; 6)79; в) 20;

Контрольні запитання.

1. Що таке дерево? Що таке ліс?

2. Що таке висота орієнтованого дерева?

3. Що таке довжина шляху між вершинами дерева?

4. Яке дерево називається m -арним? Повним m -арним? Бінарним?

5. Що таке завершене дерево?

6. Яке дерево є кореневим? Упорядкованим?

7. Які є способи представлення дерев? Який зі способів є найбільш економічним?

8. Який об’єкт називається рекурсивним?

9. Наведіть приклади обходу дерев?

10. Що таке польські вирази?

11. Як побудувати математичний вираз?

12. Наведіть алгоритм бектрекінгу.

13. Які задачі можна вирішити, використовуючи алгоритм бектрекінгу?