---
marp: true
theme: a4
paginate: true
footer: Adatszerkezetek · Záró dolgozat · „A” változat
---

# Adatszerkezetek – záró dolgozat

<div class="fejlec">
<div>Név:</div>
<div>Hallgatói azonosító:</div>
<div>Dátum:</div>
</div>

**Időtartam:** 60 perc · **Elérhető pontszám:** 100 pont · **Segédeszköz:** nem használható.
A pszeudokódban a tömbök indexelése **1-től** indul. A listaelemek mezői: `Elem[P].Érték`, `Elem[P].Köv`; a fák csomópontjainak mezői: `Elem[P].Kulcs`, `Elem[P].Bal`, `Elem[P].Jobb`. Az üres mutató jele **Nil**.

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

Jelölje X-szel a helyes választ!

<div class="ih">

| # | Állítás | Igaz | Hamis |
|---|---|---|---|
| 1. | A tömb elemei a memóriában folytonosan, egymás után helyezkednek el. | | |
| 2. | Az egyszerű láncolt lista *i*-edik eleme O(1) lépésben elérhető. | | |
| 3. | A bináris keresés rendezetlen tömbön is mindig helyes eredményt ad. | | |
| 4. | A dinamikus adatszerkezetek használata erőforrás-megosztást tesz lehetővé. | | |
| 5. | Az üres strázsás lista tárigénye nulla, hiszen nem tárolunk benne elemet. | | |
| 6. | A verem LIFO (*last in, first out*) elvű adatszerkezet. | | |
| 7. | A ciklikus sorban a kivétel (dequeue) lépésszáma O(n), mert az elemeket előre kell tolni. | | |
| 8. | A beszúrásos rendezés egy már rendezett tömbön O(n) lépésben végez. | | |
| 9. | A gyorsrendezés legrosszabb esetben O(n²) lépésszámú. | | |
| 10. | Az összefésülő rendezés stabil rendezés. | | |
| 11. | A bináris keresőfa mindig kiegyensúlyozott bináris fa. | | |
| 12. | A bináris keresőfában való keresés lehet ugyanolyan lassú, mint a láncolt listában való keresés. | | |
| 13. | A dinamikus adatszerkezetek helytelen használata memóriaszivárgást eredményezhet. | | |
| 14. | Java-ban két `String` tartalmának összehasonlítására a `==` operátort kell használni. | | |

</div>

---

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

Karikázza be az egyetlen helyes választ!

**1.** Melyik tulajdonsággal **nem** rendelkezhet az egyszerű láncolt lista?
<div class="mcq n4"><p>a) szétszórt tárolás</p><p>b) közvetlen elérés</p><p>c) homogén</p><p>d) dinamikus</p></div>

**2.** A bináris fa, mint adatszerkezet:
<div class="mcq n4"><p>a) heterogén</p><p>b) közvetlen elérésű</p><p>c) hierarchikus</p><p>d) egyik sem</p></div>

**3.** A strázsás lista elemei elérhetők:
<div class="mcq n4"><p>a) inorder módon</p><p>b) közvetlen módon</p><p>c) szekvenciálisan</p><p>d) egyik sem</p></div>

**4.** Melyik adatszerkezet **közvetlen** elérésű?
<div class="mcq n4"><p>a) kétirányú láncolt lista</p><p>b) egydimenziós tömb</p><p>c) láncolt ábrázolású verem</p><p>d) ciklikus lista</p></div>

**5.** A bináris keresőfa kulcsait növekvő sorrendben adja a(z):
<div class="mcq n4"><p>a) preorder bejárás</p><p>b) inorder bejárás</p><p>c) postorder bejárás</p><p>d) szintenkénti bejárás</p></div>

**6.** Mi a bináris keresés lépésszáma egy *n* elemű rendezett tömbben?
<div class="mcq n4"><p>a) O(1)</p><p>b) O(log n)</p><p>c) O(n)</p><p>d) O(n log n)</p></div>

**7.** Egy `int A[6][10]` mátrixot sorfolytonosan tárolunk az 1000-es címtől, 4 bájtos elemekkel, **0-tól** indexelve. Mi az `A[2][3]` elem címe?
<div class="mcq n4"><p>a) 1092</p><p>b) 1132</p><p>c) 1128</p><p>d) 1052</p></div>

