Záróvizsga kvíz - Algoritmusok

ZVAlgo

Kvízek használata, fejlesztése.
Statisztika
Átlagteljesítmény	-
Eddigi kérdések	0
Kapott pontok	0
Alapbeállított pontozás	(-)
-
Beállítások
Minden kérdés látszik	-
Véletlenszerű sorrend	-
-

Tekintsük az alábbi két függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jun)

[math]f(n)=2023 \cdot n^2 \cdot \log n-100 \cdot \sqrt{n}[/math]

[math]g(n)=\frac{1}{10^{10}} \cdot n^3+82 \cdot n \cdot \log n[/math]

Az alábbiak közül melyik állítás igaz?

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

1. [math]f(n) \in O(g(n))[/math], mert mindkét függvényre igaz, hogy [math]$O\left(n^3\right)$[/math]
2. [math]f(n) \in O(g(n))[/math], mert [math]f(n) \in O\left(n^2\right)[/math] és [math]g(n) \in O\left(n^3\right)$[/math]
3. [math]f(n) \in O(g(n))[/math], de az előző két indoklás egyike sem helyes
4. [math]f(n) \notin O(g(n))[/math]

Egy bináris keresőfa preorder bejárása a csúcsokat [math]5, 2, 4, 12, 8, 7, 10, 20[/math] sorrendben látogatja meg. (2023 jun)

Melyik igaz az alábbi állítások közül a keresőfára?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

1. A 7 a 12 egyik részfájában van.
2. A 8 a gyökérben van.
3. A 10 a 2 egyik részfájában van.
4. A 2 egy levélben van.

[math]2n[/math] darab különböző csokiból hányféleképpen tudunk kiválasztani [math]n[/math] darabot úgy, hogy a három kedvenc csokink a kiválasztottak között legyen? (2023 jun)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

1. [math]\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot\left(\begin{array}{l}n \\ 3\end{array}\right)[/math]
2. [math](2 n-3) \cdot(2 n-4) \cdot \ldots \cdot(n-2)[/math]
3. [math]\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)[/math]
4. [math]\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}[/math]

Egy csupa különböző egész számot tartalmazó bináris keresőfában egy keresés során az alábbi értékeket látjuk (x értéke nem ismert): [math]10, 5, x, 7, 8[/math]. Az alábbiak közül mi igaz x értékére? (2022 jan)

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

1. x lehet 1 is és 9 is
2. x lehet 6 is és 9 is
3. x lehet 1 is és 6 is
4. x lehet 2 is és 12 is

Egy kezdetben üres bináris keresőfába beszúrtuk az egész számokat valamilyen sorrendben (a sorrend nem ismert). Mi igaz biztosan az alábbiak közül? (2022 jan)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

1. Az 1 levélben van.
2. A fának 7 szintje van.
3. A legutoljára beszúrt érték levélben van.
4. A középső érték, azaz a 64, a gyökérben van.

Egy irányítatlan nyolc csúcsú gráfon DFS-t (mélységi bejárást) futtatunk úgy, hogy ha döntési helyzetben vagyunk, akkor az ábécé szerinti sorrend szerint haladunk. A DFS fába az alábbi élek kerülnek be ebben a sorrendben: [math]AB, BD, AF, FE, EC, FG, GH[/math]. Mi igaz a csúcs fokszámára az alábbiak közül? (2022 jan)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

1. [math]H[/math] fokszáma lehet 1 vagy 2, és más nem lehet
2. [math]H[/math] fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet
3. [math]H[/math] fokszáma lehet 1, 2 vagy 3, és más nem lehet
4. [math]H[/math] fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet

Adott egy [math]3n[/math] csúcsú teljes gráf, a csúcsok számozottak, az számozású csúcsok pirosra vannak színezve, a többi csúcs színtelen. Hány olyan különböző Hamilton-út van a gráfban, amelyben az első csúcs piros? (2022 jan)

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

1. [math]\frac{n!}{2} * n![/math]
2. [math]n! * n! * n![/math]
3. [math]2 * n! * n![/math]
4. [math]n! * (2n)![/math]

A [math]4, 3, 2, 1, 5, 6, 7, 8[/math] tömböt rendezzük öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jan)

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

1. 12
2. 7
3. 4
4. 8

Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű [math]\{a,b,c,d\}[/math] ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan)

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

