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élbe n 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!}}$

Radix rendezéssel rendezzük az alábbi sorozatot: $s_{1}=abac,s_{2}=acbc,s_{3}=bcac,s_{4}=bbbb,s_{5}=cacb$ (a karakterek mindegyik pozícióban a 3-elemű $\{a,b,c\}$ ábécéből kerülnek ki). (2023 jun)

Melyik állítás igaz a rendezés folyamatára?

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

1. $s_{5}=cacb$ soha nem előzi meg az $s_{1}=abac$ szót.
2. Van olyan fázis, amikor $s_{3}=bcac$ megelőzi az $s_{1}=abac$ szót.
3. $s_{3}=bcac$ és $s_{4}=bbbb$ sorrendje pontosan kétszer változik.
4. Van olyan fázis, amikor $s_{3}=bcac$ megelőzi az $s_{2}=acbc$ szót.

Kruskal algoritmusát futtatjuk az alábbi gráfon. (2023 jun)

Melyik állítás igaz az alábbiak közül?

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

1. Ha $x\leq 3$ akkor az $EC$ élet biztosan nem választja be az algoritmus a minimális feszítőfába.
2. Az $AC$ élet biztosan beválasztja az algoritmus a minimális feszítőfába, bármi is $x$ értéke.
3. Az $AC$ élet biztosan nem választja be az algoritmus a minimális feszítőfába, bármi is $x$ értéke.
4. Az algoritmus biztosan beválaszt legalább egy 3 súlyú élet a minimális feszítőfába.

Az $n$ csúcsú $G=(V,E)$ irányítatlan gráfra igaz, hogy bárhogyan is sorolunk fel $\left(v_{1},v_{2},\ldots ,v_{k}\right)$ csupa különböző $G$ -beli csúcsokat, ahol $3\leq k\leq n$ a $\left\{v_{1},v_{2}\right\},\left\{v_{2},v_{3}\right\},\ldots ,\left\{v_{k-1},v_{k}\right\}$ és $\left\{v_{k},v_{1}\right\}$ párok közül legalább az egyik benne van $G$ élhalmazában. Melyik állítás igaz az alábbiak közül? (2023 jun)

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

1. $G$ komplementerében nincsen kör.
2. $G$-ben van kör.
3. $G$-ben nincsen $k$ méretű független ponthalmaz.
4. $G$ komplementerében nincsen $k$ -as klikk.

Egy ország térképe egy élsúlyozott, irányítatlan $n$ csúcsú $G$ gráf szomszédossági mátrixával adott. A csomópontok a városok, az élek a városok között vezető közvetlen utak, egy él súlya a megfelelő útszakasz hosszát adja meg kilométerben. (2023 jun)

A városok közül néhányban van csak posta. Egy adott $k$ érték esetén azt szeretnénk eldönteni, hogy igaz-e, hogy bármelyik településről van $k$ kilométeren belül elérhető, postával rendelkező város (az eléréshez csak az úthálózatot használhatjuk). Az alábbi lehetőségek közül melyikkel lehet ezt eldönteni $O\left(n^{2}\right)$ lépésben?

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

1. Felveszünk egy új csúcsot, ebből 0 súlyú élet vezetünk minden postás városhoz, majd szélességi bejárást (BFS) futtatunk az új csúcsból a legrövidebb utak megkeresésére.
2. Minden csúcsból futtatunk egy szélességi bejárást (BFS) a legrövidebb utak megkeresésésére.
3. Minden csúcsból lefuttatjuk Dijktsra algoritmusát a legrövidebb utak megkeresésére.
4. Felveszünk egy új csúcsot, ebből 0 súlyú élet vezetünk minden postás városhoz, majd futtatjuk Dijkstra algoritmusát az új csúcsból a legrövidebb utak megkeresésére.

Eldöntési feladatok (2023 jun)

Az $X_{1}$ eldöntési feladatban egy irányítatlan $G$ gráfról azt szeretnénk eldönteni, hogy van-e $G$ -ben pontosan 4 élü kör. Az $X_{2}$ eldöntési feladatban egy irányítatlan $G$ gráfról és egy pozitív egész $k$ számról azt szeretnénk eldönteni, hogy van-e $G$ -ben pontosan $k$ élü kör. 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. $X_{1}\in P$ és $X_{2}\in NP\backslash P\checkmark$
2. $X_{1}\in P$ és $X_{2}\in P$
3. $X_{1}\in \operatorname {coN} P$ de $X_{1}\notin P$
4. $X_{1}\in P$ de $X_{1}\notin NP$

