Záróvizsga kvíz - Algoritmusok

ZVAlgo

Kvízek használata, importálása, 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)

$f(n)=2023\cdot n^{2}\cdot \log n-100\cdot {\sqrt {n}}$

$g(n)={\frac {1}{10^{10}}}\cdot n^{3}+82\cdot n\cdot \log n$

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

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

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

Egy bináris keresőfa preorder bejárása a csúcsokat $5,2,4,12,8,7,10,20$ 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.

Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2n} darab különböző csokiból hányféleképpen tudunk kiválasztani Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} 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. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot\left(\begin{array}{l}n \\ 3\end{array}\right)}
2. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (2 n-3) \cdot(2 n-4) \cdot \ldots \cdot(n-2)}
3. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \left(\begin{array}{c}2 n-3 \\ n\end{array}\right)}
4. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}}

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): Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 10, 5, x, 7, 8} . 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: Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle AB, BD, AF, FE, EC, FG, GH} . 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. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} fokszáma lehet 1 vagy 2, és más nem lehet
2. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet
3. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} fokszáma lehet 1, 2 vagy 3, és más nem lehet
4. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet

Adott egy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 3n} 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. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \frac{n!}{2} * n!}
2. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n! * n! * n!}
3. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 2 * n! * n!}
4. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n! * (2n)!}

A Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 4, 3, 2, 1, 5, 6, 7, 8} 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ű Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{a,b,c,d\}} á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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 4^5} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle log} függvény mindig kettes alapú logaritmust jelöl): (2022 jan)

Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \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}}

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. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f(n) \notin O(h(n))} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle g(n) \in O(h(n))}
2. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f(n) \in O(h(n))} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle g(n) \notin O(h(n))}
3. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f(n) \in O(h(n))} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle g(n) \in O(h(n))}
4. Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f(n) \notin O(h(n))} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle g(n) \notin O(h(n))}

Tekintsük azt az eldöntési feladatot, ahol egy irányított Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G} gráfról azt szeretnénk eldönteni, hogy van-e két olyan Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} csúcsa, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből van irányított út Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -be, de Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -ből nincsen irányított út Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -be (2022 jan)

Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P \neq NP} ?

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

1. A probléma Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle P} -ben és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle NP} -ben is benne van.
2. A probléma $P$-ben van, de nincs $NP$-ben.
3. A probléma $NP$-teljes és nincs $P$-ben.
4. A probléma $P$-ben van és $NP$-teljes.

Legyen $X$ az az eldöntési probléma, ahol egy irányítatlan $G$ páros gráfról és egy $k$ számról azt szeretnénk eldönteni, hogy van-e $G$-ben $k$ élű párosítás és legyen $Y$ az a kérdés, ahol egy irányítatlan $G$ gráfról és egy számról azt szeretnénk eldönteni, hogy van-e $G$-ben $k$ 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 $P\neq NP$?

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

A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk $C=10$-es hátizsák kapacitással. A táblázat $i=7$-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ő, $i=8$-as sor $V[8,b]$ értékeire az alábbiak közül, ha a 8. tárgy $w_{8}$ súlya $5$, $v_{8}$ értéke pedig $6$? ($V[i,b]$ jelentése: az első $i$ tárgyból $b$ hátizsák kapacitás mellett elérhető maximális érték.)

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

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