**8.** Melyik rendezés végez legfeljebb *n* − 1 cserét?
<div class="mcq n4"><p>a) buborékrendezés</p><p>b) kiválasztásos rendezés</p><p>c) beszúrásos rendezés</p><p>d) gyorsrendezés</p></div>

**9.** Mennyi a `5 1 2 + 4 * + 3 −` postfix kifejezés értéke?
<div class="mcq n4"><p>a) 14</p><p>b) 12</p><p>c) 18</p><p>d) 20</p></div>

**10.** Egy 8 elemű (0–7 indexű) ciklikus sorban `eleje = 6` és `db = 3`. Melyik indexre kerül a következő betett elem?
<div class="mcq n4"><p>a) 0</p><p>b) 1</p><p>c) 9</p><p>d) 7</p></div>

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

Adja meg a műveletek lépésszámát O-jelöléssel (*n* az elemek száma)!

| | Művelet | Lépésszám |
|---|---|---|
| a) | Egy tömb *i*-edik elemének elérése | |
| b) | Lineáris keresés egy *n* elemű tömbben (legrosszabb eset) | |
| c) | Új elem beszúrása egy *n* elemű rendezett tömbbe úgy, hogy rendezett maradjon | |
| d) | Beszúrás egy egyszerű láncolt lista elejére | |
| e) | Törlés egy egyszerű láncolt lista végéről | |
| f) | Push és pop egy tömbbel megvalósított veremben | |
| g) | A maximum kivétele egy *n* elemű kupacból | |
| h) | Keresés egy kiegyensúlyozott bináris keresőfában | |
| i) | Összefésülő rendezés | |
| j) | Hanoi tornyai *n* koronggal (a lépések száma) | |

---

## 4. feladat – Kódkövetés: verem <span class="pont">7 pont</span>

Mit ír ki a következő programrészlet? Általánosságban mit csinál egy tetszőleges szöveggel? (A `Stack` egy karaktereket tároló verem.)

```java
String t = "DATA STRUCTURE";
Stack s = new Stack();
for (char c : t.toCharArray()) {
    if (c != ' ') s.push(c);
    else {
        while (!s.isEmpty()) System.out.print(s.pop());
        System.out.print(' ');
    }
}
while (!s.isEmpty()) System.out.print(s.pop());
```

<div class="kitoltes szeles"><table><tr><td>Kimenet</td><td></td></tr><tr><td>Általánosan</td><td></td></tr></table></div>

## 5. feladat – Kódkövetés: sor <span class="pont">7 pont</span>

Mit ír ki a következő programrészlet? Általánosságban milyen ismert feladatot old meg, ha a sorba az 1, 2, …, *n* számokat tesszük?

```java
Queue q = new Queue();
for (int i = 1; i <= 6; i++) q.enqueue(i);
while (q.size() > 1) {
    q.enqueue(q.dequeue());
    System.out.print(q.dequeue() + " ");
}
System.out.print(q.dequeue());
```

<div class="kitoltes szeles"><table><tr><td>Kimenet</td><td></td></tr><tr><td>Általánosan</td><td></td></tr></table></div>

---

## 6. feladat – Algoritmusok végrehajtása papíron <span class="pont">4 + 4 = 8 pont</span>

**a)** Rendezze a `[6, 2, 9, 1, 5]` tömböt **beszúrásos rendezéssel**! Írja fel a tömb állapotát a külső ciklus minden lépése után!

<div class="valasz h2" style="height: 22mm"></div>

**b)** Keresse meg a `45`-öt **bináris kereséssel** az alábbi tömbben (1-től indexelve)! Írja fel minden lépésben a `bal`, `jobb` és `k` értékét! `A = [4, 9, 13, 21, 30, 38, 45, 52, 60, 71]`

<div class="valasz h2" style="height: 22mm"></div>

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

**a)** Szúrja be egy üres bináris keresőfába sorban a következő kulcsokat, és rajzolja le a fát!
`45, 20, 70, 10, 30, 60, 80, 25, 35`

<div class="valasz h3" style="height: 38mm"></div>

**b)** Adja meg a fa preorder, inorder és postorder bejárását!

