„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés

(34 közbenső módosítás, amit 5 másik szerkesztő végzett, nincs mutatva)

1. sor:

~~Záróvizsga Kvíz - Algoritmusok~~

{{Kvízoldal

|cím=ZVAlgo|pontozás=-

}}

== 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?

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

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

# <math>f(n) \in O(g(n))</math> , mert mindkét függvényre igaz, hogy <math>O\left(n^3\right)</math>

# <math>f(n) \in O(g(n))</math> , mert <math>f(n) \in O\left(n^2\right)</math> és <math>g(n) \in O\left(n^3\right)</math>

# <math>f(n) \in O(g(n))</math> , de az előző két indoklás egyike sem helyes

# <math>f(n) \notin O(g(n))</math>

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

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

# A 7 a 12 egyik részfájában van.

# A 8 a gyökérben van.

# A 10 a 2 egyik részfájában van.

# A 2 egy levélbe n van.

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

# <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot\left(\begin{array}{l}n \\ 3\end{array}\right)</math>

# <math>(2 n-3) \cdot(2 n-4) \cdot \ldots \cdot(n-2)</math>

# <math>\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)</math>

# <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math>

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

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

# <math>s_{5}=c a c b</math> soha nem előzi meg az <math>s_{1}=a b a c</math> szót.

# Van olyan fázis, amikor <math> s_{3}=b c a c</math> megelőzi az <math>s_{1}=a b a c</math> szót.

# <math>s_{3}=b c a c</math> és <math>s_{4}=b b b b</math> sorrendje pontosan kétszer változik.

# Van olyan fázis, amikor <math>s_{3}=b c a c</math> megelőzi az <math>s_{2}=a c b c</math> szót.

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

[[Fájl:2023 jun info zv algo kruskal.png|keretnélküli]]

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

# Ha <math>x < 3 </math> akkor az <math>E C</math> élet biztosan nem választja be az algoritmus a minimális feszítőfába.

# Az <math>A C</math> élet biztosan beválasztja az algoritmus a minimális feszítőfába, bármi is <math>x</math> értéke.

# Az <math>A C</math> élet biztosan nem választja be az algoritmus a minimális feszítőfába, bármi is <math>x</math> értéke.

# Az algoritmus biztosan beválaszt legalább egy 3 súlyú élet a minimális feszítőfába.

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

# <math>G</math> komplementerében nincsen kör.

# <math>G</math>-ben van kör.

# <math>G</math>-ben nincsen <math>k</math> méretű független ponthalmaz.

# <math>G</math> komplementerében nincsen <math>k</math> -as klikk.

== Egy ország térképe egy élsúlyozott, irányítatlan <math>n</math> csúcsú <math>G</math> 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 <math>k</math> érték esetén azt szeretnénk eldönteni, hogy igaz-e, hogy bármelyik településről van <math>k</math> 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 <math>O\left(n^{2}\right)</math> lépésben?

# 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.

# Minden csúcsból futtatunk egy szélességi bejárást (BFS) a legrövidebb utak megkeresésésére.

# Minden csúcsból lefuttatjuk Dijktsra algoritmusát a legrövidebb utak megkeresésére.

# 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 <math>X_{1}</math> eldöntési feladatban egy irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben pontosan 4 élü kör.

Az <math>X_{2}</math> eldöntési feladatban egy irányítatlan <math>G</math> gráfról és egy pozitív egész <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben pontosan <math>k</math> élü kör.

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

# <math>X_{1} \in P</math> és <math>X_{2} \in N P \backslash P</math>

# <math>X_{1} \in P</math> és <math>X_{2} \in P</math>

# <math>X_{1} \in \operatorname{coN} P</math> de <math>X_{1} \notin P</math>

# <math>X_{1} \in P</math> de <math>X_{1} \notin N P</math>

== Az <math>X</math> eldöntési problémáról azt tudjuk, hogy <math>N P</math> -ben van, az <math>Y</math> eldöntési problémáról pedig azt, hogy <math>N P</math> -teljes. (2023 jun) ==

Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?

# Minden olyan eldöntési probléma, ami Karp-redukálható <math>Y</math> -ra, az Karp-redukálható <math>X</math> -re is.

# <math>Y</math> biztosan Karp-redukálható <math>X</math> -re. <math>{ }^{X}</math>

# Ha <math>X</math> Karp-redukálható <math>Y</math> -ra, akkor <math>X</math> nincsen <math>P</math> -ben.

# Ha <math>Y</math> Karp-redukálható <math>X</math> -re, akkor az <math>X</math> probléma <math>N P</math> -teljes.

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

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

* ha <math>A[1]>0</math> akkor <math>P[1]=A[1]</math> és <math>N[1]=A[1]</math> .

* ha <math>A[1] < 0 </math> akkor <math>P[1]=0</math> és <math>N[1]=A[1]</math>

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

* ha <math>A[i]>0</math> akkor <math>P[i]=P[i-1]+A[i]</math> és <math>N[i]=\max \{N[i-1]+A[i], A[i]\}</math>

* ha <math>A[i] < 0</math> akkor <math>P[i]=0</math> és <math>N[i]=P[i-1]+A[i]</math>

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

# <math>N[i]</math> megadja a legnagyobb összeget, amit valamelyik, legfeljebb egy negatív számot tartalmazó <math>A[j: i]</math> résztömbből ( <math>1 \leq j \leq i)</math> kaphatunk úgy, ha a résztömb minden elemét összeadjuk.

# <math>P[i]</math> megadja a legnagyobb összeget, amit valamelyik <math>A[j: i]</math> résztömbből <math>(1 \leq j \leq i)</math> kaphatunk úgy, ha a résztömb minden elemét összeadjuk.

# <math>N[i]</math> megadja az <math>A[1: i]</math> tömbben szereplö összes negatív szám összegét

# <math>P[i]</math> megadja az <math>A[1: i]</math> 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: <math>AB, AC, AD, CE, DF, EH, FG</math>. (2023 jan) ==

Melyik csúcs lehet szomszédja az <math>F</math> csúcsnak a gráfban?

# A

# B

# C

# E

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

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

# <math>f(n) \in O(g(n)) \text { és } g(n) \in O(h(n))</math>

# <math>f(n) \in O(g(n)) \text { és } g(n) \notin O(h(n))</math>

# <math>f(n) \notin O(g(n)) \text { és } g(n) \in O(h(n))</math>

# <math>f(n) \notin O(g(n)) \text { és } g(n) \notin O(h(n))</math>

== 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) ==

# 2 helyett álljon 4

# 7 helyett álljon 8

# 5 helyett álljon 1

# 10 helyett álljon 1

== Egy <math>k</math> és egy <math>\ell</math> 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) ==

# <math>k \cdot \ell</math>

# <math>k+\ell-1</math>

# <math>\max \{k, \ell\}</math>

# <math>k+\ell x</math>

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

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

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

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

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

# Csak az <math>A, B</math> állítások igazak.

# Csak az <math>A, B, C</math> állítások igazak.

# Mind a négy igaz.

# Csak az <math>A, C</math> á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 <math>0,1,2,3,4,5,6,7,8,9</math> 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 ?

# <math>3 \cdot 26+2 \cdot 10</math>

# <math>26^{3} \cdot 10^{2}</math>

# <math>26^{3}+10^{2}</math>

# <math>3 \cdot 2 \cdot 26 \cdot 10</math>

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

Definiáljuk az <math>A</math> tömböt a következőképpen:

és <math>1 \le j \leq 200</math> esetén <math>A[j]=\max \{A[j-1]+T[j], T[j]\}</math>.

Mennyi <math>A[4]</math> értéke?

# 1

# <math>-1</math>

# <math>-2</math>

# 0

Az előző feladat folytatása:

Mi igaz az alábbiak közül a kitöltött <math>A[1: 200]</math> tömb elemeire?

# <math>A[j]=A[j-1]</math> teljesül legalább 50 esetben

# <math>A[j]=T[j]</math> teljesül legalább 50 esetben

# <math>A[j]>0</math> teljesül legalább 50 esetben <math>\checkmark</math>

# <math>A[200]</math> a legnagyobb érték az <math>A[1: 200]</math> tömbben.

== Egy ország térképe egy élsúlyozott, irányítatlan <math>G</math> 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 <math>A</math> csomópont, ahol éppen tartózkodunk és tudjuk hogy <math>B</math> liter benzinünk van. Melyik tanult algoritmussal lehet meghatározni, hogy az ország mely városaiba tudunk eljutni tankolás nélkül?

# BFS-t, azaz szélességi bejárást kell futtatni az <math>A</math> csúcsból.

# Kruskal algoritmust kell futtatni a gráfon.

# DFS-t, azaz mélységi bejárást kell futtatni az <math>A</math> csúcsból.

# Dijkstra algoritmust kell futtatni az <math>A</math> csúcsból.

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

Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?

# <math>X</math> sem Karp-redukálható <math>Y</math>-ra és <math>Y</math> sem Karp-redukálható <math>X</math>-re.

# <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re.

# <math>X</math> Karp-redukálható <math>Y</math>-ra és <math>Y</math> is Karp-redukálható <math>X</math>-re.

# <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re. <math>X</math>

== Tekintsük azt az eldöntési feladatot, ahol egy irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy hozzá lehet-e adni legfeljebb 5 élet <math>G</math>-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 <math>P \neq N P</math> ?

# A probléma <math>P</math>-ben van, de nincs <math>NP</math>-ben.

# A probléma <math>NP</math>-teljes és nincs <math>P</math>-ben.

