Strona 2
AiSD
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, 8, 5
3, 9, 3
3, 9, 5
2, 9, 5
3, 9, 4
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(log^(2)n)
O(n^3)
O(n^2)
O (nlog^(2)n)
O(n)
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
50,33,30, 40, 45, 42, 60, 53, 70, 55
42,30,40,33,45,55,53,50,70,60
30, 42, 45, 40, 33, 55, 53, 70, 60, 50
50,33,30,40,42,45,60,53,55,70
Pytanie 12
Sortowanie przez wybór (selekcję) zawiera w sobie krok, polegający na wyborze klucza:
będącego medianą
średniego
obiecującego
minimalnego
Pytanie 13
Pesymistyczny czas działania algorytmu jest jego granicą możliwego czasu działania algorytmu:
górną
dolną
oczekiwaną
średnią
Pytanie 14
Metody sortowania stosujące drzewa (np. stogowe) mają złożoność czasową rzędu:
n
nlog2n
log2n
n^2
Pytanie 15
Wielkość zasobów komputerowych potrzebnych przy "typowych" dancyh wejściowych rozmiaru n to złożoność:
optymistyczna
średnia
oczekiwana (użyteczna)
pesymistyczna