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.

$2n$ darab különböző csokiból hányféleképpen tudunk kiválasztani $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. $\left({\begin{array}{c}2n\\n\end{array}}\right)\cdot \left({\begin{array}{l}n\\3\end{array}}\right)$
2. $(2n-3)\cdot (2n-4)\cdot \ldots \cdot (n-2)$
3. $\left({\begin{array}{c}2n-3\\n\end{array}}\right)$
4. $\left({\begin{array}{c}2n\\n\end{array}}\right)\cdot {\frac {1}{3!}}$

Egy $n\times n$-es táblázat mezőin akarunk eljutni a bal felső cellából az utolsó sorba (itt mindegy, hogy a soron belül melyik oszlopba érkezünk). (2022 jun)

A szabályok a következők:

• Az első oszlop első mezőjéről kell indulnunk és a végén az utolsó sor tetszőleges mezőjére kell érkeznünk.
• Egy lépésben vagy egy cellát mehetünk lefele (és maradunk ugyanabban az oszlopban) vagy egy cellát megyünk jobbra (és maradunk ugyanabban a sorban) vagy átlósan lépünk egyet lefele jobbra (azaz egy sort lefele és egy oszlopnyit jobbra).

Jelölje $T[i,j](1\leq i,j\leq n$ esetén) azt, hogy az $i$-edik sor $j$-edik oszlopában levő mezőbe hányféleképpen juthatok el a bal felső cellából. Inicializáljuk a kezdeti értékeket így: mivel az első sor minden cellájába egyféleképpen juthatunk, ezért $T[1,j]=1$ minden $1\leq j\leq n$ esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért $T[i,1]=1$ minden $1\leq i\leq n$ esetén. Melyik rekurziós képlet a helyes a többi $T[i,j]$ érték meghatározására?

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

1. $T[i,j]=T[i-1,j]+T[i,j-1]+T[i-1,j-1]$
2. $T[i,j]=\max\{T[i-1,j],T[i,j-1],T[i-1,j-1]\}$
3. $T[i,j]=T[i-1,j]+T[i,j-1]+T[i-1,j-1]+1$
4. $T[i,j]=T[i-1,j-1]+1$

Az előző feladat folytatása:

A teljesen kitöltött $T$ táblázat segítségével hogyan kaphatjuk meg azt, hogy hányféleképpen lehet eljutni a bal felső cellából a legalsó sorba?

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

1. $\max _{1<i<n}T[i,n]$ adja meg ezt.
2. $\Sigma _{i=1}^{n}T[i,n]$ adja meg ezt.
3. $T[n,n]$ adja meg ezt.
4. $\max _{1\leq j\leq n}T[n,j]$ adja meg ezt
5. $\Sigma _{j=1}^{n}T[n,j]$ adja meg ezt.

A $G$ egyszerű, irányítatlan gráf élei súlyozottak. Tegyük fel, hogy az élek súlyai különbözőek és hogy van legalább három éle a gráfnak. (2022 jun)

Tekintsük a következő állításokat: A: $G$ minden minimális feszítőfája tartalmazza a legkisebb súlyú élt. B: $G$ minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt. C: $G$ egyik minimális feszítőfája sem tartalmazza a legnagyobb súlyú élt. Melyik a helyes az alábbi lehetőségek közül?

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

1. Csak az $A$ állítás igaz, a másik kettő nem
2. Az $A$, a $B$ és a $C$ állítás is igaz.
3. Csak az $A$ és a $B$ állítás igaz, a $C$ nem.
4. Csak az $A$ és a $C$ állítás igaz, a $B$ nem.

Legyen $X$ a Értelmezés sikertelen (formai hiba): {\displaystyle 2SZÍN} eldöntési probléma, azaz ahol egy egyszerü, irányítatlan $G$ gráfról azt szeretnénk eldönteni, hogy ki lehet-e színezni a csúcsait két színnel úgy, hogy azonos színú csúcsok közőtt ne menjen él. Az $Y$ eldöntési problémában pedig azt kell eldöntenünk $n$ darab pozitív egész számról, hogy van-e ezeknek a számoknak egy olyan részhalmaza, hogy a részhalmazban levő számok összege megegyezik a részhalmazba be nem vett számok összegével. (2022 jun)

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

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

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

Tekintsük azt a $K_{20,40}$ teljes páros gráfot, melynek $A=\left\{a_{1},a_{2},\ldots ,a_{20}\right\}$ és $B=\left\{b_{1},b_{2},\ldots ,b_{40}\right\}$ a két osztálya. Hány maximális (azaz tovább nem bővíthető) párosítás van ebben a gráfban? (Két párosítás különböző, ha nem pontosan ugyanazokból az $\left(a_{i},b_{j}\right)$ élekből áll.) (2022 jun)

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

1. $\left({\begin{array}{l}40\\20\end{array}}\right)\cdot 20$ !
2. $\left({\begin{array}{l}40\\20\end{array}}\right)$
3. $40^{20}$
4. $40!$

Az $1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16$ tömböt rendezzük a szokásos (módosítás nélkül futtatott) öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jun)

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

1. 0
2. 64
3. $\left({\begin{array}{c}16\\2\end{array}}\right)$
4. 32

Az ${\mathcal {A}}$ algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, $n$-nek a függvényében $O\left(n^{2}\right)$. (2022 jun)

Melyik nem igaz az alábbiak közül?

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

1. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ lépésszáma kisebb, mint $n^{3}$.
2. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ lépésszáma nagyobb, mint $n^{3}$.
3. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ lépésszáma kisebb, mint $n$.
4. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ lépésszáma nagyobb, mint $n$.

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): $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: $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. $H$ fokszáma lehet 1 vagy 2, és más nem lehet
2. $H$ fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet
3. $H$ fokszáma lehet 1, 2 vagy 3, és más nem lehet
4. $H$ fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet

Adott egy $3n$ csúcsú teljes gráf, a csúcsok számozottak, az 1, 2,…, n 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ő n csúcs piros? (2022 jan)

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

1. ${\frac {n!}{2}}*n!$
2. $n!*n!*n!$
3. $2*n!*n!$
4. $n!*(2n)!$

A $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ű $\{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 $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 $log$ függvény mindig kettes alapú logaritmust jelöl): (2022 jan)

${\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. $f(n)\notin O(h(n))$ és $g(n)\in O(h(n))$
2. $f(n)\in O(h(n))$ és $g(n)\notin O(h(n))$
3. $f(n)\in O(h(n))$ és $g(n)\in O(h(n))$
4. $f(n)\notin O(h(n))$ és $g(n)\notin O(h(n))$

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

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

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

1. A probléma $P$-ben és $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)

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

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

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 az é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$