# A probléma <math>P</math>-ben van és <math>N P</math>-teljes.

# A probléma <math>P</math>-ben és <math>N P</math>-ben is benne van.

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

Melyik adatszerkezettel valósítható ez meg?

# 2-3 fa

# rendezett lista

# nyílt címzésú hash

# (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) ==

# 2

# 1

# 7

# 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) ==

[[Fájl:2022 jun info zv adatb fagraf.png|keretnélküli]]

# <math>5,9,1,7,3,4</math>

# <math>5,7,4,9,3,1</math>

# <math>5,3,4,9,1,7</math>

# <math>5,4,7,3,9,1</math>

== Tekintsük azt a feladatot, ahol egy <math>n>100</math> csúcsú irányított <math>G</math> 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 <math>P \neq N P</math> ?

# A probléma <math>P</math> -ben van, de nincs <math>N P</math> -ben.

# A probléma <math>N P</math> -teljes és nincs <math>P</math> -ben.

# A probléma <math>P</math> -ben van és <math>N P</math> -teljes.

# A probléma <math>P</math> -ben és <math>N P</math> -ben is benne van.

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

[[Fájl:2022 jun info zv algoritmusok topologikus sorrend.png|keretnélküli]]

# <math>A, B, D, E, F, G, H, C</math>

# <math>A, D, F, G, H, C, E, B</math>

# <math>A, B, C, D, E, F, G, H</math>

# <math>A, D, F, E, B, G, H, C</math>

== Egy <math>n \times n</math> -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 <math>T[i, j](1 \leq i, j \leq n</math> esetén) azt, hogy az <math>i</math> -edik sor <math>j</math> -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 <math>T[1, j]=1</math> minden <math>1 \leq j \leq n</math> esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért <math>T[i, 1]=1</math> minden <math>1 \leq i \leq n</math> esetén.

Melyik rekurziós képlet a helyes a többi <math>T[i, j]</math> érték meghatározására?

# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]</math>

# <math>T[i, j]=\max \{T[i-1, j], T[i, j-1], T[i-1, j-1]\}</math>

# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]+1</math>

# <math>T[i, j]=T[i-1, j-1]+1</math>

Az előző feladat folytatása:

A teljesen kitöltött <math>T</math> 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?

# <math>\max _{1 \le i \le n} T[i, n]</math> adja meg ezt.

# <math>\Sigma_{i=1}^{n} T[i, n]</math> adja meg ezt.

# <math>T[n, n]</math> adja meg ezt.

# <math>\max _{1 \leq j \leq n} T[n, j]</math> adja meg ezt

# <math>\Sigma_{j=1}^{n} T[n, j]</math> adja meg ezt.

== A <math>G</math> 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: <math>G</math> minden minimális feszítőfája tartalmazza a legkisebb súlyú élt.

B: <math>G</math> minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt.

C: <math>G</math> 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?

# Csak az <math>A</math> állítás igaz, a másik kettő nem

# Az <math>A</math> , a <math>B</math> és a <math>C</math> állítás is igaz.

# Csak az <math>A</math> és a <math>B</math> állítás igaz, a <math>C</math> nem.

# Csak az <math>A</math> és a <math>C</math> állítás igaz, a <math>B</math> nem.

== Legyen <math>X</math> a <math>2SZÍN</math> eldöntési probléma, azaz ahol egy egyszerü, irányítatlan <math>G</math> 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 <math>Y</math> eldöntési problémában pedig azt kell eldöntenünk <math>n</math> 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 <math>P \neq N P</math> ?

# <math>X</math> nem Karp-redukálható <math>Y</math> -ra, de <math>Y</math> Karp-redukálható <math>X</math> -re.

# <math>X</math> Karp-redukálható <math>Y</math> -ra és <math>Y</math> is Karp-redukálható <math>X</math> -re.

# <math>X</math> sem Karp-redukálható <math>Y</math> -ra és <math>Y</math> sem Karp-redukálható <math>X</math> -re.

# <math>X</math> Karp-redukálható <math>Y</math> -ra, de <math>Y</math> nem Karp-redukálható <math>X</math> -re.

== Tekintsük azt a <math>K_{20,40}</math> teljes páros gráfot, melynek <math>A=\left\{a_{1}, a_{2}, \ldots, a_{20}\right\}</math> és <math>B=\left\{b_{1}, b_{2}, \ldots, b_{40}\right\}</math> 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 <math>\left(a_{i}, b_{j}\right)</math> élekből áll.) (2022 jun) ==

# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right) \cdot 20</math> !

# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right)</math>

# <math>40^{20}</math>

# <math>40!</math>

== Az <math>1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16</math> 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) ==

# 0

# 64

# <math>\left(\begin{array}{c}16 \\ 2\end{array}\right)</math>

# 32

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

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

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n^{3}</math> .

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n^{3}</math> .

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n</math> .

# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n</math> .

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

# x lehet 1 is és 9 is

11. sor:

314. sor:

# x lehet 1 is és 6 is

# 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) ==

# Az 1 levélben van.

# A fának 7 szintje van.

# A legutoljára beszúrt érték levélben van.

# A középső érték, azaz a 64, a gyökérben van.

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

# <math>H</math> fokszáma lehet 1 vagy 2, és más nem lehet

# <math>H</math> fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet

# <math>H</math> fokszáma lehet 1, 2 vagy 3, és más nem lehet

# <math>H</math> fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet

== Adott egy <math>3n</math> csúcsú teljes gráf, a csúcsok számozottak, az 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) ==

# <math>\frac{n!}{2} * n!</math>

# <math>n! * n! * n!</math>

# <math>2 * n! * n!</math>

# <math>n! * (2n)!</math>

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

# 12

# 7

# 4

# 8

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

# 1 ládarendezést használunk <math>4^5</math> ládával.

# 5 ládarendezést használunk, mindegyik esetben 4 ládával.

# 4 ládarendezést használunk, mindegyik esetben 5 ládával.

# 1 ládarendezést használunk 20 ládával.

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

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

# <math>f(n) \notin O(h(n))</math> és <math>g(n) \in O(h(n))</math>

# <math>f(n) \in O(h(n))</math> és <math>g(n) \notin O(h(n))</math>

# <math>f(n) \in O(h(n))</math> és <math>g(n) \in O(h(n))</math>

# <math>f(n) \notin O(h(n))</math> és <math>g(n) \notin O(h(n))</math>

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

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

# A probléma <math>P</math> -ben és <math>NP</math> -ben is benne van.

# A probléma <math>P</math> -ben van, de nincs <math>NP</math> -ben.

# A probléma <math>NP</math> -teljes és nincs <math>P</math> -ben.

# A probléma <math>P</math> -ben van és <math>NP</math> -teljes.

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

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

# <math>X</math> Karp-redukálható <math>Y</math> -ra, de <math>Y</math> nem Karp-redukálható <math>X</math> -re.

# <math>X</math> nem Karp-redukálható <math>Y</math> -ra, de <math>Y</math> Karp-redukálható <math>X</math> -re.

# <math>X</math> Karp-redukálható <math>Y</math> -ra és <math>Y</math> is Karp-redukálható <math>X</math> -re.

# <math>X</math> sem Karp-redukálható <math>Y</math> -ra és <math>Y</math> sem Karp-redukálható <math>X</math> -re.

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

{| class="wikitable"

|-

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

|-

| 7 || 0 || 0 || 7 || 7 || 8 || 12 || 12 || 12 || 12 || 20 || 20

|}

Mi igaz a következő, <math>i = 8</math> -as sor <math>V[8,b]</math> értékeire az alábbiak közül, ha a 8. tárgy <math>w_8</math> súlya <math>5</math> , <math>v_8</math> értéke pedig <math>6</math> ?

( <math>V[i,b]</math> jelentése: az első <math>i</math> tárgyból <math>b</math> hátizsák kapacitás mellett elérhető maximális érték.)

# <math>V[8,4]=8 \text { és } V[8,9]=17</math>

# <math>V[8,3]=7 \text { és } V[8,8]=13</math>

# <math>V[8,4]=8 \text { és } V[8,8]=12</math>

# <math>V[8,4]=5 \text { és } V[8,8]=12</math>

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

# Előfordulhat, hogy egy bináris keresőfában végrehajtott keresés belső csúcsban (azaz nem levélben) ér véget.

# Bináris keresőfában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.

# 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.

# Piros-fekete fában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.

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

Vannak olyan <math>X \subseteq V</math> és <math>Y \subseteq V</math> nemüres halmazok, melyekre igaz, hogy

* <math>X \cap Y=\emptyset</math>

* <math>X \cup Y=V</math>

* bármely <math>\{u, v\} \in E</math> él esetén az <math>\{u, v\} \cap X</math> halmaz egy elemú.

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

# Nincsen egyetlen éle sem a gráfnak.

# A gráf páros gráf, de nem feltétlenül teljes páros gráf

# A gráf teljes páros gráf

# A gráf teljes gráf.

# 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) ==

[[Fájl:2021 jan info zv algo keresofa.png|keretnélküli]]

Melyik álítás igaz?

# A 3 előbb jön, mint a 27 mindkét sorrendben.

# A 15 megelőzi a 4-et a preorder sorrendben, mert a 15 belső csúcsban van, a 4 pedig levélben.

# A 27 megelőzi a 9-et a posztorder sorrendben, mert a 27 levélben van, a 9 pedig belső csúcsban.

# A számok növekvő sorrendben vannak a két sorrend egyike szerint.

# 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) <math>100 \cdot \frac{n(n-1)}{n-2} \cdot \log _{2} n+17 n-32</math>