Az $X$ eldöntési problémáról azt tudjuk, hogy $NP$ -ben van, az $Y$ eldöntési problémáról pedig azt, hogy $NP$ -teljes. (2023 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. Minden olyan eldöntési probléma, ami Karp-redukálható $Y$ -ra, az Karp-redukálható $X$ -re is.
2. $Y$ biztosan Karp-redukálható $X$ -re. ${}^{X}$
3. Ha $X$ Karp-redukálható $Y$ -ra, akkor $X$ nincsen $P$ -ben.
4. Ha $Y$ Karp-redukálható $X$ -re, akkor az $X$ probléma $NP$ -teljes.

Adott egy egész számokat tartalmazó $A[1:n]$ tömb, melyben nem szerepel 0. (2023 jun)

Az $A[1:n]$ tömb alapján egy $P[1:n]$ és egy $N[1:n]$ tömböt töltünk ki a következőképpen:

• ha $A[1]>0$ akkor $P[1]=A[1]$ és $N[1]=A[1]$ .
• ha $A[1]\leq 0$ akkor $P[1]=0$ és $N[1]=A[1]$

A további értékeket $(i>2)$ így számoljuk:

• ha $A[i]>0$ akkor $P[i]=P[i-1]+A[i]$ és $N[i]=\max\{N[i-1]+A[i],A[i]\}$
• ha $A[i]\leq 0$ akkor $P[i]=0$ és $N[i]=P[i-1]+A[i]$

Melyik állítás igaz az alábbiak közül a kiszámolt $P[i]$ és $N[i]$ értékek jelentésére?

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

1. $N[i]$ megadja a legnagyobb összeget, amit valamelyik, legfeljebb egy negatív számot tartalmazó $A[j:i]$ résztömbből ( $1\leq j\leq i)$ kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
2. $P[i]$ megadja a legnagyobb összeget, amit valamelyik $A[j:i]$ résztömbből $(1\leq j\leq i)$ kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
3. $N[i]$ megadja az $A[1:i]$ tömbben szereplö összes negatív szám összegét
4. $P[i]$ megadja az $A[1:i]$ tömbben szereplö összes szám összegét

Egy irányítatlan nyolc csúcsú gráfon BFS-t (szélességi bejárást) futtatunk úgy, hogy ha döntési helyzetben vagyunk, akkor az ábécé szerinti sorrend szerint haladunk. A BFS fába az alábbi élek kerülnek be ebben a sorrendben: $AB,AC,AD,CE,DF,EH,FG$. (2023 jan)

Melyik csúcs lehet szomszédja az $F$ csúcsnak a gráfban?

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

1. A
2. B
3. C
4. E

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

$f(n)=n!+10\cdot n^{2}-3$

$g(n)={\frac {1}{8}}n^{n}+9\cdot \log n$

$h(n)=10^{1000}\cdot n^{1000}+37\cdot n^{3}+42$

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

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

1. $f(n)\in O(g(n)){\text{ és }}g(n)\in O(h(n))$
2. $f(n)\in O(g(n)){\text{ és }}g(n)\notin O(h(n))$
3. $f(n)\notin O(g(n)){\text{ és }}g(n)\in O(h(n))$
4. $f(n)\notin O(g(n)){\text{ és }}g(n)\notin O(h(n))$

Az alábbi lehetőségek közül melyik az a változtatás, amit ha végrehajtunk a 10,5,7,6,2, 3 számsorozaton, akkor van olyan bináris keresőfa, amiben egy keresés során láthatjuk a kapott új sorozat elemeit ebben a sorrendben? (2023 jan)

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

1. 2 helyett álljon 4
2. 7 helyett álljon 8
3. 5 helyett álljon 1
4. 10 helyett álljon 1

Egy $k$ és egy $\ell$ hosszú rendezett tömböt fésülünk össze a tanult összefésülés eljárással. Maximum mennyi összehasonlítás történhet eközben? (2023 jan)

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

1. $k\cdot \ell$
2. $k+\ell -1$
3. $\max\{k,\ell \}$
4. $k+\ell x$

Egy csupa különböző egész számot tartalmazó $T$ tömbben akarjuk eldönteni egy adott $x$ elemről, hogy igaz-e, hogy $x$ és $2\cdot x$ is szerepel $T$-ben. Az alábbi négy állítás közül melyek igazak? (2023 jan)

A: Ez megtehető $O(n)$ lépésben, ha a tömb rendezett.

B: Ez megtehető $O(\log n)$ lépésben, ha a tömb rendezett.

C: Ez megtehető $O(n)$ lépésben tetszőleges tömb esetén.

D: Ez megtehető $O(\log n)$ lépésben tetszőleges tömb esetén.

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

1. Csak az $A,B$ állítások igazak.
2. Csak az $A,B,C$ állítások igazak.
3. Mind a négy igaz.
4. Csak az $A,C$ állítások igazak.

Egy országban a rendszámok hét karakterből állnak, az első négy karakter egy 26 elemú ábécéből kerül ki, az utolsó három karakter pedig a $0,1,2,3,4,5,6,7,8,9$ halmazból. További megkötés nincs a rendszámokra. (2023 jan)

Hány olyan rendszám van, ahol az első két betû megegyezik és a három számjegyből a középső a 0 ?

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

1. $3\cdot 26+2\cdot 10$
2. $26^{3}\cdot 10^{2}$
3. $26^{3}+10^{2}$
4. $3\cdot 2\cdot 26\cdot 10$

Adott egy 200 elemű $T[1:200]$ tömb, amiben $T[3i]=i$ minden $1\leq i\leq 66$ esetén, minden egyéb esetben (azaz amikor az index nem többszöröse a 3-nak) pedig $T[j]=-1$. (2023 jan)

Definiáljuk az $A$ tömböt a következőképpen: $A[1]=T[1]$

és $1\leq j\leq 200$ esetén $A[j]=\max\{A[j-1]+T[j],T[j]\}$.

Mennyi $A[4]$ értéke?

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

1. 1
2. $-1$
3. $-2$
4. 0

Az előző feladat folytatása: Mi igaz az alábbiak közül a kitöltött $A[1:200]$ tömb elemeire?

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

1. $A[j]=A[j-1]$ teljesül legalább 50 esetben
2. $A[j]=T[j]$ teljesül legalább 50 esetben
3. $A[j]>0$ teljesül legalább 50 esetben $\checkmark$
4. $A[200]$ a legnagyobb érték az $A[1:200]$ tömbben.

Egy ország térképe egy élsúlyozott, irányítatlan $G$ gráf szomszédossági mátrixával adott. A csomópontok a városok, az élek a városok között vezető közvetlen utak, az élek súlya pedig azt adja meg, hogy az autónk az adott útszakaszon hány liter benzint fogyaszt. (2023 jan)

Adott egy $A$ csomópont, ahol éppen tartózkodunk és tudjuk hogy $B$ liter benzinünk van. Melyik tanult algoritmussal lehet meghatározni, hogy az ország mely városaiba tudunk eljutni tankolás nélkül?

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

1. BFS-t, azaz szélességi bejárást kell futtatni az $A$ csúcsból.
2. Kruskal algoritmust kell futtatni a gráfon.
3. DFS-t, azaz mélységi bejárást kell futtatni az $A$ csúcsból.
4. Dijkstra algoritmust kell futtatni az $A$ csúcsból.

Legyen $X$ az az eldöntési probléma, melynek inputja egy irányított $G$ gráfból, ezen gráf egy $s$ csúcsából és egy $k$ pozitív egészből áll és azt szeretnénk eldönteni, hogy igaz-e hogy $G$-ben $s$-ből minden más csúcsba vezet legfeljebb $k$ élből álló út. Legyen továbbá $Y$ a tanult $3-SZ$ IíN eldöntési feladat. (2023 jan)

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

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

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

Tekintsük azt az eldöntési feladatot, ahol egy irányítatlan $G$ gráfról azt szeretnénk eldönteni, hogy hozzá lehet-e adni legfeljebb 5 élet $G$-hez úgy, hogy a keletkező gráfban legyen 100 pontú teljes részgráf. (Új csúcsot nem adunk hozzá a gráfhoz, csak éleket húzunk be a már meglevő csúcsok közé.) (2023 jan)

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

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

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

Pozitív egész számokat szeretnénk tárolni valami adatszerkezet segítségével úgy, hogy $n$ tárolt elem esetén tetszőleges $x$ egész számról $O(\log n)$ lépésben meg tudjuk mondani, hogy igaz-e rá, hogy $x$ a tárolt számok között van, de sem $x-1$ , sem $x+1$ nincsen. (2022 jun)

Melyik adatszerkezettel valósítható ez meg?

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

1. 2-3 fa
2. rendezett lista
3. nyílt címzésú hash
4. (nem feltétlenül kiegyensúlyozott) bináris keresőfa

Az 1, 8, 10,12, 20, 27, 30 rendezett tömbben bináris kereséssel keressük a 30-at. Hány összehasonlítás után találjuk meg? (2022 jun)

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

1. 2
2. 1
3. 7
4. 3

Egy kezdetben üres bináris keresőfába szúrtunk be elemeket (törlés nem volt). Az alábbiak közül melyik beszúrási sorrend eredményezi az ábrán látható fát? (2022 jun)

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

1. $5,9,1,7,3,4$
2. $5,7,4,9,3,1$
3. $5,3,4,9,1,7$
4. $5,4,7,3,9,1$

Tekintsük azt a feladatot, ahol egy $n>100$ csúcsú irányított $G$ gráfról azt szeretnénk eldönteni, hogy van-e 100 olyan csúcsa, hogy a gráfból ezeket elhagyva a maradék gráf csupa izolált pontból áll. (2022 jun)

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

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

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

A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun)

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

