Test na Fronta (queue)

Otázka 1: Pre implementáciu fronty pomocou obyčajného poľa, kde sa prvky po odstránení posúvajú, má operácia Dequeue konštantnú časovú zložitosť O(1).

A. Áno

B. Nie

Vysvetlenie: Podľa študijných materiálov, pre implementáciu fronty pomocou obyčajného poľa, kde sa prvky po operácii Dequeue posúvajú, má táto operácia časovú zložitosť O(n), nie O(1). Konštantnú časovú zložitosť O(1) majú operácie Enqueue a Dequeue pri implementácii pomocou spojového zoznamu alebo kruhového poľa.

Otázka 2: V simulácii fronty v kruhovom poli sa pri operácii `dequeue` posúva ukazovateľ `tail`.

A. Áno

B. Nie

Vysvetlenie: Pri operácii `dequeue` (vybratie) sa v simulácii fronty v kruhovom poli posúva ukazovateľ `head`. Ukazovateľ `tail` sa posúva pri operácii `enqueue` (vloženie).

Otázka 3: Ktoré tvrdenia správne opisujú implementáciu fronty pomocou spojového zoznamu podľa uvedeného textu?

A. Operácia `enqueue` pridáva nový uzol na koniec zoznamu a aktualizuje ukazovateľ `tail`.

B. Operácia `dequeue` má časovú zložitosť O(n), pretože si vyžaduje posúvanie všetkých prvkov.

C. Pre správnu funkčnosť udržiava iba jeden ukazovateľ na začiatok zoznamu (head).

D. Operácie `enqueue` a `dequeue` majú konštantnú časovú zložitosť O(1).

Vysvetlenie: Podľa textu, pri implementácii fronty pomocou spojového zoznamu operácia `enqueue` pridá nový uzol na koniec zoznamu a aktualizuje ukazovateľ `tail`. Taktiež sa uvádza, že operácie `enqueue` a `dequeue` majú konštantnú časovú zložitosť O(1), pretože nevyžadujú posúvanie prvkov ani prechádzanie celým zoznamom. Implementácia spojového zoznamu udržiava dva ukazovatele, `head` na začiatok a `tail` na koniec zoznamu, nie len jeden.

Otázka 4: Ktoré tvrdenia správne opisujú implementáciu fronty pomocou kruhového poľa podľa poskytnutých študijných materiálov?

A. Operácie enqueue a dequeue majú konštantnú časovú zložitosť O(1), pretože zahŕňajú len aktualizáciu ukazovateľov.

B. Ak head a tail ukazujú na tú istú pozíciu, fronta je prázdna.

C. Fronta je plná, keď je potrebné posunúť všetky existujúce prvky, aby sa uvoľnilo miesto pre nový prvok.

D. Ukazovatele head a tail sa „pretočia“ na začiatok poľa (index 0) pomocou modulo operátora, ak dosiahnu koniec poľa.

Vysvetlenie: Podľa študijných materiálov, operácie enqueue a dequeue majú konštantnú časovú zložitosť O(1), pretože zahŕňajú len aktualizáciu ukazovateľov a vloženie/vybratie prvku na konkrétny index, bez potreby posúvania dát. Ďalej je uvedené, že prázdna fronta nastane, keď head a tail ukazujú na tú istú pozíciu. Takisto sa spomína, že ukazovatele head a tail sa „pretočia“ na začiatok poľa (index 0) pomocou modulo operátora. Tvrdenie, že fronta je plná, keď je potrebné posunúť všetky existujúce prvky, aby sa uvoľnilo miesto, je nesprávne, pretože práve toto sa snaží kruhové pole vyhnúť; plná fronta je definovaná inak, napríklad keď '(tail + 1) % kapacita_poľa == head' alebo počítadlo prvkov dosiahne kapacitu.

Otázka 5: Po prvej operácii Dequeue vráti fronta hodnotu 10 a po druhej operácii Dequeue vráti fronta hodnotu 20.

A. Áno

B. Nie

Vysvetlenie: Podľa kroku 4 "Dequeue(): Vráti 10." a kroku 8 "Dequeue(): Vráti 20." v študijných materiáloch sú uvedené hodnoty správne.