Здавалка
Главная | Обратная связь

Тема: Абстрактні типи даних



Мета роботи:порівняння реалізацій абстрактних типів даних, побудованих на базі різних структур даних.

 

Запитання на допуск до роботи

1. Поясніть різницю між термінами «тип даних», «абстрактний тип даних» «структура даних». Для чого вони застосовується?

2. Проаналізуйте АТД «зв’язний лінійний список»; перерахуйте, які різновиди списків бувають та прокоментуйте та порівняйте їх способи реалізації.

3. Проаналізуйте АТД «стек»; перерахуйте, які операції можна виконувати з цим АТД, прокоментуйте та порівняйте способи реалізації АТД.

4. Перерахуйте та проілюструйте послідовність дій при вставці елемента до стеку.

5. Перерахуйте та проілюструйте послідовність дій при видаленні елемента зі стеку.

6. Проаналізуйте АТД «черга»; перерахуйте, які операції можна виконувати з цим АТД, прокоментуйте та порівняйте способи реалізації АТД.

7. Перерахуйте та проілюструйте послідовність дій при вставці елемента до черги.

8. Проаналізуйте АТД «однозв’язний лінійний список»; перерахуйте, які операції можна виконувати з цим АТД, прокоментуйте та порівняйте способи реалізації АТД.

9. Перерахуйте та проілюструйте послідовність дій при вставці елемента в середину списку.

10. Перерахуйте та проілюструйте послідовність дій при видаленні елемента з середини списку.

11. Перерахуйте та проілюструйте послідовність дій при видаленні елемента з кінця списку.

12. Проаналізуйте АТД «відображення»; перерахуйте, які операції можна виконувати з цим АТД, прокоментуйте та порівняйте способи реалізації АТД.

13. Наведіть визначення та приклад рекурсії. Як її можна використати в математиці та в програмуванні?

14. Проаналізуйте АТД «дерево»; перерахуйте, які операції можна виконувати з цим АТД, прокоментуйте та порівняйте способи реалізації АТД.

15. Прокоментуйте та порівняйте способи реалізації бінарних дерев.

16. Поясніть термін «обхід дерева». Перерахуйте способи обходу та форми, які будуть отримані в результаті використання кожного із способів.

17. Чим відрізняються дерева бінарного пошуку та для чого вони використовуються?

18. Перерахуйте та проілюструйте послідовність дій при додаванні вузла в бінарне дерево пошуку.

19. Перерахуйте та проілюструйте послідовність дій при видаленні вузла з бінарного дерева пошуку.

 

Завдання

Ознайомтесь з реалізаціями абстрактних типів даних «список» та «дерево» за допомогою масивів та покажчиків (23-99 [1], 310-328 [4]). Для одного з АТД побудуйте блок-схеми алгоритмів для додавання та видалення елементів, використовуючи дві різні реалізації (за допомогою масивів та покажчиків). Напишіть програмні реалізації алгоритмів. Проаналізуйте ефективність та складність алгоритмів і вкажіть переваги та недоліки кожної з реалізацій.

 

Варіанти завдань

1) АТД «стек»

2) АТД «черга»

3) АТД «однозв’язний лінійний список»

4) АТД «двозв’язний лінійний список»

5) АТД «відображення»

6) АТД «бінарне впорядковане дерево»

 

ПРАКТИЧНА РОБОТА №4

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.