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<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]<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]<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: 1. 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\leq i\leq 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 minden csomó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<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.

Az $f(n)$ függvényről azt tudjuk, hogy $f(n)\in O\left(n^{2}\right)$ Az alábbiak közül melyik lehet $f$ ? (Mindegyik logaritmus kettes alapú.) (2020 jan)

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

1. $f(n)=3\cdot 2^{(\log n)^{2}}+85n^{2}$
2. $f(n)=10\cdot n\log n+12n^{1,5}-8$
3. $f(n)=3n\log(n!)$
4. $f(n)=20\cdot {\frac {n^{3}}{\log n}}-15n^{2}$
5. Egyik sem lehet.

A kezdetben üres, $M=17$ méretü $A$ hash-táblába a $h(x)\equiv x({\bmod {1}}7)$ hash-függvényt és lineáris próbát használva beraktunk 9 elemet, majd kitöröltük az egyiket. Ha tudjuk, hogy a törlés után a nem üres mezők tartalma (2020 jan)

A[3]=4, \quad A[4]=22, \quad A[5]=5, \quad A[7]=44, \quad A[9]=26, \quad A[10]=11, \quad A[11]=28, \quad A[16]=33,

akkor hol volt a törölt elem?

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

1. $A[8]$-ban
2. $A[6]$-ban
3. $A[9]$-ben
4. Nem határozható meg.
5. Az elözőek egyike sem helyes.

Az angol ábécé 26 betűjéből és a 10 számjegyből hány olyan 8 hosszú sorozat készíthető, melyben sem két betü, sem két számjegy nem állhat egymás mellett? (Egy betü vagy számjegy többször is használható.) (2020 jan)

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

1. $26\cdot 25\cdot 24\cdot 23\cdot 10\cdot 9\cdot 8\cdot 7$
2. $2\cdot \left[\left({\begin{array}{c}26\\4\end{array}}\right)+\left({\begin{array}{c}10\\4\end{array}}\right)\right]$
3. $2\cdot 26^{4}\cdot 10^{4}$
4. $26\cdot 25\cdot 24\cdot 23+10\cdot 9\cdot 8\cdot 7$
5. Az előzőek egyike sem helyes.

Az alábbi gráfon a Kruskal-algoritmust használtuk minimális feszítőfa keresésre. Azt tapasztaltuk, hogy az algoritmus által kiválasztott első 3 él sorrendben a következő: $EC,DB,DE$ A felsorolt lehetőségek közül melyik lehet igaz az ismeretlen élsúlyokra? (2020 jan)

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

1. $x=1,y=5$
2. $x=5,y=1$
3. $x=y$
4. A fentiek egyike sem lehetséges.

A $G=(V,E)$ egyszerủ, irányítatlan gráf csúcsain adott egy $f:V\rightarrow \{0,1,2\}$ függvény. Melyik feltétel írja le azt, hogy ez a függvény a gráfnak egy szabályos 3 színnel való színezése? (2020 jan)

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

1. Minden $a,b\in V$ párra, ha $a\neq b$, akkor $f(a)\neq f(b)$
2. Minden $a,b\in V$ párra, ha $\{a,b\}\in E$, akkor $f(a)\neq f(b)$
3. Minden $a,b\in V$ párra, ha $f(a)\neq f(b)$, akkor $\{a,b\}\in E$
4. Minden $a,b\in V$ párra, ha $\{a,b\}\notin E$, akkor $f(a)=f(b)$

Tegyük fel, hogy $\mathrm {P} \neq \mathrm {NP}$ Tekintsük azt a problémát, amikor adottak az $a_{1},a_{2},\ldots ,a_{n}$ pozitív egész számok, és azt kell eldönteni, hogy van-e olyan $I\subseteq \{1,2,\ldots ,n\}$, melyre $\sum _{i\in I}a_{i}=2020$ (2020 jan)

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

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 P-ben van és NP-teljes.
4. A probléma NP-teljes és nincs P-ben.

