1. B-drzewo:
jest drzewem zrównoważonym
jest
drzewem binarnym
jest
drzewem binarnym pełnym
jest
drzewem AVL
ma
operację sumowania elementów w czasie
2. Drzewo AVL:
koszt pesymistyczny wyszukiwania elementu
wynosi O(logn)
jest drzewem BST
jest drzewem binarnym
3. Wstawiamy do
pustego drzewa BST kolejno: 1 0 3 4 6 2 5. Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
0
2 5 6 4 3 1
0
2 5 6 4 3 1
0 1 2 3 4 5 6
4. Wstawiamy do
pustego drzewa BST kolejno: 6 4 3 5 2 0 1. Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
1 0 2 3 5 4 6
1 0 2 3 5 4 6
0 1 2 3 4 5 6
5. Wstawiamy do
pustego drzewa BST kolejno: 0 4 1 2 3 6 5. Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
0 1 2 3 4 5 6
3
2 1 5 6 4 0
3
2 1 5 6 4 0
6. Wstawiamy do
pustego drzewa BST kolejno: 4 0 6 1 3 5 2. Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
2
3 1 0 5 6 4
2
3 1 0 5 6 4
0 1 2 3 4 5 6
7. Wstawiamy do
pustego drzewa BST kolejno: 2 0 6 4 3 1 5.Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
1
0 3 5 4 6 2
1
0 3 5 4 6 2
0 1 2 3 4 5 6
8. Wstawiamy do
pustego drzewa BST kolejno: 2 5 3 6 1 0 4 .Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
0 1 2 3 4 5 6
0
1 4 3 6 5 2
0
1 4 3 6 5 2
9. Wstawiamy do
pustego drzewa BST kolejno: 3 2 5 4 0 6 1 .Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
1
0 2 4 6 5 3
0 1 2 3 4 5 6
1
0 2 4 6 5 3
10. Wstawiamy do
pustego drzewa BST kolejno: 3 0 6 2 4 1 5. Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
1
2 0 5 4 6 3
1
2 0 5 4 6 3
0 1 2 3 4 5 6
11. Wstawiamy do
pustego drzewa BST kolejno: 6 4 5 1 0 2 3. Wypisując wartości węzłów przy przejściu
drzewa w porządku inorder, otrzymamy:
0 1 2 3 4 5 6
0
3 2 1 5 4 6
0
3 2 1 5 4 6
12. Wstawiamy do
pustego drzewa BST kolejno: 5 1 0 3 6 2 4. Wypisując wartości węzłów przy
przejściu drzewa w porządku inorder, otrzymamy:
0 1 2 3 4 5 6
0
2 4 3 1 6 5
0
2 4 3 1 6 5
13. Wstawiamy do
pustego drzewa BST kolejno: 6 0 5 3 1 4 2. Wypisując wartości węzłów przy
przejściu drzewa w porządku postorder, otrzymamy:
2 1 4 3 5 0 6
2 1 4 3 5 0 6
0
1 2 3 4 5 6
14. Wstawiamy do
pustego drzewa BST kolejno: 2 6 0 3 5 4 1. Wypisując wartości węzłów przy
przejściu drzewa w porządku postorder, otrzymamy:
1 0 4 5 3 6 2
1 0 4 5 3 6 2
0
1 2 3 4 5 6
15. Wstawiamy do
pustego drzewa BST kolejno: 1 5 3 2 0 6
4. Wypisując wartości węzłów przy przejściu drzewa w porządku postorder,
otrzymamy:
0 2 4 3 6 5 1
0 2 4 3 6 5 1
0 1
2 3 4 5 6
16. Wstawiamy do
pustego drzewa BST kolejno: 3 0 6 2 4 1 5. Wypisując wartości węzłów przy
przejściu tego drzewa w porządku postorder, otrzymamy:
0 1 2 3 4 5 6
1 2 0 5 4 6 3
1 2 0 5 4 6 3
17. Wstawiamy do
pustego drzewa BST kolejno: 2 6 0 3 5 4
1. Wypisując wartości węzłów przy przejściu tego drzewa w porządku
postorder, otrzymamy:
1 0 4 5 3 6 2
1 0 4 5 3 6 2
0 1 2 3 4 5 6
18. Wstawiamy do
pustego drzewa BST kolejno: 1 4 3 2 5 0 6. Wypisując wartości węzłów przy przejściu
drzewa w porządku postorder, otrzymamy:
0 2 3 6 5 4 1
0 2 3 6 5 4 1
0
1 2 3 4 5 6
19. Wstawiamy do
pustego drzewa BST kolejno: 1 5 3 2 0 6 4. Wypisując wartości węzłów przy
przejściu drzewa w porządku postorder, otrzymamy:
0 2 4 3 6 5 1
0 2 4 3 6 5 1
0
1 2 3 4 5 6
20. Mamy graf niekierowany:
a--b, b--c, c --a. Wykonujemy na nim DFS z punktu ”a” i oznaczamy czasy
rozpoczęcia i zakończenia. Notując x (p/f), gdzie x-wierzchołek, p-czas
rozpoczęcia, f-czas zakończenia przetwarzania, możemy otrzymać:
a(0/5),
b(1/3), c(2/4)
a(0/3),
b(1/4), c(2/5)
a(0/5),
b(1/2), c(3/4)
21. Mamy graf
skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, b->c,
c->d, d->a. Jest on:
drzewem
pełny
acykliczny
22. Mamy graf
skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, a->c,
b->a, b->c, c->a, c->b. Jest on:
spójny
drzewem
pełny
acykliczny
23. Mamy graf
skierowany złożony z wierzchołków {a,b} i krawędzi a->b, b->a. Jest on:
pełny
acykliczny
spójny
24. Mamy graf
skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b. Jest on:
acykliczny
spójny
pełny
25. Mamy graf
skierowany złożony z wierzchołków {a} i krawędzi a->a. Jest on:
pełny
acykliczny
drzewem
spójny
26. Mamy graf
skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, c->d. Jest
on:
acykliczny
spójny
pełny
27. Mamy graf
skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, b->a,
c->d, d->c. Jest on:
spójny
drzewem
pełny
acykliczny
28. Listę, ze
zmodyfikowaną operacją get, który przesuwa żądany element na początek listy:
warto używać, kiedy większość operacji get
tyczy się małego podzbioru elementów tej listy
warto
używać, kiedy większość operacji get tyczy się różnych elementów tej listy
warto używać, kiedy większość operacji
tyczy się jednego elementu
zawsze
warto używać, kiedy większość operacji, to operacje get
warto
używać dla losowych danych
29. Listę, ze
zmodyfikowaną operacją get, który przesuwa żądany element na koniec listy:
warto
używać, kiedy większość operacji tyczy się jednego elementu
zawsze
warto używać, kiedy większość operacji, to operacje get
warto używać, kiedy większość operacji get
tyczy się różnych elementów tej listy
warto
używać, kiedy większość operacji get tyczy się małego podzbioru elementów tej
listy
warto
używać, dla losowych danych
30. Które z
niżej wymienionych wymagają co najmniej O(n) dodatkowej pamięci:
CountSort
Sortowanie
bąbelkowe
SelectionSort
31. Porównując
(dla danego algorytmu) złożoność
pesymistyczną pamięciową z oczekiwaną obliczeniową:
mogą być sobie równe
pierwsza jest (zawsze) nie lepsza od
drugiej
pierwsza
jest (zawsze) gorsza od drugiej
32. Porównując
(dla danego algorytmu) złożoność
pesymistyczną pamięciową z oczekiwaną pamięciową:
pierwsza
jest (zawsze) gorsza od drugiej
pierwsza jest (zawsze) nie lepsza od
drugiej
pierwsza
może być lepsza od drugiej
33. Porównując
(dla danego algorytmu) złożoność
pesymistyczną obliczeniową z oczekiwaną pamięciową:
pierwsza
jest (zawsze) gorsza od drugiej
pierwsza jest (zawsze) nie lepsza od
drugiej
mogą być sobie równe
34. Porównując
(dla danego algorytmu) złożoność
pesymistyczną obliczeniową z optymistyczną obliczeniową:
pierwsza
może być lepsza od drugiej
pierwsza
jest (zawsze)gorsza od drugiej
mogą być sobie równe
pierwsza jest (zawsze) nie lepsza od
drugiej
35. Porównując
(dla danego algorytmu) złożoność
pesymistyczną obliczeniową z oczekiwaną obliczeniową:
pierwsza
jest (zawsze)gorsza od drugiej
mogą być sobie równe
pierwsza może być lepsza od drugiej
36. Porównując
(dla danego algorytmu) złożoność oczekiwaną
obliczeniową z oczekiwaną pamięciową:
pierwsza
jest (zawsze) gorsza od drugiej
pierwsza
jest (zawsze) nie lepsza od drugiej
mogą być sobie równe
37. Porównując
(dla danego algorytmu) złożoność oczekiwaną
obliczeniową z optymistyczną pamięciową:
mogą być sobie równe
pierwsza jest (zawsze) nie lepsza od
drugiej
pierwsza
jest (zawsze) gorsza od drugiej
38. Szybkiej transformaty
Fouriera używamy do:
analizy i obróbki sygnałów dźwiękowych
znajdowania
najkrótszej ścieżki w grafie
mnożenia wielomianów
mnożenia liczb
sortowania
39. Jakie jest
najlepsze oszacowanie na złożoność problemu znajdowania największego elementu w
posortowanej tablicy rozmiaru n:
O(n)
O(lgn)
O(1)
40. Jakie jest
najlepsze oszacowanie na złożoność problemu znajdowania największego elementu w
danej tablicy rozmiaru n:
O(n)
O(lgn)
O(1)
41. Mnożenie
dwóch n-cyfrowych liczb da się wykonać w czasie:
O(nlogn)
O(n2)
O(nlog23))
O(n)
42. Dla
posortowanej niemalejąco tablicy A następujący algorytm:
I=0;
p=n-1;
while(I<p){
s=(I+p+1)/2;
if(x<A[s])
p=s-1;
else
I=s;
}
return I:
oblicza indeks ostatniego wystąpienia
największej liczby nieprzekraczającej x
oblicza
indeks ostatniego wystąpienia najmniejszej liczby nieprzekraczającej x
oblicza
indeks pierwszego wystąpienia najmniejszej liczby co najmniej równej x
oblicza
indeks ostatniego wystąpienia x w A
oblicza
indeks pierwszego wystąpienia x w A
oblicza
indeks pierwszego wystąpienia największej liczby nieprzekraczającej x
zawsze działa w czasie O(logn)
może
się zapętlić
43. Algorytm
Karacuby służy do:
analizy
i obróbki sygnałów dźwiękowych
przechodzenia
grafu
znajdowania
najkrótszej ścieżki w grafie
sortowania
mnożenia wielomianów
mnożenia liczb
44. Stabilne są
algorytmy sortowania:
Insertionsort
Selectionsort
MergeSort
HeapSort
QuickSort
45. Spośród następujących
rzędów złożoności minimalne są:
O(2log n)
O(n
log n)
O(ln 2n)
46. Spośród
następujących rzędów złożoności minimalne są:
O(ln 2n)
O(log102n)
O(nlogn)
47. Algorytm
Bluma-Floyda-Pratta-Rivesta-Tarjana znajdowania k-tego co do wielkości elementu
w n-elementowym zbiorze zaczyna się od podziału na m-elementowe podzbiory dla
m=5. Gdyby analogicznie pomysł wykorzystać dla innej, ale ustalonej z góry
liczności m, to liniową złożoność pesymistyczną uzyskalibyśmy dla:
m=3
m=n/5
m=7
m=√(n)
48. Jeżeli
pewien algorytm działa w pesymistycznym
czasie O(n) dla danych wielkości n, to będzie działał w pesymistycznym czasie
O(n) również dla danych wielkości:
n+1
2n
2n + 2ln n
logn
nlogn
2n + 2ln n
n2
49. Jeżeli
pewien algorytm działa w pesymistycznym
czasie O(nlogn) dla danych wielkości n, to będzie działał w pesymistycznym
czasie O(nlogn) również dla danych wielkości:
n+1
2n + 2ln n
nlogn
2n
n2
logn
50. Jeżeli
pewien algorytm działa w pesymistycznym czasie O(logn) dla danych wielkości n,
to będzie działał w pesymistycznym czasie O(logn) również dla danych wielkości:
2n
logn
n2
51. Rozważmy
graf pełny z wagami G=(V,E), gdzie |V| =n, wtedy:
rozmiar tablicy list incydencji grafu G
jest rzędu Θ(n2)
rozmiar macierzy sąsiedztwa grafu G jest
rzędu Θ(n2)
rozmiar
macierzy sąsiedztwa grafu G jest rzędu Θ(n)
rozmiar tablicy list incydencji grafu G
jest rzędu Ω(n)
rozmiar tablicy list incydencji grafu G
jest rzędu Ω(n)
52. Rozważmy algorytm
sortowania przez zliczenie CS zastosowany do sortowania n-elementowego ciągu
binarnego X, wtedy:
w
tym przypadku rezultatem działania algorytmu CS będzie ciąg binarny uporządkowany
nierosnąco
S(CS(X),n)= Θ(n2)
T(CS(X),n,m)=Œ(n+m), gdzie m jest
stałą nie większą niż 4
A(CS(X),n)≠W(CS(X),n)
S(CS(X),n)= Θ(n)
53. Rozważmy
algorytm sortowania przez wstawianie IS, z binarnym wyszukiwaniem pozycji dla
wstawianego elementu, zastosowany do danych
wejściowych rozmiaru n, wtedy:
W(IS,n)=O(n×lg(n)), jeżeli operacją
dominującą jest przestawianie danych
W(IS,n)=Ω(A(IS,n)), jeżeli operacją
dominującą jest porównywanie danych
W(IS,n)= Θ (A(IS,n)), jeżeli operacją
dominującą jest przestawianie danych
W(IS,n)=
Θ(n2), jeżeli operacją dominującą jest przestawianie danych
W(IS,n)=O(n×lg(n)),
jeżeli operacją dominującą jest porównywanie danych
54. Rozważmy zastosowanie
algorytmu sortowania przez scalanie MS do uporządkowanych nierosnąco danych
wejściowych X rozmiaru n, wtedy:
T(MS(X),n)= Θ(lg(n!))
w
tym przypadku wysokość drzewa wywołań rekurencyjnych algorytmu MS będzie nie
mniejsza niż n
T(MS(X),n)=
O(n)
55. Rozważmy
algorytm HeapSort zastosowany do sortowania n-elementowego ciągu wejściowego
zapisanego w tablicy X, wtedy:
W(HeapSort(X),n)=O(n),
jeżeli operacją dominującą jest czynność przedstawiania elementów tablicy
algorytm HeapSort sortuje dane wejściowe w
miejscu
w
drzewie decyzyjnego algorytmu HeapSort zastosowanego do rozważanych danych może
istnieć ścieżka korzeń-liść, której długość jest rzędu O(n)
S(HeapSort(X),n)=O(1)
56. Niech Alg
będzie optymalnym algorytmem dla problemu wyszukania pewnego
elementu(zakładamy, że takowy istnieje) w n-elementowym nieuporządkowanym
uniwersum, wtedy:
A(Alg,
n)= Ω(nxlg(n))
W(Alg,
n)=O(n1/2)
A(Alg, n)=O(W(Alg,n))
57. Rozważmy
graf pełny G=(V,E), gdzie V=a,b,c,d,e,f,g wtedy:
koszt algorytmu BFS dla rozważanego grafu G
jest rzędu O(|V|+|E|)
kolejność
odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm BFS
jest następująca: d,c,e,b,f,a,g, jeżeli wierzchołki wybieramy w porządku
odwrotnym do alfabetycznego
kolejność odwiedzania wierzchołków grafu G
z wierzchołka startowego d przez algorytm BFS jest następująca: d,g,f,e,c,b,a,
jeżeli wierzchołki wybieramy w porządku odwrotnym do alfabetycznego
kolejność
odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm BFS
jest następująca: d,a,b,c,e,f,g,
jeżeli
wierzchołki wybieramy w porządku alfabetycznym
koszt
algorytmu BFS dla rozważanego grafu G jest rzędu Θ(|V|)
koszt
algorytmu DFS dla rozważanego grafu G jest rzędu O(|V|)
kolejność
odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm DFS
jest następująca: d,a,g,b,f,c,e jeżeli wierzchołki wybieramy w porządku alfabetycznym
kolejność odwiedzania wierzchołków grafu G
z wierzchołka startowego d przez algorytm DFS jest następująca: d,a,b,c,e,f,g
jeżeli wierzchołki wybieramy w porządku alfabetycznym
58. Rozważmy
graf G=(V,E), gdzie |V|=n i n>10, w
którym algorytmy DFS oraz BFS generują ten sam ciąg etykiet odwiedzanych
wierzchołków z pewnego wierzchołka źródłowego, wtedy graf G może być:
grafem-drzewem
binarnym wysokości Θ(lg(n))
grafem pustym
grafem-gwiazdą, tj. grafem spójnym takim,
że każdy wierzchołek tego grafu ma rząd równy 1 za wyjątkiem wierzchołka
centralnego, którego rząd jest równy n-1
grafem-drzewem binarnym wysokości n-1
59. Niech H
będzie kopcem-drzewem typu min powstałym przez kolejne wstawianie wierzchołków
o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktury, wtedy:
wierzchołki kopca-drzewa H wypisane w
kolejności PreOrder tworzą ciąg: 0,1,5,8,6,7,2,4,3
wierzchołki kopca-drzewa H wypisane w
kolejności InOrder tworzą ciąg: 8,5,6,1,7,0,4,2,3
wysokość kopca-drzewa H jest rzędu lg(n),
gdzie n jest liczbą wierzchołków rozważanego drzewa
wysokość kopca-drzewa H jest równa 3
jeżeli w kopcu-drzewie H wykonamy operację
delmin, to etykiety kopca-drzewa będącego rezultatem rozważanej operacji
sczytane w kolejności InOrder tworzą ciąg 1,2,3,4,5,6,7,8
jeżeli w kopcu-drzewie H wykonamy operację
delmin, to etykiety kopca-drzewa będącego rezultatem rozważanej operacji
sczytane w kolejności PostOrder tworzą ciąg 8,6,7,5,4,3,2,1
liczba liści na ostatnim poziomie
kopca-drzewa H jest równa 2
jeżeli w kopcu-drzewie H wykonamy operację
delmin, to etykiety kopca-drzewa będącego rezultatem rozważanej operacji sczytane w kolejności PreOrder tworzą 1,2,5,6,7,4,3,8
wysokość kopca-drzewa H jest niezależna od
kolejności wstawiania rozważanych wierzchołków
60. Niech D
będzie drzewem decyzyjnym dla pewnego algorytmu sortowania przez porównania
zastosowanego do danych wejściowych rozmiaru n, wtedy:
liczba
liści w drzewie D jest co najwyżej rzędu n2
liczba liści w drzewie D jest co najmniej
rzędu nn
wysokość
drzewa D jest rzędu co najwyżej lg(n!)
wysokość drzewa D jest rzędu co najmniej
lg(n!)
61. Niech T
będzie drzewem BST powstałym przez losowe
wstawianie wierzchołków o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej
struktury, wtedy:
wierzchołki
drzewa T wypisane w kolejności InOrder tworzą ciąg nierosnący
wierzchołki drzewa T wypisane w kolejności
InOrder mogą odpowiadać ciągowi wierzchołków w kolejności PostOrder
wysokość
drzewa T jest równa co najwyżej 5
wysokość drzewa T jest zależna od kolejności
wstawiania rozważanych wierzchołków i w przypadku pesymistycznym może być równa
8
wysokość drzewa T jest równa co najmniej
lg(n), gdzie n jest liczbą wierzchołków rozważanego drzewa
62. Niech T
będzie drzewem BST powstałym przez kolejne
wstawianie wierzchołków o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej
struktury, wtedy:
wysokość
drzewa T jest równa co najwyżej lg(n), gdzie n jest liczbą wierzchołków
rozważanego drzewa
wierzchołki
drzewa T wypisane w kolejności InOrder tworzą ciąg 8,0,1,2,3,4,7,5,6
usunięcie wierzchołka z etykietą 8 w
drzewie T prowadzi do drzewa, którego korzeniem będzie wierzchołek z etykietą 2 usunięcie
wierzchołka z etykietą 2 w drzewie T prowadzi do drzewa, w którym w miejscu
wierzchołka z etykietą 2 znajdzie się wierzchołek z etykietą 1 lub 3
usunięcie
wierzchołka z etykietą 2 w drzewie T prowadzi do drzewa, w którym w miejscu
wierzchołka z etykietą 2 znajdzie się wierzchołek z etykietą 4
63. Załóżmy, że
kolejka Q zawiera n elementów i że wykonujemy jedynie operacje zdefiniowane w
strukturze kolejek, wtedy:
wycięcie
z kolejki Q elementu znajdującego się w odległości n/4 względem początku
kolejki wymaga wcześniejszego wyjęcia z kolejki 3n/4±1 elementów
wycięcie
z kolejki Q elementu znajdującego się w odległości n względem końca kolejki
wymaga wcześniejszego wyjęcia z kolejki n±1 elementów
wycięcie z kolejki Q elementu znajdującego
się w odległości n/4 względem początku kolejki wymaga wcześniejszego wyjęcia z
kolejki n/4±1 elementów
wycięcie
z kolejki Q elementu znajdującego się w odległości 1 względem początku kolejki
wymaga wcześniejszego wyjęcia z kolejki n±1 elementów
używając tylko co najwyżej dwóch kolejek
pomocniczych Q1 oraz Q2 i operacji kolejkowych można odwrócić kolejność
elementów w kolejce Q
64. Załóżmy, że stos
S zawiera n elementów i że wykonujemy jedynie operacje zdefiniowane w
strukturze stosów, wtedy:
zdjęcie ze stosu S elementu znajdującego
się na wysokości n/4 względem góry stosu wymaga wcześniejszego zdjęcia ze stosu
n/4±1 elementów
zdjęcie ze stosu S elementu znajdującego
się na wysokości n względem góry stosu wymaga wcześniejszego zdjęcia ze stosu
n±1 elementów
używając tylko co najwyżej dwóch stosów
pomocniczych S1 i S2 i operacji stosowanych można odwrócić kolejność elementów
na stosie S
zdjęcie
ze stosu S elementu znajdującego się na wysokości 1 względem góry stosu wymaga
wcześniejszego zdjęcia ze stosu n±1 elementów
65. Nazwa
struktury danych AVL i związany z nią algorytm pochodzi od:
pierwszych
liter nazwisk trzech twórców tej metody
pierwszych
liter angielskiego skrótu opisującego najważniejszą cechę tej struktury
nazwy
uniwersyteckiej ligi siatkówki, której pasjonatami byli jej twórcy
66. Niech T
będzie drzewem AVL powstałym przez kolejne wstawianie wierzchołków o etykietach
8,2,4,7,6,1,3,0,5 do początkowo pustej struktury, wtedy:
wysokość
drzewa jest równa 4
w
trakcie budowy drzewa wykonamy co najmniej dwie podwójne rotacje
w trakcie budowy
drzewa T wykonamy dwie podwójne i jedną pojedynczą rotację
wysokość drzewa
jest niezależna od kolejności wstawiania rozważanych wierzchołków
wierzchołki drzewa wypisane w
kolejności PreOrder tworzą ciąg 3,4,2,1,0,7,6,5,8
wierzchołki drzewa wypisane w
kolejności PostOrder tworzą ciąg 0,1,3,2,5,6,8,7,4
wierzchołki
drzewa wypisane w
kolejności InOrder tworzą ciąg 0,1,2,3,4,5,6,7,8
67. Kopiec
n-elementowy można:
przekształcić
w kopiec odwrotny(z najmniejszym, a nie największym elementem w każdym
korzeniu) w czasie O(n)
rozebrać
w czasie O(n)
utworzyć w czasie O(n)
scalić z innym kopcem n-elementowym (czyli
utworzyć nowy kopiec z tych dwóch) w czasie O(n)
68. Które z
poniższych zdań jest zawsze prawdziwe w strukturze kolejek priorytetowych typu
min:
empty(pq)→empty(delmin(insert(insert(pq,e),e)))
min(pq)=min(insert(delmin(pq),min(pq)))
min(pq)=min(insert(pq,e))
empty(pq)→empty(delmin(insert(pq,e),e))
69. Które z
poniższych zdań jest zawsze prawdziwe w strukturze kolejek:
¬empty(q) → empty(out(q))=true
¬empty(q) →first(q)≠first(in(out(q),e))
out(in(in(q,e),e))=in(out(in(q,e)),e)
70. Niech X=[0,3,2,4,3,3,2,0,0]
będzie tablicą danych wejściowych dla algorytmu sortowania przez zliczenie CS,
wtedy:
stan
tablicy pomocniczej, w której odbywa się zliczanie, po zakończeniu
sumowania(tj. tuż po 3-ciej pętli iteracyjnej algorytmu CS) jest następujący
[3,3,5,7,9]
stan
tablicy pomocniczej, w której odbywa się zliczanie, po zakończeniu
sumowania(tj. tuż po 3-ciej pętli iteracyjnej algorytmu CS) jest następujący [2,3,5,8,9]
rozmiar tablicy pomocniczej niezbędnej do
realizacji czynności zliczania w algorytmie CS jest nie mniejszy niż 5
stan tablicy pomocniczej, w której odbywa
się zliczanie, po zakończeniu sumowania(tj. tuż po 2-giej pętli iteracyjnej
algorytmu CS) jest następujący [3,0,2,3,1]
71. Które z
poniższych zdań jest prawdziwe: NIEopracowane
istnieje
algorytm, który z zadanego n-wierzchołkowego kopca-drzewa konstruuje drzewo BST
w czasie O(n)
istnieje
algorytm, który konstruuje kopiec-drzewo z losowego ciągu n elementów
wejściowych w czasie O(n)
istnieje
algorytm, który z zadanego n-wierzchołkowego drzewa AVL konstruuje
kopiec-drzewo w czasie O(n1/2)
istnieje
algorytm, który konstruuje kopiec-drzewo z losowego ciągu n elementów
wejściowych w czasie O(lg(n))
istnieje
algorytm, który z zadanego n-wierzchołkowego kopca-drzewa konstruuje drzewo AVL
w czasie O(n× lg(n))
72. Rozważmy
algorytm Alg i korzeń drzewa binarnego root, gdzie Alg(root)=
{
if(root==NULL)
return
0
else
if(root.left==NULL AND root.right==NULL)
return
1
else
return Alg(root.left) + Alg(root.right) +1
},
wtedy:
rezultatem
wywołania algorytmu Alg dla drzewa binarnego o korzeniu root jest liczba
wierzchołków zewnętrznych tego drzewa
rezultatem wywołania algorytmu Alg dla
drzewa binarnego o korzeniu root jest liczba wierzchołków tego drzewa
rezultatem
wywołania algorytmu Alg dla drzewa binarnego o korzeniu root jest liczba
wierzchołków wewnętrzn. tego drzewa
S(Alg, root)=Θ(n), gdzie n jest liczbą
wierzchołków drzewa o korzeniu root i uwzględniamy stos wywołań rekurencyjnych
rezultatem
wywołania algorytmu Alg dla drzewa binarnego o korzeniu root jest wysokość tego
drzewa
73. Rozważmy
algorytm Alg(n)=
{
int k=1, x=1;
while(k<n)
do
k=k+1;
x=x*k
od
}.
Która z wymienionych poniżej formuł jest
niezmiennikiem pętli iteracyjnej w algorytmie Alg?
x=1+2+3+…+(k-1)+k
x=x*k
i k ≤x
x=k!
x=k! i x≥k
x=k!
i s≥k
k
≤n
74. Rozważmy
algorytm Alg(n)=
{
int s=0, k=1;
while(k<=n) do
s=k*k;
k=k+1
od
}.
Które z poniższych zdań jest prawdziwe:
algorytm Alg zatrzymuje się dla dowolnej
parzystej liczby naturalnej
algorytm
Alg jest całkowicie poprawny dla warunku początkowego i końcowego odpowiednio
WP=(n jest liczbą naturalną) oraz WK=(s=Σni=1 (i+k2))
algorytm
Alg nie zatrzymuje się dla dowolnej liczby naturalnej n≥210
75. Rozważmy
algorytm Alg(n)=
{
int s=0, k=1;
while(k<=n) do
s=s+k*k;
k=k+1
od
}.
Które z poniższych zdań jest prawdziwe:
Algorytm
Alg jest całkowicie poprawny dla warunku początkowego i końcowego odpowiednio
WP=(n jest liczbą naturalną) oraz WK=(s=Σni=1(i-1)2)
Algorytm
Alg jest całkowicie poprawny dla warunku początkowego i końcowego odpowiednio
WP=(n jest liczbą naturalną) oraz WK=(s=Σni=1(i+k)2)
Algorytm Alg jest częściowo poprawny dla
warunku początkowego i końcowego odpowiednio WP=(n jest liczbą naturalną) oraz
WK=(s=Σni=1 i2)
76. Rozważmy
algorytm Alg(n)=
{
if(n=
=0)
return
3
else return Alg(n-1) + Alg(n-1) +
Alg(n-1))
},
wtedy dla n naturalnego:
S(Alg,
n)=Θ(n), jeżeli uwzględnimy stos wywołań rekurencyjnych
S(Alg, n)=O(n), jeżeli nie uwzględnimy stos
wywołań rekurencyjnych
W(Alg,
n)≠ Θ(A(Alg,n))
Alg(n)=3n
T(Alg, n)=Ω(3n)
77. Rozpatrujemy
całkowitą poprawność algorytmu, poprzez metodę niezmienników pętli. Jesteśmy w
miejscu, tuż po zakończeniu pętli. Wiemy, że:
zachodzi zaprzeczenie dozoru pętli
zachodzi zaprzeczenie dozoru pętli oraz
niezmiennik pętli z ostatniej iteracji
zachodzi
dozór pętli oraz niezmiennik pętli z ostatniej iteracji
78. Przy
haszowaniu otwartym z uporządkowanymi listami wykonanie k operacji insert do
pustej n-elementowej tablicy:
pesymistycznie kosztuje O(k2)
pesymistycznie
kosztuje O(n2)
średnio kosztuje O(k2/n)
79. Przy założeniu,
że n>
j=n;
x=k;
while(j!=0)
{
x+=j;
j--;
}
poprawnym niezmiennikiem jest:
parzystość
zmiennych j oraz x są zawsze różne
jeśli pętla wykonała co najmniej 4 obroty,
to parzystość x oraz j są takie same, jak cztery obroty pętli wcześniej
x≥0
j ≥0
80. Sortowanie
radixsort pozwala posortować n elementów szybciej niż w czasie O(nlogn) m.in.
dzięki temu, że:
NIEopracowane
reprezentacje
elementów z sortowanego zbioru mają określoną i stałą ze względu na n długość
liczoną w bitach
algorytm
countsort jest stabilny
nie
wykonujemy bezpośrednich operacji na elementach, tylko odwołujemy się do ich
reprezentacji bitowej
81. Aby otrzymać
B-drzewo o wysokości 2 dla t=5
wstawić
co najwyżej 1000 elementów
doprowadzić do sytuacji, w której łącznie
będzie co najmniej 9 węzłów
ustalić
jego stopień na co najmniej 5
należy
po zainicjalizowaniu pustego drzewa wstawić co najmniej 25 elementów
82. Rozważmy
drzewo T typu AVL powstałe przez losowe wstawianie wierzchołków o etykietach
1,2,3,…., n-1,n do początkowo pustej struktury, wtedy:
w drzewie T może istnieć ścieżka
korzeń-liść, której długość jest rzędu O(n1/2)
wysokość drzewa T jest nie większa niż c×n, gdzie c jest pewną stałą
w
drzewie T może istnieć ścieżka korzeń-liść, której długość jest rzędu lg(lg(n))
usunięcie pewnego wierzchołka z drzewa T
może wymagać wykonania co najwyżej jednej podwójnej rotacji
usunięcie pewnego wierzchołka z drzewa T
może wymagać wykonania Θ(lg(n)) rotacji
wstawienie wierzchołka z etykietą n+1 do
drzewa T wymaga wykonania co najwyżej jednej podwójnej rotacji
wstawienie
wierzchołka z etykietą n+1 do drzewa T wymaga Θ(n) rotacji
wysokość drzewa T jest nie większa niż
c×lg(n), gdzie c jest pewną stałą
83. Które z
poniższych zdań jest zawsze prawdziwe w strukturze słowników:
┐member(insert(delete(d,e),e),e)
empty(d)↔empty(delete(insert(insert(d,e),e),e))
member(insert(delete(d,e),e),e)
┐empty(d) ↔
empty(delete(insert(insert(d,e),e),e))
84. Które z
poniższych zdań jest zawsze prawdziwe w strukturze stosów:
┐empty(s)→top(s)≠top(push(pop(s),e))
empty(s)→ ┐empty(pop(push(s,e))
┐empty(s)→top(pop(push(s,top(s))))=top(s)
85. Mamy pewien
algorytm o złożoności obliczeniowej O(n2), zmierzyliśmy czas
działania dla pewnych danych o dużej liczbie elementów, równej n i czas wyniósł
t.
Szacunkowo, algorytm w ciągu 4t, jest w
stanie przetworzyć dane o wielkości 2n
Szacunkowo,
algorytm w ciągu 16t, jest w stanie przetworzyć dane o wielkości 8n
Szacunkowo, algorytm w ciągu 8t, jest w
stanie przetworzyć dane o wielkości 2n
Szacunkowo,
algorytm dla danych wielkości 4n, będzie działać 4t.
Szacunkowo, algorytm w ciągu 64t, jest w
stanie przetworzyć dane o wielkości 8n
86. Dana jest
funkcja laszująca h(i)=i mod17 oraz rehaszująca r(i)=(i+3)mod17. Korzystając z
tych funkcji wprowadzamy do początkowo pustej tablicy intA[16] kolejno
wartości: 6,0,20,13,3,17. Po wprowadzeniu tych liczb:
trzy liczby znajdują się pod indeksami im
równymi
0 poprzedza wszystkie inne wprowadzone
wartości
3
występuje przed 6
17
znajdzie się po wszystkich wprowadzonych wartościach
87. Wyznaczenie
operacji(i) dominującej/ych jest potrzebne do określenia:
złożoności optymistycznej pamięciowej
złożoności oczekiwanej pamięciowej
złożoności oczekiwanej obliczeniowej
88. Analizujemy
częściową poprawność algorytmu. Powinniśmy więc sprawdzić:
własność stopu
krok
indukcyjny
czy niezmiennik pętli jest prawdziwy po
wejściu do pętli dla danych spełniających warunek początkowy
czy
niezmiennik pętli jest prawdziwy po wejściu do pętli dla każdych danych wejściowych
89. Niech f(n)=n
2 lg(n), wtedy prawdą jest, że:
f(n) × f(n)=Ω(n3)
f(n)
× f(n)= Θ(n3)
f(n) =O(n3)
f(n)
= Ω (2n)
f(n)=Θ (n2)
f(n)+f(n)=Θ(n3)
f(n)+f(n)=O(n3)
90. Pesymistycznie
operacja wyszukiwania elementu w n-elementowym drzewie AVL: Niech f(n)=n 2 lg(n),
wtedy prawdą jest, że:
wymaga
Θ(logn) pamięci
ma złożoność obliczeniową O(lg n)
wymaga Θ(1) pamięci
91. Rozważmy
algorytm Hoare’a wyszukania elementu k-tego co do wielkości w nieuporządkowanym
uniwersum rozmiaru n, wtedy:
złożoność pesymistyczna algorytmu jest
rzędu co najmniej n
złożoność
średnia algorytmu jest rzędu co najwyżej lg(n)
liczba
wywołań procedury podziału (np. Split, Partition) jest rzędu co najwyżej k
złożoność pesymistyczna algorytmu jest
rzędu co najwyżej n2
92. Niech Alg1
oraz Alg2 będą algorytmami takimi, że T(Alg1,n)=O(nlg(n)) oraz A(Alg2,n)=O(lg(n!)) i W(Alg2,n)=Θ(n3).
Rozważmy teraz algorytm Alg3 taki, że Alg3(n)=
{
int
i=0;
while(i<n)
do
if((i
MOD 2)= =0)
Alg1(i)
else Alg2(i);
i=i+1
od
},
wtedy:
A(Alg3,n)=Θ(n3)
A(Alg3,n)=O(n2)
W(Alg3,n)=Ω(n3lg(n))
93. Niech X będzie tablicą n losowych liczb naturalnych
oraz SS, IS, QS będą odpowiednio algorytmami sortowania przez selekcję,
sortowania przez wybór i sortowania szybkiego, wtedy:
W(QS(SS(IS(X))),n)= Ω(n)
A(IS(QS(X)),n)=O(lg(n!))
A(QS(IS(SS(X))),n)=O(n3)
W(SS(IS(X)),n)=Θ(n×lg(n))
A(SS(QS(X)),n)=O(n×lg(n))
94. Lepiej użyć
algorytmu InsertionSort, zamiast MergeSort, kiedy…
dane są prawie posortowane
mamy do czynienia z bardzo małymi danymi
mamy bardzo mało dodatkowej pamięci
95. Czym można
posortować dane używając:
sortowania
kubełkowego, a w kubełkach posortować dane używając algorytmu Dijkstry
sortowania
kubełkowego, a w kubełkach posortować dane używając Sita Eratostenesa
RadixSort,a do sortowaia po poszczególnych
kolumnach sortowania kubełkowego, a w kubełkach stabilnej wersji QuickSort
sortowania kubełkowego, a w kubełkach posortować dane
używając QuickSort
drzewa AVL
96. Który z
podanych poniżej ciągów jest asymptotycznie rosnącym ciągiem funkcji zmiennej n
w dziedzinie liczb naturalnych dodatnich:
2n, (3!)n/2, (32)n/2,
(n/2)!, n!-7n, nn/3
2n-1,
lg(lg(n!)), lg(n)-3, n1/3, n3, 2n, 3n-2
lg(n),
lg(n!), n2, n2-n, n3+100, lg(n)×n!, n!