ASD egzamin 09
rozw

rarameiry testu. I53 m 27 s
nosc pyian. zu Czas (min): 60 Punktacja: Duże punkty (punkt za całą odpowiedź poprawną)
1	Wstawiamy do pustego drzewa BST kolejno: 2 5 3 6 1 0 4. Wypisując wartości węzłów przy przejściu tego drzewa w porządku inorder, otrzymamy:
	0 1 2 3 4 5 6	m
	0143652	r
	0143652	r
2	Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi: a->b. Jest on:
	acykliczny	r
	spójny	r
	pełny	r
O	Listę, ze zmodyfikowaną operacją get, która przesuwa żądany element na początek 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
	zawsze warto używać, kiedy większość operacji, to operacje get	r
4	Które z niżej wymienionych wymagają co najmniej ^(^n) dodatkowej pamięci:
	CountSort	m
	Sortowanie bąbelkowe	r
	SelectionSort	r
5	Porównując (dla danego algorytmu) złożoność pesymistyczną obliczeniową z optymistyczną obliczeniową
	pierwsza jest (zawsze) gorsza od drugiej	m
	pierwsza może być lepsza od drugiej	Bj
	mogą być sobie równe	*
6	Nazwa struktury danych AVL i związanych z nią algorytmów pochodzi od
	pierwszych liter angielskiego skrótu opisującego najważniejszą cechę tej struktur.-	r
	nazwy uniwersyteckiej ligi siatkówki, której pasjonatami byli jej twórcy	O
	pierwszych liter nazwisk trzech twórców tej metody	m
T	Aby otrzymać B-drzewo 0 wysokości 2 dla t=5
	ustalić jego stopień na co najmniej 5	r
	wstawić co najwyżej 1000 elementów	r
	doprowadzić do sytuacji, w której łącznie będzie co najmniej 9 węzłów	r
8	Dla cosortowanei niemaleiaco tablicv A nastecuiacv alciorvtm 1=0 c=n-1 while i'I<dK s=i'I+d+1V2 if ix<Arsl: d=s-1 else l=s:} returmT;
	może się zapętlić	r
	oblicza indeks ostatniego wystąpienia najmniejszej liczby co najmniej równej x	Bj
	oblicza indeks pierwszego wystąpienia największej liczby nieprzekraczającej x	c
9	Jeżeli pewien algorytm działa w pesymistycznym czasie ^(^n) dla danych wielkości n, to będzie działał w pesymistycznym czasie ^(^n) również dla danych wielkości
	n+1	m
	logn	•
	r\logr\	r
10	Sortowanie radixsort pozwala posortować n elementów szybciej niż w czasie O(nlogti) mym dzięki temu, że
	reprezentacje elementów z sortowanego zbioru mają określoną i stałą ze względu na n długość liczoną w bitach	r
	algorytm countsort jest stabilny	a
	nie wykonujemy bezpośrednich operacji na elementach, tylko odwołujemy się do ich reprezentacji bitowej	r
11	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 = 3	c
		a
	m = nj 5	c
12	Stabilne są algorytmy sortowania Selectionsort
	Quicksort	r
	Heapsort	r
13	Jeżeli pewien algorytm działa w pesymistycznym czasie O(logti) dla danych wielkości n, to będzie działał w pesymistycznym czasie O[logn) również dla danych wielkości
	2 n	r
	logn	*
	n^2	u
14	Rozważmy algorytm Alg(n)={int k=l, x=l; while (k<n) do k=k~ 1; x=x*k od}. Któraz z wymienionych poniżej formuł jest niezmiennikiem pętli iteracyjnej w algorytmie Alg?
	x = k\	r
	x~k\ i^J>*	r
	x = i*k i^<^	r
15	Które z poniższych zdań jest zawsze prawdziwe w strukturze kolejek priorytetowych typu min:
	empty(pg) => empty^delminf^nsert^nsert^pg^ej^j	r
	mi ^n(pg) — min^insert^pg^	r
	empty{pg} => empty[delmin[insert{pg	m
16	Niech H będzie kopcem-drzewem typu min powstałym przez kolejne wstawianie wierzchołków' 0 etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktur.', wtedy:
	liczba liści na ostatnim poziomie kopca-drzewa H jest równa 2	f*
	jeżeli w kopcu-drzewie H wykonamy operację delmin; to etykiety kopca-drzewa będącego rezultatem rozważanej operacji sczytane w kolejności PreOrder tworzą ciąg 1.2.5.6.".4.3.8	r
	wierzchołki kopca-drzewa H wypisane w kolejności PreOrder tworzą ciąg 0.1.5.8.6.”.2.4.3	m
17	Rozważmy algorytm Alg(n)={if (n==0) return 3 else return Alg(n-1)-Alg(n-1)-Alg(n-1)}, wtedy dla n naturalnego:
	S(Alg,n) = O(n) jeżeli nie uwzględnimy stosu wywołań rekurencyjnych	r
	S(Alg,ń] = O(n) jeżeli uwzględnimy stos wywołań rekurencyjnych	a
	T(Alg,n) = i7(3^n)	a
18	Niech T będzie drzewem AVL powstałym przez kolejne wstawianie wierzchołków 0 etykietach 8,2,4,7,6,1,3,0,5 do początkowo pustej struktur.', wtedy:
	w trakcie budowy drzewa T wykonamy dwie podwójne i jedną pojedynczą rotację	r
	wierzchołki drzewa T wypisane w kolejności PostOrder tworzą ciąg 0.1.3.2.5.6.8.“.4	m
	wierzchołki drzewa T wypisane w' kolejności InOrder tworzą ciąg 0.1.2.3.4.5.6.“.8	m
19	Rozw^rażmy graf pełny & — (V>E); gdzie V — ^aJ,c,d,e,f,g wtedy:
	kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm BFS jest następująca: _ jeżeli wierzchołki wybieramy w porządku alfabetycznym	r
	kolejność odwiedzania wierzchołków grafu G z wierzchołka startowego d przez algorytm BFS jest następująca: ; jeżeli wierzchołki wybieramy w porządku odwrotnym do alfabetycznego	r
	koszt algorytmu BFS dla rozważanego grafu G jest rzędu ^(M+l-^1)	BI
20	Rozważmy algorytm Hoarea wyszukania elementu ł-tego co do wielkości w nieuporządkowanym uniwersum rozmiaru n, wtedy:
	złożoność pesymistyczna algorytmu jest rzędu co najmniej n	m
	liczba wywołań procedur.- podziału (np. Split, Partition) jest rzędu co najwyżej k	O
	złożoność pesymistyczna algorytmu jest rzędu co najwyżej n^2	m
Wyślij |