Структуры данных и Сортировка. Быстрый поиск С++

[user100]

1. Разреженная матрица целых чисел представлена в виде виде упорядоченного (сначала по первому индексу, а затем по второму) списка (с двумя связями) триплетов. Заполнив элементом по умолчанию элементы матрицы А, расположенные по ее периметру, составить новый список триплетов.

2. Два множества, элементами которых являются буквы латинского алфавита, представлены в виде характеристических векторов. Найти разность первого и второго множеств. Проверить, принадлежит ли данный элемент множеству А. Если “да”, то перенести его в множество В.

3. Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылка на отца. Представление дерева на выходе: имя вершины; ссылки на самого левого сына и правого брата.

4. Формула, реализующая булеву функцию, задается (с клавиатуры или из текстового файла) символьным выражением с использованием связок полной системы:
! - отрицания и V - дизъюнкции.
4.1. Распознать символьную информацию, создав соответствующее данной формуле бинарное дерево.
4.2. Составить таблицу значений булевой функции.
4.3. Проверить, принадлежит ли данная функция классу Т0 функций, сохраняющих константу 0.
5. Частично отсортировать числовую последовательность методом быстрой сортировки, используя порог = 6. Затем сортировать методом простого включения. Методом дихотомического поиска найти заданный элемент и вывести на экран его порядковый номер в упорядоченной последовательности.


6. Прочитать исходные данные из входного текстового файла. Представив эти данные в виде массива записей с тремя полями, поочередно отсортировать массив по каждому из полей. Вывести отсортированные данные в выходной текстовый файл.
Набор данных “Автомагазин” содержит для каждого из имеющихся в продаже автомобилей: марку (12 символов), год выпуска (целое значение), цвет (10 символов).
Использовать сортировку вычерпыванием.


7. Используя те же записи, что и в задаче 6 (до сортировки!!!), организовать их в виде дерева поиска. В качестве ключа использовать значение первого поля. Перестроить дерево поиска, произведя последовательно следующие операции:
• добавив новую запись,
• удалив запись из корня.