ASD egzamin 09 rozw

Wstawiamy do pustego drzewa BST kolejno: 3 2 5 4 0 6 1. Wypisując wartości węzłów przy przejściu tego drzewa w porządku inorder, otrzymamy:
1024653	r
0123456	•
1024653	r
Mamy graf skierowany złożony z wierzchołków {a} i krawędzi: a->a. Jest on:
pełny	w
acykliczny	w
spójny	w
Listę, ze zmodyfikowaną operacjąget, która przesuwa żądany element na koniec listy:
warto używać, dla losowych danych.	r
warto używać, kiedy większość operacji get tyczy się różnych elementów tej listy	r
warto używać, kiedy większość operacji get tyczy się małego podzbioru elementów tej listy	r
Jakie jest najlepsze oszacowanie na złożoność problemu znajdowania największego elementu w danej tablicy rozmiaru n:
°(^n)	m
0(l$n)	r
0(1)	w
Porównując (dla danego algorytmu) złożoność pesymistyczną pamięciową z oczekiwaną pamięciową
pierwsza jest (zawsze) gorsza od drugiej	r
pierwsza może być lepsza od drugiej	m
pierwsza jest (zawsze) nie lepsza od drugiej	•
Sortowanie radksort pozwala posortować n elementów szybciej niż w czasie O(r\logr\) m jn dzięki temu, że
algorytm countsort jest stabilny	r
reprezentacje elementów z sortowanego zbioru mają określoną i stałą ze względu na n długość liczoną w bitach	r
nie wykonujemy bezpośrednich operacji na elementach, tylko odwołujemy się do ich reprezentacji bitowej	r
Stabilne są algorytmy sortowania
Heapsort * Selectionsort	r
	r
Quicksort	r
Dla Dosortowanei niemaleiaco tablicy A nastenuiacv alaorvtm: 1=0: n=n-1: while fkolf s=U+n+1V2: if fx<Afsl'l o=s-1: else l=s;} retum(l);
oblicza indeks pierwszego wystąpienia największej liczby nieprzekraczającej x	r
oblicza indeks ostatniego wystąpienia x w A	r
oblicza indeks ostatniego wystąpienia najmniejszej liczby co najmniej równej x	r
Przy założeniu, że n>0, a przy tym n jest liczbą parzystą, zaś k jest liczbą całkowitą nieparzystą, dla pętli J — 0){jt+ — ;} poprawnym niezmiennikiem jest
parzystość zmiennych j oraz x są zawsze różne	r
jeśli pętla wykonała co najmniej 4 obroty, to parzystość x oraz j są takie same, jak cztery obroty pętli wcześniej	r
x>0	r
Nazwa struktury danych AVL i związanych z nią algorytmów pochodzi od
pierwszych liter nazwisk trzech twórców tej metody	*
pierwszych liter angielskiego skrótu opisującego najważniejszą cechę tej struktury	w
nazwy uniwersyteckiej ligi siatkówki, której pasjonatami byli jej twórcy	r
Mnożenie dwóch n-cyfrowych liczb da się wykonać w czasie
0{n‘°9,i))	m
O(n)	r
0(n2)	m
Algorytm Bluma-Floyda-Pratta-Rivesta-Tarjana znajdowania k-tego co do wielkości elementu w n-elementowym zbiorze zaczyna się od podziału na m-elementowe podzbiory dla m=5. Gdyby
analogiczny pomysł wykorzystać dla innej, ale ustalonej z góry liczności m, to liniową złożoność pesymistyczną uzyskalibyśmy dla
m = 7	r
m = nf 5	r
m = 3	r
Algorytm Karacuby służy do
sortowania	r
mnożenia wielomianów	r
mnożenia liczb	w
Rozważmy algorytm Alg(n)={int k=l, x=l; while (k<n) do k=k+l; x=x*k od). Któraz z wymienionych poniżej formuł jest niezmiennikiem pętli iteracyjnej w algorytmie Alg?
x —1+2-|-3-|-...-|-(£—1)+£	r
k<n	r
.r = £! i^>£	r
Niech X będzie tablicą n losowych liczb naturalnych oraz SS, IS, QS będą odpowiednio algorytmami sortowania przez selekcję, sortowania przez wybór i sortowania szybkiego, wtedy:
W(QS(SS(JS(X))),n) = (?(n)	r
A(/5(<?5(X)))n) = 0(fi;(n!))	r
A(<?5(/5(55(X))),n) = 0(n3)	r
Załóżmy, że stos 5 zawiera n elementów i że wykonujemy jedynie operacje zdefiniowane w strukturze stosów, wtedy:
zdjęcie ze stosu 5 elementu znajdującego się na wysokości^n/^ względem góry stosu wymaga wcześniejszego zdjęcia ze stosu ^n/4±l elementów	r
zdjęcie ze stosu 5 elementu znajdującego się na wysokości n względem dołu stosu wymaga wcześniejszego zdjęcia ze stosu n±l elementów	r
używając tylko co najwyżej dwóch stosów pomocniczych 51 oraz 52 i operacji stosowych można odwrócić kolejność elementów na stosie 5	r
Rozważmy drzewo T typu AVL powstałe przez losowe wstawianie wierzchołków o etykietach l,2,3,...,n-l,n do początkowo pustej struktury, wtedy:
wstawienie wierzchołka z etykietą n+1 do drzewa T wymaga wykonania co najwyżej jednaj co najwyżej podwójnej rotacji	9
wstawienie wierzchołka z etykietą n+1 do drzewa T wymaga wykonania ^(^n) rotacji	r
wysokość drzewa T jest nie większa niż (n) ? gdzie c jest pewną stałą	m
Rozważmy graf pełny & — (V,E)r gdzie V — , wtedy:
koszt algorytmu DFS dla rozważanego grafu G jest rzędu	r
kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm DFS jest następująca: d,a,^,6,/,c,e, jeżeli wierzchołki wybieramy w porządku
alfabetycznym
kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm DFS jest następująca: jeżeli wierzchołki wybieramy w porządku
alfabetycznym
Rozważmy algorytm sortowania przez zliczanie CS zastosowany do sortowania n-elementowego ciągu binarnego X, wtedy:
5(C5(X),n) = 0(n)	r
A(CS(X),n)^W(CS(X),n)	r
T(CS(X),n,m) = CB(n+m) ^ g^e m jest stałą nie większą niż 4	r
Rozważmy graf ^ — W-^), gdzie M ^n i n>10? w którym algorytmy DFS oraz BFS generują ten sam ciąg etykiet odwiedzanych wierzchołków z pewnego wierzchołka źródłowego, wtedy graf
G może być:
grafem-drzewem binarnym wysokości ^(^(^n))	r
graf-drzewem binarnym wysokości n—1	r
grafem-pierścieniem, tj. grafem spójnym takim, że M —1-^1 oraz deg(v) = 2^ każdego v będącego elementem zbioru V	r