(b) <math>2 \cdot n^{2} \cdot \sqrt{n}+44 n^{2}+13</math>

(c) <math>\frac{1}{10^{10}} \cdot \frac{4^{n}}{2^{n}}</math>

(d) <math>4 n^{2}+37 n-12</math>

# Az (a) függvény <math>O\left(2^{n}\right)</math>, a (b) függvény <math>O\left(n^{2}\right)</math>

# <math>\mathrm{Az}</math> (a) és a (d) függvény is <math>O\left(n^{2}\right)</math>

# <math>\mathrm{Az}</math> (b) függvény <math>O\left(n^{n}\right)</math>, a (c) függvény <math>O\left(n^{2}\right)</math>

# A négy függvény közül csak a (d) függvény <math>O\left(n^{2}\right)</math>

# A (b), a (c) és a (d) függvény is <math>O\left(n^{2}\right)</math>

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

# <math>n</math>

# <math>2^{\lfloor n / 2\rfloor}</math>

# <math>2^{n-1}</math>

# <math>2^{n}</math>

# Más a formula attól függően, hogy <math>n</math> páros vagy páratlan.

== Egy város úthálózatát a <math>G</math> 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 <math>v</math> 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 <math>v</math>-ből az összes többi csúcsba.

B: A Bellman-Ford-algoritmussal határozzák meg a legrövidebb utakat <math>v</math>-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?

# Csak az A módszer.

# Csak a B módszer.

# Csak a C módszer

# Csak az A és a B módszer.

# Mindhárom módszer

== Tudjuk, hogy az <math>\mathcal{A}</math> probléma <math>N P</math>-teljes, a <math>\mathcal{B}</math> probléma pedig <math>N P</math>-beli, de nem feltétlenül <math>N P</math>-teljes. (2021 jan) ==

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

A: Ha az <math>\mathcal{A}</math> problémára van polinom idejü algoritmus, akkor <math>P=N P</math>.

B: Ha a <math>\mathcal{B}</math> problémára van polinom idejú algoritmus, akkor <math>P=N P</math>.

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

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

# Csak az A és a C igaz.

# Csak az A igaz.

# Az A, B, C mindegyike igaz.

# Csak a B igaz.

# Csak az A és a B igaz.

== Adott egy <math>n</math> hosszú számsorozat, <math>a_{1}, a_{2}, \ldots, a_{n}</math>. (2021 jan) ==

Definiáljuk a <math>T</math> és <math>S</math> tömböt a következőképpen:

és <math>1 \le i \leq n</math> esetén:

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

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

# <math>T[10]=10</math>

# <math>T[4]=4</math>

# <math>S[10]=9</math>

# <math>S[3 n]=3 n</math>

# <math>T[36]=37</math>

== Adott <math>n</math> tárgy, tudjuk, hogy az <math>i</math>-ediknek a súlya <math>s_{i}</math> kilogramm, az értéke <math>v_{i}</math> forint, az <math>s_{i}, v_{i}</math> 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 <math>P \neq N P</math>?

# A probléma <math>P</math>-ben és <math>N P</math>-ben is benne van.

# A probléma <math>P</math>-ben van és <math>N P</math>-teljes.

# A probléma <math>N P</math>-teljes és nincs <math>P</math>-ben.

# A probléma <math>P</math>-ben van, de nincs <math>N P</math>-ben.

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

Legközelebbi pár: Adott <math>n</math> 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 <math>n</math> 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 <math>O(n \log n)</math> lépésben.

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

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

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

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

# Csak az A.

# Mind a négy igaz.

# Csak az A, a B és a D.

# Csak a B és a D.

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

# <math>f(n)=3 \cdot 2^{(\log n)^{2}}+85 n^{2}</math>

# <math>f(n)=10 \cdot n \log n+12 n^{1,5}-8</math>

# <math>f(n)=3 n \log (n !)</math>

# <math>f(n)=20 \cdot \frac{n^{3}}{\log n}-15 n^{2}</math>

# Egyik sem lehet.

== A kezdetben üres, <math>M=17</math> méretü <math>A</math> hash-táblába a <math>h(x) \equiv x(\bmod 17)</math> 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?

# <math>A[8]</math>-ban

# <math>A[6]</math>-ban

# <math>A[9]</math>-ben

# Nem határozható meg.

# 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) ==

# <math>26 \cdot 25 \cdot 24 \cdot 23 \cdot 10 \cdot 9 \cdot 8 \cdot 7</math>

# <math>2 \cdot\left[\left(\begin{array}{c}26 \\ 4\end{array}\right)+\left(\begin{array}{c}10 \\ 4\end{array}\right)\right]</math>

# <math>2 \cdot 26^{4} \cdot 10^{4}</math>

# <math>26 \cdot 25 \cdot 24 \cdot 23+10 \cdot 9 \cdot 8 \cdot 7</math>

# 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ő: <math>E C, D B, D E</math> A felsorolt lehetőségek közül melyik lehet igaz az ismeretlen élsúlyokra? (2020 jan) ==

[[Fájl:2020 jan info zv kruskal.png|keretnélküli]]

# <math>x=1, y=5</math>

# <math>x=5, y=1</math>

# <math>x=y</math>

# A fentiek egyike sem lehetséges.

== A <math>G=(V, E)</math> egyszerủ, irányítatlan gráf csúcsain adott egy <math>f: V \rightarrow\{0,1,2\}</math> 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) ==

# Minden <math>a, b \in V</math> párra, ha <math>a \neq b</math>, akkor <math>f(a) \neq f(b)</math>

# Minden <math>a, b \in V</math> párra, ha <math>\{a, b\} \in E</math>, akkor <math>f(a) \neq f(b)</math>

# Minden <math>a, b \in V</math> párra, ha <math>f(a) \neq f(b)</math>, akkor <math>\{a, b\} \in E</math>

# Minden <math>a, b \in V</math> párra, ha <math>\{a, b\} \notin E</math>, akkor <math>f(a)=f(b)</math>

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

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

# A probléma P-ben és NP-ben is benne van.

# A probléma P-ben van, de nincs NP-ben.

# A probléma P-ben van és NP-teljes.

# A probléma NP-teljes és nincs P-ben.

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

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

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

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

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

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

# <math>\mathcal{C} \prec \mathcal{A}</math> és <math>\mathcal{C} \prec \mathcal{B}</math>

# <math>\mathcal{A} \prec \mathcal{C}</math> és <math>\mathcal{A} \prec \mathcal{B}</math>

# <math>\mathcal{B} \prec \mathcal{C}</math> és <math>\mathcal{C} \prec \mathcal{A}</math>

# <math>\mathcal{A} \prec \mathcal{B}</math> és <math>\mathcal{B} \prec \mathcal{C}</math>

== Legyen adott egy <math>G</math> gráf, melynek adott két különböző csúcsa <math>A</math> és <math>B</math> 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 <math>A</math>-ból <math>B</math>-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?

# Irányított gráf esetében a Dijkstra-algoritmus segítségével a feladat megoldható, de szélességi kereséssel nem.

# Irányított gráf esetében a Dijkstra-algoritmus segítségével és szélességi kereséssel is megoldható a feladat.

# 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.

# 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 <math>O\left(n^{2}\right)</math> lépésben müködő algoritmus? (2020 jan) ==

# Adott <math>n</math> különböző egész szám közül a legkisebb kiválasztása.

# Adott <math>n</math> csúcsú bináris keresőfában tárolt elemek közül a legnagyobb meghatározása.

# Adott <math>n</math> bites <math>k</math> egész számra <math>5^{k}</math> kiszámolása.

# Adott <math>n</math> csúcsú, irányított, körmentes gráfban az adott <math>s</math> csúcsból az adott <math>t</math> csúcsba vezető legkevesebb élü út meghatározása.

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

<math>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}</math>

Legyen <math>n=100, m=20</math>, az <math>s</math> az a 0 -val kezdődő sorozat, melyben az 1-ek és 0-k felváltva követik egymást, azaz <math>s=010101 \cdots 01</math> és <math>t</math> 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?

# <math>T[1,10]=15</math>

# <math>T[2,20]=2</math>

# <math>T[100,15]=10</math>

# Az előzőek egyike sem igaz.

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

# 2

# 3

# 4

# 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) ==

[[Fájl:2019 jun info zv algo graf.jpg|keretnélküli]]

# A 15 a gyökérben lesz.

# A fa magassága nem változik meg.

# A 15 egy olyan csúcsba kerül, ami gyereke a 12-es számot tartalmazónak.

# 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) ==

# <math>\frac{100 !}{2}</math>

# <math>\frac{100 !}{50 !}</math>

# <math>50 !+50 !</math>

# <math>50 ! \cdot 50</math> !

# 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?

# <math>(B, E)</math>

# <math>(C, A)</math>

# <math>(C, D)</math>

# <math>(F, B)</math>

# 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: <math>A, B, C, 1,2,3</math>. (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?

# Mind a hat kártyát megfordítjuk.

# Csak a <math>B</math> kártyát fordítjuk meg.

# Csak a <math>B</math> és <math>C</math> kártyákat fordítjuk meg.

# Az elözőek egyike sem helyes.

== <math>\mathcal{A}: \quad \operatorname{Adott}</math> egy <math>G</math> irányítatlan gráf. (2019 jun) ==

Van-e <math>G</math>-ben kör?

# <math>\mathcal{A}</math> Benne van P-ben, de nincs benne NP-ben.

# <math>\mathcal{A}</math> Benne van NP-ben, de nincs benne P-ben.

# <math>\mathcal{A}</math> Benne van P-ben is és NP-ben is.

