Примерные
варианты контрольной N 1
ВАРИАНТ 1.
1.(15) Пусть
в массиве A[1..N] первые n (n < N ) элементов представляют
сортирующее
дерево. Опишите алгоритм добавления к этому дереву
нового
элемента A[n+1] и оцените его сложность.
2.(15) Как
изменить алгоритм, использующий метод динамического программирования для
распознавания кс-языка, порождаемого кс-грамматикой в нормальной форме
Хомского,
чтобы он в
случае положительного ответа возвращал и дерево вывода исходного слова?
3.(15)
Hаписать битовyю линейнyю пpогpаммy в базисе {&, V, +(mod 2)} для вычисления
квадpата
двyхpазpядного двоичного числа и оценить ее сложность.
4.(10)
Построить для дерева Т, заданного списком дуг, представляющее его бинарное
дерево Т1. Описать Т1 с помощью матрицы смежности.
T = {(v1,v2), (v1,v3), (v1,v10),(v2,v4),(v2,v5),
(v2,v6),
(v2,v7),(v3,v8),(v3,v9), (v5,v11)}.
5.(10) Найти
4-ый минимальный элемент следующей последовательности с помощью алгоритма
линейной сложности:
7,2,5,81,10,14,3,17,2,1,3,4,5,8,5,56,23,13,-2,0,4,32,20,17.
6. (20)
Пусть массив A[1..n] содержит все целые числа от 0 до n, кроме одного. Предположим, что за одно
действие можно просмотреть заданный бит заданного элемента А. Предложите
алгоритм для нахождения недостающего числа сложности O(n).
7. (15)
Пусть G=(V, E) – ориентированный ациклический
граф, в котором из некоторой вершины v в любую другую вершину u
из V
ведет единственный путь. Покажите, что неориентированный вариант графа G
является деревом.
8. (15)
Пусть исходный массив А уже отсортирован в порядке возрастания. Каким будет
время его сортировки с помощью дерева? А каким оно будет, если он отсортирован
в порядке убывания?
Вариант 2
1.(15)
Оценить сложность вызова PE(A[1..N]) следующего алгоритма
(N - степень 4).
procedure
PE( A[m..n]):
begin p:= n-m+1;
обработать A[m]; обработать A[n];
PE( A[1.. m+p/2-1]); PE( A[m+p/2.. n]); PE(A[m+p/4..m+3p/4])
end
(сложность процедуры "обработать"
считать константой).
2.(15)
Используя алгоритм Янгера-Касами, проверить входит ли слово aabcaa
в кс-язык,
порожденный следующей кс-грамматикой:
S => AA | AB
A => a | AA
| CA
B => b | BB
| BC
C => c | CC
| CA
Если входит,
то построить дерево его вывода.
3.(15) Пусть
в массиве A[1..N] первые n (n < N ) элементов представляют
сортирующее
дерево. Опишите алгоритм добавления к этому дереву
нового
элемента A[n+1] и оцените его сложность.
4.(15) В док-ве
теоремы Кислицына о сложности нахождения второго
по величине
элемента введено отношение "А превосходит В".
Докажите,
что "чемпион" превосходит всех остальных игроков.
(Используйте
индукцию по числу игроков).
5.(15)
Модифицировать алгоритм МИНК так, чтобы первоначальная
последовательность
разбивалась на отрезки длины 7 ( а не 5 ).
Оценить
сложность получившегося алгоритма.
6.(10) Отсортировать
следующую последовательность методом слияния.
7,2,5,81,10,4,3,7,2,1,23,5, 6, 12, 22
Определить количество вызовов процедуры
СЛИ(А, В,С).
7. (15)
Напишите алгоритм, определяющий 2-ой наибольший элемент в массиве из 8
элементов с наименьшим (каким?) числом сравнений.
8.(15)
Предложите алгоритм сложности O(n),
который проверяет содержит ли ориентированный граф, заданный матрицей
смежностей, вершину, к которой ведут дуги из остальных (n –1) вершин и из которой не выходит ни
одна дуга.
Вариант 3
1.(10) Начертить двоичное дерево, соответствующее
формуле
(( a + b)*(w-s +
c)+ x) /( d-(f+g*(z+x+v))).
Выписать его узлы в суффиксном порядке.
2.(20) Написать эффективный алгоритм для
определения порядка вычисления произведения матриц М1 х М2 х ...х Мn,
минимизирующего число умножений элементов, в случае, когда каждая матрица Mi имеет один из размеров 1 х 1, 1 х d, d x
1, d x d при некотором фиксированном d . Он должен быть более быстрым, чем
алгоритм, который оптимизирует умножение произвольных матриц.
3.(15) В
основе алгоритма сортировки слиянием лежит слияние 2-х
упорядоченных массивов в один. Опишите
процедуру слияния
3-х упорядоченных массивов и соответствующий
алгоритм сортировки
и оцените его сложность.
4.(15)
Оценить сложность следующего алгоритма.
n - степень тройки.
procedure PEL( A[1..n]):
begin
y := МИНК(6,A); A[n/3-1] :=
2*y;
PEL(
A[1.. n/3-1]); PEL( A[n/3..2n/3-1]);PEL( A[2n/3..n-1]);
PEL(
A[n/2.. 5n/6 -1])
end
5.(15) Пусть
дан массив записей, который нужно отсортировать по ключу, имеющему 2 значения 0
и 1. Предложите алгоритм такой сортировки за линейное время и с дополнительной
памятью O(1).
6.(10)
Упорядочить последовательность 23,16,23,14,11,3,8,32,11, 10 применяя алгоритм быстрой сортировки
(разбиение массива производить
относительно медианы его концов и середины ). Сколько сравнений производится ? Какова теоретическая оценка
среднего числа сравнений в этом случае ?
7.(15) Какие
ответы бyдет давать "стpатегия дьявола" из теоpемы
Кислицына в
ответ на следyющие вопpосы:
a>b?; b>c?;
c>a?; a>d?; a>e?; f>g?; f>c?; a>f? b>f?
(если ответ
не опpеделен, пyсть "побеждает" игpок, стоящий в сpавнениии слева).
Какое отношение "Х пpевосходит Y" полyчается в pезyльтате?
8.(15) Пусть
А - упорядоченный массив положительных и отрицательных целых чисел:
A[1] < A[2] <...< A[n]. Написать алгоритм нахождения такого
i, что A[i] = i (если такое i
существует).Оценить его сложность ( "хороший" алгоритм имеет
сложность O(log n) ).
Вариант 4
1.(15) В
быстром алгоритме умножения двоичных чисел в операторе
u := (a + b)*(c + d);
числа a+b и
c+d могут иметь длину n/2 + 1 (а не n/2, как предполагалось при получении
рекуррентного соотношения T(n)=3T(n/2) + kn). Как уточнить алгоритм в этом случае,
чтобы
получить ту же оценку сложности?
2.(20) Пусть
правила умножения элементов алфавита {a, b, c} задаются равенствами: aa=b, ab=c, ac=a, ba=a, bb=b, bc=c, ca=a,cb=a, cc=c.Написать алгоритм, проверяющий по слову w в алфавите
{a,b,c},можно ли его сократить до a. Например, для w=bbbba имеем (b(bb))(ba)=a.
Оценить сложность предложенного алгоритма.
3.(15) Доказать, что время работы линейного
алгоритма МИНК для выбора
k-го наименьшего элемента T(n) <= 20
cn, где cn – время для n < 50.
4.(20) Идея алгоритма сортировки вставками
заключается в том, что
на этапе j ( j=2,3,...,n ) элемент A[j]
ставится на свое место
среди элементов A[1], A[2], ..., A[j-1].
Докажите, что следующая
программа сортирует массив A[1..n] и оцените
время ее работы.
FOR j = 2 UNTIL
n DO
BEGIN
x
:= A[j]; k:=1;
WHILE x > A[k] AND k<j DO
k := k + 1 ;
FOR
i=j UNTIL k+1 STEP -1 DO
A[i] := A[i-1];
A[k] := x
END.
5.(15) В док-ве
теоремы Кислицына о сложности нахождения второго по величине элемента
введено отношение "А превосходит В". Докажите, что оно транзитивно.
6.(10)
Используя алгоритм лексикографической сортировки,
упорядочить
последовательность:
ВОЛК,ЛООВ,КОВО,ВОЛО,ЛОКК,КВОК,КООЛ.
7.(15) Дано n целых чисел от 1 до k. Предложите алгоритм, который подвергает их предварительной
обработке, а затем за время O(1) отвечает на любой вопрос вида «сколько чисел
из данного набора лежит между a и b?»
Время предварительной обработки должно быть O(n+k).
8. (10)
Пусть дана хеш-функция для расстановки двухзначных чисел в таблице размера m=7:
h('AB')= (A * B)mod 7. Выполните следующие операции, используя внутренние цепи
при коллизиях:
ВСТАВИТЬ(25,07,91,31,14,44),УДАЛИТЬ(25,91),ВСТАВИТЬ(70,90).
Какова длина
максимальной внутренней цепи ?
Вариант 5
1.(15)
Выбрать представление дерева и написать алгоритм подсчета
для каждой
вершины числа ее потомков. Какова его сложность?
2.(15)
Доказать, что алгоритм, использующий
метод динамического программирования для распознавания кс-языка, порождаемого
кс-грамматикой в нормальной форме Хомского,
имеет
сложность O(n^3).
3.(20)
Рассмотрим следующую программу для разбиения множества S
на
подмножества S1 = {b | b из S, b < a} и S2={b | b из S,b>=a}.
Вход: массив A[1..n] и число a.
Выход: массив A'[1..n], в котором вначале идут элементы S1,
а затем - S2.
BEGIN i := 1; j := n;
WHILE i < j+1 DO
BEGIN
WHILE (A[j] => a) AND (j
> 0) DO j := j-1;
WHILE (A[i] <a )AND (i < n+1) DO
i := i +1;
IF i < j THEN
BEGIN
переставить A[i] и A[j];
i := i + 1;
j := j -1
END END
END.
Доказать правильность алгоритма и оценить
время работы.
4.(20) Пусть
S1, S2,..., Sk - множества чисел, лежащих между 1 и n,
и их суммарная мощность не больше n.
Описать алгоритм, упорядочивающий все множества Si за время O(n).
5.(15) В
док-ве теоремы Кислицына о сложности
нахождения второго
по величине
элемента введено отношение "А превосходит В".
Докажите,
что "чемпион" превосходит всех остальных игроков.
6.(10) Используя алгоритм лексикографической
сортировки, упорядочить
последовательность:
БАРР, АРАБ, КРАБ,
АРБА,БРАК,КАРК,БАБА, АББА.
Какова
теоретическая оценка сложности этого алгоритма?
7.(10)
Используя алгоритм вычисления дискретного логарифма,
определите
число операций, достаточное для вычисления x^23 mod g.
8. (10)
Пусть дана хеш-функция для расстановки двухзначных чисел в таблице размера m=7:
h('AB')= (A * B)mod 7. Выполните следующие операции, используя при коллизиях линейное опpобывание с фyнкцией hi(k) = [h('AB')+11*i] mod 7:
ВСТАВИТЬ(25,07,91,31,14,44),УДАЛИТЬ(25,91),ВСТАВИТЬ(70,90).
Подсчитайте
число коллизий (т.е. неyдачных попыток).