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 — структури и алгоритми.

Уроци за четене

  1. Структури от данни — определение, класификация и масив
  2. Низове — представяне и основни операции
  3. Множества — представяне и основни операции

Литература

Библиографски сведения и източници · Официален конспект. Конкретните раздели и страници ще се посочват към всеки разработен урок.

Примери и упражнения

Задача 106: продажби за три дни · Задача 107: код на книга · Задача 108: читателски клуб.

Проверка на знанията

Всеки урок съдържа четири въпроса със скрити отговори за самопроверка.

Писмена разработка и устни въпроси

Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:

  1. Въведение: предмет, предназначение и място на темата.
  2. Точни определения, означения и основни понятия.
  3. Последователно изложение на подточките от конспекта и връзките между тях.
  4. Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
  5. Важни свойства, ограничения, сравнения и типични грешки.
  6. Кратко обобщение.

Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.