infovos

Question 1

Általában milyen bonyolultságú egy BT algoritmus?

Answer 1

Exponenciális
Faktoriális

Question 2

Mit jelent a belső feltétel a BT algoritmusok segítségével megoldott feladatok esetén?

Answer 2

• A BT algoritmusok esetében a belső feltétel segítségével döntsük el hogy az adott eredmény/részeredmény megfelel e az adott keresett eredménynek, ha nem felel meg akkor új elemet kell választani

Question 3

Mikor ajánlott a divide et impera módszer?

Answer 3

– a feladatot fel lehet bontani egymástól független
részfeladatokra,
– amelyeket az eredeti feladathoz hasonlóan oldunk meg, de
kisebb méretű adathalmaz esetében.

Question 4

Mit értünk AAT esetén az implementáció függetlensége alatt?

Answer 4

Az implementáció függetlensége azt jelenti, hogy egy adatszerkezet használata során a felhasználónak (programozónak) nem kell ismernie annak belső megvalósítását, csak az általa biztosított funkcionalitást (absztrakt viselkedést). Az implementáció rejtve marad a felhasználó előtt, így az adatszerkezet különböző megvalósításokkal helyettesíthető anélkül, hogy a felhasználó kódja módosításra szorulna.

Question 5

Mit értünk előfeltétel alatt?

Answer 5

Az előfeltétel egy olyan követelmény vagy feltétel, amelynek teljesülnie kell egy adott művelet vagy algoritmus elindítása előtt ahhoz, hogy helyesen működjön, és garantálható legyen a várt eredmény.

Question 6

Mit értünk utófeltétel alatt?

Answer 6

Utófeltétel egy program vagy függvény végrehajtása után garantáltan teljesülő állapotot vagy feltételt jelent.
Ez azt írja le, hogy a program vagy függvény futása után milyen eredményeket várhatunk el, illetve milyen állapotok lesznek érvényesek.

Question 7

Milyen műveletekkel szúrna be egy elemet a q pointer által mutatott elem után egy kétszeresen láncolt listába?

Answer 7

1 UjElem ← nodeCreate(adat)
2 q.köv.elozo ← UjElem
3 UjElem.kov ← q.kov
4 UjElem.elozo ← q
5 q.kov ← UjElem

Question 8

Mi történik, ha egy bináris keresőfát inorder sorrendben járunk be?

Answer 8

Ha egy bináris keresőfát inorder sorrendben járunk be, a kulcsok növekvő (illetve csökkenő) sorrendben követik egymást.

Question 9

Mi igaz egy bináris keresőfa bármely csomópontjára a bal és a jobb részfáját tekintve?

Answer 9

Egy bináris keresőfa bármely csomópontjára igaz, hogy a bal részfájában csak a saját kulcsértékénél kisebb értékek, jobb részfájában pedig csak nagyobb értékek találhatók.

Question 10

Igaz-e, hogy egy bináris keresőfában a kulcsok értékei mindig különbözőek?

Answer 10

Egy bináris keresőfában a kulcsok értéke különböző.

Question 11

Mi a preorder bejárás sorrendje egy bináris fán?

Answer 11

Az aktuális csomópontot járjuk be először, majd a bal részfát, végül a jobb részfát.
(Sorrend: gyökér → bal részfa → jobb részfa)

Question 12

Ha egy bináris fát preorder sorrendben járunk be, a kulcsok rendezett sorrendben lesznek?

Answer 12

Nem, a preorder bejárás nem garantálja a kulcsok növekvő vagy csökkenő sorrendjét.

Question 13

Mi a postorder bejárás sorrendje egy bináris fán?

Answer 13

Válasz: Először a bal részfát, majd a jobb részfát, végül az aktuális csomópontot járjuk be.
(Sorrend: bal részfa → jobb részfa → gyökér)

Question 14

Mik a lépései a divide et impera módszer használatának?

Answer 14

• Az eredeti feladatot felbontjuk egymástól független részfeladatokra: az eredetihez hasonlóak, de kisebb adathalmazra definiáltak.
• A részfeladatokkal hasonlóan járunk el. A felbontást akkor állítjuk le, amikor a feladat megoldása a lehető legegyszerűbb (alapeset).
• Ezt a legegyszerűbb feladatot megoldjuk.
• A részfeladatok eredményeiből rendre felépítjük a következő méretű feladat eredményeit. Az utolsó összerakás az eredeti feladat eredményét adja.

Question 15

Nevezze meg és adjon saját példát az adattipusok absztrakciójának három szintjére!

Answer 15

Absztrakt szint: Verem fogalma és műveletek (push, pop, peek).
Virtuális szint: A verem megvalósítása tömbbel vagy láncolt listával.
Fizikai szint: A memóriacímek, adatmozgatás és tárolás módja a hardver szinten

Question 16

Beszúr elem q pointer elé DL lista

Answer 16

1 UjElem ← nodeCreate(adat)
2 q.elozo.köv ← UjElem
3 UjElem.elozo ← q.elozo
4 UjElem.kov ← q
5 q.elozo ← UjElem

Question 17

Divide et impera bonyolultsága

Answer 17

• nem pontosan meghatározható

Question 18

Mi a különbség a belső feltétel és a folytatási feltétel között?

Answer 18

• A BT algoritmusok esetében a belső feltétel segítségével döntsük el hogy az adott eredmény/részeredmény megfelel e az adott keresett eredménynek, ha nem felel meg akkor új elemet kell választani
• a folytatási feltétel a belső feltétel igazzá válása után következik, amely segítségével számolunk tovább míg elérjük az eredményt

Question 19

A verem lehet

Answer 19

• statikus implementált adatszerkezet
• lineáris lista
• félstatikus adatszerkezet

Question 20

Egyszeresen láncolt lista q pointer által mutatott elem elé

Answer 20

1 UjElem ← nodeCreate(-)
2 UjElem.mezők ← q.mezők
3 q.köv ← UjElem
4 q.adat ← adat

Question 21

Folytatási feltétel BT

Answer 21

• a folytatási feltétel a belső feltétel igazzá válása után következik, amely segítségével számolunk tovább míg elérjük az eredményt

Question 22

Mit értünk az AAT esetében a félstatikus tulajdonság alatt?

Answer 22

Például egy verem (stack) adattípus lehet statikus a műveletek szerkezetében (például, hogy “LIFO” elv szerint működik), de dinamikus abban az értelemben, hogy a verem tartalma a futás során változhat.

Question 23

Mi a bináris fa?

Answer 23

• Egy bináris fa vagy üres vagy tartalmaz egy csomópontot, amelyhez bizonyos típusú információkat rendeltünk, valamint még két komponenst, amelyek szintén a bináris fák (jobb s bal részfa)

Question 24

A félstatikus adatszerkezetek implementálhatók

Answer 24

dinamikusan és statikusan

Question 25

A statikus adatszerkezetek számára lefoglalt tárhely mérete

Answer 25

nem változik a program aktív állapota alatt

Question 26

Inorder bejárás dbeagfc mig a preordere abdecfg posztorder?

Answer 26

d e b g f c a

Question 27

Mennyi a futási ideje egy új csomópont beszurásnak egy n elemű bin fába?

Answer 27

O(n) - lineáris

Question 28

Mit értünk absztrakt adattípus alatt?

Answer 28

Absztrakt adattípusnak nevezünk egy adathalmazt(szám, karaktr, objektum) és a rajta elvégezhető műveleteket.(implementáció nélkül).