Вариант 1
1. Приведите определение следующего понятия,
сопроводив,
примером: 2-d-деревья.
При
решении каких задач оно применяется?
(10)
2.
Расположите следующие функции в порядке
возрастания (при n ®µ ):
a) n2 log3n
; b) n√ n/ n3 ; c) n3/ log100
n ; d) n1/10 / log4n;
e)2n log(n);
f) n 3n ; g) n0.05log10n; h) nlogn loglog n ; i) n 2lognn; j) n0.5loglog
n
(20)
3.
Пусть T – двоичное дерево поиска, с различными метками всех вершин. Пусть x - его лист, а y – отец вершины x в T. Покажите, что метки l(x) и l(y)
являются соседями в упорядоченном списке всех меток T.
(25)
4.
Найти минимальное остовное дерево для
неориентированного графа G=(V,E), где V={v1,v2,v3,v4,v5,v6,v7,v8,v9},
E = {(v1,v2,8), (v1,v3,2), (v3,v2,4),
(v3,v4,6), (v3,v5,8), (v4,v6,5),
(v5,v4,4), (v6,v1,7), (v6,v8,4), (v6,v7,3),
(v7,v5,1), (v7,v8,7),
(v8,v1,5), (v8,v9,3), (v9,v1,1)}
(третий
параметр в скобках - длина ребра).
(20)
5. Hаписать алгоpитм коppектиpовки
меток L:M во внyтpенних
веpшинах 2-3 деpева после выполнения опеpации
ВСТАВИТЬ.
Оценить
его сложность.
(25)
1. Приведите определение следующего
понятия, сопроводив
примером: красно-черное дерево.
В
решении каких задач оно применяется и какова сложность основных операций на нем
?
(10)
2.
Расположите следующие функции в порядке
возрастания (при n ®µ ):
b) 2nlog n log3n
; b) n√log n ; c) n2/ log1000 n ; d) n19/10
; e)2n log(n)/ nÖn
f) n 2n ; g) n1.5log10n; h) nlogn loglog n ; i) n log40n; j) n.2.5/
loglog n
(20)
3.
Построить алгоритм, который в B-дереве T
степени t по ключу k
находит
следующий за ним ключ k’, т.е. такой, что k < k’ и в T нет
такого ключа x, что k< x < k’, и возвращает ссылку на содержащую k’
вершину.
(25)
4.. Построить с помощью поиска в ширину остовной лес для неориентированного графа G = (V,E), где V = v1,v2,v3,v4,v5,v6,v7, v8,v9,v10,v11, E =(v1,v2),(v1,v5),(v1,v6),(v2,v6),(v3,v4),(v4,v7), (v3,v7),(v8,v3),(v3,v11),(v8,v7),(v8,v11)(v9,v10).
Применить к этому же графу поиск в глубину и
определить соответствующую нумерацию.
(20)
5.
Покажите, что, если для фиббоначиевых куч выполняются лишь операции добавления
вершины, слияния двух куч и удаления вершины с минимальным ключом, то в куче с n
вершинами все вершины имеют степень не больше
[ log2 n ].
(25)
1. Приведите определение следующего
понятия, сопроводив,
примером:
В-дерево степени n..
В
решении каких задач оно применяется? Какова сложность основных операций для
В-деревьев?
(10)
2.
Расположите следующие функции в порядке
возрастания (при n ®µ ):
c) n2 /log3n ; b) n√ n n3 ; c) n1.99 log100
n ; d) n1/10 log4n; e)nn / log(n);
f) n!/ 3n ; g) n0.05log10n; h) n2 logn + loglog n ; i) n 2lognn; j) n2
(loglog n)10/ log n
(20)
3.
Предложите алгоритм для реализации в фиббоначиевых кучах операции Change-Key(H, x, k),
которая присваивает ключу вершины x значение k.
Оцените
учетную стоимость этой операции (в вашей реализации) для случаев
k < x.key; k = x.key ; k > x.key.
(25)
4.
Построить с помощью поиска в глубину остовной лес и нумерацию вершин для ориентированного
графа G = (V,E), где V = {v1,v2,v3,v4,v5,v6,v7, v8},
E
={(v1,v2),(v1,v5),(v1,v6),(v2,v6),(v2,v3),(v8,v3),(v4,v8), (v8,v7), (v7,v4), (v4,v6)}.
Применить к этому же графу поиск в ширину и
определить соответствующую нумерацию.
(20)
5. Пyсть в pезyльтате
выполнения алгоpитма ПОГ на оpиентиpованном
гpафе G=(V,E) дyга (v,w)
оказалась попеpечной, т.е. v и w не являются
потомками
дpyг дpyга в постpоенном остовном лесе T. Доказать, что
тогда NUM[v] > NUM[w].
(25)
Вариант 4
1. Приведите определение следующего
понятия, сопроводив
примером: биномиальная куча
В
решении каких задач оно применяется? Какова сложность основных операций с
биномиальными кучами.
(10)
2.
Расположите следующие функции в порядке
возрастания (при n ®µ ):
d) n3 log3n
; b) (log n)n/ n3 ; c) n3log 4 n/log
log100 n ; d) n31/10 / log4n; e)2n Ön
f) n3 3n
; g) n3.05/ log10n; h) nlogn loglog n ; i) nlog n lognn; j) n2.5log
n
(20)
3.
Найти минимальное остовное дерево для
неориентированного графа G=(V,E), где V={v1,v2,v3,v4,v5,v6,v7,v8,v9},
E = {(v1,v2,5), (v1,v3,12), (v3,v2,4),
(v3,v4,2), (v3,v5,4), (v4,v6,15),
(v5,v4,9), (v6,v1,3), (v6,v8,8), (v6,v7,5),
(v7,v5,10), (v7,v8,7),
(v8,v1,7), (v8,v9,4), (v9,v1,11)}
(третий
параметр в скобках - длина ребра).
(20)
4. Пусть q - последовательность
операций ОБЪЕДИНИТЬ и НАЙТИ,
причем
все операции ОБЪЕДИНИТЬ входят в q перед
операциями
НАЙТИ.
Докажите, что алгоритм со сжатием путей выполняет q
за
время, пропорциональное длине q.
(25)
5. Рассмотpите модификацию алгоpитма
ПОШ для оpиентиpованного
гpафа G= (V, E), в
котоpой для каждой v из V L(v)={ w | (v,w) из V}, в стpокy 5
добавлен опеpатоp T:={}, а в стpокy 12
добавлен опеpатоp T:= T + {(w,u)}; .
Покажите,
что полyченный алгоpитм нyмеpyет все веpшины гpафа и
стpоит
остовной лес T.
(25)
Вариант 5
1. Приведите определение следуюшего
понятия, сопроводив,
примером: фиббоначиева куча
В
решении каких задач оно применяется? Какова сложность основных операций с
фиббоначиевыми кучами.
(10)
2.
Расположите следующие функции в порядке
возрастания (при n ®µ ):
e) n ! log3n
; b) 2√ n n3
; c) n / log100 n ; d) n9/10 log4n; e)2n!/ nn
f) n4 3n
; g) n1.05/ log10
(n+10); h) nlogn ; i)
n 2lognn; j) n0.91 /loglog7 n
(20)
3.. Построить с помощью поиска в ширину остовной лес для ориентированного графа G = (V,E), где V = v1,v2,v3,v4,v5,v6,v7, v8,v9,v10,v11, E =(v1,v2),(v1,v5),(v1,v6),(v2,v6),(v4,v3),(v4,v7), (v3,v7),(v8,v3),(v8,v11),(v8,v7),(v8,v10)(v9,v10).
Применить к этому же графу поиск в глубину и
определить соответствующую нумерацию.
(20)
4 Опишите красно-черное дерево, содержащее n>2
ключей, с наибольшим возможным отношением числа красных внутренних вершин к
числу черных внутренних вершин. Чему равно это отношение? Для какого дерева это
отношение будет наименьшим, и чему оно равно?
(25)
5. Пусть S= <V,T> -
остовное дерево наименьшей стоимости, пос-
троенное
алгоритмом Крускала. Пусть S' - произвольное остовное
дерево
со стоимостями ребер d1 <= d2
<=... <= dn. Показать, что
ci <= di для всех i: 1
<= i <= n.
(25)