# <math>\mathcal{A}</math> Nincs benne P-ben se és NP-ben se.

== <math>\mathcal{B}: \quad</math> Adott egy <math>G</math> irányítatlan gráf. (2019 jun) ==

Van-e <math>G</math>-ben pontosan 2019 csúcsot tartalmazó kör?

# <math>\mathcal{B}</math> Benne van P-ben, de nincs benne NP-ben.

# <math>\mathcal{B}</math> Benne van NP-ben, de nincs benne P-ben.

# <math>\mathcal{B}</math> Benne van P-ben is és NP-ben is.

# <math>\mathcal{B}</math> Nincs benne P-ben se és NP-ben se.

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

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

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

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

# <math>\mathcal{A} \prec \mathcal{B}</math> és <math>\mathcal{B} \prec \mathcal{A}</math>

# <math>\mathcal{A} \prec \mathcal{B}</math> és <math>\mathcal{B} \nprec \mathcal{A}</math>

# <math>\mathcal{A} \nprec \mathcal{B}</math> és <math>\mathcal{B} \prec \mathcal{A}</math>

# <math>\mathcal{A} \nprec \mathcal{B}</math> és <math>\mathcal{B} \nprec \mathcal{A}</math>

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

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

# 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ó.

# Tetszőleges irányított gráfban leghosszabb utat lehet polinom időben találni, és egy ilyen algoritmussal a feladat egyszerüen megoldható.

# 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ó.

# 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 <math>O(n)</math> lépésben? (2019 jun) ==

# Tetszőleges <math>n</math> különböző szám növekvő sorrendbe rendezése.

# Annak ellenőrzése, hogy egy <math>n</math> csúcsú gráf összefüggő-e.

# Tetszőleges, <math>n</math> elemet tároló bináris keresőfa alapján a tárolt elemek növekvő sorrendben való felsorolása.

# Tetszőleges <math>n</math> elemből egy bináris keresőfa építése.

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

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

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

# <math>T[2,15]=1</math>

# <math>T[3,9]=0</math>

# <math>T[3,10]=1</math>

# <math>T[20,3]=0</math>

# Az előzőek egyike sem igaz.

@@ 1. sor: / 1. sor: @@
-Záróvizsga Kvíz - Algoritmusok
 {{Kvízoldal
 |cím=ZVAlgo|pontozás=-
 }}
