Test on Gráfok és szélességi és mélységi bejárás

Question 1: A szélességi bejárás (BFS) algoritmus mindig megtalálja a legrövidebb utat súlyozott gráfokban is.

A. Yes

B. No

Explanation: A szélességi bejárás (BFS) nem találja meg a legrövidebb utat súlyozott gráfokban, ha az élsúlyok eltérőek. Ehelyett súlyozatlan gráfokban biztosítja a kezdőcsúcstól számított élszámban legrövidebb utat.

Question 2: Melyik állítás írja le HELYESEN a szomszédsági lista előnyét a gráfreprezentáció során?

A. Két csúcs közötti él létezésének ellenőrzése O(1) idő alatt történik.

B. Ritka gráfok esetén kisebb térigénnyel (O(V + E) memória) rendelkezik.

C. Mindig szimmetrikus mátrixként reprezentálható, ami egyszerűsíti az irányítatlan gráfok kezelését.

D. Egy csúcs szomszédjainak lekérdezése O(V) időt vesz igénybe.

Explanation: A szomszédsági lista egyik fő előnye, hogy ritka gráfok esetén kisebb térigénnyel rendelkezik (O(V + E) memória), ellentétben a szomszédsági mátrixszal, amely O(V²) memóriát igényel. Az él létezésének ellenőrzése O(fokszám) időt vehet igénybe, nem O(1). A szimmetrikus mátrix a szomszédsági mátrix jellemzője. Egy csúcs szomszédjainak lekérdezése a szomszédsági lista esetén hatékony (O(fokszám) idő), nem pedig O(V) idő.

Question 3: A szélességi bejárás (BFS) térkomplexitása O(V), ahol V a csúcsok száma?

A. Yes

B. No

Explanation: A tanulmányi anyag egyértelműen kimondja, hogy a BFS térkomplexitása O(V), mivel a sorban legfeljebb az összes csúcs tárolódhat, és a látogatott jelzők is V csúcsra vonatkoznak.

Question 4: Melyik állítás írja le helyesen a BFS algoritmus működési elvét a megadott tanulmányi anyag alapján?

A. A BFS egy verem (stack) adatszerkezetet használ a bejárás során.

B. A BFS egy sor (queue) adatszerkezetet használ, amely FIFO (First-In, First-Out) elven működik.

C. A sor (queue) adatszerkezet LIFO (Last-In, First-Out) elven működik a BFS-ben.

D. A BFS először mindig a kezdőcsúcstól legtávolabbi csúcsokat fedezi fel.

Explanation: Az anyag egyértelműen kimondja: 'A BFS egy sor (queue) adatszerkezetet használ a bejárás során. A sor FIFO (First-In, First-Out) elven működik, azaz az elsőként bekerülő elem távozik először.' Ez pontosan a második opciót írja le. Az első opció (verem) és a harmadik opció (LIFO) ellentmond az anyagnak. A negyedik opció (legtávolabbi csúcsok felfedezése) szintén helytelen, mert a BFS rétegenként haladva a kezdőponthoz legközelebbi csúcsokat fedezi fel először.

Question 5: A DFS algoritmus rekurzív megvalósítása során a látogatott csúcsok jelölésére listát vagy tömböt kell létrehozni.

A. Yes

B. No

Explanation: A tanulmányi anyag egyértelműen kimondja a rekurzív megvalósítás lépései között, hogy 'Hozzon létre egy listát vagy tömböt a látogatott csúcsok jelölésére (pl. `látogatott` boolean tömb, minden eleme `hamis`).'