<div class="kitoltes">

| | Bejárás |
|---|---|
| Pre | |
| In | |
| Post | |

</div>

**c)** Törölje a `20`-as kulcsot az a) pontban kapott fából! Rajzolja le az eredményt, és írja le, melyik törlési esetről van szó!

<div class="valasz h3" style="height: 38mm"></div>

**d)** Mennyi az a) pontban kapott fa magassága? Hány kulcs-összehasonlítás kell a `35` megtalálásához?

<div class="valasz h1"></div>

---

A 8–10. feladatban egészítse ki a pszeudokódot! A hiányzó részek egy-egy kifejezést, mutatót vagy **relációjelet** (=, ≠, <, >, ≤, ≥) jelentenek. A válaszokat a kód melletti táblázatba írja!

## 8. feladat – Keresés bináris keresőfában <span class="pont">5 × 2 = 10 pont</span>

A függvény az `x` kulcsú csomópont mutatóját adja vissza, vagy Nil-t, ha nincs ilyen kulcs. A fa gyökerére a **Gyökér** mutató mutat.

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

```text
Függvény Keres(Gyökér, x)
  P ← __(1)__
  Ciklus amíg P __(2)__ Nil és
              Elem[P].Kulcs __(3)__ x
    Ha x __(4)__ Elem[P].Kulcs akkor
      P ← Elem[P].Bal
    különben
      P ← __(5)__
    Elágazás vége
  Ciklus vége
  Vissza: P
Függvény vége
```

</div>
<div class="kitoltes">

| | Hiányzó rész |
|---|---|
| (1) | |
| (2) | |
| (3) | |
| (4) | |
| (5) | |

</div>
</div>

## 9. feladat – Strázsás keresés <span class="pont">5 × 2 = 10 pont</span>

A strázsás lista a **Fej** és a **Vég** mutatóval adott; a Vég a lista végén álló strázsa elemre mutat. A függvény az `x` értéket tartalmazó első elem mutatóját adja vissza, vagy Nil-t, ha `x` nincs a listában.

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

```text
Függvény StrázsásKeres(Fej, Vég, x)
  Elem[Vég].Érték ← __(1)__
  P ← __(2)__
  Ciklus amíg Elem[P].Érték __(3)__ x
    P ← __(4)__
  Ciklus vége
  Ha P __(5)__ Vég akkor
    Vissza: Nil
  különben
    Vissza: P
  Elágazás vége
Függvény vége
```

</div>
<div class="kitoltes">

| | Hiányzó rész |
|---|---|
| (1) | |
| (2) | |
| (3) | |
| (4) | |
| (5) | |

</div>
</div>

---

## 10. feladat – Beszúrás egy egyszerű láncolt lista végére <span class="pont">6 × 2 = 12 pont</span>

A lista a **Fej** mutatóval adott. A `Lefoglal(P)` függvény új elemet foglal: siker esetén P a lefoglalt elemre mutat, és a függvény értéke igaz.

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

```text
Függvény VégéreBeszúr(Fej, Adat)
  Ha nem Lefoglal(P) akkor Vissza: hamis
  Elem[P].Érték ← Adat
  Elem[P].Köv ← __(1)__
  Ha Fej __(2)__ Nil akkor
    Fej ← __(3)__
  különben
    Q ← Fej
    Ciklus amíg Elem[Q].Köv __(4)__ Nil
      Q ← __(5)__
    Ciklus vége
    __(6)__ ← P
  Elágazás vége
  Vissza: igaz
Függvény vége
```

</div>
<div class="kitoltes">

| | Hiányzó rész |
|---|---|
| (1) | |
| (2) | |
| (3) | |
| (4) | |
| (5) | |
| (6) | |

</div>
</div>

## Pontozás

| Feladat | 1. | 2. | 3. | 4. | 5. | 6. | 7. | 8. | 9. | 10. | Összesen |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Elérhető | 14 | 10 | 10 | 7 | 7 | 8 | 12 | 10 | 10 | 12 | **100** |
| Elért | | | | | | | | | | | |

| 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) |

**Javító:** ................................................ &nbsp;&nbsp;&nbsp;&nbsp; **Érdemjegy:** ................