Tegyük fel, hogy $\mathrm {P} \neq \mathrm {NP}$ és jelölje $P_{1}\prec P_{2}$ azt, hogy a $P_{1}$ probléma Karp-redukálható (polinomiálisan visszavezethető) a $P_{2}$ problémára. Tekintsük az alábbi három problémát. (2020 jan)

Adott egy $(G,k)$ pár, ahol $G$ egy irányítatlan gráf, $k$ egy pozitív egész és a kérdés az alábbi:

${\mathcal {A}}$ : a $G$ gráfban van-e legalább $k$ pontból álló kör

${\mathcal {B}}$ : a $G$ gráfban van-e legfeljebb $k$ pontból álló kör

${\mathcal {C}}$ : a $G$ gráfban van-e pontosan $k$ pontból álló kör

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

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

1. ${\mathcal {C}}\prec {\mathcal {A}}$ és ${\mathcal {C}}\prec {\mathcal {B}}$
2. ${\mathcal {A}}\prec {\mathcal {C}}$ és ${\mathcal {A}}\prec {\mathcal {B}}$
3. ${\mathcal {B}}\prec {\mathcal {C}}$ és ${\mathcal {C}}\prec {\mathcal {A}}$
4. ${\mathcal {A}}\prec {\mathcal {B}}$ és ${\mathcal {B}}\prec {\mathcal {C}}$

Legyen adott egy $G$ gráf, melynek adott két különböző csúcsa $A$ és $B$ Ez a két csúcs színtelen, a többi csúcs mindegyike vagy pirosra vagy kékre van színezve. (Szomszédos csúcsok lehetnek azonos színüek is.) Meg szeretnénk határozni a legkevesebb élú olyan utat $A$-ból $B$-be, ami csupa azonos színü csúcson megy át. Ehhez egy ismert algoritmust akarunk használni, akár többször is futtatva az alkalmas bemeneteken. (2020 jan)

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

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

1. Irányított gráf esetében a Dijkstra-algoritmus segítségével a feladat megoldható, de szélességi kereséssel nem.
2. Irányított gráf esetében a Dijkstra-algoritmus segítségével és szélességi kereséssel is megoldható a feladat.
3. Irányítatlan gráf esetében sem a Dijkstra-algoritmus segítségével, sem szélességi bejárással nem oldható meg a feladat.
4. Irányított és irányítatlan gráf esetében sem oldható meg a feladat a Dijkstra-algoritmus segítségével, de szélességi kereséssel mindig megoldható.

Melyik feladatra nem ismert $O\left(n^{2}\right)$ lépésben müködő algoritmus? (2020 jan)

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

1. Adott $n$ különböző egész szám közül a legkisebb kiválasztása.
2. Adott $n$ csúcsú bináris keresőfában tárolt elemek közül a legnagyobb meghatározása.
3. Adott $n$ bites $k$ egész számra $5^{k}$ kiszámolása.
4. Adott $n$ csúcsú, irányított, körmentes gráfban az adott $s$ csúcsból az adott $t$ csúcsba vezető legkevesebb élü út meghatározása.

Egy $n$ hosszú $s=s_{1}s_{2}\cdots s_{n}$ és egy $m$ hosszú $t=t_{1}t_{2}\cdots t_{m}$ sorozathoz a $T$ tömböt definiáljuk a következőképpen: Legyen $T[0,j]=T[i,0]=0$ minden $1\leq i\leq n$ és $1\leq j\leq m$ estén, továbbá $T[0,0]=0$ Az $1\leq i\leq n$ és $1\leq j\leq m$ esetekben pedig (2020 jan)

$T[i,j]={\begin{cases}\max\{T[i,j-1],T[i-1,j],T[i-1,j-1]+1\}&{\text{ ha }}s_{i}=t_{j}\\\max\{T[i,j-1],T[i-1,j]\}&{\text{ ha }}s_{i}\neq t_{j}\end{cases}}$

