Fiszki
AiSD
Test w formie fiszek zadania z egz 1
Ilość pytań: 15
Rozwiązywany: 1003 razy
Zwykle algorytmy klasyfikowane są w zależności od złożoności:
pamięciowej i obliczeniowej
czasowej i pamięciowej
czasowej i objętościowej
czasowej i obliczeniowej
czasowej i pamięciowej
W drzewie zapisanym za pomocą struktury lewolistowej:
A(B(D(I),E(J,K,L)),C(F(O),G(M,N),(H(P)))
1
2
4
3
2
Graf kubiczny jest to:
graf regularny stopnia 3
graf planarny stopnia 2
graf, którego nie można narysować na płaszczyźnie(musi być rysowany w 3D)
graf platoński
graf regularny stopnia 3
Jeśli graf nieskierowany jest grafem n-dzielnym to:
zbiór krawędzi został rozdzielony na n rozdzielnych podzbiorów
liczba wierzchołków została podzielona przez n
nie ma takiego grafu - są tylko grafy dwudzielne lub trójdzielne
zbiór wierzochołków podzielony został na n rozdzielnych podziorów
zbiór wierzochołków podzielony został na n rozdzielnych podziorów
Algorytm przez wstawianie można poprawić poprzez zastosowanie:
mediany
średniej
wartownika
zanegowanego wartownika
wartownika
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
średnia
środek
mediteriana
mediana
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, 53, 45
30, 33, 40, 42, 50, 53, 45, 55, 60, 70
30, 33, 50, 40, 42, 70, 45, 60, 55, 53
30, 33, 50, 40, 42, 70, 55, 60, 45, 53
30, 33, 50, 40, 42, 70, 55, 60, 45, 53
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, 4
3, 9, 3
3, 9, 5
3,8, 5
2, 9, 5
3, 9, 5
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
3, 8, 5
2, 9, 5
3, 9, 4
3, 9, 3
3, 9, 5
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)
O(n^2)
O (nlog^(2)n)
O(n^3)
O(log^(2)n)
O(n^2)
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
30, 42, 45, 40, 33, 55, 53, 70, 60, 50
50,33,30,40,42,45,60,53,55,70
50,33,30, 40, 45, 42, 60, 53, 70, 55
42,30,40,33,45,55,53,50,70,60
50,33,30,40,45,42,60,53,55,70
50,33,30,40,45,42,60,53,55,70
Sortowanie przez wybór (selekcję) zawiera w sobie krok, polegający na wyborze klucza:
obiecującego
będącego medianą
minimalnego
średniego
minimalnego
Pesymistyczny czas działania algorytmu jest jego granicą możliwego czasu działania algorytmu:
średnią
górną
oczekiwaną
dolną
górną
Metody sortowania stosujące drzewa (np. stogowe) mają złożoność czasową rzędu:
nlog2n
n^2
n
log2n
nlog2n
Wielkość zasobów komputerowych potrzebnych przy "typowych" dancyh wejściowych rozmiaru n to złożoność:
średnia
oczekiwana (użyteczna)
pesymistyczna
optymistyczna
oczekiwana (użyteczna)