I85PREP
⌘ K
Matura Computer Science study materials
Matura Computer Science study resources

Matura Computer Science practice questions

One question at a time. Build your Matura Computer Science understanding.

First 50 of 200 questions. Each one lists the choices, the correct answer, and an explanation. The checker at the top of this page saves progress in this browser when it is available.

Continue in the practice tool above to load more questions, 50 at a time.

Question 1Algorithms and Programming

W kodzie zapisanym w języku Python wykonywana jest instrukcja: x = [3, 1, 4, 1, 5]. Którą wartość zwróci wyrażenie x[1] + x[-1]?

  1. 5
  2. 4
  3. 6 Correct answer.
  4. 8

Explanation

W Pythonie indeksy dodatnie liczone są od początku, a ujemne od końca listy, więc x[1] to drugi element (1), a x[-1] to ostatni element (5). Suma wynosi 1 + 5 = 6. Warto pamiętać, że indeksowanie zaczyna się od zera, więc pierwszy element ma indeks 0.

Question 2Algorithms and Programming

Który algorytm sortowania ma w typowym przypadku złożoność czasową O(n log n) i działa w miejscu, sortując tablicę bez dodatkowej tablicy pomocniczej o rozmiarze n?

  1. Sortowanie bąbelkowe
  2. Sortowanie szybkie (quicksort) Correct answer.
  3. Sortowanie przez zliczanie
  4. Sortowanie przez scalanie

Explanation

Sortowanie szybkie dzieli tablicę wokół elementu osiowego i sortuje części rekurencyjnie, osiągając średnio O(n log n) przy pracy w miejscu. Sortowanie przez scalanie wymaga tablicy pomocniczej, a sortowanie bąbelkowe ma złożoność O(n^2). Sortowanie przez zliczanie nie jest porównawcze i wymaga tablicy zliczeń.

Question 3Algorithms and Programming

Dana jest tablica posortowana rosnąco: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Ile porównań z elementami tablicy wykona wyszukiwanie binarne przy szukaniu wartości 23, licząc każde sprawdzenie elementu środkowego?

  1. 4
  2. 5
  3. 2
  4. 3 Correct answer.

Explanation

Wyszukiwanie binarne porównuje najpierw element środkowy. Dla dziesięciu elementów środkiem jest indeks 4 o wartości 16, potem w prawej części środkiem jest 38, a następnie 23. Potrzebne są trzy porównania, zanim zostanie znaleziona szukana wartość.

Question 4Algorithms and Programming

Który opis najlepiej charakteryzuje złożoność pamięciową algorytmu rekurencyjnego obliczającego n-tą liczbę Fibonacciego metodą naiwną (bez zapamiętywania wyników)?

  1. O(n), bo głębokość rekurencji rośnie liniowo Correct answer.
  2. O(1), bo rekurencja nie tworzy struktur danych
  3. O(2^n), bo powstaje wykładnicza liczba wywołań
  4. O(n^2), bo każdy poziom zajmuje n komórek

Explanation

Naiwna rekurencja Fibonacciego wykonuje wykładniczo wiele wywołań, ale w danym momencie aktywny jest tylko jeden łańcuch wywołań o długości proporcjonalnej do n. Stos wywołań zajmuje więc O(n) pamięci. Wykładnicza jest złożoność czasowa, a nie pamięciowa.

Question 5Algorithms and Programming

W jakim celu w algorytmie stosuje się tablicę mieszającą (hash table) zamiast listy posortowanej?

  1. Aby zmniejszyć zużycie pamięci do stałej liczby komórek
  2. Aby uniknąć konieczności definiowania funkcji mieszającej
  3. Aby zagwarantować uporządkowanie kluczy rosnąco
  4. Aby uzyskać średnio stały czas wyszukiwania po kluczu Correct answer.

Explanation

Tablica mieszająca odwzorowuje klucz na indeks za pomocą funkcji mieszającej, dzięki czemu wyszukiwanie, wstawianie i usuwanie są średnio wykonywane w czasie O(1). Lista posortowana pozwala na wyszukiwanie binarne w O(log n), ale nie daje stałego czasu. Uporządkowanie kluczy nie jest cechą tablicy mieszającej.

Question 6Algorithms and Programming

