EGZAMIN 2005
1. Co rozumiemy pod pojęciem algorytmu poprawnego wg Floyda?
To taki algorytm, który dla każdego egzemplarza problemu zatrzymuje się i daje dobry wynik
2. Pesymistyczny czas działania algorytmu jest jego:
górną...
3. Złożoność czasowa algorytmu jest to:
Czas wykonania algorytmu wyrażony funkcją rozmiaru problemu
4. Złożoność pamięciowa algorytmu wyrażona jest funkcją:
S(n)
5. Algorytm przez proste wstawianie można poprawić poprzez zastosowanie:
wstawianie klucza z wartością 0
6. Sortowanie wymyślone przez CA.R.Hoare'a to:
sortowanie przez podział (quick-sort)
7. Obiekt nie większy (mniejszy lub równy) połowie n obiektów oraz nie mniejszy (większy lub równy) od drugiej połowy n obiektów to obiekt:
mediana
8. Kopiec definiujemy jako ciąg kluczy hi, hi+1... ,hp takich, że:
hi<=h2i i hi<=h2i+1
9. W tablicy rozproszonej rozwiązanie problemu kolizji polegające na przeglądaniu pamięci cyklicznie, że stałą długością kroku: d|" (do+a-i) mod p nazywane jest szukaniem
liniowym
10. Ścieżka w grafie jest nazywana prostą, jeśli wszystkie jej wierzchołki są:
a) położone na linii prostej b) równe
c) różne d) współliniowe
11. Digraf to graf:
skierowany
12. Minimalne drzewo rozpinające w grafie nieskierowanym łączy wszystkie wierzchołki grafu tak, aby łączna waga drzewa była:
minimalna
13. Binarne drzewo zrównoważone to drzewo, w którym dla każdego węzła liczby węzłów w jego lewym i prawym poddrzewie różnią się co najwyżej o:
1
14. Jeżeli obiekt składa się z siebie samego lub jego definicja odwołuje się do niego samego, to taki obiekt nazywamy:
rekurencyjnym
15. Złożoność obliczeniowa wyszukiwania w tablicy rozproszonej jest rzędu:
O(n)
16. Sortowanie drzewiaste wykorzystuje:
binarne drzewo sortujące
17. Graf, w którym każdy wierzchołek ma ten sam stopień nazywamy:
regularnym
18. Długość ścieżki hierarchicznej do węzła na poziomie k w drzewie jest równa:
k-1
19. W drzewie zapisanym za pomocą struktury lewolistowej: A(B(D(I),E(J,K,L))',C(F(O),G(M,N),H(P))) liczba węzłów na poziomie 2 wynosi:
2
20. W binarnym drzewie poszukiwań, dla każdego węzła wszystkie klucze z lewego poddrzewa są w stosunku do klucza w tym węźle:
mniejsze
21. W binarnym drzewie poszukiwań, dla każdego węzła wszystkie klucze z prawego poddrzewa są w stosunku do klucza w tym węźle:
większe
22. Klasa problemów P (polonomial) zawiera wszystkie problemy rozwiązywalne w czasie wielomianowym, a więc takie, które rozwiązuje w co najwyżej czasie wielomianowym:
deterministyczna maszyna Turinga
23. Złożoność pesymistyczna wyrażona jest wzorem:
Tpes(n)=max{T(d), d-dane rozmiaru n}
24. Notacja O pochodzi od słowa (z jęz. ang.):
rząd
25. Jedną z najgorszych metod sortowania jest:
sortowanie bąbelkowe
26. Najlepsze metody sortowania (stogowe, szybkie) mają złożoność obliczeniową rzędu:
nlog2n
27. Szukanie kwadratowe to naturalna metoda uwolnienia się od grupowania kluczy w tablicy rozproszonej i wygląda następująco:
hi=(ho+a*i+b*i2) mod p
28. Jeśli w grafie nieskierowanym każda para wierzchołków jest połączona ścieżką, to taki graf nazywamy:
spójnym
29. Euler w swym twierdzeniu o ścieżkach w grafach wymaga:
Parzystej liczby krawędzi wychodzących z każdego wierzchołka
30. Który z podanych algorytmów nie jest algorytmem tworzenia minimalnego drzewa rozpinającego:
Dijkstry
31. W teorii grafów nie istnieje następujące pojęcie:
graf Euklidesa
32. Liczbę bezpośrednich potomków węzła w drzewie nazywamy jego:
Stopniem
33. Przeglądając drzewo reprezentujące wyrażenia algebraiczne uzyskano następujący rezultat: abc/+def*-* jest to porządek typu:
postorder (postfiks, wsteczny)