algorytmy egzamin, !!!Uczelnia, wsti, materialy, II SEM, algorytmy struktury danych


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 wezł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. Nąjlepsze 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)



Wyszukiwarka

Podobne podstrony:
algo zadania egzamin, !!!Uczelnia, wsti, materialy, II SEM, algorytmy struktury danych, egzamin
AiSD Egzamin 2005, !!!Uczelnia, wsti, materialy, II SEM, algorytmy struktury danych
AiSD Egzamin Zadania, !!!Uczelnia, wsti, materialy, II SEM, algorytmy struktury danych
AiSD Egzamin 2006, !!!Uczelnia, wsti, materialy, II SEM, algorytmy struktury danych
ALGORYTMY I STRUKTURY DANYCH, !!!Uczelnia, wsti, materialy, II SEM, algorytmy struktury danych
Sciaga Przykladowe Zadania, !!!Uczelnia, wsti, materialy, II SEM, algorytmy struktury danych
systemy operacyjne egzamin pytania-odpowiedzi, !!!Uczelnia, wsti, materialy, II SEM
quota, !!!Uczelnia, wsti, materialy, II SEM, systemy operacyjne linux
algebra zbior w, !!!Uczelnia, wsti, materialy, II SEM, matematyka
quota, !!!Uczelnia, wsti, materialy, II SEM, systemy operacyjne linux
EGZAMIN U PAW A JANIKA, !!!Uczelnia, wsti, materialy, III SEM, teleinformatyka, egzamin
Analiza i przetwarzanie obraz w W.1, !!!Uczelnia, wsti, materialy, III SEM, Wyk ady
nowe zadanie, !!!Uczelnia, wsti, materialy, III SEM, teleinformatyka, zadania raporty
WIRTUALNA SIE PRYWATNA, !!!Uczelnia, wsti, materialy, III SEM, teleinformatyka, voip vpn
Serwer Poczty, !!!Uczelnia, wsti, materialy, III SEM, teleinformatyka, windows2003 server
lista pytan ustne, !!!Uczelnia, wsti, materialy, III SEM, programowanie c
zadanie1 tresc, !!!Uczelnia, wsti, materialy, III SEM, teleinformatyka
Analiza i przetwarzanie obraz w W.6, !!!Uczelnia, wsti, materialy, III SEM, Wyk ady
Analiza i przetwarzanie obraz w W.7, !!!Uczelnia, wsti, materialy, III SEM, Wyk ady

więcej podobnych podstron