Задачи на зачет по С (структуры данных)

Стек и очередь

• (4) количество островов (через стек) (рекомендуют сначала заливкой)

• (4) очередь на динамическом массиве
  • struct Queue {int first, last; Data * arr;};
  • struct Queue {int first, last; Data arr[1];};
    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);

• (?) очередь на односвязном списке stuct List { struct Node * head; struct Node * tail; };

• перевернуть односвязный список
  • на месте;
  • сделать перевернутую копию, оригинальный список не трогаем.

Список двусвязный (циклический с барьерным элементом )

Можете любой список, если сами себе злобные буратины.

• (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 раза больше, чем второй, если не на первом шаге они указывают на один узел, цикл есть)

• (5) дан сигма-образный непустой список (т.е. next последнего узла содержит адрес некоторого узла), найти число элементов в нём или хотя бы предположить идею того, как это сделать;

Дерево бинарное

Задачи обычно предполагают демонстрацию функции на дереве, содержащем в узлах целые числа.

• (3) Обход дерева в глубину тремя способами. (Перефраз задачи: напечатайте дерево по убыванию; что будет напечатано, если функцию печати поменять вот эти строчки местами.)

• (3-4) Распечатать / подсчитать сколько узлов в дереве:
  • глубиной меньше k
  • глубиной больше k
  • в каждый узел дерева добавить поле depth и записать туда глубину наиболее глубокого поддерева
    • (3-4) прописывать глубину отдельной функцией set_depth по уже построенному дереву (те. если прописали, а потом добавили узлы, значение глубины может стать неактуальным).
    • (4-5) прописывать (изменять) глубины при добавлении узла в дерево.

• Поиск по значению:
  • (3) Поиск по значению (вернуть 0 или не 0)
  • (3) Поиск по значению (вернуть указатель на узел)
  • (3) Посчитать сколько в дереве узлов:
    • только с правым (левым) ребенком;
    • с нечетными числами (четными, кратными 3 и тп)
  • (3-4) значения х, в узлах, глубиной не больше k
  • (4) значения х, в узлах, глубиной больше k

• (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));
  • определить высоту дерева, если она не превышает заданный предел; иначе вернуть значение этого предела;
  • (если был поиск в ширину) найти, содержит ли дерево значение, равное заданному; иметь в виду, что так представленное дерево не обязано иметь сколько-нибудь разумный размер; вернуть то, в левом или правом поддереве корня значение найдено, либо признак неудачи;

Прочие структуры данных

• (5) Лес

• (*) любые задачи на графы, когда храним список ребер (или вершин)

-- TatyanaDerbysheva - 19 May 2014

---