1. 1 ládarendezést használunk [math]4^5[/math] ládával.
2. 5 ládarendezést használunk, mindegyik esetben 4 ládával.
3. 4 ládarendezést használunk, mindegyik esetben 5 ládával.
4. 1 ládarendezést használunk 20 ládával.

Tekintsük az alábbi három függvényt (itt a [math]log[/math] függvény mindig kettes alapú logaritmust jelöl): (2022 jan)

[math]\begin{aligned} & f(n)=2022 \cdot n^2 \cdot \log n+7 \cdot \sqrt{n} \\ & g(n)=\log n+1000+n \cdot(\log n)^2 \\ & h(n)=n \cdot \sqrt{n}+\frac{1}{1000} \cdot n^2-8 \end{aligned}[/math]

Az alábbiak közül melyik állítás igaz ezen három függvény nagyságrendjére?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

1. [math]f(n) \notin O(h(n))[/math] és [math]g(n) \in O(h(n))[/math]
2. [math]f(n) \in O(h(n))[/math] és [math]g(n) \notin O(h(n))[/math]
3. [math]f(n) \in O(h(n))[/math] és [math]g(n) \in O(h(n))[/math]
4. [math]f(n) \notin O(h(n))[/math] és [math]g(n) \notin O(h(n))[/math]

Tekintsük azt az eldöntési feladatot, ahol egy irányított [math]G[/math] gráfról azt szeretnénk eldönteni, hogy van-e két olyan [math]s[/math] és [math]t[/math] csúcsa, hogy [math]s[/math]-ből van irányított út [math]t[/math]-be, de [math]t[/math]-ből nincsen irányított út [math]s[/math]-be (2022 jan)

Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy [math]P \neq NP[/math]?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

1. A probléma [math]P[/math]-ben és [math]NP[/math]-ben is benne van.
2. A probléma [math]P[/math]-ben van, de nincs [math]NP[/math]-ben.
3. A probléma [math]NP[/math]-teljes és nincs [math]P[/math]-ben.
4. A probléma [math]P[/math]-ben van és [math]NP[/math]-teljes.

Legyen [math]X[/math] az az eldöntési probléma, ahol egy irányítatlan [math]G[/math] páros gráfról és egy [math]k[/math] számról azt szeretnénk eldönteni, hogy van-e [math]G[/math]-ben [math]k[/math] élű párosítás és legyen [math]Y[/math] az a kérdés, ahol egy irányítatlan [math]G[/math] gráfról és egy számról azt szeretnénk eldönteni, hogy van-e [math]G[/math]-ben [math]k[/math] pontból álló klikk (azaz teljes gráf). (2022 jan)

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

Mi igaz az alábbiak közül, ha feltételezzük, hogy [math]P \neq NP[/math]?

1. [math]X[/math] Karp-redukálható [math]Y[/math]-ra, de [math]Y[/math] nem Karp-redukálható [math]X[/math]-re.
2. [math]X[/math] nem Karp-redukálható [math]Y[/math]-ra, de [math]Y[/math] Karp-redukálható [math]X[/math]-re.
3. [math]X[/math] Karp-redukálható [math]Y[/math]-ra és [math]Y[/math] is Karp-redukálható [math]X[/math]-re.
4. [math]X[/math] sem Karp-redukálható [math]Y[/math]-ra és [math]Y[/math] sem Karp-redukálható [math]X[/math]-re.

A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk [math]C = 10[/math]-es hátizsák kapacitással. A táblázat [math]i = 7[/math]-es sora a értékekkel így néz ki: (2022 jan)

X	0	1	2	3	4	5	6	7	8	9	10
7	0	0	7	7	8	12	12	12	12	20	20

Mi igaz a következő, [math]i = 8[/math]-as sor [math]V[8,b][/math] értékeire az alábbiak közül, ha a 8. tárgy [math]w_8[/math] súlya [math]5[/math], [math]v_8[/math] értéke pedig [math]6[/math]? ([math]V[i,b][/math] jelentése: az első [math]i[/math] tárgyból [math]b[/math] hátizsák kapacitás mellett elérhető maximális érték.)

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

1. [math]V[8,4]=8 \text { és } V[8,9]=17[/math]
2. [math]V[8,3]=7 \text { és } V[8,8]=13[/math]
3. [math]V[8,4]=8 \text { és } V[8,8]=12[/math]
4. [math]V[8,4]=5 \text { és } V[8,8]=12[/math]