Legyen $n=100,m=20$, az $s$ az a 0 -val kezdődő sorozat, melyben az 1-ek és 0-k felváltva követik egymást, azaz $s=010101\cdots 01$ és $t$ az a sorozat, melynek első tíz eleme 0 , a második tíz pedig 1 . Az alábbiak közül melyik állítás helyes?

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

1. $T[1,10]=15$
2. $T[2,20]=2$
3. $T[100,15]=10$
4. Az előzőek egyike sem igaz.

Melyik az a legkisebb pozitív egész $d$ szám, melyre $f(n)\in O\left(n^{d}\right)$ teljesül, ha $f(n)=\sum _{k=1}^{n^{2}}{\frac {k}{3}}$? (2019 jun)

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

1. 2
2. 3
3. 4
4. 5
5. nincs ilyen d

Ha az alábbi bináris keresőfán végrehajtjuk a BESZÚR(15) műveletet, akkor az eredményül kapott bináris kereső́ára melyik állítás igaz? (2019 jun)

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

1. A 15 a gyökérben lesz.
2. A fa magassága nem változik meg.
3. A 15 egy olyan csúcsba kerül, ami gyereke a 12-es számot tartalmazónak.
4. Az előzőek egyike sem igaz.

Egy 200 csúcsú teljes páros gráfban az egyik oldalon a csúcsok 1-től 100-ig, a másik oldalon 101-től 200-ig vannak megszámozva. Hány olyan teljes párosítás található ebben a gráfban, amelyben minden páros csúcsnak páratlan, minden páratlannak pedig páros a szomszédja? (2019 jun)

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

1. ${\frac {100!}{2}}$
2. ${\frac {100!}{50!}}$
3. $50!+50!$
4. $50!\cdot 50$ !
5. Az előzőek egyike sem helyes.

Egy 6 csúcsú irányítatlan gráfon mélységi bejárást végeztünk. Az alábbi táblázat tartalmazza a csúcsok mélységi és befejezési számait. (2019 jun)

	A	B	C	D	E	F
mélységi	4	3	2	5	1	6
befejezési	4	1	5	2	6	3

Melyik élről állíthatjuk biztosan, hogy nem lehet a gráfban?

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

1. $(B,E)$
2. $(C,A)$
3. $(C,D)$
4. $(F,B)$
5. A felsoroltak bármelyike előfordulhat.

Hat kártya van elöttünk az asztalon, tudjuk, hogy mindegyiknek az egyik oldalán egy betủ, a másik oldalán egy szám van. A következőket látjuk: $A,B,C,1,2,3$. (2019 jun)

Valaki azt állítja, hogy az is igaz, hogy minden mássalhangzó túloldalán páratlan szám szerepel. Ha minél kevesebb kártya megfordításával akarjuk ezt az állítást ellenőrizni, akkor melyik a jó módszer?

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

1. Mind a hat kártyát megfordítjuk.
2. Csak a $B$ kártyát fordítjuk meg.
3. Csak a $B$ és $C$ kártyákat fordítjuk meg.
4. Az elözőek egyike sem helyes.

${\mathcal {A}}:\quad \operatorname {Adott}$ egy $G$ irányítatlan gráf. (2019 jun)

Van-e $G$-ben kör?

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

1. ${\mathcal {A}}$ Benne van P-ben, de nincs benne NP-ben.
2. ${\mathcal {A}}$ Benne van NP-ben, de nincs benne P-ben.
3. ${\mathcal {A}}$ Benne van P-ben is és NP-ben is.
4. ${\mathcal {A}}$ Nincs benne P-ben se és NP-ben se.

${\mathcal {B}}:\quad$ Adott egy $G$ irányítatlan gráf. (2019 jun)

Van-e $G$-ben pontosan 2019 csúcsot tartalmazó kör?

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

