Test on Sor (queue)

Question 1: A verem adatszerkezet a FIFO (First-In, First-Out) elv alapján működik.

A. Yes

B. No

Explanation: A verem (stack) a LIFO (Last-In, First-Out) elv alapján működik, azaz az utoljára beérkező elem távozik elsőként. A sor adatszerkezet működik a FIFO elv alapján.

Question 2: Melyik állítás írja le HELYESEN a sor adatszerkezet egyszerű, tömb alapú implementációjának egyik jelentős hátrányát?

A. A láncolt lista alapú implementációhoz képest az alapműveletek időkomplexitása O(log n).

B. Minden elem kivétele (dequeue) után a tömb elején üres helyek keletkeznek, ami a tömb felesleges telítődéséhez vezethet.

C. A tömb alapú megvalósítás alapértelmezetten dinamikus méretű, ami memória pazarláshoz vezethet.

D. Az `enqueue` művelet során az elemek mindig a tömb 0-ás indexére kerülnek, ami lassítja a műveletet.

Explanation: A tanulmányi anyag szerint az egyszerű tömb alapú implementáció jelentős hátránya, hogy minden `dequeue` művelet után a tömb elején üres helyek keletkeznek, és a `front` és `rear` mutatók folyamatosan a tömb végéhez közelednek. Ez azt eredményezheti, hogy a tömb megtelik, még akkor is, ha valójában sok üres hely van az elején. Az O(log n) időkomplexitás nem szerepel a hátrányok között, sőt, az alapműveletek ideális esetben O(1) komplexitásúak. A tömb alapú implementáció általában fix méretű. Az `enqueue` művelet a `rear` indexénél helyezi el az elemeket, nem feltétlenül a 0-ás indexen.

Question 3: A körkörös tömb inicializálásakor a `front` és `rear` mutatók kezdőértéke beállítható úgy, hogy mindkettő `-1` legyen.

A. Yes

B. No

Explanation: A 'Körkörös tömb (Circular Array) implementáció' rész 'Inicializálás' pontja szerint kezdetben 'front = -1 és rear = -1' is lehetséges, jelezve, hogy a sor üres.

Question 4: Az `enqueue` művelet során, ha a sor üres, a `rear` mutatót beállítjuk 0-ra, mielőtt növelnénk.

A. Yes

B. No

Explanation: Az `enqueue` művelet során, ha a sor üres (`front == -1`), akkor a `front` mutatót állítjuk 0-ra. A `rear` mutatót ilyenkor is a szokásos módon növeljük (`rear = (rear + 1) % kapacitás`), ami az inicializált `rear = -1` értékből 0-ra eredményezi a növelés után, de nem direktben állítjuk be 0-ra a növelés előtt.

Question 5: A mellékelt tananyag alapján mely feltétel(ek) jelzik helyesen, hogy egy körkörös tömb implementációjú sor tele van?

A. (rear + 1) % kapacitás == front

B. méret == kapacitás

C. front == -1 és rear == -1

D. rear == kapacitás - 1

Explanation: A tananyag szerint a sor tele van, ha „(rear + 1) % kapacitás == front” (feltételezve, hogy egy üres helyet mindig fenntartunk a megkülönböztetéshez), vagy ha „méret == kapacitás”. Az első két opció pontosan ezeket a feltételeket tartalmazza.