2 (1346)

t’) Edukacja - Mozilla Firefox

m

Plik Edycja Widok Historia Zakładki Narzędzia Pomoc
łj|^lg) O IŁj $1 ~*1 ^ httos://edu.oiwstk.edu.ol/result2.asD?id=1033	'£? ” ^1 Google	P ©I •
Allegro [2] ^BPH iJ Damoria [2J Darkwarez [2) Desert Operations [23 Edu Pjwstk [23 Epg M Grnail Google ^INI Interia [2] Koleje Mazowieckie Q Kurnik (© Nasza kJasa Onet PAYBACK Poczta PJWSTK	1^1 SQL 4" Teksty Torrenty £3 Wirtualna Polska
Edukacja		-
eau ^ pjwsiK		A
M F N II TESTY2 Zatoqc«arv:Ml:ł3łPh«k Kirt:AfciofvtwlttMKtiW(larvcł cosm	POMOC	WYLOGUJ

B Kurs ^ Wykłady >/ Oceny Materiały ED Toldery zadań f ¹ Forum Chat

QjO) Ogłoszenia Kalendarz

Q taq

Lekcje % Testy 2 □ Zadania Q Bibliografia W Inny kurs Si Wyloguj

jT, Administrator

Twój wynik: 3 punktów na 6 możliwych do uzyskania (50 %).

Piwek Michał

■

_Nr_

Opcja

Punkty

Poprawna

Odpowiedź

Dany jest dowolny ciąg n - elementowy. Zadanie polega na zbadaniu, czy dany element X występuje w tym ciągu czy nie. Rozważmy następującą modyfikację algorytmu wyszukiwania sekwencyjnego: rzucamy sprawiedliwą monetą:

1

•    jeśli wypadnie orzeł, to przeszukujemy ciąg sekwencyjnie w kierunku od lewej do prawej,

•    jeśli wypadnie reszka, to przeszukujemy ciąg sekwencyjnie od prawej do lewej.

Ile porównań trzeba średnio wykonać, jeżeli element szukany znajduje się na t-tej pozycji w danym ciągu?

	n 2	1	+	+
	Dokładnie 1	0
	0(n)	1	+	+
2	W ciągu (^e(0i^e(^)ł^e(^)>—i^e(^n)) uporządkowanym rosnąco szukamy metodą binarnych poszukiwań takie go t, by ^e(^l)<^x<^e(^l 1 0, dla pewnego ustalonego x. Jakiej długo ś ci jest prze szukiwanjr ciąg, jeśli wykonaliśmy dokładnie 11 porównań?
	Długość ciągu jest mniejsza 11^	0		+
	1 Co najwyżej R razy tyle ile w przypadku 12-stu porównań i tej samej metody postępowania	0		+
	Co najwyżej 4 razy tyle ile w przypadku Ifl-ciu porównań i tej samej metody postępowania	1	+
3	Niech k będzie liczbą porównań, jaką wykona w najgorszym przypadku algorytm poszukiwań binarnych BinSearch zastosowany do ciągu o n elementach. Która odpowiedź jest poprawna?
	Jeśli n = 128, to k = 5	0
	Jeśli n = 1024, to k = 0(lgn)	1	+	+
	Jeśli n = 1024, to	0
4	Ile porównań musi wykonać w najgorszym razie algorytm BinSearch binarnych poszukiwań zastosowany do ciągu o . 27 elementach?
	0(Vń)	1	+	+
	Dokładnie 7	1	+	+
	OK	0
5	Które z podanych zdań jest prawdziwe?
	Koszt wyszukiwania binarnego mierzony liczbą wykonanych porównań można oszacować przez ^(A^n), gdzie n jest liczbą elementów w przeszukiwanym ciągu	1	+	+
	Złożoność pesymistyczna algorytmu BinSearch jest co najwyżej równa średniej złożoności algorytmu wyszukiwania sekwencyjnego	1	+
	Istnieją takie dane wejściowe, dla których koszt wykonania algorytmu binarnego jest asymptotycznie większy niż koszt wykonania algorytmu skoki co k, dla k=n, gdzie n jest rozmiarem danych wejściowych	1	+
	Niechbędzie dana tablica n liczb rzeczywistych A[^n] ipewna liczba x. Co jest wynikiem następującego algorytmu -^(Ai^ni^r).
ó	1.    inti:=0, j:=0; 2.    while(i<n)do 3.    if (A [i+1 ]=x) then j :=j+l; fi 4.    i:=i+l; 5.    od ó. return j;
	iMgorytm zapętla się dla dowolnych danych wejściowych	0
	Po wykonaniu pętli zachodzi warunek i >n	1	+	+
	Wartością zmiennej J jest liczba pozycji, na których znajduje się liczba X w rozważanej tablicy wejściowej	1	+

emacftiy. PJWSTK 2001-2007

Zakończono

B

/; Start

■^,) Edukacja - Mozilla Fir...

$ 1 - Paint

* / *
i i 4) O Aktualna pogoda: Zachmurzenie umiarkowane, -2 °C	Pon: 3 °C	Wt: 5 °C <0

ES ^f<    '!Q 20:53