Завдання на залік по С (структури даних)
Стек та черга
- (4) кількість островів (через стек) (рекомендують спочатку заливкою)
- (4) черга на динамічному масиві
- struct Queue;
- struct Queue; struct Queue * q = create(100); q = enqueue(q, 3); x = dequeue (q)
- (5) Пошук у стеку мінімуму за O(1) – елегантний хінт, зберігати пару (елемент, мінімум).
Однозв'язковий список
- (?) Стек на однозв'язковому списку.
- stuct Node * list = NULL; push(&list 3); x = pop(&list);
- перевернути список
- на місці;
- зробити перевернуту копію, оригінальний список не чіпаємо.
Список двозв'язковий (циклічний з бар'єрним елементом)
- (3) Знайти кількість елементів у списку
- парних, непарних, кратних 3 і тп.
- Список у зворотному порядку
- (3) надрукувати
- (4) зробити
- (5) зробити ще один, вихідний не чіпаємо
- Знайти елемент та видалити
- (3) перший знайдений
- (4) останній
- (5) все
- Відсортувати (вузли, а не дані у вузлах.)
- (5) вставками
- (5) qsort
- (на місці)
- (Копію)
- Конкатенація
- (3) на думку
- (3) у хвіст
- (5) злити два відсортованих списки
Список (складність завдання зазвичай не залежить від типу списку)
- Список розщепити (зробити 2 з одного)
- (4) Дано список із чисел. Створити дві черги: перша має містити числа з вихідного набору з непарними номерами (1, 3, …, 9), а друга – з парними (2, 4, …, 10); порядок чисел у кожній черзі має збігатисяз порядком чисел у вихідному наборі.
- (4) Дано список із чисел. Створити дві черги: перша має містити непарні числа з вихідного набору (1, 3, …, 9), а друга – парні (2, 4, …, 10); порядок чисел у кожній черзі має збігатися з порядком чисел у вихідному наборі.
- (3) у списку, що містить цілі числа, знайти та вивести суму всіх непарних елементів (0, якщо таких немає);
- критерій – за фантазією викладача.
- (3) у списку, що містить символи, знайти останній цифровий символ, вивести відповідне число, помножене на три (тобто якщо останній такий символ - '6', то вивести 18) або нічого, якщо такого немає;
- (5) дано масив об'єктів виду [ціле число, індекс]; дано списки (тобто індекси голови) реальних об'єктів та вільних вузлів:
- видалити перший вузол списку реальних об'єктів, якщо він існує;
- додати на початок (альтернативно - на кінець) списку реальних об'єктів новий елемент, що зберігає значення 0 (* - придумати, що робити, якщо список вільних вузлів порожній);
- розгорнути пари у списку (тобто список (a, b, c, d, e, f, g) повинен перетворитися на (b, a, d, c, f, e, g));
- (3-4) поміняти вузол у списку з наступним вузлом (для різних типів списків)
- (3-4) поміняти вузол у списку з довільним вузлом (для різних типів списків)
- (4-5) розгорнути пари у списку
- дано список, що містить цілі числа, перевірити, чи він упорядкований за:
- (3-4) спадання, зростання, придуманого вами критерію.
- (5) критерій визначається функцією bool cmp(int, int)
- (4-5) злити два відсортованих списки в один
- побудувати третій список на одновідвох вихідних (які не змінюються).
- (5) знайти петлю в списку (два вказівники, один біжить по списку зі швидкістю в 2 рази більше, ніж другий, якщо не на першому кроці вони вказують на один вузол, цикл є)
Дерево бінарне
Завдання зазвичай припускають демонстрацію функції дереві, що містить у вузлах цілі числа.
- (3) Обхід дерева в глибину трьома способами. (Перефраз завдання: надрукуйте дерево за спаданням; що буде надруковано, якщо функцію друку поміняти ось ці рядки місцями.)
- (3-4) Роздрукувати / підрахувати скільки вузлів у дереві:
- глибиною менше k
- глибиною більше k
- у кожен вузол дерева додати поле depth і записати туди глибину найбільш глибокого піддерева
- (3-4) прописувати глибину окремою функцією set_depth по вже побудованому дереву (тобто якщо прописали, а потім додали вузли, значення глибини може стати неактуальним).
- (4-5) прописувати (змінювати) глибини при додаванні вузла дерево.
- Пошук за значенням:
- (3) Пошук за значенням (повернути 0 або 0)
- (3) Пошук за значенням (повернути вказівник на вузол)
- (3) Порахувати скільки в дереві вузлів:
- тільки з правою (лівою) дитиною;
- з непарними числами (парними, кратними 3 і тп)
- (3-4) дано дерево, що містить цілі числа; перевірити, чи правильно, що:
- у кожного вузла праве поддерево немає, тільки якщо немає ліве;
- кожен вузол або містить парне число, або в нього існують ліве та праве піддерев'я;
- у кожного вузла існує не більшеодного піддерева;
- (4) злиття 2 дерев
- будуємо третє, перші два залишаються як є
- у перше вливаємо друге, друге видаляємо
- (4-5) Обхід дерева завширшки (є в контесті). Модифікація - спочатку правої дитини.
- (5) Дано два довільних вузла в дереві, знайти їх найближчого спільного батька - бажано за O(глибина дерева), але можна краще.
- (5) Видалення елемента з дерева пошуку (збереження впорядкованості).
- (5) Виведення дерева на екран у гарному вигляді двома способами:
- вершина зверху
- вершина збоку
- (5) дерево як масиви (масив вершин та масив дуг)
- (5) Перетворити дерево на масив вузлів, що зберігає індекс батька, і назад на дерево.
- (5) Перетворити арифметичний вираз з рядка на дерево і назад.
- (4) дано дерево, у якого деякі вузли як деякі піддерева посилаються на корінь, знайти число таких посилань;
- (4-5) дано дерево, що містить цілі числа, побудувати список, що містить тільки позитивні (альтернативно - непарні) числа, що зберігаються в дереві (якщо деяке число зустрічається в дереві більше одного разу, до списку воно повинно входити стільки ж разів);
- (4-5) дано список, що містить цілі числа, побудувати дерево, що містить всі об'єкти списку, таке, що в лівому піддереві кореня знаходяться лише непарні елементи, а правому - лише парні;
- дано дерево, представлене як покажчик на деякий об'єкт ічотири функції - value(), left(), right(), clone() приймають такий покажчик і повертають перша - ціле число, інші -покажчик на такий самий об'єкт; left() і right() мають право змінювати переданий об'єкт, для покажчика, повернутого clone(), слід викликати delete коли потреба відпаде; виконати таке:
- визначити, чи містить дерево значення, більше чи рівне заданого, лише на рівні не глибше заданого (корінь вважається мають рівень 0) (* - задовольняє заданому предикату, переданому як покажчик на функцію виду bool(int));
- визначити висоту дерева, якщо вона не перевищує задану межу; інакше повернути значення цієї межі;
- (якщо був пошук завширшки) знайти, чи містить дерево значення, що дорівнює заданому; мати на увазі, що таке представлене дерево не повинно мати скільки-небудь розумний розмір; повернути те, у лівому чи правому піддереві кореня значення знайдено, або ознака невдачі;
Інші структури даних
- (*) будь-які завдання на графи, коли зберігаємо список ребер (або вершин)