Fiszki
AiSD
Test w formie fiszek zadania z egz 1
Ilość pytań: 15
Rozwiązywany: 998 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)))
3
1
2
4
2
Graf kubiczny jest to:
graf, którego nie można narysować na płaszczyźnie(musi być rysowany w 3D)
graf planarny stopnia 2
graf regularny stopnia 3
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
nie ma takiego grafu - są tylko grafy dwudzielne lub trójdzielne
zbiór wierzochołków podzielony został na n rozdzielnych podziorów
liczba wierzchołków została podzielona przez n
zbiór wierzochołków podzielony został na n rozdzielnych podziorów
Algorytm przez wstawianie można poprawić poprzez zastosowanie:
mediany
wartownika
zanegowanego wartownika
średniej
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:
mediteriana
mediana
średnia
środek
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, 40, 42, 50, 53, 45, 55, 60, 70
30, 33, 50, 40, 42, 70, 55, 60, 53, 45
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,8, 5
3, 9, 4
2, 9, 5
3, 9, 3
3, 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, 8, 5
3, 9, 5
2, 9, 5
3, 9, 3
3, 9, 4
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 (nlog^(2)n)
O(n^2)
O(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
50,33,30,40,42,45,60,53,55,70
42,30,40,33,45,55,53,50,70,60
30, 42, 45, 40, 33, 55, 53, 70, 60, 50
50,33,30,40,45,42,60,53,55,70
50,33,30, 40, 45, 42, 60, 53, 70, 55
50,33,30,40,45,42,60,53,55,70
Sortowanie przez wybór (selekcję) zawiera w sobie krok, polegający na wyborze klucza:
minimalnego
obiecującego
będącego medianą
średniego
minimalnego
Pesymistyczny czas działania algorytmu jest jego granicą możliwego czasu działania algorytmu:
średnią
dolną
oczekiwaną
górną
górną
Metody sortowania stosujące drzewa (np. stogowe) mają złożoność czasową rzędu:
log2n
n
n^2
nlog2n
nlog2n
Wielkość zasobów komputerowych potrzebnych przy "typowych" dancyh wejściowych rozmiaru n to złożoność:
pesymistyczna
optymistyczna
średnia
oczekiwana (użyteczna)
oczekiwana (użyteczna)