1. $A,B,D,E,F,G,H,C$
2. $A,D,F,G,H,C,E,B$
3. $A,B,C,D,E,F,G,H$
4. $A,D,F,E,B,G,H,C$

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:

1. 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.
2. 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)

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

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$

Az alábbi állítások közül pontosan egy hamis. Válassza ki a HAMIS állítást! (2021 jan)

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

1. Előfordulhat, hogy egy bináris keresőfában végrehajtott keresés belső csúcsban (azaz nem levélben) ér véget.
2. Bináris keresőfában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.
3. Bináris keresőfában a tárolt értékek közül a középsőt 1 lépésben meg lehet találni, mert az mindig a gyökérben van.
4. Piros-fekete fában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.

Legyen $G(V,E)$ egy egyszerú, irányítatlan gráf. Tekintsük a következő tulajdonságot: (2021 jan)

Vannak olyan $X\subseteq V$ és $Y\subseteq V$ nemüres halmazok, melyekre igaz, hogy

• $X\cap Y=\emptyset$
• $X\cup Y=V$
• bármely $\{u,v\}\in E$ él esetén az $\{u,v\}\cap X$ halmaz egy elemú.

Az alábbiak közül melyik írja le pontosan a megadott tulajdonságú gráfokat?

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

1. Nincsen egyetlen éle sem a gráfnak.
2. A gráf páros gráf, de nem feltétlenül teljes páros gráf
3. A gráf teljes páros gráf
4. A gráf teljes gráf.
5. A gráfban van teljes párosítás

