I.2. Структури от данни (СД)
I. Обща част · Тема 2 · Подготовка по конспекта на СУ / ФМИ № 19, 2026/2027
Обхват от конспекта
Структури от данни (СД). Определение. Класификация на структурите от данни. Представяне и основни операции за работа със СД низ, множество и масив.
Цел на подготовката
Да можеш самостоятелно да обясниш понятията и връзките между тях, да дадеш собствен пример и да приложиш изброените подходи в задача.
Примерна писмена разработка
Авторски образец за подготовка по тази тема. Не е официален отговор, утвърден от СУ, и не задава задължителен обем или схема за оценяване. Чети го за разбиране; упражнявай възпроизвеждане със собствени примери и сверявай с пълния обхват на конспекта.
Определение и класификация
Структурата от данни е организация на данни и връзките между тях, заедно с начин за изпълнение на операции. Абстрактният тип данни задава допустимите стойности и операции независимо от физическото представяне. Един и същ абстрактен тип може да има няколко реализации с различни разходи на време и памет. Множеството например може да се реализира с масив, битов вектор, хеш-таблица или дърво.
Структурите могат да бъдат линейни и нелинейни, еднородни и разнородни, с фиксиран или променлив размер, с последователно или свързано представяне. Класификациите описват различни признаци и не са взаимозаменяеми. Динамичен масив е линейна структура с непрекъснат блок памет, въпреки че размерът му може да се променя.
Масив, низ и множество
Масивът представлява индексирана последователност от еднотипни елементи. При обичайното непрекъснато представяне адресът на елемент се изчислява от началния адрес, индекса и размера на елемента. Затова достъпът по индекс е O(1). Обхождането и линейното търсене са O(n). В сортиран масив двоичното търсене е O(log n), но вмъкването в средата изисква преместване на елементи и е O(n). Добавянето в края на динамичен масив е амортизирано O(1) при геометрично увеличаване на капацитета; отделно преоразмеряване е O(n).
Низът е крайна последователност от символи. Възможни представяния са масив с дължина или масив с краен маркер. Основни операции са сравнение, конкатенация, извличане на подниз и търсене. Обикновеното сравнение е лексикографско. Наивното търсене на образец с дължина m в текст с дължина n изисква до O(nm) сравнения. При Unicode индексът на кодова единица не е непременно индекс на видим символ; избраното кодиране е част от представянето.
Множеството е неподредена колекция без повторения. Операциите включват принадлежност, добавяне, премахване, обединение, сечение и разлика. Битов вектор е подходящ при малък фиксиран универсум и дава непосредствена проверка за принадлежност. Хеш-таблицата обичайно дава очаквано O(1) за основните операции при подходящо хеширане, но не гарантира това в най-лошия случай. Балансираното дърво осигурява O(log n) и подредено обхождане.
Извод
Изборът на структура зависи от преобладаващите операции, размера на данните и необходимите гаранции. Последователно четене, чести вмъквания и заявки за принадлежност поставят различни изисквания. Затова оценката на сложността трябва винаги да посочва представянето и разглеждания случай, а не само името на абстрактния тип.
Литературна опора
За сверяване с литературата от конспекта: позиции 2 и 5 в библиографията. Допълнително: MIT 6.006 — структури и алгоритми.
Уроци за четене
- Структури от данни — определение, класификация и масив
- Низове — представяне и основни операции
- Множества — представяне и основни операции
Литература
Библиографски сведения и източници · Официален конспект. Конкретните раздели и страници ще се посочват към всеки разработен урок.
Примери и упражнения
Задача 106: продажби за три дни · Задача 107: код на книга · Задача 108: читателски клуб.
Проверка на знанията
Всеки урок съдържа четири въпроса със скрити отговори за самопроверка.
Писмена разработка и устни въпроси
Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:
- Въведение: предмет, предназначение и място на темата.
- Точни определения, означения и основни понятия.
- Последователно изложение на подточките от конспекта и връзките между тях.
- Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
- Важни свойства, ограничения, сравнения и типични грешки.
- Кратко обобщение.
Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.