Jaka jest wartość wyrażenia w notacji ONP (odwrotnej notacji polskiej): 6 2 3 * - 4 +?

  1. -16
  2. 16
  3. 4 Correct answer.
  4. -4

Explanation

W ONP operatory występują po argumentach, więc czytamy stos: 6, 2, 3, mnożenie daje 6, odejmowanie 6 - 6 daje 0, a dodanie 4 daje 4. Wynikiem jest 4. Należy pamiętać o kolejności argumentów przy odejmowaniu.

Question 7Algorithms and Programming

Które zdanie poprawnie opisuje własność kolejki FIFO w kontekście algorytmicznym?

  1. Element dodany jako pierwszy jest usuwany jako pierwszy Correct answer.
  2. Element dodany jako ostatni jest usuwany jako pierwszy
  3. Element o największym kluczu jest usuwany jako pierwszy
  4. Element jest usuwany w losowej kolejności

Explanation

Kolejka FIFO (first in, first out) usuwa elementy w kolejności ich dodawania, więc najstarszy element opuszcza kolejkę jako pierwszy. Operacja dodawania odbywa się na końcu, a usuwania na początku. Kolejność LIFO dotyczy stosu, a nie kolejki.

Question 8Algorithms and Programming

Algorytm przeszukiwania grafu w głąb (DFS) uruchomiono na grafie nieskierowanym. Którą strukturę danych najczęściej wykorzystuje się do jego implementacji iteracyjnej?

  1. Kopiec maksymalny
  2. Drzewo zrównoważone
  3. Stos Correct answer.
  4. Kolejkę FIFO

Explanation

Iteracyjna wersja DFS odkłada wierzchołki do odwiedzenia na stos, dzięki czemu jako następny przetwarzany jest ostatnio dodany wierzchołek. Kolejka FIFO jest typowa dla BFS. Kopiec i drzewo zrównoważone nie są standardowymi strukturami dla DFS.

Question 9Algorithms and Programming

W grafie skierowanym bez cykli ujemnych stosujemy algorytm Dijkstry do wyznaczenia najkrótszych ścieżek. Który warunek jest wymagany, aby algorytm działał poprawnie?

  1. Wszystkie wagi krawędzi są nieujemne Correct answer.
  2. Liczba krawędzi musi być mniejsza niż liczba wierzchołków
  3. Każdy wierzchołek ma stopień co najmniej 2
  4. Graf musi być nieskierowany

Explanation

Algorytm Dijkstry zakłada nieujemne wagi krawędzi, ponieważ po wybraniu wierzchołka o najmniejszym dystansie nie może on zostać później poprawiony przez dłuższą ścieżkę. Przy wagach ujemnych potrzebny jest algorytm Bellmana-Forda. Graf może być skierowany, a stopnie wierzchołków nie mają znaczenia.

Question 10Algorithms and Programming

W programie zadeklarowano zmienną całkowitą i oraz wykonano pętlę: for i in range(0, 10, 3): print(i). Które wartości zostaną wypisane?

  1. 3, 6, 9
  2. 0, 3, 6, 9 Correct answer.
  3. 0, 3, 6
  4. 0, 1, 2, 3

Explanation

Funkcja range(start, stop, step) generuje liczby od start do stop wyłącznie, zwiększając je o step. Dla range(0, 10, 3) otrzymujemy 0, 3, 6, 9, ponieważ 12 przekracza granicę. Wartość stop nie jest generowana.

Question 11Algorithms and Programming

Który algorytm znajdowania najkrótszej ścieżki w grafie z wagami ujemnymi, ale bez cykli ujemnych, jest poprawny?

  1. Algorytm Kruskala
  2. Przeszukiwanie w głąb bez zapamiętywania dystansów
  3. Algorytm Dijkstry
  4. Algorytm Bellmana-Forda Correct answer.

Explanation

Algorytm Bellmana-Forda wielokrotnie relaksuje wszystkie krawędzie, więc radzi sobie z wagami ujemnymi, o ile w grafie nie ma cykli ujemnych. Dijkstra wymaga wag nieujemnych, a DFS nie gwarantuje najkrótszej ścieżki. Kruskal służy do budowy minimalnego drzewa rozpinającego.

Question 12Algorithms and Programming

Program ma odwrócić kolejność znaków w łańcuchu s. Które wyrażenie w Pythonie zwróci łańcuch odwrócony?

  1. s[::-1] Correct answer.
  2. s[::2]
  3. s[:-1]
  4. s[1:]