-== 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?
+== Tekintsük az alábbi két függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jun) ==
+<math>f(n)=2023 \cdot n^2 \cdot \log n-100 \cdot \sqrt{n}</math>
+<math>g(n)=\frac{1}{10^{10}} \cdot n^3+82 \cdot n \cdot \log n</math>
+Az alábbiak közül melyik állítás igaz?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>f(n) \in O(g(n))</math> , mert mindkét függvényre igaz, hogy <math>O\left(n^3\right)</math>
+# <math>f(n) \in O(g(n))</math> , mert <math>f(n) \in O\left(n^2\right)</math> és <math>g(n) \in O\left(n^3\right)</math>
+# <math>f(n) \in O(g(n))</math> , de az előző két indoklás egyike sem helyes
+# <math>f(n) \notin O(g(n))</math>
+== Egy bináris keresőfa preorder bejárása a csúcsokat <math>5, 2, 4, 12, 8, 7, 10, 20</math> sorrendben látogatja meg. (2023 jun) ==
+Melyik igaz az alábbi állítások közül a keresőfára?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# A 7 a 12 egyik részfájában van.
+# A 8 a gyökérben van.
+# A 10 a 2 egyik részfájában van.
+# A 2 egy levélbe n van.
+== <math>2n</math> darab különböző csokiból hányféleképpen tudunk kiválasztani <math>n</math> darabot úgy, hogy a három kedvenc csokink a kiválasztottak között legyen? (2023 jun) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot\left(\begin{array}{l}n \\ 3\end{array}\right)</math>
+# <math>(2 n-3) \cdot(2 n-4) \cdot \ldots \cdot(n-2)</math>
+# <math>\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)</math>
+# <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math>
+== Radix rendezéssel rendezzük az alábbi sorozatot: <math>s_{1}=a b a c, s_{2}=a c b c, s_{3}=b c a c, s_{4}=b b b b, s_{5}=c a c b</math> (a karakterek mindegyik pozícióban a 3-elemű <math>\{a, b, c\}</math> ábécéből kerülnek ki). (2023 jun) ==
+Melyik állítás igaz a rendezés folyamatára?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# <math>s_{5}=c a c b</math> soha nem előzi meg az <math>s_{1}=a b a c</math> szót.
+# Van olyan fázis, amikor <math> s_{3}=b c a c</math> megelőzi az <math>s_{1}=a b a c</math> szót.
+# <math>s_{3}=b c a c</math> és <math>s_{4}=b b b b</math> sorrendje pontosan kétszer változik.
+# Van olyan fázis, amikor <math>s_{3}=b c a c</math> megelőzi az <math>s_{2}=a c b c</math> szót.
+== Kruskal algoritmusát futtatjuk az alábbi gráfon. (2023 jun) ==
+[[Fájl:2023 jun info zv algo kruskal.png|keretnélküli]]
+Melyik állítás igaz az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# Ha <math>x < 3 </math> akkor az <math>E C</math> élet biztosan nem választja be az algoritmus a minimális feszítőfába.
+# Az <math>A C</math> élet biztosan beválasztja az algoritmus a minimális feszítőfába, bármi is <math>x</math> értéke.
+# Az <math>A C</math> élet biztosan nem választja be az algoritmus a minimális feszítőfába, bármi is <math>x</math> értéke.
+# Az algoritmus biztosan beválaszt legalább egy 3 súlyú élet a minimális feszítőfába.
+== Az <math>n</math> csúcsú <math>G=(V, E)</math> irányítatlan gráfra igaz, hogy bárhogyan is sorolunk fel <math>\left(v_{1}, v_{2}, \ldots, v_{k}\right)</math> csupa különböző <math>G</math> -beli csúcsokat, ahol <math>3 \leq k \leq n</math> a <math>\left\{v_{1}, v_{2}\right\},\left\{v_{2}, v_{3}\right\}, \ldots,\left\{v_{k-1}, v_{k}\right\}</math> és <math>\left\{v_{k}, v_{1}\right\}</math> párok közül legalább az egyik benne van <math>G</math> élhalmazában. Melyik állítás igaz az alábbiak közül? (2023 jun) ==
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>G</math> komplementerében nincsen kör.
+# <math>G</math>-ben van kör.
+# <math>G</math>-ben nincsen <math>k</math> méretű független ponthalmaz.
+# <math>G</math> komplementerében nincsen <math>k</math> -as klikk.
+== Egy ország térképe egy élsúlyozott, irányítatlan <math>n</math> csúcsú <math>G</math> 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 <math>k</math> érték esetén azt szeretnénk eldönteni, hogy igaz-e, hogy bármelyik településről van <math>k</math> 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 <math>O\left(n^{2}\right)</math> lépésben?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 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.
+# Minden csúcsból futtatunk egy szélességi bejárást (BFS) a legrövidebb utak megkeresésésére.
+# Minden csúcsból lefuttatjuk Dijktsra algoritmusát a legrövidebb utak megkeresésére.
+# 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 <math>X_{1}</math> eldöntési feladatban egy irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben pontosan 4 élü kör.
+Az <math>X_{2}</math> eldöntési feladatban egy irányítatlan <math>G</math> gráfról és egy pozitív egész <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben pontosan <math>k</math> élü kör.
+Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>X_{1} \in P</math> és <math>X_{2} \in N P \backslash P</math>
+# <math>X_{1} \in P</math> és <math>X_{2} \in P</math>
+# <math>X_{1} \in \operatorname{coN} P</math> de <math>X_{1} \notin P</math>
+# <math>X_{1} \in P</math> de <math>X_{1} \notin N P</math>
+== Az <math>X</math> eldöntési problémáról azt tudjuk, hogy <math>N P</math> -ben van, az <math>Y</math> eldöntési problémáról pedig azt, hogy <math>N P</math> -teljes. (2023 jun) ==
+Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# Minden olyan eldöntési probléma, ami Karp-redukálható <math>Y</math> -ra, az Karp-redukálható <math>X</math> -re is.
+# <math>Y</math> biztosan Karp-redukálható <math>X</math> -re. <math>{ }^{X}</math>
+# Ha <math>X</math> Karp-redukálható <math>Y</math> -ra, akkor <math>X</math> nincsen <math>P</math> -ben.
+# Ha <math>Y</math> Karp-redukálható <math>X</math> -re, akkor az <math>X</math> probléma <math>N P</math> -teljes.
+== Adott egy egész számokat tartalmazó <math>A[1: n]</math> tömb, melyben nem szerepel 0. (2023 jun) ==
+Az <math>A[1: n]</math> tömb alapján egy <math>P[1: n]</math> és egy <math>N[1: n]</math> tömböt töltünk ki a következőképpen:
+* ha <math>A[1]>0</math> akkor <math>P[1]=A[1]</math> és <math>N[1]=A[1]</math> .
+* ha <math>A[1] < 0 </math> akkor <math>P[1]=0</math> és <math>N[1]=A[1]</math>
+A további értékeket <math>(i>2)</math> így számoljuk:
+* ha <math>A[i]>0</math> akkor <math>P[i]=P[i-1]+A[i]</math> és <math>N[i]=\max \{N[i-1]+A[i], A[i]\}</math>
+* ha <math>A[i] < 0</math> akkor <math>P[i]=0</math> és <math>N[i]=P[i-1]+A[i]</math>
+Melyik állítás igaz az alábbiak közül a kiszámolt <math>P[i]</math> és <math>N[i]</math> értékek jelentésére?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>N[i]</math> megadja a legnagyobb összeget, amit valamelyik, legfeljebb egy negatív számot tartalmazó <math>A[j: i]</math> résztömbből ( <math>1 \leq j \leq i)</math> kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
+# <math>P[i]</math> megadja a legnagyobb összeget, amit valamelyik <math>A[j: i]</math> résztömbből <math>(1 \leq j \leq i)</math> kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
+# <math>N[i]</math> megadja az <math>A[1: i]</math> tömbben szereplö összes negatív szám összegét
+# <math>P[i]</math> megadja az <math>A[1: i]</math> 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: <math>AB, AC, AD, CE, DF, EH, FG</math>. (2023 jan) ==
+Melyik csúcs lehet szomszédja az <math>F</math> csúcsnak a gráfban?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# A
+# B
+# C
+# E
+== Tekintsük az alábbi három függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jan) ==
+<math>f(n)=n !+10 \cdot n^{2}-3</math>
+<math>g(n)=\frac{1}{8} n^{n}+9 \cdot \log n</math>
+<math>h(n)=10^{1000} \cdot n^{1000}+37 \cdot n^{3}+42</math>
+Az alábbiak közül melyik állitás igaz ezen három függvény nagyságrendjére?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>f(n) \in O(g(n)) \text { és } g(n) \in O(h(n))</math>
+# <math>f(n) \in O(g(n)) \text { és } g(n) \notin O(h(n))</math>
+# <math>f(n) \notin O(g(n)) \text { és } g(n) \in O(h(n))</math>
+# <math>f(n) \notin O(g(n)) \text { és } g(n) \notin O(h(n))</math>
+== 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) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# 2 helyett álljon 4
+# 7 helyett álljon 8
+# 5 helyett álljon 1
+# 10 helyett álljon 1
+== Egy <math>k</math> és egy <math>\ell</math> 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) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>k \cdot \ell</math>
+# <math>k+\ell-1</math>
+# <math>\max \{k, \ell\}</math>
+# <math>k+\ell x</math>
+== Egy csupa különböző egész számot tartalmazó <math>T</math> tömbben akarjuk eldönteni egy adott <math>x</math> elemről, hogy igaz-e, hogy <math>x</math> és <math>2 \cdot x</math> is szerepel <math>T</math>-ben. Az alábbi négy állítás közül melyek igazak? (2023 jan) ==
+A: Ez megtehető <math>O(n)</math> lépésben, ha a tömb rendezett.
+B: Ez megtehető <math>O(\log n)</math> lépésben, ha a tömb rendezett.
+C: Ez megtehető <math>O(n)</math> lépésben tetszőleges tömb esetén.
+D: Ez megtehető <math>O(\log n)</math> lépésben tetszőleges tömb esetén.
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Csak az <math>A, B</math> állítások igazak.
+# Csak az <math>A, B, C</math> állítások igazak.
+# Mind a négy igaz.
+# Csak az <math>A, C</math> á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 <math>0,1,2,3,4,5,6,7,8,9</math> 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 ?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>3 \cdot 26+2 \cdot 10</math>
+# <math>26^{3} \cdot 10^{2}</math>
+# <math>26^{3}+10^{2}</math>
+# <math>3 \cdot 2 \cdot 26 \cdot 10</math>
+== Adott egy 200 elemű <math>T[1: 200]</math> tömb, amiben <math>T[3 i]=i</math> minden <math>1 \leq i \leq 66</math> esetén, minden egyéb esetben (azaz amikor az index nem többszöröse a 3-nak) pedig <math>T[j]=-1</math>. (2023 jan) ==
+Definiáljuk az <math>A</math> tömböt a következőképpen:
+<math>A[1]=T[1]</math>
+és <math>1 \le j \leq 200</math> esetén <math>A[j]=\max \{A[j-1]+T[j], T[j]\}</math>.
+Mennyi <math>A[4]</math> értéke?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 1
+# <math>-1</math>
+# <math>-2</math>
+# 0
+Az előző feladat folytatása:
+Mi igaz az alábbiak közül a kitöltött <math>A[1: 200]</math> tömb elemeire?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>A[j]=A[j-1]</math> teljesül legalább 50 esetben
+# <math>A[j]=T[j]</math> teljesül legalább 50 esetben
+# <math>A[j]>0</math> teljesül legalább 50 esetben <math>\checkmark</math>
+# <math>A[200]</math> a legnagyobb érték az <math>A[1: 200]</math> tömbben.
+== Egy ország térképe egy élsúlyozott, irányítatlan <math>G</math> 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 <math>A</math> csomópont, ahol éppen tartózkodunk és tudjuk hogy <math>B</math> liter benzinünk van. Melyik tanult algoritmussal lehet meghatározni, hogy az ország mely városaiba tudunk eljutni tankolás nélkül?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# BFS-t, azaz szélességi bejárást kell futtatni az <math>A</math> csúcsból.
+# Kruskal algoritmust kell futtatni a gráfon.
+# DFS-t, azaz mélységi bejárást kell futtatni az <math>A</math> csúcsból.
+# Dijkstra algoritmust kell futtatni az <math>A</math> csúcsból.
+== Legyen <math>X</math> az az eldöntési probléma, melynek inputja egy irányított <math>G</math> gráfból, ezen gráf egy <math>s</math> csúcsából és egy <math>k</math> pozitív egészből áll és azt szeretnénk eldönteni, hogy igaz-e hogy <math>G</math>-ben <math>s</math>-ből minden más csúcsba vezet legfeljebb <math>k</math> élből álló út. Legyen továbbá <math>Y</math> a tanult <math>3-S Z</math> IíN eldöntési feladat. (2023 jan) ==
+Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>X</math> sem Karp-redukálható <math>Y</math>-ra és <math>Y</math> sem Karp-redukálható <math>X</math>-re.
+# <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re.
+# <math>X</math> Karp-redukálható <math>Y</math>-ra és <math>Y</math> is Karp-redukálható <math>X</math>-re.
+# <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re. <math>X</math>
+== Tekintsük azt az eldöntési feladatot, ahol egy irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy hozzá lehet-e adni legfeljebb 5 élet <math>G</math>-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 <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# A probléma <math>P</math>-ben van, de nincs <math>NP</math>-ben.
+# A probléma <math>NP</math>-teljes és nincs <math>P</math>-ben.
+# A probléma <math>P</math>-ben van és <math>N P</math>-teljes.
+# A probléma <math>P</math>-ben és <math>N P</math>-ben is benne van.
+== Pozitív egész számokat szeretnénk tárolni valami adatszerkezet segítségével úgy, hogy <math>n</math> tárolt elem esetén tetszőleges <math>x</math> egész számról <math>O(\log n)</math> lépésben meg tudjuk mondani, hogy igaz-e rá, hogy <math>x</math> a tárolt számok között van, de sem <math>x-1</math> , sem <math>x+1</math> nincsen. (2022 jun) ==
+Melyik adatszerkezettel valósítható ez meg?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# 2-3 fa
+# rendezett lista
+# nyílt címzésú hash
+# (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) ==
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 2
+# 1
+# 7
+# 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) ==
+[[Fájl:2022 jun info zv adatb fagraf.png|keretnélküli]]
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>5,9,1,7,3,4</math>
+# <math>5,7,4,9,3,1</math>
+# <math>5,3,4,9,1,7</math>
+# <math>5,4,7,3,9,1</math>
+== Tekintsük azt a feladatot, ahol egy <math>n>100</math> csúcsú irányított <math>G</math> 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 <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# A probléma <math>P</math> -ben van, de nincs <math>N P</math> -ben.
+# A probléma <math>N P</math> -teljes és nincs <math>P</math> -ben.
+# A probléma <math>P</math> -ben van és <math>N P</math> -teljes.
+# A probléma <math>P</math> -ben és <math>N P</math> -ben is benne van.
+== A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun) ==
+[[Fájl:2022 jun info zv algoritmusok topologikus sorrend.png|keretnélküli]]
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>A, B, D, E, F, G, H, C</math>
+# <math>A, D, F, G, H, C, E, B</math>
+# <math>A, B, C, D, E, F, G, H</math>
+# <math>A, D, F, E, B, G, H, C</math>
+== Egy <math>n \times n</math> -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 <math>T[i, j](1 \leq i, j \leq n</math> esetén) azt, hogy az <math>i</math> -edik sor <math>j</math> -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 <math>T[1, j]=1</math> minden <math>1 \leq j \leq n</math> esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért <math>T[i, 1]=1</math> minden <math>1 \leq i \leq n</math> esetén.
+Melyik rekurziós képlet a helyes a többi <math>T[i, j]</math> érték meghatározására?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]</math>
+# <math>T[i, j]=\max \{T[i-1, j], T[i, j-1], T[i-1, j-1]\}</math>
+# <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]+1</math>
+# <math>T[i, j]=T[i-1, j-1]+1</math>
+Az előző feladat folytatása:
+A teljesen kitöltött <math>T</math> 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?
+{{Kvízkérdés|típus=egy|válasz=5}}
+# <math>\max _{1 \le i \le n} T[i, n]</math> adja meg ezt.
+# <math>\Sigma_{i=1}^{n} T[i, n]</math> adja meg ezt.
+# <math>T[n, n]</math> adja meg ezt.
+# <math>\max _{1 \leq j \leq n} T[n, j]</math> adja meg ezt
+# <math>\Sigma_{j=1}^{n} T[n, j]</math> adja meg ezt.
+== A <math>G</math> 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: <math>G</math> minden minimális feszítőfája tartalmazza a legkisebb súlyú élt.
+B: <math>G</math> minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt.
+C: <math>G</math> 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?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# Csak az <math>A</math> állítás igaz, a másik kettő nem
+# Az <math>A</math> , a <math>B</math> és a <math>C</math> állítás is igaz.
+# Csak az <math>A</math> és a <math>B</math> állítás igaz, a <math>C</math> nem.
+# Csak az <math>A</math> és a <math>C</math> állítás igaz, a <math>B</math> nem.
+== Legyen <math>X</math> a <math>2SZÍN</math> eldöntési probléma, azaz ahol egy egyszerü, irányítatlan <math>G</math> 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 <math>Y</math> eldöntési problémában pedig azt kell eldöntenünk <math>n</math> 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 <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# <math>X</math> nem Karp-redukálható <math>Y</math> -ra, de <math>Y</math> Karp-redukálható <math>X</math> -re.
+# <math>X</math> Karp-redukálható <math>Y</math> -ra és <math>Y</math> is Karp-redukálható <math>X</math> -re.
+# <math>X</math> sem Karp-redukálható <math>Y</math> -ra és <math>Y</math> sem Karp-redukálható <math>X</math> -re.
+# <math>X</math> Karp-redukálható <math>Y</math> -ra, de <math>Y</math> nem Karp-redukálható <math>X</math> -re.
+== Tekintsük azt a <math>K_{20,40}</math> teljes páros gráfot, melynek <math>A=\left\{a_{1}, a_{2}, \ldots, a_{20}\right\}</math> és <math>B=\left\{b_{1}, b_{2}, \ldots, b_{40}\right\}</math> 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 <math>\left(a_{i}, b_{j}\right)</math> élekből áll.) (2022 jun) ==
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right) \cdot 20</math> !
+# <math>\left(\begin{array}{l}40 \\ 20\end{array}\right)</math>
+# <math>40^{20}</math>
+# <math>40!</math>
+== Az <math>1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16</math> 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) ==
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 0
+# 64
+# <math>\left(\begin{array}{c}16 \\ 2\end{array}\right)</math>
+# 32
+== Az <math>\mathcal{A}</math> algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, <math>n</math> -nek a függvényében <math>O\left(n^{2}\right)</math> . (2022 jun) ==
+Melyik nem igaz az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n^{3}</math> .
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n^{3}</math> .
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n</math> .
+# Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n</math> .
+== Egy csupa különböző egész számot tartalmazó bináris keresőfában egy keresés során az alábbi értékeket látjuk (x értéke nem ismert): <math>10, 5, x, 7, 8</math> . Az alábbiak közül mi igaz x értékére? (2022 jan) ==
 {{Kvízkérdés|típus=egy|válasz=2}}
 # x lehet 1 is és 9 is