1. ${\mathcal {B}}$ Benne van P-ben, de nincs benne NP-ben.
2. ${\mathcal {B}}$ Benne van NP-ben, de nincs benne P-ben.
3. ${\mathcal {B}}$ Benne van P-ben is és NP-ben is.
4. ${\mathcal {B}}$ Nincs benne P-ben se és NP-ben se.

Tegyük fel, hogy $\mathrm {P} \neq$ NP és jelölje $P_{1}\prec P_{2}$ azt, hogy a $P_{1}$ probléma Karp-redukálható (polinomiálisan visszavezethető) a $P_{2}$ problémára. Tekintsük azt a két problémát, melyeknél adott egy $(G,k)$ pár és (2019 jun)

${\mathcal {A}}$ : a $G$ élsúlyozott gráfban van-e legfeljebb $k$ súlyú Hamilton-kör (2019 jun) ==

${\mathcal {B}}$ : a $G$ gráfban van-e legalább $k$ pontú teljes részgráf

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

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

1. ${\mathcal {A}}\prec {\mathcal {B}}$ és ${\mathcal {B}}\prec {\mathcal {A}}$
2. ${\mathcal {A}}\prec {\mathcal {B}}$ és ${\mathcal {B}}\nprec {\mathcal {A}}$
3. ${\mathcal {A}}\nprec {\mathcal {B}}$ és ${\mathcal {B}}\prec {\mathcal {A}}$
4. ${\mathcal {A}}\nprec {\mathcal {B}}$ és ${\mathcal {B}}\nprec {\mathcal {A}}$

Több különböző megbízás közül válogatunk, melyek mindegyikét adott napokon lehet elvégezni. Ha az $i$.ediket elvállaljuk, akkor a $k_{i}$ naptól a $v_{i}$ napig csak ezt csinálhatjuk. Legyen adott $n$ megbízás a hozzájuk tartozó $k_{i}$ és $v_{i}$ dátumokkal. Azt akarjuk eldönteni, hogy elvállalható-e közülük legalább $n/2$ darab (mindegy, hogy melyikek). (2019 jun)

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

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

1. Tetszőleges irányított gráfban legrövidebb utat lehet polinom időben találni, és egy ilyen algoritmussal a feladat egyszerüen megoldható.
2. Tetszőleges irányított gráfban leghosszabb utat lehet polinom időben találni, és egy ilyen algoritmussal a feladat egyszerüen megoldható.
3. Irányított körmentes gráfban legrövidebb utat lehet polinom időben találni, és egy ilyen algoritmussal a feladat egyszerüen megoldható.
4. Irányított körmentes gráfban leghosszabb utat lehet polinom időben találni, és egy ilyen algoritmussal a feladat egyszerüen megoldható.

Melyik feladat oldható meg $O(n)$ lépésben? (2019 jun)

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

1. Tetszőleges $n$ különböző szám növekvő sorrendbe rendezése.
2. Annak ellenőrzése, hogy egy $n$ csúcsú gráf összefüggő-e.
3. Tetszőleges, $n$ elemet tároló bináris keresőfa alapján a tárolt elemek növekvő sorrendben való felsorolása.
4. Tetszőleges $n$ elemből egy bináris keresőfa építése.

Tekintsük a következő, az $a_{1},a_{2},\ldots ,a_{n}$ paraméterektől függő rekurzív definíciót! Az $(n+1)\times 1001$ tömbben (2019 jun)

$T[i,0]=1$ ha $0\leq i\leq n$

$T[0,j]=0$ ha $1\leq j\leq 1001$

$T[i,j]=T[i-1,j]$ ha $i\geq 1$ és $j<a_{i}$

$T[i,j]=\max \left\{T[i-1,j],T\left[i-1,j-a_{i}\right]\right\}$ ha $i\geq 1$ és $j\geq a_{i}$.

Legyen $a_{i}=3^{i-1},i=1,2,\ldots$ Melyik igaz az alábbiak közül?

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

1. $T[2,15]=1$
2. $T[3,9]=0$
3. $T[3,10]=1$
4. $T[20,3]=0$
5. Az előzőek egyike sem igaz.