Explanation

Składnia wycinania s[start:stop:step] z krokiem -1 przechodzi przez łańcuch od końca do początku, dając odwrócenie. Wyrażenie s[1:] usuwa pierwszy znak, a s[:-1] usuwa ostatni. Krok 2 zwraca co drugi znak.

Question 13Algorithms and Programming

Rozważamy algorytm, który dla tablicy n elementów wykonuje pętlę zewnętrzną n razy, a w każdej iteracji pętlę wewnętrzną również n razy, wykonując w niej stałą liczbę operacji. Jaka jest złożoność czasowa tego algorytmu?

  1. O(n^2) Correct answer.
  2. O(log n)
  3. O(2^n)
  4. O(n)

Explanation

Liczba operacji jest iloczynem liczby iteracji obu pętli, czyli n * n = n^2, pomnożonym przez stały czas operacji w ciele. Złożoność asymptotyczna to O(n^2). Zagnieżdżone pętle o liniowej liczbie iteracji dają wynik kwadratowy.

Question 14Algorithms and Programming

W drzewie binarnym wyszukiwania (BST) przechowywane są unikalne liczby całkowite. Który warunek musi być spełniony dla każdego węzła?

  1. Wszystkie klucze w lewym poddrzewie są większe, a w prawym mniejsze od klucza węzła
  2. Wszystkie klucze w lewym poddrzewie są mniejsze, a w prawym większe od klucza węzła Correct answer.
  3. Każdy węzeł ma dokładnie dwoje dzieci
  4. Klucz lewego dziecka jest mniejszy, a prawego większy, bez ograniczeń na dalsze poziomy

Explanation

Właściwość BST dotyczy całych poddrzew, nie tylko bezpośrednich dzieci: wszystkie klucze w lewym poddrzewie są mniejsze, a w prawym większe od klucza węzła. Tylko taki warunek gwarantuje poprawne wyszukiwanie. Drzewo BST nie musi być pełne.

Question 15Algorithms and Programming

Funkcja rekurencyjna ma postać: f(0) = 1, f(n) = 2 * f(n-1) dla n > 0. Ile wynosi f(4)?

  1. 16 Correct answer.
  2. 8
  3. 32
  4. 4

Explanation

Rozwijamy rekurencję: f(1) = 2, f(2) = 4, f(3) = 8, f(4) = 16. Wzór odpowiada potędze 2^n, więc dla n = 4 wynik to 16. Warto sprawdzić przypadek bazowy, aby nie pominąć pierwszego kroku.

Question 16Algorithms and Programming

Który algorytm zachłanny wyznacza minimalne drzewo rozpinające grafu ważonego?

  1. Algorytm Dijkstry
  2. Algorytm Kruskala Correct answer.
  3. Sortowanie przez scalanie
  4. Algorytm Forda-Fulkersona

Explanation

Algorytm Kruskala sortuje krawędzie według wag i dodaje je, jeśli nie tworzą cyklu, aż powstanie drzewo rozpinające. Dijkstra wyznacza najkrótsze ścieżki, a Ford-Fulkerson maksymalny przepływ. Sortowanie przez scalanie nie dotyczy grafów.

Question 17Algorithms and Programming

W programie występuje pętla while z warunkiem sprawdzanym na początku. Które zdanie poprawnie opisuje jej działanie?

  1. Ciało pętli zawsze wykona się co najmniej raz
  2. Pętla while nie może zawierać instrukcji warunkowej
  3. Warunek jest sprawdzany dopiero po wykonaniu ciała
  4. Ciało pętli może nie wykonać się ani razu, jeśli warunek jest fałszywy na starcie Correct answer.

Explanation

W pętli while warunek jest testowany przed każdą iteracją, więc gdy jest fałszywy od początku, ciało nie zostanie wykonane. Gwarancję co najmniej jednego wykonania daje pętla do-while. Instrukcje warunkowe mogą występować wewnątrz pętli.

Question 18Algorithms and Programming

Dana jest tablica [7, 3, 9, 1]. Po pierwszym przebiegu sortowania bąbelkowego (rosnąco, porównania sąsiednich elementów od lewej) tablica ma postać:

  1. [1, 3, 7, 9]
  2. [3, 7, 1, 9] Correct answer.
  3. [7, 3, 1, 9]
  4. [3, 1, 7, 9]

