Quiz do lekcji

Algorytm wyszukiwania w zbiorze danych

10 pytań, każde z wyjaśnieniem odpowiedzi. Wynik nigdzie się nie zapisuje, możesz wracać do niego dowolnie wiele razy.

Pytanie 1 z 10

Który zapis jest algorytmem, a nie zwykłym opisem pomysłu?

Poziom: podstawowy

Poszukaj numeru gdzieś w środku listy, a potem sprawdzaj dalej 1. Ustaw dolną na 1, górną na 16. 2. Jeśli dolna większa od górnej, wypisz nie ma i zakończ. 3. Sprawdź numer ze środka zakresu Trzeba znaleźć numer możliwie szybko i nie sprawdzać niepotrzebnych pozycji

Pytanie 2 z 10

Uczeń zapisał algorytm połowienia bez kroku „jeśli dolna jest większa od górnej, wypisz nie ma i zakończ”. Co się stanie przy szukaniu numeru, którego nie ma na liście?

Poziom: podstawowy

Algorytm zwróci pozycję najbliższego numeru Algorytm wypisze komunikat o błędzie danych Algorytm nie będzie miał jak się zakończyć i będzie się wykonywał w kółko

Pytanie 3 z 10

Na uporządkowanej liście 16 numerów szukamy ostatniego z nich. Ile kroków potrzebuje szukanie po kolei, a ile połowienie zakresu?

Poziom: rozszerzony

Po kolei 16 kroków, połowienie 5 kroków Po kolei 5 kroków, połowienie 16 kroków Obie metody potrzebują po 8 kroków Po kolei 1 krok, połowienie 1 krok

Pytanie 4 z 10

Lista 16 numerów jest ustawiona w przypadkowej kolejności. Co da zastosowanie do niej algorytmu połowienia zakresu?

Poziom: podstawowy

Ten sam wynik, tylko wolniej Wynik może być błędny, bo porównanie ze środkiem nie mówi, po której stronie leży szukany numer Algorytm sam uporządkuje listę przed szukaniem

Pytanie 5 z 10

Zbiór ma 1000 uporządkowanych pozycji. Ilu kroków potrzebuje połowienie zakresu w najgorszym przypadku?

Poziom: rozszerzony

Do 500 kroków, czyli połowy zbioru Do 100 kroków Do 10 kroków, bo każdy krok zmniejsza zakres o połowę Dokładnie tyle samo co szukanie po kolei

Pytanie 6 z 10

Krok „sprawdź środek listy” oblewa test jednoznaczności. Dlaczego?

Poziom: podstawowy

Bo przy 16 pozycjach środek może wypaść na 8 albo na 9 i wykonawca musi sam wybrać Bo lista ma za mało pozycji, żeby miała środek Bo środek listy wolno sprawdzać dopiero na końcu

Pytanie 7 z 10

Uczeń zapisał szukanie po kolei tak: 1. Ustaw pozycję na 1. 2. Porównaj numer na tej pozycji z szukanym. 3. Jeśli równy, wypisz pozycję i zakończ. 4. Zwiększ pozycję o 1 i wróć do kroku 2. Wykonawca szuka numeru 1305 na liście 16 numerów z lekcji. Co się stanie?

Poziom: rozszerzony

Po 16 porównaniach algorytm wypisze „nie ma” i zakończy się Algorytm zakończy się po 9 porównaniach, bo numer 1315 jest większy od 1305 Algorytm wypisze pozycję 8, bo 1290 jest najbliżej 1305 Po 16 porównaniach wykonawca ustawi pozycję na 17 i spróbuje porównać numer, którego nie ma, bo brakuje kroku kończącego dla końca listy

Pytanie 8 z 10

Dwie pary wykonały ten sam zapis algorytmu połowienia dla numeru 1233 na liście 16 numerów z lekcji. Jedna para uzyskała 3 kroki, druga 4. Zapis mówił „ustaw środek na sumę dolnej i górnej podzieloną przez 2”, bez słowa o zaokrąglaniu. Co jest przyczyną różnicy?

Poziom: rozszerzony

Jedna z par pomyliła się przy porównaniu i policzyła o jeden krok za mało Numer 1233 stoi na liście na dwóch różnych pozycjach Zapis nie był jednoznaczny: przy 17 podzielonym przez 2 zaokrąglenie w górę daje środek 9 i 3 kroki, a zaokrąglenie w dół daje środek 8 i 4 kroki Połowienie zawsze daje inną liczbę kroków przy każdym wykonaniu

Pytanie 9 z 10

Kiedy szukanie po kolei jest lepszym wyborem niż połowienie zakresu?

Poziom: podstawowy

Gdy lista ma milion pozycji i szukamy w niej codziennie Gdy lista jest uporządkowana i szukamy w niej wiele razy Gdy lista jest nieuporządkowana, a szukamy w niej tylko raz

Pytanie 10 z 10

Na uporządkowanej liście 16 numerów z lekcji szukasz numeru 1087. Ile kroków potrzebuje szukanie po kolei, a ile połowienie zakresu, jeśli krok to jedno porównanie?

Poziom: rozszerzony

Po kolei 16 kroków, połowienie 5 kroków Po kolei 2 kroki, połowienie 3 kroki, więc tym razem wygrywa szukanie po kolei Po kolei 2 kroki, połowienie 2 kroki, remis Po kolei 2 kroki, połowienie 4 kroki