---
marp: true
theme: a4
paginate: true
footer: Adatszerkezetek · Záró dolgozat „A” · MEGOLDÓKULCS – csak az oktatónak
---

# Záró dolgozat „A” – megoldókulcs és pontozási útmutató

<span class="kicsi">Részpontszám adható. A kitöltendő pszeudokódban minden egyértelmű, helyes megoldás elfogadható (pl. `<>` vagy `!=` a `≠` helyett, `null` a `Nil` helyett). Szintaktikai apróságokért ne vonjunk le pontot.</span>

## 1. feladat – Igaz vagy hamis <span class="pont">14 pont</span>

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| **I** | **H** | **H** | **I** | **H** | **I** | **H** | **I** | **I** | **I** | **H** | **I** | **I** | **H** |

<span class="kicsi">Indoklás a vitás esetekhez: 2 – szekvenciális elérés, O(n) · 5 – a strázsa elem foglal helyet · 7 – csak az indexek változnak, O(1) · 12 – degenerált fa (pl. rendezett beszúrás) · 14 – `equals` kell.</span>

## 2. feladat – Feleletválasztás <span class="pont">10 pont</span>

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| **b** | **c** | **c** | **b** | **b** | **b** | **a** | **b** | **a** | **b** |

<span class="kicsi">7: 1000 + (2 · 10 + 3) · 4 = 1092 · 9: 5 + (1 + 2) · 4 − 3 = 14 · 10: (6 + 3) mod 8 = 1.</span>

## 3. feladat – Lépésszámok <span class="pont">10 pont</span>

| a) | b) | c) | d) | e) | f) | g) | h) | i) | j) |
|---|---|---|---|---|---|---|---|---|---|
| O(1) | O(n) | O(n) | O(1) | O(n) | O(1) | O(log n) | O(log n) | O(n log n) | O(2ⁿ) |

## 4. feladat – Verem <span class="pont">7 pont</span>

Kimenet: **`ATAD ERUTCURTS`** <span class="pontozas">(5 pont; ha a szavak sorrendje vagy a szóköz hibás: 3 pont)</span>
Általánosan: a szöveg **minden szavát külön megfordítja**, a szavak sorrendje és a szóközök megmaradnak. <span class="pontozas">(2 pont)</span>

## 5. feladat – Sor <span class="pont">7 pont</span>

Kimenet: **`2 4 6 3 1 5`** <span class="pontozas">(5 pont; legfeljebb egy hibás szám esetén 3 pont)</span>
Általánosan: a **Josephus-probléma** k = 2-re: *n* ember körben, minden második kiesik; a kiírás a kiesési sorrend, az utolsó szám a túlélő. <span class="pontozas">(2 pont; a „minden második elemet kiveszi/kiírja” leírás is teljes értékű)</span>

## 6. feladat – Algoritmusok papíron <span class="pont">8 pont</span>

**a)** Beszúrásos rendezés <span class="pontozas">(lépésenként 1 pont, összesen 4)</span>

| Lépés | 1. (2 beszúrása) | 2. (9 beszúrása) | 3. (1 beszúrása) | 4. (5 beszúrása) |
|---|---|---|---|---|
| Tömb | [2, 6, 9, 1, 5] | [2, 6, 9, 1, 5] | [1, 2, 6, 9, 5] | [1, 2, 5, 6, 9] |

**b)** Bináris keresés, x = 45 <span class="pontozas">(lépésenként 1 pont, összesen 4)</span>

| Lépés | bal | jobb | k | A[k] | Döntés |
|---|---|---|---|---|---|
| 1. | 1 | 10 | 5 | 30 | 30 < 45 → bal ← 6 |
| 2. | 6 | 10 | 8 | 52 | 52 > 45 → jobb ← 7 |
| 3. | 6 | 7 | 6 | 38 | 38 < 45 → bal ← 7 |
| 4. | 7 | 7 | 7 | 45 | megtaláltuk: 7. index |

---

## 7. feladat – Bináris keresőfa <span class="pont">12 pont</span>

<div class="ket-hasab">
<div>

**a)** A fa <span class="pontozas">(3 pont)</span>

```text
            45
          /    \
        20      70
       /  \    /  \
     10   30  60   80
         /  \
       25    35
```

**c)** A 20 törlése után <span class="pontozas">(3 pont)</span>

```text
            45
          /    \
        25      70
       /  \    /  \
     10   30  60   80
            \
             35
```

</div>
<div>

**b)** Bejárások <span class="pontozas">(1–1 pont)</span>

- Preorder: **45 20 10 30 25 35 70 60 80**
- Inorder: **10 20 25 30 35 45 60 70 80**
- Postorder: **10 25 35 30 20 60 80 70 45**

**c)** A 20-nak **két gyereke** van (3. eset): a helyére a jobb részfa legkisebb eleme, az **inorder rákövetkező (25)** kerül, majd a 25-öt (levél) töröljük. <span class="pontozas">(az eset megnevezése 1 pont, a helyes fa 2 pont; ha az inorder megelőzőt (10) használja, az is helyes)</span>

**d)** Magasság: **3** (45 – 20 – 30 – 25). A 35 megtalálásához **4** összehasonlítás kell (45, 20, 30, 35). <span class="pontozas">(magasság 1 pont, összehasonlítások 2 pont)</span>

</div>
</div>

## 8–10. feladat – Kitöltendő pszeudokód <span class="pont">hiányzó részenként 2 pont</span>

<div class="ket-hasab">
<div>

**8. Keresés keresőfában** <span class="pontozas">(10 pont)</span>

| | Megoldás |
|---|---|
| (1) | `Gyökér` |
| (2) | `≠` |
| (3) | `≠` |
| (4) | `<` (a `≤` is elfogadható) |
| (5) | `Elem[P].Jobb` |

**9. Strázsás keresés** <span class="pontozas">(10 pont)</span>

| | Megoldás |
|---|---|
| (1) | `x` |
| (2) | `Fej` |
| (3) | `≠` |
| (4) | `Elem[P].Köv` |
| (5) | `=` |

</div>
<div>

**10. Beszúrás a lista végére** <span class="pontozas">(12 pont)</span>

| | Megoldás |
|---|---|
| (1) | `Nil` |
| (2) | `=` |
| (3) | `P` |
| (4) | `≠` |
| (5) | `Elem[Q].Köv` |
| (6) | `Elem[Q].Köv` |

<span class="kicsi">8/(4): ha x = Elem[P].Kulcs, a ciklus már nem fut le, ezért a `≤` is helyes eredményt ad. 9: a strázsa miatt a ciklusfeltételben nincs szükség a `P ≠ Vég` vizsgálatra. 10/(1): ha az új elem `Köv` mezője nem Nil, a lista vége „lóg” – gyakori hiba.</span>

</div>
</div>

## Érdemjegy

| Pontszám | 0–49 | 50–61 | 62–74 | 75–86 | 87–100 |
|---|---|---|---|---|---|
| Érdemjegy | elégtelen (1) | elégséges (2) | közepes (3) | jó (4) | jeles (5) |