Explanation

Pierwszy przebieg porównuje 7 i 3 (zamiana), potem 7 i 9 (bez zamiany), a na końcu 9 i 1 (zamiana). Otrzymujemy [3, 7, 1, 9], a największy element 9 trafia na koniec. Pełne posortowanie wymaga kolejnych przebiegów.

Question 19Algorithms and Programming

Który problem jest klasycznym przykładem problemu NP-zupełnego?

  1. Wyszukiwanie binarne w posortowanej tablicy
  2. Obliczanie sumy elementów tablicy
  3. Problem komiwojażera w wersji decyzyjnej Correct answer.
  4. Sortowanie tablicy algorytmem przez scalanie

Explanation

Decyzyjna wersja problemu komiwojażera, pytająca czy istnieje trasa krótsza niż zadana długość, jest NP-zupełna. Pozostałe wymienione problemy mają algorytmy wielomianowe i należą do klasy P. NP-zupełność oznacza, że nie znamy algorytmu wielomianowego, a problem jest co najmniej tak trudny jak każdy problem NP.

Question 20Algorithms and Programming

W języku Python zdefiniowano funkcję: def suma(a, b=3): return a + b. Jaki będzie wynik wywołania suma(4, 5)?

  1. 7
  2. 12
  3. 9 Correct answer.
  4. 8

Explanation

Argument domyślny b=3 jest używany tylko wtedy, gdy przy wywołaniu nie podano wartości. Tutaj podano oba argumenty, więc b przyjmuje wartość 5, a wynik to 4 + 5 = 9. Wartość domyślna zostaje przesłonięta.

Question 21Algorithms and Programming

Rozważamy algorytm dziel i zwyciężaj, którego czas opisuje rekurencja T(n) = 2T(n/2) + O(n). Jaka jest złożoność asymptotyczna tego algorytmu?

  1. O(log n)
  2. O(n)
  3. O(n^2)
  4. O(n log n) Correct answer.

Explanation

Zgodnie z twierdzeniem o rekurencji głównej mamy dwa podproblemy o rozmiarze n/2 i liniowy koszt scalania, co daje O(n log n). Przykładem jest sortowanie przez scalanie. Złożoność liniowa wystąpiłaby, gdyby koszt scalania był stały.

Question 22Algorithms and Programming

Który mechanizm programowania dynamicznego odróżnia ją od prostego dziel i zwyciężaj?

  1. Podział problemu na podproblemy o rozłącznych danych
  2. Rekurencyjne wywołanie funkcji dla połowy danych
  3. Sortowanie danych wejściowych przed obliczeniami
  4. Zapamiętywanie wyników podproblemów, które się powtarzają Correct answer.

Explanation

Programowanie dynamiczne wykorzystuje nakładanie się podproblemów i zapisuje ich wyniki, aby uniknąć wielokrotnych obliczeń. Dziel i zwyciężaj zakłada zwykle podproblemy rozłączne. Zapamiętywanie może przyjąć formę tablicy lub memoizacji.

Question 23Algorithms and Programming

W algorytmie sortowania szybkiego wybierany jest element osiowy (pivot). Który wybór pivota prowadzi do najgorszego przypadku złożoności O(n^2) przy już posortowanej tablicy?

  1. Mediana z trzech elementów
  2. Element środkowy tablicy
  3. Losowy element tablicy
  4. Zawsze pierwszy element tablicy Correct answer.

Explanation

Gdy pivotem jest zawsze pierwszy element posortowanej tablicy, podział tworzy jedno poddrzewo o rozmiarze n-1 i drugie puste, co daje O(n^2). Losowy pivot lub mediana z trzech zmniejszają ryzyko takiego podziału. Wybór środkowego elementu w posortowanej tablicy daje zrównoważone podziały.

Question 24Algorithms and Programming

W programie zadeklarowano dwuwymiarową tablicę całkowitą o wymiarach 3 na 4, indeksowaną od zera. Ile elementów można zapisać w tej tablicy?

  1. 3
  2. 4
  3. 12 Correct answer.
  4. 7

Explanation

Liczba elementów tablicy dwuwymiarowej to iloczyn liczby wierszy i kolumn, czyli 3 * 4 = 12. Indeksy w każdym wymiarze zaczynają się od zera, więc poprawne indeksy to od 0 do 2 oraz od 0 do 3. Suma wymiarów nie opisuje liczby komórek.