Az alábbi bináris keresőfa csúcsait a posztorder és a preorder bejárás szerinti sorrendben is kiírjuk. (2021 jan)

Melyik álítás igaz?

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

1. A 3 előbb jön, mint a 27 mindkét sorrendben.
2. A 15 megelőzi a 4-et a preorder sorrendben, mert a 15 belső csúcsban van, a 4 pedig levélben.
3. A 27 megelőzi a 9-et a posztorder sorrendben, mert a 27 levélben van, a 9 pedig belső csúcsban.
4. A számok növekvő sorrendben vannak a két sorrend egyike szerint.
5. A 3 után közvetlenül a 4 következik a két sorrend valamelyikében.

Melyik állítás igaz az alábbi négy függvény nagyságrendjére? (2021 jan)

(a) $100\cdot {\frac {n(n-1)}{n-2}}\cdot \log _{2}n+17n-32$

(b) $2\cdot n^{2}\cdot {\sqrt {n}}+44n^{2}+13$

(c) ${\frac {1}{10^{10}}}\cdot {\frac {4^{n}}{2^{n}}}$

(d) $4n^{2}+37n-12$

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

1. Az (a) függvény $O\left(2^{n}\right)$, a (b) függvény $O\left(n^{2}\right)$
2. $\mathrm {Az}$ (a) és a (d) függvény is $O\left(n^{2}\right)$
3. $\mathrm {Az}$ (b) függvény $O\left(n^{n}\right)$, a (c) függvény $O\left(n^{2}\right)$
4. A négy függvény közül csak a (d) függvény $O\left(n^{2}\right)$
5. A (b), a (c) és a (d) függvény is $O\left(n^{2}\right)$

Legyen $X$ egy $n$ elemú véges halmaz, $n>0$. Hány páratlan elemú részhalmaza van $X$-nek? (2021 jan)

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

1. $n$
2. $2^{\lfloor n/2\rfloor }$
3. $2^{n-1}$
4. $2^{n}$
5. Más a formula attól függően, hogy $n$ páros vagy páratlan.

Egy város úthálózatát a $G$ egyszerú, irányítatlan, összefüggő gráf írja le, a gráf csúcsai a csomópontok, az élek az ezeket összekötőútszakaszokat jelölik. (2021 jan)

