Материал: Вопросы к экзамену

Примечание:

Красным цветом написаны вопросы и та часть ответов на вопросы на счет правильности которых есть сомнения.

Черным цветом написаны ответы на вопросы.

Фиолетовым цветом написаны алгоритмы и псевдокоды в ответах на вопросы.

Все что синим цветом – это дополнительная информация (не обращайте внимания)

10.Линейные структуры данных. Стеки. Деки. Использование стека для решения задачи о

11.Формы представления выражений. Польская и обратная польская нотации. Алгоритм

13.Сбалансированные деревья. Основныепонятия. Малый и большой поворотыдерева.

11

16.Сбалансированные деревья. АВЛ-деревья. Алгоритм удаления существующего узла..13

18.Сбалансированные деревья.Красно-чёрныедеревья. Алгоритм добавления нового узла. 15

19.Сбалансированные деревья.Красно-чёрные деревья. Алгоритм удаления

22.Сбалансированные деревья. 2-3-4 деревья. Алгоритм удаления существующего узла.18

23.Хэш-таблицы. Понятие хэш-функции. Хэширование делением. Хэширование

1. Алгоритмическая сложность. Оценка роста функции. Оценка сверху, снизу, в среднем.

Алгоритмическая (Вычислительная) сложность – это параметр для сравнивнения быстродействия алгоритмов, чётко описывающее их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входных данных.

Временная сложность алгоритма — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.

Оценка роста функции (оценка слоности) – это оценка алгоритма (по времени

сортировки – обратно сортированная последовательность.

Оценкаснизу– этооценкаработыалгоритмавлучшемслучаи.Напримердлясортировки

– уже отсортированная последовательность.

Оценка в среднем – это оценка работы алгоритма в среднем случаи. Например для сортировки – частично отсортированная последовательность.

2. Алгоритмы поиска. Линейный поиск. ( )

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

Линейный, последовательный поиск — алгоритм нахождения заданного значения в произвольной структуре данных. Данный алгоритм является простейшим алгоритмом поиска и работает за линейное время – с увеличением данных время выполнения увеличивается прямопропорционально. ''Метод поиска в лоб'' – перебирать все элементы в структуре данных начиная с первого (или с последнего) элемента и сравнить с искомым значением.

Псевдо код:

ЦИКЛ пока не закончились элементы, для каждого элемента ЕСЛИ очередной элемент совпадает с искомым, ТО

нашли, выходим из цикла Конец ЕСЛИ

Конец ЦИКЛА

3. Алгоритмы поиска. Бинарный поиск. ( )

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

Двоичный (бинарный) поиск – классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. В каждой итерации работы алгоритма в массиве данных выбирается средний элемент и сравнивается с

3

искомым элементом, исходя из того будет элемент болше или меньше искомого, поиск продолжается в соответствующей половине.

Псевдокод:

Пусть есть некий отсортированный массив. Рекурсивно выполнить. ФУНКЦИЯ ПОИСКА (МАССИВ, НАЧАЛО, КОНЕЦ)

вычислить СРЕДНИЙ элемент, // средний = (int)(НАЧАЛО+КОНЕЦ / 2) сравнить с искомым ЕСЛИ ИСКОМЫЙ < СРДНЕГО

ФУНКЦИЯ ПОИСКА (МАССИВ, НАЧАЛО, СРЕДНИЙ) Конец ЕСЛИ ЕСЛИ ИСКОМЫЙ > СРДНЕГО

ФУНКЦИЯ ПОИСКА (МАССИВ, СРЕДНИЙ, КОНЕЦ) Конец ЕСЛИ ИНАЧЕ

нашли Конец ИНАЧЕ Конец ФУНКЦИИ

4.Поиск подстроки в строке. Простой поиск.

Поиск подстроки в строке (String searching algorithm) — класс алгоритмов над строками,

которые позволяют найти паттерн (pattern) в тексте (text). Простой поиск подстроки в строке из себяпредставляет''примитивныйметодпоискавлоб''(brutе-force,наивныйалгоритм):накаждом

шагуберетсяочереднойкусокизстроки(длинойискомойстроки) исравнивается,еслирезультат

стравнения false( то −двигаемся) на−однусреднийпозициюслучайвперед иснова( 2) −сравниваемхудшийслучайи так до конца строки.

find(String

failed:

for (int i = 0; i < |строка| - |подстрока|; i++) { for (int j = 0; j < |подстрока|; j++) {

if (строка[i + j] != подстрока[j]) { goto failed;

}

}

return i; // нашли, вернули начальную позицию подстроки в строке

}

return -1; // не нашли

}

5. Поиск подстроки в строке. Алгоритм Кнута-Мориса-Прата.

Поиск подстроки в строке (String searching algorithm) — класс алгоритмов над строками, которые позволяют найти паттерн (pattern) в тексте (text).

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки встроке. Времяработы алгоритмалинейнозависит от объёма входныхданных,тоесть разработатьасимптотическиболееэффективныйалгоритмневозможно.

4

int find(String p, String s) { String c = p + "#" + s;

int[] prefix = new int[c.length()]; for (int i = 1; i < c.length(); i++) {

int j = prefix[i - 1];

while (j > 0 && c[i] != c[j]) { j = prefix[j - 1];

}

if (c[i] == c[j]) { prefix[i] = j + 1;

}

if (prefix[i] == p.length()) { return i - 2 * p.length();

}

}

return -1;

}

+++++++++++++++++++++++++++++++++++++++++++++++++

Пусть дан текст в виде массива T[n] и образец (то что ищем) P[1…m]; mn. Символы принадлежат

алфавиту в бинарном коде; в текстовом файле.

Р входит в Т со сдвигом S, если T[S+1…S+m]=P[1…m]; S от 0 до n-m, такой сдвиг называется допустимым. #T=abcabaabc;

P=abaa;

Pabaa, сдвиг S=3.

Пусть дана строка символов X[1…n], тогда для любой пары i, j; 1 определяем подстроку

X[i…j]=X[i] X[i+1]…X[j].

Будем говорить, что подстрока X[i…j], начинается с позиции i и её длина равна j-i+1, если величина меньше чем n, то подстрока называется собственной подстрокой строки X.

(сигма) X=

Для произвольного целого j от 0 до n подстрока X[1…j] называется префиксом подстроки. Если j<n собственный префикс подстроки X.

Для произвольного целого i от 1 до n+1 подстрока X[i…n] называется суффиксом строки X. Если i>1 то подстрока называется собственным суффиксом X.

Например, X=abaab

-префиксы a, ab, aba, abaa, abaab; -суфиксы b, ab, aab, baab, abaab=X.

Алгоритм поиска образца:

5