Zasady wyszukiwania binarnego

Autor: justine

Quiz sprawdza znajomość definicji, wymagań i implementacji wyszukiwania binarnego oraz wariantów granicznych. Obejmuje złożoność, pułapki i przykłady z kodu.

12 wyświetleń 0 ukończeń 15 pytań

Rozwiąż quiz

Twoje imię

Rozwiąż quiz

1 Jak najlepiej opisać wyszukiwanie binarne?

A Algorytm przeszukuje losowo wybrane elementy w nieuporządkowanej kolekcji B Algorytm dzieli posortowany zakres na połowy i odrzuca jedną C Algorytm sortuje dane przed linearnym przeszukaniem D Algorytm sprawdza wszystkie elementy równocześnie w tabeli

2 Dlaczego kolekcja musi być posortowana dla wyszukiwania binarnego?

A Porządek upraszcza tylko implementację, ale nie jest konieczny B Porządek potrzebny jest wyłącznie do zliczania duplikatów C Porządek pozwala porównaniem ze środkiem wykluczyć całą połowę D Porządek skraca czas porównania pojedynczego elementu

3 Dlaczego złożoność czasowa wynosi O(log n)?

A Każdy krok zmniejsza problem mniej więcej o połowę, więc liczba kroków rośnie logarytmicznie B Algorytm używa dodatkowej pamięci logarytmicznej, co ogranicza czas C Algorytm wykonuje stałą liczbę porównań niezależnie od rozmiaru D Każdy krok przegląda stałą liczbę elementów, więc rośnie liniowo

4 Ile kroków zwraca przykład max_binary_steps dla size = 1024?

A 11 kroków B 12 kroków C 10 kroków D 9 kroków

5 Co zwraca funkcja binary_search w przykładzie, gdy element nie istnieje?

A False B 0 C None D -1

6 Co zwraca find_by_id(records, 25) w podanym przykładzie?

A None B -1 C Bob D ""

7 Dlaczego lista wiązana nie obsługuje efektywnie wyszukiwania binarnego?

A Lista wiązana ma większą pamięciochłonność niż tablica B Brak dostępu losowego O(1) wymusza sekwencyjne przejście do środka C Porównania w liście wiązanej są wolniejsze niż w tablicy D Elementy nie mogą być posortowane w liście wiązanej

8 Jaka jest zasadnicza różnica między right = len(values)-1 a right = len(values)?

A Pierwszy daje indeks poza zakresem, drugi zawsze daje poprawny środek B Pierwszy to przedział domknięty, drugi zwykle to przedział prawostronnie otwarty C Pierwszy używa innego porządku sortowania niż drugi D Pierwszy działa tylko dla nieparzystych długości, drugi dla parzystych

9 Co zwraca lower_bound zgodnie z opisem?

A Pierwszy indeks z elementem > target B Indeks pierwszego dokładnego dopasowania == target C Liczbę wystąpień target w tablicy D Pierwszy indeks z elementem >= target

10 Co zwraca upper_bound zgodnie z opisem?

A Liczbę elementów mniejszych lub równych target B Pierwszy indeks z elementem >= target C Indeks ostatniego wystąpienia target D Pierwszy indeks z elementem > target

11 Jakie wyniki wypisuje przykład z bisect_left i bisect_right dla wartości 2?

A 2 i 5 B 1 i 4 C 0 i 3 D 1 i 3

12 Jaki wynik zwraca first_true(0, 30, lambda x: x >= threshold) przy threshold = 17?

A 18 B 17 C 16 D 30

13 Jaki problem może powodować użycie mid = (low + high) // 2 w C lub Javie?

A Powoduje odwrotne sortowanie tablicy B Zmusza do użycia większej złożoności pamięciowej C Zawsze powoduje off-by-one i pomija elementy D Przekroczenie INT_MAX i ryzyko przepełnienia

14 Jaka własność predykatu jest wymagana w wzorcu "find first true"?

A Jednokrotna zmiana z True na False B Losowy rozkład wartości True i False C Symetryczne występowanie True i False D Monotoniczność w postaci False, False, ..., True, True

15 Co stanowi praktyczną pułapkę dotycząca kosztu sortowania przed wyszukiwaniem?

A Sortowanie kosztuje O(n log n), więc opłaca się przy wielu wyszukiwaniach B Sortowanie zmienia porządek i unieważnia wyszukiwanie binarne C Sortowanie natychmiast redukuje złożoność wyszukiwania do O(1) D Sortowanie zawsze kosztuje O(n^2), więc unika się go przed wyszukiwaniem

0 z 15 odpowiedzi

Nie odpowiedziano na 15 z 15 pytań. Wróć i uzupełnij brakujące odpowiedzi.

Często zadawane pytania

Ile pytań zawiera quiz Zasady wyszukiwania binarnego?

Quiz Zasady wyszukiwania binarnego zawiera 15 pytań testowych z możliwością wyboru jednej poprawnej odpowiedzi.

Czy quiz Zasady wyszukiwania binarnego jest darmowy?

Tak, wszystkie quizy na Odpytywarka.pl są całkowicie darmowe. Możesz rozwiązywać dowolną liczbę quizów bez żadnych opłat.

Jak mogę stworzyć własny quiz?

Wgraj plik PDF na stronie głównej, a nasz system AI automatycznie wygeneruje pytania testowe. Po wygenerowaniu możesz edytować treść pytań i odpowiedzi w panelu quizu.

Podobne quizy

Techniki projektowania algorytmów

Quiz sprawdza znajomość podstawowych technik projektowania algorytmów, takich...

127 15 pytań

Bosch Motronic — budowa i działanie

Quiz sprawdza znajomość budowy, odmian i zasad działania elementów systemu Bo...

29 15 pytań

Eksploatacja urządzeń elektroenergetycznych

Quiz sprawdza wiedzę z zakresu eksploatacji i bezpieczeństwa urządzeń elektro...

28 15 pytań

Levenshtein — embedding i regresja

Krótkie pytania sprawdzające zrozumienie artykułu o osadzeniu odległości Leve...

23 15 pytań

Wróć do panelu | Stwórz własny quiz