ASD egzamin 09 rozw

1 Wstawiamy do pustego drzewa BST kolejno: 0 4 1 2 3 6 5. Wypisując wartości węzłów przy przejściu tego drzewa w porządku inorder, otrzymamy:
0123456
3215640	r
3215640	r
2 Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi: a->b: b->ą c->d, d->c. Jest on:
spójny	9>
acykliczny	r
drzewem	r
3 Listę, ze zmodyfikowaną operacją get: która przesuwa żądany element na koniec listy:
zawsze warto używać, kiedy większość operacji, to operacje get	r
warto używać, dla losowych danych.	r
warto używać, kiedy większość operacji get tyczy się małego podzbioru elementów^r tej Esty
4 Jakie jest najlepsze oszacow^ranie na złożoność problemu znajdowania największego elementu w posortow^ranej tabHcy rozmiaru n:
O(tyn)	r
	r
0(1)	•

5	Porównując (dla danego algorytmu) złożoność oczekiw^raną obEczenkwą z oczekiw^raną pamięciową
	pierwsza jest (zawsze) gorsza od drugiej	m
	mogą być sobie równe	#
	pierwsza jest (zawsze) nie lepsza od drugiej	•
6	Przy założeniu, że n>0, a przy tym n jest Kczbą parzystą, zaś k jest Hczbą całkowitą nieparzystą dla pętE J le(j! = 0) {x-\- = ;} poprawnym niezmiennikiem jest
	parzystość zmiennych j oraz x są zawsze różne	r
	;>0	r
	.r>0	r
7	Szybkiej transformat)' Fouriera używamy do
	sortow^rania	r
	mnożenia wielomianów'	m
	analiz)' i obróbki sygnałów' dźwiękowych	*
8	Nazwa struktur)' danych AVL i związanych z nią algorytmów pochodzi od
	pierwszych Eter angielskiego skrótu opisującego najważniejszą cechę tej struktur)'	r
	pierwszych Eter nazwisk trzech twórców' tej metody	*
	nazwy uniw'ersyteckiej ligi siatkówki, której pasjonatami byE jej twórcy	r
9	JeżeE pewien algorytm działa w pesymistycznym czasie O(nlogn) <lla danych wielkości n, to będzie działał w pesymistycznym czasie O[nlogn) również dla danych wielkości
	2n+2*««	*
	n^2	r
	2 n	m
10	Dla Dosortowanei niemaleiaco tablicv A nasteDuiacv alaorvtm: 1=0: D=n-1: while A<dU s=0+d+1V2: if fx<AFsll d=s-1: else l=s:} return(l):
	obEcza indeks pierwszego wystąpienia największej Eczby nieprzekraczającej x	r
	obEcza indeks ostatniego wystąpienia najmniejszej Eczby co najmniej równej x	r
	zawsze działa w czasie O(logn)	r

u	StabiEie są algorytmy sortow^rania
	Insertionsort	m
	Quicksort ^	r
	Heapsort	$ m
12	Spośród następujących rzędów' złożoności minimalne są
	O(nlogr\)	r
	0(Zn2^n)	%
	Q( 2^lo9^n)	•
13	Algorytm Karacuby służ)' do
	mnożenia Eczb	*
	przechodzenia grafu	m
	znajdow^rania najkrótszej ścieżki w grafie	r
14	Rozważmy graf ^ gdzie M — ^n i n>10: w któiym 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 pustym	r
	grafem-gwiazdą, tj. grafem spójnym takim, że każdy wierzchołek tego grafu ma rząd równy 1 za wyjątkiem wierzchołka centraEiego, którego rząd jest równy n-1	r
	graf-drzew^rem binarnym wysokości n—1	m
15	Niech Algi oraz Alg2 będą algorytmami takimi, że T(Alglir\) — 0(nty(n)) oraz A(Alg7ir\) — 0(lg(r\\)){W(Alg7ir\) — 0(r\^) Rozważmy teraz algorytm Alg3 taki, że Alg3(n)=(int i=0; while (i<n) do if ((i MOD 2)=0) Algi© else Alg2(i): i=i+l od}, wtedy:
	A(Aty3,n) = 6>(n3)	r
	A(Alg3,r\) = 0(n2)	r
	W(Alg3,r\) = i?(r\Zlg(n))	r
16	Rozważmy zastosow^ranie algor)tmu sortow^rania przez scalanie MS do uporządkow^ranych nierosnąco danych wejściowych X rozmiaru n, wtedy:
	T(MS(X),n) = 0(lg(r>\))	*
	w tym przypadku wysokość drzewa wywołań rekurencyjnych algorytmu MS będzie nie mniejsza niż n	r
	T(MS(X),n) = G{n)	r
17	Niech /(^n) — wtedy prawdą jest, że:
	II 3 to	m
	/(«)+/(«) = 0(n3)	•
	/(n)x/(n) = ©(n3)	n
18	Rozważmy algorytm Alg(n)={mt k= 1, x= 1; while (k<n) do k=k+l; x=x*k od}. Któraz z wymienionych poniżej formuł jest niezmiennikiem pętE iteracyjnej w algorytmie Alg?
	x = l+2+3+...+(ł-l)+it	0
	x = x*k i^<^	B
	x = k\ i^^£	E
19	Rozważmy algorytm Hoarea wyszukania elementu ł-tego co do wielkości w nieuporządkow'anym uniwersum rozmiaru n, wtedy:
	Eczba wywołań procedur)' podziału (np. SpEt, Partition) jest rzędu co najwyżej k	r
	złożoność średnia algoiytmu jest rzędu co najwyżej W^n)	r
	złożoność pes)mist)'czna algoiytmu jest rzędu co najmniej n	m
20	Niech H będzie kopcem-drzew^Tem typu min powstałym przez kolejne wstawianie wierzchołków o etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktur)', wtedy:
	wierzchołki kopca-drzewa H wypisane w kolejności InOrder tworzą ciąg 8.5.6.1.7.0.4.2.3
	wysokość kopca-drzew^ra H jest równa 3	m
	wysokość kopca-drzew^ra H jest niezależna od kolejności wstawiania rozważanych wierzchołków	m

Wyślij I