wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Przeszukiwanie - złożoność - sortowanie

Total questions: 30

Worksheet time: 21mins

Name
Class
Date
1.

Co opisuje czasowa złożoność obliczeniowa algorytmu?

a)

Liczbę linii kodu programu

b)

Liczbę operacji dominujących w zależności od wielkości danych

c)

Ilość pamięci RAM, jaką zajmuje program

d)

Liczbę błędów logicznych w algorytmie

2.

Operacjami dominującymi w algorytmie wyszukiwania są zwykle:

a)

Mnożenie liczb

b)

Porównania elementów

c)

Instrukcje wejścia/wyjścia

d)

Losowanie liczb

3.

Co składa się na złożoność obliczeniową algorytmu?

a)

Tylko czas wykonania algorytmu w sekundach

b)

Złożoność czasowa (liczba operacji dominujących)

c)

Złożoność pamięciowa (zapotrzebowanie na pamięć)

d)

Złożoność sprzętowa (szybkość procesora)

4.

Złożoność wyszukiwania binarnego w uporządkowanej tablicy to:

a)

O(n³)

b)

O(log n)

c)

O(n² / 2)

d)

O(1)

5.

Które z poniższych zdań dotyczących algorytmu przeszukiwania liniowego są prawdziwe?

a)

Wymaga, aby zbiór danych był uporządkowany

b)

Jego pesymistyczna złożoność wynosi n (dla n elementów)

c)

Można go stosować zarówno do zbiorów uporządkowanych, jak i nieuporządkowanych

d)

Jest szybszy od przeszukiwania binarnego dla bardzo dużych zbiorów danych

6.

Na czym polega sortowanie bąbelkowe (przez prostą zamianę)?

a)

Na wyszukiwaniu najmniejszego elementu i wstawianiu go na początek tablicy

b)

Na dzieleniu zbioru na mniejsze podzbiory i ich niezależnym sortowaniu

c)

Na porównywaniu sąsiadujących elementów i zamianie ich miejscami, jeśli są w złej kolejności

d)

Na wstawianiu kolejnych elementów w odpowiednie miejsca już posortowanego podciągu

7.

Które z poniższych metod zaliczamy do metod sortowania prostego?

a)

Sortowanie przez wybieranie (Selection Sort)

b)

Sortowanie przez scalanie (Merge Sort)

c)

Sortowanie bąbelkowe (Bubble Sort)

d)

Sortowanie przez wstawianie (Insertion Sort)

8.

Jaka jest typowa złożoność czasowa algorytmów sortowania prostego (bąbelkowego, przez wybieranie, przez wstawianie)?

a)

O(n)

b)

O(n log n)

c)

O(n2)

d)

O(log n)

9.

W algorytmie sortowania przez wstawianie (Insertion Sort), aby usprawnić działanie i uniknąć każdorazowego sprawdzania wyjścia poza zakres tablicy, stosuje się:

a)

Wartownika (np. na pozycji A[0])

b)

Zmienną globalną

c)

Rekurencję

d)

Wskaźniki.

10.

Porównując sortowanie bąbelkowe z sortowaniem przez wybieranie, która z poniższych obserwacji jest prawdziwa?

a)

Sortowanie bąbelkowe wykonuje zazwyczaj mniej zamian elementów niż sortowanie przez wybieranie

b)

Sortowanie przez wybieranie jest nieco sprawniejsze, ponieważ zamiana elementów następuje w pętli zewnętrznej (rzadziej)

c)

Sortowanie bąbelkowe ma złożoność O(n), a przez wybieranie O(n2)

d)

Obie metody nie wymagają operacji porównania elementów

11.

Co określa notacja dużego O (np. O(n))?

a)

Dokładny czas wykonania programu w sekundach.

b)

Rząd wielkości liczby wykonywanych operacji dominujących w zależności od rozmiaru danych

c)

Ilość pamięci RAM zużytej przez zmienne lokalne.

d)

Maksymalną wielkość tablicy, jaką może obsłużyć komputer.

12.

Złożoność O(log n) (logarytmiczna) jest charakterystyczna dla algorytmu:

a)

Przeszukiwania liniowego.

b)

Sortowania bąbelkowego

c)

Przeszukiwania binarnego

d)

Sprawdzania, czy w tablicy powtarza się element (metodą "każdy z każdym").

13.

Pamięciowa złożoność obliczeniowa algorytmu wyszukującego liczbę w zbiorze n-elementowym (wykorzystującego pojedynczą tablicę) wynosi:

a)

O(1)

b)

O(n)

c)

O(n2)

d)

O(log n)

14.

Które z poniższych zdań dotyczących złożoności są prawdziwe?

a)

Złożoność pesymistyczna określa liczbę operacji w najgorszym możliwym przypadku

b)

Stała złożoność O(1) oznacza, że liczba operacji nie zależy od rozmiaru danych

c)

Złożoność wykładnicza (np. O(2n)) jest bardzo pożądana i oznacza szybki algorytm dla dużych danych

d)

Przy szacowaniu złożoności w notacji dużego O pomijamy stałe współczynniki (np. n/2 zapisujemy jako rząd wielkości n)

15.

Ile bajtów pamięci zajmuje zazwyczaj typ prosty int

a)

1 bajt

b)

2 bajty

c)

4 bajty

d)

8 bajtów

16.

Jaki warunek musi być spełniony, aby można było zastosować algorytm przeszukiwania binarnego?

a)

Tablica nie może zawierać liczb ujemnych

b)

Zbiór danych musi być uporządkowany (posortowany)

c)

Liczba elementów w tablicy musi być parzysta

d)

Zbiór musi być przechowywany na liście, a nie w tablicy

17.

W jaki sposób w języku C++ można przekazać parametr do funkcji, aby funkcja pracowała na oryginale zmiennej (a nie na kopii)?

a)

Przez wartość (standardowe przekazanie)

b)

Przez referencję (używając operatora &)

c)

Przez wskaźnik (przekazując adres zmiennej)

d)

Używając słowa kluczowego const

18.

Ile wynosi maksymalna liczba porównań w algorytmie przeszukiwania liniowego dla zbioru n-elementowego (przypadek pesymistyczny)?

a)

n/2

b)

log n

c)

n

d)

n2

19.

Jaki jest algorytm optymalny (o najmniejszej liczbie porównań) przy jednoczesnym znajdowaniu minimum i maksimum w zbiorze?

a)

Sortowanie tablicy, a następnie wzięcie pierwszego i ostatniego elementu.

b)

Przeszukanie liniowe dwa razy: raz szukając minimum, drugi raz maksimum.

c)

Porównywanie elementów tablicy parami (dziel i zwyciężaj), a następnie szukanie min wśród mniejszych i max wśród większych.

d)

Losowanie elementów i sprawdzanie, czy są minimum lub maksimum.

20.

Jakim wzorem w C++ można wylosować liczbę całkowitą z przedziału [a,b]?

a)

rand() % b + a

b)

rand() % (b - a + 1) + a

c)

rand() % a + b

d)

rand(a, b)

21.

Z jakiego zakresu liczb będzie losowała funkcja Losuj(), przedstawiona w kodzie

a)

0-100

b)

2-102

c)

2-100

d)

0-102

22.

W której linii przedstawionego kodu funkcja SzukajLin(), może zakończyć swoje działanie

a)

tylko w 25

b)

tylko w 26

c)

w 25 i w 26

d)

w 25 lub w 26

23.

Co może zwrócić funkcja przedstawiona w kodzie obok?

a)

dowolną liczbę naturalną

b)

ciąg znaków

c)

true lub false

d)

nic nie zwraca

24.

Proszę zaznaczyć poprawne wywołanie funkcji Obliczenia()

a)

cout << Obliczenia();

b)

x=Obliczenia();

c)

Obliczenia();

d)

x=Obliczenia()+y;

25.

Który fragment kodu zapewnia zamianę wartości pomiędzy zmiennymi a i b

a)

a=b;

b=a;

b)

swap(a, b);

c)

temp=a;

a=b;

b=temp;

d)

a=b=c;

26.

Która funkcja podaje rozmiar w bajtach jaki zajmuje zmienna x w pamięci operacyjnej?

a)

byte(x)

b)

length(x)

c)

size(x)

d)

sizeof(x)

27.

Ile razy wykona się pętla przedstawiona w kodzie

a)

5

b)

4

c)

6

d)

ani razu

28.

Która pętla nie wykona się ani razu

a)

b)

c)

d)

29.

Która pętla będzie pętlą nieskończoną?

a)

b)

c)

d)

30.

Czy na ekranie zobaczymy napis "OK", według załączonego kodu

a)

Tak

b)

Nie

Similar Resources on Wayground

Python Programming Quiz

28 questions

Python Programming Quiz

quiz

Worksheet

•

1st Grade