Question 25Algorithms and Programming

Który opis poprawnie charakteryzuje algorytm zachłanny?

  1. Gwarantuje optymalność dla każdego problemu optymalizacyjnego
  2. Zawsze przegląda wszystkie możliwe rozwiązania i wybiera najlepsze
  3. Wymaga zapamiętywania wyników wszystkich podproblemów
  4. Podejmuje lokalnie najlepszą decyzję i nie wraca do niej, co nie zawsze daje rozwiązanie optymalne Correct answer.

Explanation

Algorytm zachłanny wybiera najlepszą opcję w danym kroku i nie modyfikuje wcześniejszych decyzji. Optymalność jest gwarantowana tylko wtedy, gdy problem ma własność wyboru zachłannego i optymalnej podstruktury. Przegląd wszystkich rozwiązań to metoda siłowa, a zapamiętywanie podproblemów to programowanie dynamiczne.

Question 26Algorithms and Programming

W języku Python wykonano instrukcję: s = "matura"; print(s[1:4]). Który łańcuch zostanie wypisany?

  1. at
  2. atu Correct answer.
  3. matu
  4. atur

Explanation

W notacji wycinka s[a:b] indeks początkowy a jest włączany, a końcowy b wykluczany. Dla s = "matura" znaki o indeksach 1, 2 i 3 to 'a', 't', 'u', więc wynikiem jest "atu".

Question 27Algorithms and Programming

W algorytmie sortowania przez wstawianie (insertion sort) przetwarzamy tablicę [5, 2, 4, 1]. Jak będzie wyglądać tablica po dwóch pełnych krokach wstawiania kolejnych elementów?

  1. [2, 5, 4, 1]
  2. [4, 2, 5, 1]
  3. [1, 2, 4, 5]
  4. [2, 4, 5, 1] Correct answer.

Explanation

Po pierwszym kroku element 2 wstawiamy przed 5, otrzymując [2, 5, 4, 1]. W drugim kroku element 4 wstawiamy do posortowanego prefiksu [2, 5], co daje [2, 4, 5, 1].

Question 28Algorithms and Programming

Funkcja rekurencyjna jest zdefiniowana: f(0) = 0, f(n) = n + f(n-1) dla n > 0. Którą wartość zwraca f(5)?

  1. 120
  2. 15 Correct answer.
  3. 20
  4. 10

Explanation

Rozwijając rekurencję otrzymujemy sumę 5 + 4 + 3 + 2 + 1 + 0, czyli 15. Ogólnie funkcja liczy sumę liczb od 0 do n, co dla n = 5 daje 15.

Question 29Algorithms and Programming

Który opis poprawnie charakteryzuje złożoność pamięciową algorytmu sortowania przez scalanie (merge sort) działającego na tablicy?

  1. O(log n), ponieważ rekurencja zajmuje stos wywołań bez dodatkowej tablicy
  2. O(n), ponieważ scalanie wymaga dodatkowej tablicy pomocniczej Correct answer.
  3. O(1), ponieważ sortuje w miejscu
  4. O(n^2), ponieważ tworzy tablicę dla każdej pary elementów

Explanation

Scalanie dwóch posortowanych fragmentów wymaga bufora o rozmiarze proporcjonalnym do liczby scalanych elementów. Dlatego dodatkowa pamięć jest rzędu O(n), niezależnie od głębokości rekurencji O(log n).

Question 30Algorithms and Programming

W grafie skierowanym stosujemy sortowanie topologiczne. Który warunek jest konieczny, aby takie uporządkowanie wierzchołków istniało?

  1. Graf musi mieć co najmniej jedną krawędź
  2. Graf musi być spójny
  3. Graf musi być pełny
  4. Graf musi być acykliczny Correct answer.

Explanation

Sortowanie topologiczne porządkuje wierzchołki tak, by każda krawędź prowadziła od wcześniejszego do późniejszego. Istnienie takiego porządku jest równoważne brakowi cykli w grafie skierowanym.

Question 31Algorithms and Programming

