{"id":"informatyka-2019-maj-matura-rozszerzona/zad/2.1","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"2.1","points":2,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Zadanie 2.1. (0-2)\na) Uzupełnij miejsca oznaczone kropkami w drzewie wywołań funkcji pisz otrzymanym\nw wyniku wywołania pisz(\"\",2,2).\nb) W kwadratowych polach, przy węzłach drzewa, podaj odpowiednią kolejność wywołań\nfunkcji pisz, tzn. przy pierwszym wywołaniu - 1, przy kolejnym - 2 itd.\npisz(\"\",2,2)\npisz(\"0\",2,2)\npisz(\"1\",2,2)\npisz(\"00\",2,2)\npisz(\"01\",2,2)\n1\nMIN_1R","answer":null,"answer_text":"Zadanie 2.1. (0-2)\nWymagania ogólne\nWymagania szczegółowe\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji […]\nz zastosowaniem podejścia algorytmicznego.\n5. Rozwiązywanie problemów\ni podejmowanie decyzji […], stosowanie\npodejścia algorytmicznego.\nZdający:\n5) posługuje się podstawowymi technikami\nalgorytmicznymi;\n9) stosuje rekurencję w prostych sytuacjach\nproblemowych;\n11) opisuje podstawowe algorytmy\ni stosuje:[…]\nd) algorytmy na tekstach […]\n16) opisuje własności algorytmów na\npodstawie ich analizy;\n17) ocenia zgodność algorytmu ze\nspecyfikacją problemu;\n18) oblicza liczbę operacji wykonywanych\nprzez algorytm.\nSchemat punktowania\n2 p. - za poprawną odpowiedź, w tym:\n1 p. - poprawne uzupełnienie drzewka wywołań funkcji pisz,\n1 p. - prawidłową kolejność wywołań.\n0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.\nPoprawna odpowiedź","solution":"## Poprawna odpowiedź\n\n**a) Brakujące węzły:** `pisz(\"10\", 2, 2)` i `pisz(\"11\", 2, 2)`.\n\n**b) Kolejność wywołań:**\n\n| Numer | Wywołanie |\n| 1 | pisz(\"\", 2, 2) |\n| 2 | pisz(\"0\", 2, 2) |\n| 3 | pisz(\"00\", 2, 2) |\n| 4 | pisz(\"01\", 2, 2) |\n| 5 | pisz(\"1\", 2, 2) |\n| 6 | pisz(\"10\", 2, 2) |\n| 7 | pisz(\"11\", 2, 2) |\n\n**Drzewo z numeracją (pre-order DFS):**\n\n[1] pisz(\"\", 2, 2)\n[2] pisz(\"0\", 2, 2) [5] pisz(\"1\", 2, 2)\n[3] pisz(\"00\") [4] pisz(\"01\") [6] pisz(\"10\") [7] pisz(\"11\")\n\n## Sposób 1 - symulacja rekurencji krok po kroku\n\nFunkcja `pisz(s, n, k)`:\n- jeśli `dł(s) = n` → wypisz s (warunek bazowy);\n- inaczej → dla i = 0 k-1 wywołaj `pisz(s + napis(i), n, k)`.\n\nDla `pisz(\"\", 2, 2)` (n=2, k=2):\n\n**[1] pisz(\"\", 2, 2):** dł(\"\")=0 ≠ 2 → pętla `i=0,1`:\n- i=0: wywołaj **[2] pisz(\"0\", 2, 2)**:\n- dł(\"0\")=1 ≠ 2 → pętla i=0,1:\n- i=0: **[3] pisz(\"00\", 2, 2)** → dł(\"00\")=2 → **wypisz \"00\"**.\n- i=1: **[4] pisz(\"01\", 2, 2)** → dł(\"01\")=2 → **wypisz \"01\"**.\n- i=1: wywołaj **[5] pisz(\"1\", 2, 2)**:\n- dł(\"1\")=1 ≠ 2 → pętla i=0,1:\n- i=0: **[6] pisz(\"10\", 2, 2)** → dł(\"10\")=2 → **wypisz \"10\"**.\n- i=1: **[7] pisz(\"11\", 2, 2)** → dł(\"11\")=2 → **wypisz \"11\"**.\n\n**Wypisany ciąg: 00, 01, 10, 11** (wszystkie binarne liczby 2-bitowe!).\n\n## Sposób 2 - interpretacja jako pre-order DFS po drzewie pełnym\n\nFunkcja `pisz` buduje **pełne drzewo k-arne** głębokości n. Liście to wszystkie napisy długości n nad alfabetem {0, 1, , k-1}, a wewnętrzne węzły to wszystkie krótsze prefiksy.\n\nKolejność wywołań to **pre-order traversal** (NLR): najpierw węzeł aktualny (wywołanie funkcji), potem rekurencyjnie poddrzewa od i=0 do i=k-1 (lewe do prawego).\n\n**Implementacja Python (do weryfikacji):**\n```python\nlicznik = [0]\nkolejnosc = []\n\ndef pisz(s, n, k):\nlicznik[0] += 1\nkolejnosc.append((licznik[0], s))\nif len(s) == n:\nprint(s)\nreturn\nfor i in range(k):\npisz(s + str(i), n, k)\n\npisz(\"\", 2, 2)\nfor nr, s in kolejnosc:\nprint(nr, repr(s))\n# 1 '' 2 '0' 3 '00' 4 '01' 5 '1' 6 '10' 7 '11'\n\n## Reference informatyczny - pre-order DFS\n\n> Reference - Drzewo wywołań rekurencji:\n> - Każde wywołanie funkcji = węzeł drzewa. Wywołania zagnieżdżone = krawędzie.\n> - Kolejność wywołań = **pre-order DFS** (NLR): najpierw węzeł, potem rekurencyjnie poddrzewa.\n> - Liczba liści = liczba kombinacji ciągu długości n nad alfabetem k-elementowym = **k^n**.\n> - Łączna liczba węzłów (wywołań) = 1 + k + k² + + k^n = **(k^(n+1) - 1) / (k - 1)**.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 2.1, max 2 pkt):\n> - **2 pkt** - poprawna odpowiedź, w tym:\n> - 1 pkt - poprawne uzupełnienie drzewa (pisz(\"10\") i pisz(\"11\"))\n> - 1 pkt - prawidłowa kolejność wywołań (1-7)\n> - **0 pkt** - błędna lub brak\n\n## Typowe pułapki\n\n- **Numerowanie tylko liści** zamiast wszystkich węzłów - kolejność powinna obejmować WSZYSTKIE wywołania.\n- **Pomylenie pre-order z post-order** - w post-order: 3, 4, 2, 6, 7, 5, 1 (najpierw liście, na końcu korzeń).\n- **Mylenie kolejności i=0,1** - najpierw idzie i=0 (lewa), potem i=1 (prawa).\n- **Brakujące dopisanie cyfry**: pisz(\"\") + i=1 → pisz(\"1\"), NIE pisz(\"01\").\n\n## Złożoność obliczeniowa\n\n- Liczba wywołań dla `pisz(\"\", n, k)`: **(k^(n+1) - 1) / (k - 1)**.\n- Dla pisz(\"\", 2, 2): (2³ - 1)/(2 - 1) = 7 ✓.\n- Czas pojedynczego wywołania (bez rekurencji): O(dł(s)) na konkatenację - łącznie O(n · k^n).\n- Pamięć stosu rekurencji: O(n) (głębokość drzewa).","image":"img/informatyka-2019-maj-matura-rozszerzona/zad-2.1.webp","solution_image":null,"topics":null,"page_from":4,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2019 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2.1. (0-2)
a) Uzupełnij miejsca oznaczone kropkami w drzewie wywołań funkcji pisz otrzymanym
w wyniku wywołania pisz("",2,2).
b) W kwadratowych polach, przy węzłach drzewa, podaj odpowiednią kolejność wywołań
funkcji pisz, tzn. przy pierwszym wywołaniu - 1, przy kolejnym - 2 itd.
pisz("",2,2)
pisz("0",2,2)
pisz("1",2,2)
pisz("00",2,2)
pisz("01",2,2)
1
MIN_1R

