ALGORYTMY I STRUKTURY DANYCH ©Lisek89 -> odczyt z Kozackich fotek 11.02.2010r.
EGZAMIN - Wersja A
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:
f1(n) = 0,01 45Ø[Ü + 1005Ø[Ü2, 5ØSÜ2(n) = lognn + 0,15Ø[Ü2, 5ØSÜ3(5Ø[Ü) = 2log 2 5Ø[Ü + 5ØYÜ5Ø\Ü5ØTÜ5Ø[Ü100
oraz następujące rzędy funkcji:
Qð(n), Qð(logn), Qð(2n), Qð(4n), Qð(n2), Qð(n1/2), Qð(nlogn), Qð(n100), Qð(n!), Qð(nn)
Przyporządkuj każdej z funkcji odpowiedni rząd:
f1 n =
5ØSÜ2 n =
5ØSÜ3 5Ø[Ü =
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: & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
Strona 1
ALGORYTMY I STRUKTURY DANYCH ©Lisek89 -> odczyt z Kozackich fotek 11.02.2010r.
EGZAMIN - Wersja A
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 5ØQÜ5ØYÜ5ØNÜ 5Ø[Ü d" 2
5Ø[Ü
5ØGÜ5ØZÜ5ØNÜ5ØeÜ 5Ø[Ü = 25ØGÜ5ØZÜ5ØNÜ5ØeÜ + 5Ø[Ü 5ØQÜ5ØYÜ5ØNÜ 5Ø[Ü > 2
2
Jaki jest rzÄ…d funkcji kosztu tego algorytmu:
Åšð Qð(nlogn)
Åšð Qð(n2)
Åšð Qð(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.
Strona 2
ALGORYTMY I STRUKTURY DANYCH ©Lisek89 -> odczyt z Kozackich fotek 11.02.2010r.
EGZAMIN - Wersja A
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Ä… odpowiedz
: & & & & & & & & & & & & & & & & & & & ......
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
Strona 3
ALGORYTMY I STRUKTURY DANYCH ©Lisek89 -> odczyt z Kozackich fotek 11.02.2010r.
EGZAMIN - Wersja A
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=
2
5
2
4
1
1
4 2
3
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
Strona 4
ALGORYTMY I STRUKTURY DANYCH ©Lisek89 -> odczyt z Kozackich fotek 11.02.2010r.
EGZAMIN - Wersja A
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 5ØUÜ 5ØeÜ, 5ØVÜ = 5ØUÜ2 5ØeÜ + 5ØVÜ %5ØZÜ, gdzie 5ØUÜ2 5ØeÜ = 5ØeÜ%5ØZÜ. Wyznacz zawartoÅ›d tablicy T.
T = [ ]
0 1 2 3 4 5 6 7 8 9 10
Strona 5