@@ 11. sor: / 314. sor: @@
 # x lehet 1 is és 6 is
 # 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) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# Az 1 levélben van.
+# A fának 7 szintje van.
+# A legutoljára beszúrt érték levélben van.
+# A középső érték, azaz a 64, a gyökérben van.
+== Egy irányítatlan nyolc csúcsú gráfon DFS-t (mélységi bejárást) futtatunk úgy, hogy ha döntési helyzetben vagyunk, akkor az ábécé szerinti sorrend szerint haladunk. A DFS fába az alábbi élek kerülnek be ebben a sorrendben: <math>AB, BD, AF, FE, EC, FG, GH</math> . Mi igaz a csúcs fokszámára az alábbiak közül? (2022 jan) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>H</math> fokszáma lehet 1 vagy 2, és más nem lehet
+# <math>H</math> fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet
+# <math>H</math> fokszáma lehet 1, 2 vagy 3, és más nem lehet
+# <math>H</math> fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet
+== Adott egy <math>3n</math> csúcsú teljes gráf, a csúcsok számozottak, az 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) ==
+{{Kvízkérdés|típus=egy|válasz=4}}
+# <math>\frac{n!}{2} * n!</math>
+# <math>n! * n! * n!</math>
+# <math>2 * n! * n!</math>
+# <math>n! * (2n)!</math>
+== A <math>4, 3, 2, 1, 5, 6, 7, 8</math> tömböt rendezzük öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jan) ==
+{{Kvízkérdés|típus=egy|válasz=1}}
+# 12
+# 7
+# 4
+# 8
+== Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű <math>\{a,b,c,d\}</math> ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan) ==
+{{Kvízkérdés|típus=egy|válasz=2}}
+# 1 ládarendezést használunk <math>4^5</math> ládával.
+# 5 ládarendezést használunk, mindegyik esetben 4 ládával.
+# 4 ládarendezést használunk, mindegyik esetben 5 ládával.
+# 1 ládarendezést használunk 20 ládával.
+== Tekintsük az alábbi három függvényt (itt a <math>log</math> függvény mindig kettes alapú logaritmust jelöl): (2022 jan) ==
+<math>f(n)=2022 \cdot n^2 \cdot \log n+7 \cdot \sqrt{n}</math>
+<math>g(n)=\log n+1000+n \cdot(\log n)^2</math>
+<math>h(n)=n \cdot \sqrt{n}+\frac{1}{1000} \cdot n^2-8</math>
+Az alábbiak közül melyik állítás igaz ezen három függvény nagyságrendjére?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>f(n) \notin O(h(n))</math> és <math>g(n) \in O(h(n))</math>
+# <math>f(n) \in O(h(n))</math>  és <math>g(n) \notin O(h(n))</math>
+# <math>f(n) \in O(h(n))</math> és <math>g(n) \in O(h(n))</math>
+# <math>f(n) \notin O(h(n))</math>  és <math>g(n) \notin O(h(n))</math>
+== Tekintsük azt az eldöntési feladatot, ahol egy irányított <math>G</math> gráfról azt szeretnénk eldönteni, hogy van-e két olyan <math>s</math> és <math>t</math> csúcsa, hogy <math>s</math> -ből van irányított út <math>t</math> -be, de <math>t</math> -ből nincsen irányított út <math>s</math> -be (2022 jan) ==
+Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy <math>P \neq NP</math> ?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# A probléma <math>P</math> -ben és <math>NP</math> -ben is benne van.
+# A probléma <math>P</math> -ben van, de nincs <math>NP</math> -ben.
+# A probléma <math>NP</math> -teljes és nincs <math>P</math> -ben.
+# A probléma <math>P</math> -ben van és <math>NP</math> -teljes.
+== Legyen <math>X</math> az az eldöntési probléma, ahol egy irányítatlan <math>G</math> páros gráfról és egy <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben <math>k</math> élű párosítás és legyen <math>Y</math> az a kérdés, ahol egy irányítatlan <math>G</math> gráfról és egy számról azt szeretnénk eldönteni, hogy van-e <math>G</math> -ben <math>k</math> pontból álló klikk (azaz teljes gráf). (2022 jan) ==
+Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq NP</math> ?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>X</math> Karp-redukálható <math>Y</math> -ra, de <math>Y</math> nem Karp-redukálható <math>X</math> -re.
+# <math>X</math> nem Karp-redukálható <math>Y</math> -ra, de <math>Y</math> Karp-redukálható <math>X</math> -re.
+# <math>X</math> Karp-redukálható <math>Y</math> -ra és <math>Y</math> is Karp-redukálható <math>X</math> -re.
+# <math>X</math> sem Karp-redukálható <math>Y</math> -ra és <math>Y</math> sem Karp-redukálható <math>X</math> -re.
+== A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk <math>C = 10</math> -es hátizsák kapacitással. A táblázat <math>i = 7</math> -es sora az értékekkel így néz ki: (2022 jan) ==
+{| class="wikitable"
+|-
+! X !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
+|-
+| 7 || 0 || 0 || 7 || 7 || 8 || 12 || 12 || 12 || 12 || 20 || 20
+|}
+Mi igaz a következő, <math>i = 8</math> -as sor <math>V[8,b]</math> értékeire az alábbiak közül, ha a 8. tárgy <math>w_8</math> súlya <math>5</math> , <math>v_8</math> értéke pedig <math>6</math> ?
+( <math>V[i,b]</math> jelentése: az első <math>i</math> tárgyból <math>b</math> hátizsák kapacitás mellett elérhető maximális érték.)
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>V[8,4]=8 \text { és } V[8,9]=17</math>
+# <math>V[8,3]=7 \text { és } V[8,8]=13</math>
+# <math>V[8,4]=8 \text { és } V[8,8]=12</math>
+# <math>V[8,4]=5 \text { és } V[8,8]=12</math>
+== Az alábbi állítások közül pontosan egy hamis. Válassza ki a HAMIS állítást! (2021 jan) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# Előfordulhat, hogy egy bináris keresőfában végrehajtott keresés belső csúcsban (azaz nem levélben) ér véget.
+# Bináris keresőfában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.
+# 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.
+# Piros-fekete fában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.
+== Legyen <math>G(V, E)</math> egy egyszerú, irányítatlan gráf. Tekintsük a következő tulajdonságot: (2021 jan) ==
+Vannak olyan <math>X \subseteq V</math> és <math>Y \subseteq V</math> nemüres halmazok, melyekre igaz, hogy
+* <math>X \cap Y=\emptyset</math>
+* <math>X \cup Y=V</math>
+* bármely <math>\{u, v\} \in E</math> él esetén az <math>\{u, v\} \cap X</math> halmaz egy elemú.
+Az alábbiak közül melyik írja le pontosan a megadott tulajdonságú gráfokat?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Nincsen egyetlen éle sem a gráfnak.
+# A gráf páros gráf, de nem feltétlenül teljes páros gráf
+# A gráf teljes páros gráf
+# A gráf teljes gráf.
+# 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) ==
+[[Fájl:2021 jan info zv algo keresofa.png|keretnélküli]]
+Melyik álítás igaz?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# A 3 előbb jön, mint a 27 mindkét sorrendben.
+# A 15 megelőzi a 4-et a preorder sorrendben, mert a 15 belső csúcsban van, a 4 pedig levélben.
+# A 27 megelőzi a 9-et a posztorder sorrendben, mert a 27 levélben van, a 9 pedig belső csúcsban.
+# A számok növekvő sorrendben vannak a két sorrend egyike szerint.
+# 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) <math>100 \cdot \frac{n(n-1)}{n-2} \cdot \log _{2} n+17 n-32</math>
+(b) <math>2 \cdot n^{2} \cdot \sqrt{n}+44 n^{2}+13</math>
+(c) <math>\frac{1}{10^{10}} \cdot \frac{4^{n}}{2^{n}}</math>
+(d) <math>4 n^{2}+37 n-12</math>
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Az (a) függvény <math>O\left(2^{n}\right)</math>, a (b) függvény <math>O\left(n^{2}\right)</math>
+# <math>\mathrm{Az}</math> (a) és a (d) függvény is <math>O\left(n^{2}\right)</math>
+# <math>\mathrm{Az}</math> (b) függvény <math>O\left(n^{n}\right)</math>, a (c) függvény <math>O\left(n^{2}\right)</math>
+# A négy függvény közül csak a (d) függvény <math>O\left(n^{2}\right)</math>
+# A (b), a (c) és a (d) függvény is <math>O\left(n^{2}\right)</math>
+== Legyen <math>X</math> egy <math>n</math> elemű véges halmaz, <math>n>0</math>. Hány páratlan elemű részhalmaza van <math>X</math>-nek? (2021 jan) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>n</math>
+# <math>2^{\lfloor n / 2\rfloor}</math>
+# <math>2^{n-1}</math>
+# <math>2^{n}</math>
+# Más a formula attól függően, hogy <math>n</math> páros vagy páratlan.
+== Egy város úthálózatát a <math>G</math> 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 <math>v</math> 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 <math>v</math>-ből az összes többi csúcsba.
+B: A Bellman-Ford-algoritmussal határozzák meg a legrövidebb utakat <math>v</math>-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?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# Csak az A módszer.
+# Csak a B módszer.
+# Csak a C módszer
+# Csak az A és a B módszer.
+# Mindhárom módszer
+== Tudjuk, hogy az <math>\mathcal{A}</math> probléma <math>N P</math>-teljes, a <math>\mathcal{B}</math> probléma pedig <math>N P</math>-beli, de nem feltétlenül <math>N P</math>-teljes. (2021 jan) ==
+Tekintsük a következő álításokat:
+A: Ha az <math>\mathcal{A}</math> problémára van polinom idejü algoritmus, akkor <math>P=N P</math>.
+B: Ha a <math>\mathcal{B}</math> problémára van polinom idejú algoritmus, akkor <math>P=N P</math>.
+C: Ha az <math>\mathcal{A}</math> problémára van polinom idejú algoritmus, akkor a <math>\mathcal{B}</math> problémára is van polinom idejú algoritmus.
+Melyik helyes az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# Csak az A és a C igaz.
+# Csak az A igaz.
+# Az A, B, C mindegyike igaz.
+# Csak a B igaz.
+# Csak az A és a B igaz.
+== Adott egy <math>n</math> hosszú számsorozat, <math>a_{1}, a_{2}, \ldots, a_{n}</math>. (2021 jan) ==
+Definiáljuk a <math>T</math> és <math>S</math> tömböt a következőképpen:
+<math>T[0]=S[0]=0, T[1]=a_{1}</math>
+és <math>1 \le i \leq n</math> esetén:
+<math>T[i]=\max _{j <i-1}\left\{T[j]+a_{i}\right\}</math>
+<math>S[i]=\max _{j \leq i}\{T[j]\}</math>
+Legyen most a számsorozat olyan, hogy ha <math>i</math> hárommal osztható, akkor <math>a_{i}=3</math>, különben meg <math>a_{i}=1</math>.
+Az alábbiak közül melyik állítás helyes?
+{{Kvízkérdés|típus=egy|válasz=5}}
+# <math>T[10]=10</math>
+# <math>T[4]=4</math>
+# <math>S[10]=9</math>
+# <math>S[3 n]=3 n</math>
+# <math>T[36]=37</math>
+== Adott <math>n</math> tárgy, tudjuk, hogy az <math>i</math>-ediknek a súlya <math>s_{i}</math> kilogramm, az értéke <math>v_{i}</math> forint, az <math>s_{i}, v_{i}</math> 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 <math>P \neq N P</math>?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# A probléma <math>P</math>-ben és <math>N P</math>-ben is benne van.
+# A probléma <math>P</math>-ben van és <math>N P</math>-teljes.
+# A probléma <math>N P</math>-teljes és nincs <math>P</math>-ben.
+# A probléma <math>P</math>-ben van, de nincs <math>N P</math>-ben.
+== Nézzük a következő két problémát: (2021 jan) ==
+Legközelebbi pár: Adott <math>n</math> 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 <math>n</math> 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 <math>O(n \log n)</math> lépésben.
+B: A Legközelebbi pár feladat megoldható a cseréken túl <math>O\left(n^{2}\right)</math> lépésben.
+C: A Legtávolabbi pár feladat megoldható a cseréken túl <math>O(n)</math> lépésben.
+D: A Legtávolabbi pár feladat megoldható a cseréken túl <math>O(n \log n)</math> lépésben.
+Melyik helyes az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Csak az A.
+# Mind a négy igaz.
+# Csak az A, a B és a D.
+# Csak a B és a D.
+== Az <math>f(n)</math> függvényről azt tudjuk, hogy <math>f(n) \in O\left(n^{2}\right)</math> Az alábbiak közül melyik lehet <math>f</math> ? (Mindegyik logaritmus kettes alapú.) (2020 jan) ==
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>f(n)=3 \cdot 2^{(\log n)^{2}}+85 n^{2}</math>
+# <math>f(n)=10 \cdot n \log n+12 n^{1,5}-8</math>
+# <math>f(n)=3 n \log (n !)</math>
+# <math>f(n)=20 \cdot \frac{n^{3}}{\log n}-15 n^{2}</math>
+# Egyik sem lehet.
+==  A kezdetben üres, <math>M=17</math> méretü <math>A</math> hash-táblába a <math>h(x) \equiv x(\bmod 17)</math> 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?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>A[8]</math>-ban
+# <math>A[6]</math>-ban
+# <math>A[9]</math>-ben
+# Nem határozható meg.
+# 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) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>26 \cdot 25 \cdot 24 \cdot 23 \cdot 10 \cdot 9 \cdot 8 \cdot 7</math>
+# <math>2 \cdot\left[\left(\begin{array}{c}26 \\ 4\end{array}\right)+\left(\begin{array}{c}10 \\ 4\end{array}\right)\right]</math>
+# <math>2 \cdot 26^{4} \cdot 10^{4}</math>
+# <math>26 \cdot 25 \cdot 24 \cdot 23+10 \cdot 9 \cdot 8 \cdot 7</math>
+# 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ő: <math>E C, D B, D E</math> A felsorolt lehetőségek közül melyik lehet igaz az ismeretlen élsúlyokra? (2020 jan) ==
+[[Fájl:2020 jan info zv kruskal.png|keretnélküli]]
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>x=1, y=5</math>
+# <math>x=5, y=1</math>
+# <math>x=y</math>
+# A fentiek egyike sem lehetséges.
+== A <math>G=(V, E)</math> egyszerủ, irányítatlan gráf csúcsain adott egy <math>f: V \rightarrow\{0,1,2\}</math> 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) ==
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Minden <math>a, b \in V</math> párra, ha <math>a \neq b</math>, akkor <math>f(a) \neq f(b)</math>
+# Minden <math>a, b \in V</math> párra, ha <math>\{a, b\} \in E</math>, akkor <math>f(a) \neq f(b)</math>
+# Minden <math>a, b \in V</math> párra, ha <math>f(a) \neq f(b)</math>, akkor <math>\{a, b\} \in E</math>
+# Minden <math>a, b \in V</math> párra, ha <math>\{a, b\} \notin E</math>, akkor <math>f(a)=f(b)</math>
+== Tegyük fel, hogy <math>\mathrm{P} \neq \mathrm{NP}</math> Tekintsük azt a problémát, amikor adottak az <math>a_{1}, a_{2}, \ldots, a_{n}</math> pozitív egész számok, és azt kell eldönteni, hogy van-e olyan <math>I \subseteq\{1,2, \ldots, n\}</math>, melyre <math>\sum_{i \in I} a_{i}=2020</math> (2020 jan) ==
+Melyik állítás igaz az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# A probléma P-ben és NP-ben is benne van.
+# A probléma P-ben van, de nincs NP-ben.
+# A probléma P-ben van és NP-teljes.
+# A probléma NP-teljes és nincs P-ben.
+== Tegyük fel, hogy <math>\mathrm{P} \neq \mathrm{NP}</math> és jelölje <math>P_{1} \prec P_{2}</math> azt, hogy a <math>P_{1}</math> probléma Karp-redukálható (polinomiálisan visszavezethető) a <math>P_{2}</math> problémára. Tekintsük az alábbi három problémát. (2020 jan) ==
+Adott egy <math>(G, k)</math> pár, ahol <math>G</math> egy irányítatlan gráf, <math>k</math> egy pozitív egész és a kérdés az alábbi:
+<math>\mathcal{A}</math> : a <math>G</math> gráfban van-e legalább <math>k</math> pontból álló kör
+<math>\mathcal{B}</math> : a <math>G</math> gráfban van-e legfeljebb <math>k</math> pontból álló kör
+<math>\mathcal{C}</math> : a <math>G</math> gráfban van-e pontosan <math>k</math> pontból álló kör
+Melyik állítás helyes az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>\mathcal{C} \prec \mathcal{A}</math> és <math>\mathcal{C} \prec \mathcal{B}</math>
+# <math>\mathcal{A} \prec \mathcal{C}</math> és <math>\mathcal{A} \prec \mathcal{B}</math>
+# <math>\mathcal{B} \prec \mathcal{C}</math> és <math>\mathcal{C} \prec \mathcal{A}</math>
+# <math>\mathcal{A} \prec \mathcal{B}</math> és <math>\mathcal{B} \prec \mathcal{C}</math>
+== Legyen adott egy <math>G</math> gráf, melynek adott két különböző csúcsa <math>A</math> és <math>B</math> 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 <math>A</math>-ból <math>B</math>-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?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Irányított gráf esetében a Dijkstra-algoritmus segítségével a feladat megoldható, de szélességi kereséssel nem.
+# Irányított gráf esetében a Dijkstra-algoritmus segítségével és szélességi kereséssel is megoldható a feladat.
+# 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.
+# 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 <math>O\left(n^{2}\right)</math> lépésben müködő algoritmus? (2020 jan) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# Adott <math>n</math> különböző egész szám közül a legkisebb kiválasztása.
+# Adott <math>n</math> csúcsú bináris keresőfában tárolt elemek közül a legnagyobb meghatározása.
+# Adott <math>n</math> bites <math>k</math> egész számra <math>5^{k}</math> kiszámolása.
+# Adott <math>n</math> csúcsú, irányított, körmentes gráfban az adott <math>s</math> csúcsból az adott <math>t</math> csúcsba vezető legkevesebb élü út meghatározása.
+== Egy <math>n</math> hosszú <math>s=s_{1} s_{2} \cdots s_{n}</math> és egy <math>m</math> hosszú <math>t=t_{1} t_{2} \cdots t_{m}</math> sorozathoz a <math>T</math> tömböt definiáljuk a következőképpen: Legyen <math>T[0, j]=T[i, 0]=0</math> minden <math>1 \leq i \leq n</math> és <math>1 \leq j \leq m</math> estén, továbbá <math>T[0,0]=0</math> Az <math>1 \leq i \leq n</math> és <math>1 \leq j \leq m</math> esetekben pedig (2020 jan) ==
+<math>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}</math>
+Legyen <math>n=100, m=20</math>, az <math>s</math> az a 0 -val kezdődő sorozat, melyben az 1-ek és 0-k felváltva követik egymást, azaz <math>s=010101 \cdots 01</math> és <math>t</math> 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?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>T[1,10]=15</math>
+# <math>T[2,20]=2</math>
+# <math>T[100,15]=10</math>
+# Az előzőek egyike sem igaz.
+== Melyik az a legkisebb pozitív egész <math>d</math> szám, melyre <math>f(n) \in O\left(n^{d}\right)</math> teljesül, ha <math>f(n)=\sum_{k=1}^{n^{2}} \frac{k}{3}</math>? (2019 jun) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# 2
+# 3
+# 4
+# 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) ==
+[[Fájl:2019 jun info zv algo graf.jpg|keretnélküli]]
+{{Kvízkérdés|típus=egy|válasz=2}}
+# A 15 a gyökérben lesz.
+# A fa magassága nem változik meg.
+# A 15 egy olyan csúcsba kerül, ami gyereke a 12-es számot tartalmazónak.
+# 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) ==
+{{Kvízkérdés|típus=egy|válasz=4}}
+# <math>\frac{100 !}{2}</math>
+# <math>\frac{100 !}{50 !}</math>
+# <math>50 !+50 !</math>
+# <math>50 ! \cdot 50</math> !
+# 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?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# <math>(B, E)</math>
+# <math>(C, A)</math>
+# <math>(C, D)</math>
+# <math>(F, B)</math>
+# 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: <math>A, B, C, 1,2,3</math>. (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?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# Mind a hat kártyát megfordítjuk.
+# Csak a <math>B</math> kártyát fordítjuk meg.
+# Csak a <math>B</math> és <math>C</math> kártyákat fordítjuk meg.
+# Az elözőek egyike sem helyes.
+== <math>\mathcal{A}: \quad \operatorname{Adott}</math> egy <math>G</math> irányítatlan gráf. (2019 jun) ==
+Van-e <math>G</math>-ben kör?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>\mathcal{A}</math> Benne van P-ben, de nincs benne NP-ben.
+# <math>\mathcal{A}</math> Benne van NP-ben, de nincs benne P-ben.
+# <math>\mathcal{A}</math> Benne van P-ben is és NP-ben is.
+# <math>\mathcal{A}</math> Nincs benne P-ben se és NP-ben se.
+== <math>\mathcal{B}: \quad</math> Adott egy <math>G</math> irányítatlan gráf. (2019 jun) ==
+Van-e <math>G</math>-ben pontosan 2019 csúcsot tartalmazó kör?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>\mathcal{B}</math> Benne van P-ben, de nincs benne NP-ben.
+# <math>\mathcal{B}</math> Benne van NP-ben, de nincs benne P-ben.
+# <math>\mathcal{B}</math> Benne van P-ben is és NP-ben is.
+# <math>\mathcal{B}</math> Nincs benne P-ben se és NP-ben se.
+== Tegyük fel, hogy <math>\mathrm{P} \neq</math> NP és jelölje <math>P_{1} \prec P_{2}</math> azt, hogy a <math>P_{1}</math> probléma Karp-redukálható (polinomiálisan visszavezethető) a <math>P_{2}</math> problémára. Tekintsük azt a két problémát, melyeknél adott egy <math>(G, k)</math> pár és  (2019 jun) ==
+<math>\mathcal{A}</math> : a <math>G</math> élsúlyozott gráfban van-e legfeljebb <math>k</math> súlyú Hamilton-kör (2019 jun) ==
+<math>\mathcal{B}</math> : a <math>G</math> gráfban van-e legalább <math>k</math> pontú teljes részgráf
+Melyik állítás helyes az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <math>\mathcal{A} \prec \mathcal{B}</math> és <math>\mathcal{B} \prec \mathcal{A}</math>
+# <math>\mathcal{A} \prec \mathcal{B}</math> és <math>\mathcal{B} \nprec \mathcal{A}</math>
+# <math>\mathcal{A} \nprec \mathcal{B}</math> és <math>\mathcal{B} \prec \mathcal{A}</math>
+# <math>\mathcal{A} \nprec \mathcal{B}</math> és <math>\mathcal{B} \nprec \mathcal{A}</math>
+== Több különböző megbízás közül válogatunk, melyek mindegyikét adott napokon lehet elvégezni. Ha az <math>i</math>.ediket elvállaljuk, akkor a <math>k_{i}</math> naptól a <math>v_{i}</math> napig csak ezt csinálhatjuk. Legyen adott <math>n</math> megbízás a hozzájuk tartozó <math>k_{i}</math> és <math>v_{i}</math> dátumokkal. Azt akarjuk eldönteni, hogy elvállalható-e közülük legalább <math>n / 2</math> darab (mindegy, hogy melyikek). (2019 jun) ==
+Melyik helyes az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 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ó.
+# Tetszőleges irányított gráfban leghosszabb utat lehet polinom időben találni, és egy ilyen algoritmussal a feladat egyszerüen megoldható.
+# 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ó.
+# 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 <math>O(n)</math> lépésben? (2019 jun) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# Tetszőleges <math>n</math> különböző szám növekvő sorrendbe rendezése.
+# Annak ellenőrzése, hogy egy <math>n</math> csúcsú gráf összefüggő-e.
+# Tetszőleges, <math>n</math> elemet tároló bináris keresőfa alapján a tárolt elemek növekvő sorrendben való felsorolása.
+# Tetszőleges <math>n</math> elemből egy bináris keresőfa építése.
+== Tekintsük a következő, az <math>a_{1}, a_{2}, \ldots, a_{n}</math> paraméterektől függő rekurzív definíciót! Az <math>(n+1) \times 1001</math> tömbben (2019 jun) ==
+<math>T[i, 0]=1</math>  ha <math>0 \leq i \leq n</math>
+<math>T[0, j]=0</math>  ha <math>1 \leq j \leq 1001</math>
+<math>T[i, j]=T[i-1, j]</math>  ha <math>i \geq 1</math> és <math>j <a_{i}</math>
+<math>T[i, j]=\max \left\{T[i-1, j], T\left[i-1, j-a_{i}\right]\right\}</math>  ha <math>i \geq 1</math> és <math>j \geq a_{i}</math>.
+Legyen <math>a_{i}=3^{i-1}, i=1,2, \ldots</math> Melyik igaz az alábbiak közül?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>T[2,15]=1</math>
+# <math>T[3,9]=0</math>
+# <math>T[3,10]=1</math>
+# <math>T[20,3]=0</math>
+# Az előzőek egyike sem igaz.