MINP-R0-100-2305 • Otwarte rozszerzone • 7 pkt • Trudność: ★★★★☆

Zadanie 1

Matura z informatyki, maj 2023, poziom rozszerzony

Wymaganie:

Wymaganie ogólne II (Programowanie i rozwiązywanie problemów z wykorzystaniem komputera) oraz III.1 (algorytmy rekurencyjne, struktury drzewiaste). Podstawa programowa: drzewa binarne, rekurencja, złożoność obliczeniowa.

Treść zadania

Zadanie 1. Biblioteczka

Pewna biblioteczka ma strukturę drzewa binarnego z 5 poziomami (poziomy ponumerowane są 0, 1, 2, 3, 4). Na każdym poziomie i znajduje się 2^i przegródek (na poziomie 0 - jedna, na poziomie 4 - szesnaście). Książki wstawia się do biblioteczki zgodnie z następującą zasadą: pierwszą wstawiamy do przegródki o numerze 1 na poziomie 0. Kolejne książki wstawiamy w taki sposób, że jeśli rodzic znajduje się w przegródce B[i, j], to lewe dziecko trafia do B[i+1, 2j-1], a prawe do B[i+1, 2j]. Książkę zawsze wstawiamy do najwyżej położonej i najbardziej z lewej strony wolnej przegródki (przy zachowaniu reguł drzewa).

Zadanie 1.1. (0–2) Podaj zawartość biblioteczki po wstawieniu do niej kolejno książek o numerach: 14, 18, 12, 9, 20, 15, 17. Numery książek wpisz we właściwe miejsca na schemacie.

Zadanie 1.2. (0–3) Uzupełnij tabelkę – wpisz, ile minimalnie, a ile maksymalnie musi być półek w biblioteczce, żeby można było umieścić w niej n książek i żeby na ostatniej półce znalazła się co najmniej jedna książka. Wypełnij wiersze dla n = 7, 16, 31, 32 oraz dla n = 2^k − 1 (k > 0).

Zadanie 1.3. (0–2) Dany jest rekurencyjny algorytm A(i, j):

wypisz numer książki z przegródki B[i, j]
jeżeli przegródka B[i+1, 2j−1] nie jest pusta, to wykonaj A(i+1, 2j−1)
jeżeli przegródka B[i+1, 2j] nie jest pusta, to wykonaj A(i+1, 2j)

Działanie rozpoczynamy od wywołania A(0, 1). Podaj ciągi liczb wypisane przez algorytm A dla dwóch podanych zawartości biblioteczek (a) i (b).

Źródło: arkusz CKE MINP-R0-100-2305. Otwórz oryginalny PDF

Rozwiązanie

1.1. Wstawianie do drzewa binarnego (kopca BST – zawsze do najwyższego, najbardziej lewego wolnego miejsca):

14 → B[0,1]
18 → B[1,1]
12 → B[1,2]
9 → B[2,1]
20 → B[2,2]
15 → B[2,3]
17 → B[2,4]

Schemat:

1.2. Każda półka i (oprócz ostatniej) musi być w pełni zapełniona; na ostatniej co najmniej 1 książka.

n	min półek	max półek
7	3	7
16	5	16
31	5	31
32	6	32
2^k − 1	k	2^k − 1

Uzasadnienie: minimum osiągamy, gdy wypełniamy drzewo od góry (potrzeba ⌈log₂(n+1)⌉ poziomów ⇒ ⌈log₂(n+1)⌉ półek). Maksimum osiągamy układając książki "łańcuszkowo" – każda na osobnej półce, więc max = n (ograniczone do 5 dla biblioteczki z zadania; tu pytamy ogólnie, max = n).

1.3. Algorytm A wykonuje przejście drzewa w porządku pre-order (najpierw korzeń, potem lewe poddrzewo, potem prawe).

a) Drzewo: 9 (korzeń); lewe poddrzewo: 2 → (10, 13); prawe poddrzewo: 12 → (14, 15).
Ciąg pre-order: 9, 2, 10, 13, 12, 14, 15
b) Drzewo: 10 (korzeń); lewe poddrzewo: 8 → (4, 6), (-, -); prawe poddrzewo: 15 → (12, -); węzeł 4 ma dziecko - puste, węzeł 6 ma dziecko 13.
Odczyt schematu: 10 → 8 → 4 → (lewe puste, prawe puste) → 6 → 13 → ... → 15 → 12.
Ciąg pre-order: 10, 8, 4, 6, 13, 15, 12

Typowy błąd / pułapka

Algorytm A to klasyczne pre-order (NLR), a nie in-order ani BFS. Typowy błąd: wypisywanie według poziomów (BFS) zamiast rekurencyjnie w głąb. Druga pułapka 1.2: pomylić "co najmniej jedna na ostatniej półce" z "ostatnia półka pełna" – maksimum to liczba półek równa liczbie książek (każda na osobnej półce), a nie 2^k.

Strona arkusza CKE z treścią zadania

Zadanie 1 - informatyka 2023 PR — Strona arkusza CKE 2023 PR informatyka - zadanie 1 (Biblioteczka). Na podstawie: CKE 2023 Oryginalny PDF CKE, str. 5

Rozwiązanie

1.1. Wstawianie 14, 18, 12, 9, 20, 15, 17

Reguła “rodzic B[i,j] → dzieci B[i+1, 2j−1] i B[i+1, 2j]” oznacza pełne drzewo binarne wypełniane poziomami od lewej do prawej.

poziom 0:         14
poziom 1:    18         12
poziom 2:  9    20    15    17

1.2. Tabelka min/max półek

Minimum: trzeba ⌈log₂(n+1)⌉ poziomów, więc tyle samo półek (poziom 0 to półka 1). Maksimum: jedna książka na półce — n półek.

n	min	max
7	3	7
16	5	16
31	5	31
32	6	32
2^k − 1	k	2^k − 1

1.3. Algorytm A = pre-order (NLR)

Definicja A(i,j): wypisz B[i,j], potem rekurencyjnie lewe dziecko, potem prawe.

def A(B, i, j):
    print(B[i][j])
    if (i+1, 2*j-1) in B:
        A(B, i+1, 2*j-1)
    if (i+1, 2*j) in B:
        A(B, i+1, 2*j)

a) 9, 2, 10, 13, 12, 14, 15
b) 10, 8, 4, 6, 13, 15, 12

Rozumiesz, jak to rozwiązać?

Przećwicz podobne typy zadań w aplikacji

matury-online.pl ma tysiące zadań pogrupowanych po dziedzinach. Sprawdź, czy temat „drzewo binarne, biblioteczka, algorytm rekurencyjny, struktury danych" zrobisz samodzielnie.

Otwórz matury-online.pl