1.  Класификация на структурите  от данни: прости и съставни структури; статични и динамични структури; линейни и нелинейни структури от данни.
  2. Линейни динамични структури от данни. 
    • Структура от данни стек. Логическо описание. Физическо представяне. Шаблон на клас, реализиращ последователното представяне на стек. Шаблон на клас, реализиращ свързаното представяне на стек. Приложения на структурата стек: намиране на стойност на аритметичен израз като се използва обратен полски запис Използване на стек за премахване на рекурсия.
    • Структура от данни опашка. Логическо описание. Физическо представяне. Шаблон на клас, реализиращ последователното представяне на опашка. Шаблон на клас, реализиращ свързаното представяне на опашка. Приложения на опашка.
    • Структура от данни линеен списък. Логическо описание. Физическо представяне. Последователен и свързан линеен списък. Шаблон на клас, реализиращ представяне на свързан списък с една връзка. Основни операции за работа със свързан списък: обхождане, обръщане, конкатениране, сортиране, сливане, проверка на свойства. Рекурсивни функции за работа със списъци. Функции от по-висок ред за работа със списъци.
      Шаблон на клас, реализиращ свързан списък с две връзки. Приложения на двусвързани списъци.
      Итератор и MapAdaptor.
      Шаблон на клас, реализиращ цикличен списък. Приложения на циклични списъци. (незадължителен въпрос)
  3. Йерархични структури от данни. 
    • Двоично дърво. Логическо описание. Физическо представяне. Шаблон на клас, реализиращ свързаното представяне на двоично дърво. Представяне и намиране на стойност на аритметичен израз.
    • Двоично наредено дърво. Шаблон на клас, реализиращ свързаното представяне на двоично наредено дърво. Приложения. Основни операции върху двоични наредени дървета: включване и изключване на елемент. Приложения.
    • Балансирани и идеално балансирани двоично наредени дървета. Информационна система, основана на идеално балансирани двоично наредени дървета. (незадължителен въпрос)
    • Структура от данни граф. Логическо описание. Физическо представяне. Представяне списък със съседи. Обхождане в ширина и в дълбочина (DFS && BFS). Път в граф. Проверка и намиране, ако съществува, на  път между два върха на граф. Намиране на всички пътища между два върха на граф. Топологично сортиране. Откриване на цикли. Най-кратък път между две върха на ориентиран граф.
    • Хеширане - HashMap и TrieMap
    • Структура от данни пирамида (незадължителен въпрос)

Част от крусовете по УП и ООП

Анализ на алгоритми. Асимптотична нотация. Нотации: O(n), Ω(n), θ(n)

Структури от данни. Определение и примери. Описание.

Понятие за поток. Входно-изходни операции. Входно-изходни оператори. Потокови входно/изходни оператори за класове, дефинирани от потребителя.

Файлове. Основни операции. Режими на достъп.

Файлове с последователен достъп. Основни операции. Приложения.

Файлове с пряк достъп. Основни операции за работа с файлове с пряк достъп. Приложения.

Абстракции. Абстрактни типове данни. Създаване на абстрактни типове данни.

Алгоритми за търсене и реализацията им за  масиви и файлове с пряка организация: последователно търсене;  двоично търсене.

Алгоритми за сортиране и реализацията им за едномерни масиви и файлове с пряка организация: метод на пряката селекция, метод на мехурчето и сортиране чрез клатене; сортиране чрез вмъкване.

Алгоритми за сортиране и реализацията им за едномерни масиви и файлове с пряка организация: метод на Шел; бързо сортиране; пирамидално сортиране; сливане и сортиране чрез сливане; балансирано многоходово сливане.




Последно модифициране: понеделник, 5 октомври 2020, 17:40