Pytania i odpowiedzi
AiSD
Zebrane pytania i odpowiedzi do zestawu. zadania z egz 1
Ilość pytań: 15
Rozwiązywany: 998 razy
Pytanie 1
Zwykle algorytmy klasyfikowane są w zależności od złożoności:
czasowej i pamięciowej
Pytanie 2
W drzewie zapisanym za pomocą struktury lewolistowej:
A(B(D(I),E(J,K,L)),C(F(O),G(M,N),(H(P)))
2
Pytanie 3
Graf kubiczny jest to:
graf regularny stopnia 3
Pytanie 4
Jeśli graf nieskierowany jest grafem n-dzielnym to:
zbiór wierzochołków podzielony został na n rozdzielnych podziorów
Pytanie 5
Algorytm przez wstawianie można poprawić poprzez zastosowanie:
wartownika
Pytanie 6
Obiekt nie większy (mniejszy lub równy) połowie n obietków oraz nie mniejszy (większy lub równy) od drugiej połowy n obiektów to:
mediana
Pytanie 7
Z podanych liczb utworzyć stóg (kopiec) z wartością najmniejszą na szczycie i zapisać go w tablicy. Podać wartość kolejnych elementów tablicy 50,60,33,40,53,70,55,45,30,42
30, 33, 50, 40, 42, 70, 55, 60, 45, 53
Pytanie 8
Dane jest drzewo w zapisie leworekusywnym:
10(8(5)15(12(13)20(30(25))))
Podać 3 liczby określające dla tego drzewa odpowiednio:
- liczbę liści
- moment
- liczbę poziomów
3, 9, 5
Pytanie 9
Dane jest drzewo w zapisie leworekusywnym:
A(B(C)D(EF)G(H(J))))
Podać 3 liczby określające dla tego drzewa odpowiednio:
- liczbę liści
- moment
- liczbę poziomów
3, 9, 5
Pytanie 10
Jakiego rzędu jest złożoność czasowa podanego algorytmu względem n = MAX:
for nr 2 := 1 to MAX - 1 do
if t[nr2] < t[nr2 + 1] then begin
pom := t[nr2];
t[nr2] := t[nr2 + 1];
t[nr2 + 1] := pom;
end
O(n^2)
Pytanie 11
Z podanych liczb utworzyć BST i zapisać je motodą preorder. Podać wartość kolejnych kluczy w tym zapisie.
50,60,33,40,53,70, 55, 45, 30, 42
50,33,30,40,45,42,60,53,55,70
Pytanie 12
Sortowanie przez wybór (selekcję) zawiera w sobie krok, polegający na wyborze klucza:
minimalnego
Pytanie 13
Pesymistyczny czas działania algorytmu jest jego granicą możliwego czasu działania algorytmu:
górną
Pytanie 14
Metody sortowania stosujące drzewa (np. stogowe) mają złożoność czasową rzędu:
nlog2n
Pytanie 15
Wielkość zasobów komputerowych potrzebnych przy "typowych" dancyh wejściowych rozmiaru n to złożoność:
oczekiwana (użyteczna)