Nowy obraz

® Edukacja - Mozilla Firefo>

Plik Edycja Widok Historia Zakładki Sglit Narzędzia Pomoc

mojo box office

pjwstk.edu.pl https://edu.pjwstk.edu.pl/result2.asp7id3l033

'.‘St] darkwarez ^ Gmail |S] Allegro ^ PJWSTK Q Wikipedia, the free en... Q Wikipedia, wolna ency... Filmweb.pl - łeb pełen...

darkwarez.pl - Dzień świstaka / Grou... □    ^ Szalone serce/Crazy Heart (2009) -... E3 ^ Single Man, A (2009) - Film - FILMW... E3 ^ Księga ocalenia / Book of Eli, The (2... □ Gmail - Odebrane - bujalski.marek... □ Edukacja

opcja    i    ruiiiuy

rupiawiia

□ +

uupuwicui

[fal Foldery zadań Forum Chat

Q]>)) Ogłoszenia 0 Kalendarz @ FAQ & Lekcje @ Testy 2 O Zadania Q Bibliografia ^ Ankieta Inny kurs a Wyloguj JK Administrator

1

Dany jest n elementowy ciąg uporzadkow^rany. gdzie n jest podzielene przez 4. Który z algorytmów' wyszukiwania ma mniejszy koszt w najgorszym przypadku: algorytm sekwencyjny ze skokami co 4. czy algorytm n

ze skokami co 4?

Oba algorytmy wykonują dokładnie taką samą liczbę porównań w przypadku optymistycznym

1

+

+

	Oba algorytmy wykonują asymptotycznie taką samą liczbę porównań w dow^rolnym przypadku	0		+
	Rozważane algorytmy nie są poprawnym rozwiązaniem dla problemu wyszukiw'ania w danych uporządkow^ranych	0
2	W słowniku (uporządkow'anym leksykograficznie) zawierającym 2048 stron, szukamy hasła "algorytmika". Do wyszukiw'ania strony z tym hasłem zastosow^raliśmy algorytm binarnych poszukiw'ań. Obejrzenie jednej strony i stwierdzenie, czy to ta właściwa zajmuje nam 3 sek. Po 9 sek. stwierdziliśmy, że hasła "algorytmika" nie ma w słowniku. Ile sekund zajmie nam, w przypadku pesymistycznym, wyszukanie w tym słowniku hasła "struktura" (przy zastosow^raniu tej samej metody wyszukiw'ania)?
	Co najmniej 18 sek.	1	+
	Dokładnie 9 sek. w przypadku, gdy słow^ro "struktura" nie należy do rozważanego słownika	0		+
	Dokładnie tyle samo co w przypadku słow^ra "algorytmika"	0		+
3	W słowniku (uporządkow'anym leksykograficznie) zawierającym 6144 haseł, szukamy hasła "algorytmika". Na każdej stronie słownika znajdują się 24 hasła. Do wyszukiw'ania strony z tym hasłem zastosow^raliśmy algorytm binarnych poszukiw'ań, a obejrzenie jednej strony i stwierdzenie, czy to ta właściwa zajmuje nam 3 sek. Które z podanych oszacow^rań poprawnie określa pesymistyczny czas wyszukiwania?
	Tyle sekund, z dokładnością do 2 sek., ile w przypadku pesymistycznym wyszukiw'ania słow^ra "dane"	1	+	+
	6143-2 sek	0
	2-24 sek.	0

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ą:

•    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 % -tej pozycji w danym ciągu?

	Dokładnie n-\-z	0
	Dokładnie 1	0
	n 2	1	+	+
5	Oszacuj koszt algorytmu skoki co k zastosow^ranego do uporządkow^ranego ciągu n elementowego.
	Nie więcej niż l"& 1 ^ porównań	1	+	+
	^(^n) porównań	0		+
	Co najwyżej 5 porównań, jeśli n = 25, k = 5	0
6	Ile porównań musi wykonać w najgorszym razie algorytm BinSearch binarnych poszukiw'ań zastosow^rany do ciągu o 127 elementach?
	Dokładnie 7	1	+
	[ipl27J+l	1	+	+
	Asymptotycznie co najmniej tyle ile algorytm wyszukiwania ze skokami co k : gdzie k = fn	0

System edukacyjny. PJWSTK 2001-2007

Zakończono

10:37

2010-02-09

^PL <■ - $ IV <»