W programie wykonano: x = 17; y = 5; print(x // y, x % y). Co zostanie wypisane?

  1. 3 3
  2. 3.4 2
  3. 3 2 Correct answer.
  4. 4 1

Explanation

Operator // zwraca część całkowitą dzielenia (17 // 5 = 3), a % resztę z dzielenia (17 % 5 = 2). Oba wyniki są wypisywane oddzielone spacją.

Question 32Algorithms and Programming

W drzewie binarnym wyszukiwania (BST) usuwamy węzeł, który ma dwoje dzieci. Które postępowanie zachowuje własność BST?

  1. Zastąpienie wartości węzła maksimum z lewego poddrzewa i usunięcie tego maksimum Correct answer.
  2. Usunięcie całego lewego poddrzewa wraz z węzłem
  3. Zastąpienie wartości węzła dowolnym liściem z prawego poddrzewa
  4. Zamiana wartości węzła z wartością jego rodzica

Explanation

Maksimum lewego poddrzewa jest większe od wszystkich pozostałych kluczy w tym poddrzewie i mniejsze od kluczy prawego poddrzewa, więc zachowuje porządek BST. Analogicznie można użyć minimum z prawego poddrzewa.

Question 33Algorithms and Programming

Który algorytm rozwiązuje problem wydawania reszty metodą zachłanną poprawnie dla dowolnego systemu nominałów?

  1. Zawsze algorytm wybierający najmniejszy nominał
  2. Zawsze algorytm zachłanny wybierający największy nominał
  3. Algorytm sortujący nominały rosnąco i biorący pierwszy z nich
  4. Żaden; zachłanność nie gwarantuje optimum dla dowolnego systemu nominałów Correct answer.

Explanation

Metoda zachłanna jest optymalna tylko dla niektórych systemów nominałów, takich jak polski. Dla innych systemów, na przykład {1, 3, 4}, wydanie 6 zachłannie daje trzy monety, a optymalnie dwie.

Question 34Algorithms and Programming

Która struktura danych najlepiej nadaje się do implementacji kolejki priorytetowej w algorytmie Dijkstry?

  1. Stos LIFO
  2. Sterta binarna Correct answer.
  3. Tablica haszująca
  4. Lista jednokierunkowa bez sortowania

Explanation

Sterta binarna pozwala w czasie O(log n) wstawiać elementy i wyjmować minimum, co daje efektywną implementację Dijkstry. Zapewnia to złożoność O((V+E) log V) przy reprezentacji listowej.

Question 35Algorithms and Programming

Program zawiera pętlę: for i in range(3): for j in range(4): suma += 1. Ile razy zostanie wykonane zwiększenie suma?

  1. 4
  2. 12 Correct answer.
  3. 7
  4. 3

Explanation

Pętla zewnętrzna wykonuje się 3 razy, a wewnętrzna 4 razy dla każdej iteracji zewnętrznej. Łączna liczba wykonań wynosi więc 3 * 4 = 12.

Question 36Algorithms and Programming

Rozważamy problem plecakowy 0-1 rozwiązywany programowaniem dynamicznym. Co oznacza komórka tablicy dp[i][w]?

  1. Liczbę przedmiotów mieszczących się w pojemności w
  2. Minimalną liczbę przedmiotów potrzebną do wypełnienia pojemności w
  3. Maksymalną wartość osiągalną przy użyciu przedmiotów od 1 do i i pojemności w Correct answer.
  4. Wartość i-tego przedmiotu przy pojemności w

Explanation

Stan dp[i][w] opisuje najlepsze rozwiązanie podproblemu ograniczonego do pierwszych i przedmiotów i pojemności w. Przejście polega na wyborze między pominięciem przedmiotu i a jego dodaniem, jeśli się mieści.

Question 37Algorithms and Programming

Który warunek zatrzymania jest poprawny dla algorytmu wyszukiwania binarnego w posortowanej tablicy rosnącej?

  1. Zakończ, gdy lewy = prawy
  2. Zakończ, gdy lewy > prawy Correct answer.
  3. Zakończ, gdy środkowy = 0
  4. Zakończ po dokładnie n krokach

Explanation

Przedział poszukiwań jest wyznaczany przez indeksy lewy i prawy; gdy lewy przekroczy prawy, przedział jest pusty i elementu nie ma. Warunek lewy > prawy poprawnie obsługuje też przypadek braku elementu.

Question 38Algorithms and Programming

W programie zdefiniowano: a = [1, 2, 3]; b = a; b.append(4). Jaki będzie wynik print(a)?

  1. [4]
  2. [1, 2, 3, 4] Correct answer.
  3. [1, 2, 3]
  4. Błąd wykonania

Explanation

Przypisanie b = a kopiuje referencję do tej samej listy, a nie samą listę. Modyfikacja przez b zmienia więc obiekt widziany również przez a.

Question 39Algorithms and Programming

Rozważamy problem decyzyjny należący do klasy NP. Co oznacza, że problem jest NP-zupełny?

  1. Należy do NP i każdy problem z NP sprowadza się do niego w czasie wielomianowym Correct answer.
  2. Nie należy do NP, ale da się zweryfikować w czasie wykładniczym
  3. Należy do P i jest nierozstrzygalny
  4. Należy do NP i da się rozwiązać w czasie wielomianowym

Explanation

NP-zupełność wymaga dwóch rzeczy: problem jest w NP oraz jest NP-trudny, czyli każdy problem z NP redukuje się do niego w czasie wielomianowym. To sprawia, że rozwiązanie wielomianowe dla jednego NP-zupełnego problemu rozwiązałoby wszystkie problemy z NP.

Question 40Algorithms and Programming

W języku Python wykonano: print(len("abc") + int("2") * 3). Jaki będzie wynik?

  1. 15
  2. 9 Correct answer.
  3. Błąd typu
  4. abc23

Explanation

len("abc") wynosi 3, a int("2") daje liczbę 2, która pomnożona przez 3 daje 6. Suma 3 + 6 wynosi 9.

Question 41Algorithms and Programming

Algorytm przeszukiwania grafu wszerz (BFS) uruchomiono na grafie nieskierowanym bez wag. Co gwarantuje wynik BFS dla wierzchołka startowego?

  1. Najmniejszą sumę wag na ścieżce do każdego wierzchołka
  2. Najmniejszą liczbę krawędzi na ścieżce do każdego osiągalnego wierzchołka Correct answer.
  3. Odwiedzenie wierzchołków w kolejności malejących etykiet
  4. Znalezienie wszystkich cykli w grafie

Explanation

BFS odwiedza wierzchołki warstwami według odległości od źródła, więc po raz pierwszy dociera do wierzchołka najkrótszą ścieżką pod względem liczby krawędzi. Właściwość ta dotyczy grafów nieważonych.

Question 42Algorithms and Programming

Funkcja T(n) opisuje liczbę operacji algorytmu: T(1) = 1 oraz T(n) = T(n-1) + n dla n > 1. Którą złożoność asymptotyczną ma ten algorytm?

  1. O(n)
  2. O(2^n)
  3. O(n log n)
  4. O(n^2) Correct answer.

Explanation

Rozwijając rekurencję otrzymujemy sumę 1 + 2 + ... + n, która wynosi n(n+1)/2. Dominujący składnik jest kwadratowy, więc złożoność to O(n^2).

Question 43Algorithms and Programming

W algorytmie sortowania szybkiego (quicksort) stosujemy schemat podziału Lomuto z pivotem wybieranym jako ostatni element. Kiedy liczba porównań jest największa?

  1. Gdy tablica zawiera same różne wartości losowe
  2. Gdy tablica jest już posortowana, a pivot jest skrajnym elementem Correct answer.
  3. Gdy pivot jest medianą tablicy
  4. Gdy pivot zawsze dzieli tablicę na dwie równe części

Explanation

Przy posortowanej tablicy i pivotcie będącym ostatnim elementem każdy podział wydziela podproblem o rozmiarze n-1 i pusty. Prowadzi to do rekurencji T(n) = T(n-1) + O(n), czyli złożoności O(n^2).

Question 44Algorithms and Programming

Który mechanizm jest charakterystyczny dla programowania dynamicznego w odróżnieniu od czystego dziel i zwyciężaj?

  1. Rekurencyjne wywołania funkcji
  2. Zapamiętywanie wyników powtarzających się podproblemów Correct answer.
  3. Dzielenie problemu na mniejsze części
  4. Sortowanie danych wejściowych przed obliczeniami

Explanation

Programowanie dynamiczne wykorzystuje nakładanie się podproblemów, więc zapamiętuje ich wyniki w tablicy lub mapie. Dzięki temu każdy podproblem jest liczony raz, co odróżnia je od dziel i zwyciężaj, gdzie podproblemy są rozłączne.

Question 45Algorithms and Programming

W programie zadeklarowano tablicę dwuwymiarową o wymiarach 5 wierszy i 3 kolumn, indeksowaną od zera. Który indeks jest poprawny dla ostatniego elementu w pamięci przy porządku wierszowym?

  1. tab[5][3]
  2. tab[2][4]
  3. tab[3][5]
  4. tab[4][2] Correct answer.

Explanation

Przy indeksowaniu od zera ostatni wiersz ma indeks 4, a ostatnia kolumna indeks 2. Element tab[4][2] jest więc ostatnim elementem przy porządku wierszowym.

Question 46Algorithms and Programming

Który opis poprawnie charakteryzuje własność optymalnej podstruktury wykorzystywaną w programowaniu dynamicznym?

  1. Optymalne rozwiązanie problemu zawiera optymalne rozwiązania podproblemów Correct answer.
  2. Każdy podproblem można rozwiązać niezależnie od pozostałych
  3. Lokalnie najlepszy wybór zawsze prowadzi do optimum globalnego
  4. Problem można rozwiązać w czasie wielomianowym

Explanation

Optymalna podstruktura oznacza, że rozwiązanie optymalne da się złożyć z rozwiązań optymalnych dla podproblemów. To warunek pozwalający budować tablicę wyników od mniejszych podproblemów.

Question 47Algorithms and Programming

Który algorytm znajdowania minimalnego drzewa rozpinającego grafu ważonego działa poprawnie również wtedy, gdy wagi krawędzi są ujemne?

  1. Algorytm Kruskala Correct answer.
  2. Algorytm Floyda-Warshalla
  3. Algorytm Dijkstry
  4. Algorytm Bellmana-Forda

Explanation

Kruskal sortuje krawędzie według wag i dodaje je, jeśli nie tworzą cyklu, więc znak wag nie wpływa na poprawność. Dijkstra wymaga nieujemnych wag, a Bellman-Ford i Floyd-Warshall rozwiązują problem najkrótszych ścieżek, a nie MST.

Question 48Algorithms and Programming

Program ma sprawdzić, czy liczba całkowita n > 1 jest pierwsza. Który warunek zakończenia pętli jest poprawny dla testu dzielenia przez kolejne liczby?

  1. Przerwij, gdy dzielnik przekroczy n/2
  2. Przerwij, gdy dzielnik osiągnie n
  3. Przerwij, gdy dzielnik przekroczy pierwiastek z n Correct answer.
  4. Przerwij, gdy dzielnik będzie liczbą parzystą

Explanation

Jeśli n ma dzielnik większy od pierwiastka z n, to ma też dzielnik mniejszy od tego pierwiastka, więc wystarczy sprawdzić dzielniki do pierwiastka z n włącznie. Daje to złożoność O(sqrt(n)) zamiast O(n).

Question 49Algorithms and Programming

Który problem jest klasycznym przykładem problemu, dla którego nie znamy algorytmu wielomianowego i który jest NP-zupełny?

  1. Problem komiwojażera w wersji decyzyjnej Correct answer.
  2. Sortowanie tablicy liczb całkowitych
  3. Znajdowanie największego elementu tablicy
  4. Sprawdzanie, czy liczba jest parzysta

Explanation

Decyzyjna wersja problemu komiwojażera, pytająca czy istnieje trasa krótsza niż zadana wartość, jest NP-zupełna. Pozostałe wymienione problemy mają algorytmy wielomianowe, a sortowanie nawet O(n log n).

Question 50Algorithms and Programming

W grafie skierowanym z wagami dodatnimi chcemy znaleźć najkrótsze ścieżki z jednego źródła. Który algorytm daje poprawny wynik i jest efektywniejszy od Bellmana-Forda dla grafów rzadkich?

  1. Przeszukiwanie w głąb (DFS)
  2. Algorytm Dijkstry ze stertą binarną Correct answer.
  3. Sortowanie topologiczne
  4. Algorytm Floyda-Warshalla

Explanation

Dla nieujemnych wag Dijkstra ze stertą osiąga złożoność O((V+E) log V), lepszą niż O(VE) Bellmana-Forda w grafach rzadkich. Poprawność wynika z faktu, że po wyjęciu wierzchołka o najmniejszym dystansie jego odległość jest już ostateczna.