","answer_text_html":"

Zadanie 2.1. (0-2)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji […]
z zastosowaniem podejścia algorytmicznego.

\n
  1. Rozwiązywanie problemów
\n

i podejmowanie decyzji […], stosowanie
podejścia algorytmicznego.
Zdający:

\n
  1. posługuje się podstawowymi technikami
\n

algorytmicznymi;

\n
  1. stosuje rekurencję w prostych sytuacjach
\n

problemowych;

\n
  1. opisuje podstawowe algorytmy
\n

i stosuje:[…]
d) algorytmy na tekstach […]

\n
  1. opisuje własności algorytmów na
\n

podstawie ich analizy;

\n
  1. ocenia zgodność algorytmu ze
\n

specyfikacją problemu;

\n
  1. oblicza liczbę operacji wykonywanych
\n

przez algorytm.
Schemat punktowania
2 p. - za poprawną odpowiedź, w tym:
1 p. - poprawne uzupełnienie drzewka wywołań funkcji pisz,
1 p. - prawidłową kolejność wywołań.
0 p. - za podanie odpowiedzi błędnej albo brak odpowiedzi.
Poprawna odpowiedź

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

a) Brakujące węzły: pisz("10", 2, 2) i pisz("11", 2, 2).

\n

b) Kolejność wywołań:

\n

| Numer | Wywołanie |
| 1 | pisz("", 2, 2) |
| 2 | pisz("0", 2, 2) |
| 3 | pisz("00", 2, 2) |
| 4 | pisz("01", 2, 2) |
| 5 | pisz("1", 2, 2) |
| 6 | pisz("10", 2, 2) |
| 7 | pisz("11", 2, 2) |

\n

Drzewo z numeracją (pre-order DFS):

\n

[1] pisz("", 2, 2)
[2] pisz("0", 2, 2) [5] pisz("1", 2, 2)
[3] pisz("00") [4] pisz("01") [6] pisz("10") [7] pisz("11")

\n

Sposób 1 - symulacja rekurencji krok po kroku

\n

Funkcja pisz(s, n, k):

\n\n

Dla pisz("", 2, 2) (n=2, k=2):

\n

[1] pisz("", 2, 2): dł("")=0 ≠ 2 → pętla i=0,1:

\n\n

Wypisany ciąg: 00, 01, 10, 11 (wszystkie binarne liczby 2-bitowe!).

\n

Sposób 2 - interpretacja jako pre-order DFS po drzewie pełnym

\n

Funkcja pisz buduje pełne drzewo k-arne głębokości n. Liście to wszystkie napisy długości n nad alfabetem {0, 1, , k-1}, a wewnętrzne węzły to wszystkie krótsze prefiksy.

\n

Kolejność wywołań to pre-order traversal (NLR): najpierw węzeł aktualny (wywołanie funkcji), potem rekurencyjnie poddrzewa od i=0 do i=k-1 (lewe do prawego).

\n

Implementacja Python (do weryfikacji):
```python
licznik = [0]
kolejnosc = []

\n

def pisz(s, n, k):
licznik[0] += 1
kolejnosc.append((licznik[0], s))
if len(s) == n:
print(s)
return
for i in range(k):
pisz(s + str(i), n, k)

\n

pisz("", 2, 2)
for nr, s in kolejnosc:
print(nr, repr(s))

\n

1 '' 2 '0' 3 '00' 4 '01' 5 '1' 6 '10' 7 '11'

\n

Reference informatyczny - pre-order DFS

\n
Reference - Drzewo wywołań rekurencji:
- Każde wywołanie funkcji = węzeł drzewa. Wywołania zagnieżdżone = krawędzie.
- Kolejność wywołań = pre-order DFS (NLR): najpierw węzeł, potem rekurencyjnie poddrzewa.
- Liczba liści = liczba kombinacji ciągu długości n nad alfabetem k-elementowym = k^n.
- Łączna liczba węzłów (wywołań) = 1 + k + k² + + k^n = (k^(n+1) - 1) / (k - 1).
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 2.1, max 2 pkt):
- 2 pkt - poprawna odpowiedź, w tym:
- 1 pkt - poprawne uzupełnienie drzewa (pisz("10") i pisz("11"))
- 1 pkt - prawidłowa kolejność wywołań (1-7)
- 0 pkt - błędna lub brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}