ALGORYTMY I STRUKTURY DANYCH
©Lisek89
-> odczyt z Kozackich fotek
11.02.2010r.
E
GZAMIN
-
Wersja
A
Strona 1
1. (2 pkt) Dany jest algorytm, który dla dowolnej liczby naturalnej n, powinien wyznaczyd sumę
kolejnych liczb naturalnych mniejszych od n. Wynik algorytmu jest zapisany w zmiennej suma.
Algorytm
i=1; suma=0;
while(i!=n){
suma+=i;
i+=2;
}
Czy powyższy algorytm jest:
poprawny całkowicie,
poprawny częściowo,
nie jest poprawny ani całkowicie ani częściowo
2. (3 pkt) Dane są trzy funkcje:
f
1
(n) = 0,01 4
𝑛
+ 100𝑛
2
,
𝑓
2
(n) = logn
n
+ 0,1𝑛
2
,
𝑓
3
(𝑛) = 2
log
2
𝑛
+ 𝑙𝑜𝑔𝑛
100
oraz następujące rzędy funkcji:
(n),
(logn),
(2
n
),
(4
n
),
(n
2
),
(n
1/2
),
(nlogn),
(n
100
),
(n!),
(n
n
)
Przyporządkuj każdej z funkcji odpowiedni rząd:
f
1
n =
𝑓
2
n =
𝑓
3
𝑛 =
3. (2 pkt) Dana jest następująca funkcja:
int F(int n){
if(n==0 || n==1)
return 1;
return F(n-1)+F(n-2);
}
Jaki jest co do rzędu, pesymistyczny koszt czasowy powyższej funkcji. Zakładamy, że rozmiarem
zadania jest n, a operacją elementarną dodawanie.
ODP: …………………………………………………………………………………………
4. (2 pkt) Dana jest następująca funkcja:
int G(int n, int k){
if(n==k || k==0) return 1;
return G(n-1, k-1)+G(n-1,k);
}
Ile razy wywoła się powyższa funkcja dla danych n=4 i k=2?
ODP: …………………………………………………………………………………………
5. Z którymi elementami tablicy uporządkowanej będzie porównany element x=1 w algorytmie
wyszukiwania binarnego. Wynik zapisz w kolejności wykonywanych porównao.
tablica: 1, 5, 20, 25, 30, 50, 80, 100, 200
ODP: …………………………………………………………………………………………
ALGORYTMY I STRUKTURY DANYCH
©Lisek89
-> odczyt z Kozackich fotek
11.02.2010r.
E
GZAMIN
-
Wersja
A
Strona 2
6. (2 pkt) Pewien problem o rozmiarze n został rozwiązany przy użyciu strategii „dziel i zwyciężaj”. Jego
czasowa złożonośd pesymistyczna została następnie zapisana w postaci poniższego równania
rekurencyjnego:
𝑇
𝑚𝑎𝑥
𝑛 =
2 𝑑𝑙𝑎 𝑛 ≤ 2
2𝑇
𝑚𝑎𝑥
𝑛
2
+ 𝑛 𝑑𝑙𝑎 𝑛 > 2
Jaki jest rząd funkcji kosztu tego algorytmu:
(nlogn)
(n
2
)
(logn)
Inny koszt. Jak?: …………………………………………………………………………………
7. (3 pkt) Dany jest zbiór n przedmiotów o wagach wyrażonych w kg będących liczbami naturalnymi.
Chcemy załadowad możliwie najpełniej przyczepę o ładowności m kg. Czy tak zdefiniowany problem
można rozwiązad strategią zachłanną, stosując w pierwszym kroku algorytmu sortowanie
przedmiotów nierosnąco po wagach?
Tak.
Nie. Podaj kontrprzykład (tzn. przykład danych wejściowych, dla których rozwiązanie
algorytmem zachłannym nie będzie optymalne):
………………………………………………………………………………………………………………………………
………………………………………………………………………………………………………………………………
………………………………………………………………………………………………………………………………
8. (1 pkt) Które z poniższych zdao są prawdziwe?
Wszystkie problemy posiadające własnośd optymalnej podstruktury można optymalnie
rozwiązad strategią zachłanną
Wszystkie problemy posiadające własnośd wyboru zachłannego można rozwiązad optymalnie
strategią zachłanną
Problemy posiadające obie własności: optymalnej podstruktury i wyboru zachłannego,
można rozwiązad optymalnie strategią zachłanną.
Żadne z powyższych zdao nie jest prawdziwe.
9. (1 pkt) Wskaż algorytmy wykorzystujące programowanie dynamiczne:
Algorytm Dijkstry
Algorytm Forda-Bellmana
Algorytm wyszukiwania binarnego
Żaden z powyższych algorytmów nie wykorzystuje techniki programowania dynamicznego
10. (2 pkt) W tablicy liczb został zbudowany kopiec zupełny. Zawartośd kopca jest następująca: 10, 8, 7,
5, 3, 6. Do kopca dodano następnie liczbę 9. Jaka jest kolejnośd liczb w kopcu po dodaniu tej
wartości:
ODP: …………………………………………………………………………………………
11. Nie mam treści zadania widad koniec pierwszej linijki: „ciągu uporządkowanym:”
Jak ktoś może niech dopisze to zadanie na forum.
ALGORYTMY I STRUKTURY DANYCH
©Lisek89
-> odczyt z Kozackich fotek
11.02.2010r.
E
GZAMIN
-
Wersja
A
Strona 3
12. (2 pkt) Jaki jest koszt pesymistyczny wyszukiwania elementu w następujących strukturach danych,
zawierających w momencie wyszukiwania n elementów? Wystarczy podad rząd funkcji kosztu.
Lista nieuporządkowana:
……………………………………………
Tablica posortowana:
……………………………………………
Drzewo BST:
……………………………………………
Drzewo AVL:
……………………………………………
13. (2 pkt) Ile co najwyżej elementów może zawierad drzewo binarne składające się z n poziomów?
Zakładamy, że drzewo posiadające tylko jeden element składa się z jednego poziomu. Podaj
dokładny wynik.
ODP: …………………………………………………………………………………………
14. (2 pkt) Zbuduj drzewo BST wstawiając kolejno elementy: 8, 12, 25, 1, 6, 20, 10. Jaki element może
zastąpid wartośd 8 w procesie usuwania tej wartości z drzewa.
ODP: …………………………………………………………………………………………
15. (2 pkt) Do początkowo pustego drzewa AVL wstawiono kolejno elementy: 15, 5, 10, 25, 35, 12.
Etykietą korzenia utworzonego w ten sposób drzewa jest:
10
25
15
Żadna z wartości. Podaj poprawną odpowiedź: …………………………………………………......
16. (1 pkt) Jaki jest optymalny koszt algorytmu wyświetlającego zawartośd drzewa BST w porządku
rosnącym?
ODP: …………………………………………………………………………………………
17. (1 pkt) Które z poniższych zdao są prawdziwe:
Algorytm Dijkstry zawsze działa skutecznie w grafach o ujemnych wagach.
Algorytm Forda-Bellmana można zastosowad tylko do grafów z wagami dodatnimi.
Algorytm Floyda-Warshalla służy do wyznaczania najkrótszych ścieżek między wszystkimi
odległościami wierzchołków.
Żaden z powyższych algorytmów nie daje dobrych wyników w grafach z cyklami o ujemnych
wagach.
Żadne z powyższych zdao nie jest prawdziwe.
18. (2 pkt) Dany jest graf o następujących listach incydencji:
1: 2, 4
2: 1, 3, 5
3: 2, 5, 6
4: 1
5: 2, 3, 6
6: 3, 5, 7
Wypisz kolejno odwiedzane wierzchołki w wyniku przeglądania tego grafu „wszerz” rozpoczynając od
wierzchołka nr 1.
ODP: …………………………………………………………………………………………
19. (3 pkt) Określ kolory poszczególnych wierzchołków ustalone w algorytmie aproksymacyjnym
kolorowania opartym o maksymalne zbiory niezależne dla grafu o następujących listach incydencji:
1: 2, 3, 4
2: 1, 3, 4
3: 1, 2, 6
4: 1, 2, 6
5: 6
6: 3, 4, 5
ALGORYTMY I STRUKTURY DANYCH
©Lisek89
-> odczyt z Kozackich fotek
11.02.2010r.
E
GZAMIN
-
Wersja
A
Strona 4
Zakładamy, że jeżeli w trakcie realizacji algorytmu dochodzi do wyboru wierzchołków według
ustalonego kryterium i kilka wierzchołków spełnia to kryterium to wybierany jest wierzchołek o
najniższym numerze.
nr wierzchołka
1
2
3
4
5
6
nr koloru
20. (3 pkt) Ustal zawartośd tabeli odległości d (tabeli odległości minimalnych) po każdym kroku
algorytmu Dijkstry dla następującego grafu. Wierzchołek startowy s=
tablica d
d[1]
d[2]
d[3]
d[4]
po inicjalizacji
po I kroku
po II kroku
ostatecznie
21. (2 pkt) Mamy dany problem maksymalnego wypełnienia różnymi towarami windy o ładowności 1000
kilogramów. W rozwiązaniu optymalnym udało się wypełnid kabinę windy maksymalnie. Algorytm
przybliżony (bazujący na strategii zachłannej) posiada ograniczenie względne błędu
aproksymacyjnego równe 2. Oznacza to, że:
Algorytm ten zdoła zapełnid windę przynajmniej 998 kilogramami towaru.
Algorytm ten zdoła zapełnid windę przynajmniej do połowy jej ładowności.
Algorytm ten zdoła zapełnid windę co najwyżej do połowy jej ładowności.
Algorytm ten załaduje do windy jedynie 2kg towaru.
Żadna z powyższych odpowiedzi nie jest poprawna.
22. (1 pkt) Które z poniższych zdao jest prawdziwe:
Każdy problem NP-zupełny posiada rozwiązanie działające w czasie wielomianowym.
Żaden problem NP-zupełny nie posiada rozwiązania działającego w czasie wielomianowym.
Nie wiadomo, czy problemy NP-zupełne mają rozwiązanie działające w czasie
wielomianowym.
Żadne z powyższych zdao nie jest prawdziwe.
23. (2 pkt) Który z poniższych problemów jest NP-zupełny?
problem domina
problem sortowania topologicznego grafu
problem cyklu Hamiltona
problem komiwojażera
Żaden z powyższych problemów
2
1
5
4
2
1
2
3
4
ALGORYTMY I STRUKTURY DANYCH
©Lisek89
-> odczyt z Kozackich fotek
11.02.2010r.
E
GZAMIN
-
Wersja
A
Strona 5
24. (2 pkt) Który z cykli Hamiltona wygeneruje się jako pierwszy dla grafu z zadania nr 19. Wierzchołek
startowy cyklu ma numer 1.
ODP: …………………………………………………………………………………………
25. (3 pkt) Do tablicy z haszowaniem T o długości m=11 wstawiamy kolejno klucze 11, 23, 34, 4, 15, 25,
22, używając adresowania otwartego typu liniowego do rozwiązywania problemu kolizji. Funkcja
haszująca ma wzór 𝑥, 𝑖 =
′
𝑥 + 𝑖 %𝑚, gdzie
′
𝑥 = 𝑥%𝑚. Wyznacz zawartośd tablicy T.
T = [
]
0
1
2
3
4
5
6
7
8
9
10