Az utak sajnos eléggé rossz állapotúak, minden élre adott, hogy azt az útszakaszt mennyiért lehetne felújítani. A város vezetése azt szeretné megtudni, hogy mely útszakaszokat újitassa fel, ha a célja az, hogy a $v$ csúccsal jelzett főtérről mindencsomópontba el lehessen jutni kizárólag felújított útszakaszokon. A következő ötletek merültek fel a legolcsóbb ilyen felújitás megtalálására: A: Dijkstra algoritmusával határozzák meg a legrövidebb utakat $v$-ből az összes többi csúcsba. B: A Bellman-Ford-algoritmussal határozzák meg a legrövidebb utakat $v$-ből az összes többi csúcsba. C: Kruskal algoritmusával határozzanak meg egy minimális feszítófát a gráfban. Melyik ad helyes eredményt a feladatra?

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

1. Csak az A módszer.
2. Csak a B módszer.
3. Csak a C módszer
4. Csak az A és a B módszer.
5. Mindhárom módszer

Tudjuk, hogy az ${\mathcal {A}}$ probléma $NP$-teljes, a ${\mathcal {B}}$ probléma pedig $NP$-beli, de nem feltétlenül $NP$-teljes. (2021 jan)

Tekintsük a következő álításokat:

A: Ha az ${\mathcal {A}}$ problémára van polinom idejü algoritmus, akkor $P=NP$.

B: Ha a ${\mathcal {B}}$ problémára van polinom idejú algoritmus, akkor $P=NP$.

C: Ha az ${\mathcal {A}}$ problémára van polinom idejú algoritmus, akkor a ${\mathcal {B}}$ problémára is van polinom idejú algoritmus.

Melyik helyes az alábbiak közül?

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

1. Csak az A és a C igaz.
2. Csak az A igaz.
3. Az A, B, C mindegyike igaz.
4. Csak a B igaz.
5. Csak az A és a B igaz.

Adott egy $n$ hosszú számsorozat, $a_{1},a_{2},\ldots ,a_{n}$. (2021 jan)

Definiáljuk a $T$ és $S$ tömböt a következőképpen:

$T[0]=S[0]=0,T[1]=a_{1}$

és $1\leq i\leq n$ esetén:

$T[i]=\max _{j\leq i-1}\left\{T[j]+a_{i}\right\}$

$S[i]=\max _{j\leq i}\{T[j]\}$

Legyen most a számsorozat olyan, hogy ha $i$ hárommal osztható, akkor $a_{i}=3$, különben meg $a_{i}=1$.

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

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

1. $T[10]=10$
2. $T[4]=4$
3. $S[10]=9$
4. $S[3n]=3n$
5. $T[36]=37$

Adott $n$ tárgy, tudjuk, hogy az $i$-ediknek a súlya $s_{i}$ kilogramm, az értéke $v_{i}$ forint, az $s_{i},v_{i}$ számok pozitív egészek. (2021 jan)

Azt szeretnénk eldönteni, hogy ki lehet-e közülük választani néhányat úgy, hogy ezek berakhatók legyenek egy összesen 100 kg teherbírású zsákba, és a kiválasztott tárgyak értékeinek összege legalább 2021 Ft legyen. 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 és $NP$-teljes.
3. A probléma $NP$-teljes és nincs $P$-ben.
4. A probléma $P$-ben van, de nincs $NP$-ben.

Nézzük a következő két problémát: (2021 jan)

Legközelebbi pár: Adott $n$ szám egy rendezetlen tömbben. Határozzuk meg, hogy melyik két elem értéke van legközelebb egymáshoz. Legtávolabbi pár: Adott $n$ szám egy rendezetlen tömbben. Határozzuk meg, hogy melyik két elem értéke van legtávolabb egymástól. A megengedett lépések legyenek: két elem összehasonlítása, két elem távolságának (azaz különbségének) a meghatározása, két elemcseréje a tömbben.

Tekintsük a követkető állításokat:

A: A Legközelebbi pár feladat megoldható a cseréken túl $O(n\log n)$ lépésben.

B: A Legközelebbi pár feladat megoldható a cseréken túl $O\left(n^{2}\right)$ lépésben.

C: A Legtávolabbi pár feladat megoldható a cseréken túl $O(n)$ lépésben.

D: A Legtávolabbi pár feladat megoldható a cseréken túl $O(n\log n)$ lépésben.

Melyik helyes az alábbiak közül?

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

1. Csak az A.
2. Mind a négy igaz.
3. Csak az A, a B és a D.
4. Csak a B és a D.