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

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

43. sor:

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

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

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

69. sor:

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 ~~\checkmark~~</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>

85. sor:

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] ~~\le~~ 0 </math> akkor <math>P[1]=0</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] ~~\le~~ 0</math> akkor <math>P[i]=0</math> és <math>N[i]=P[i-1]+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.

195. sor:

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

442. sor:

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

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

452. sor:

== 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 ~~mindencsomópontba~~ el lehessen jutni kizárólag felújított útszakaszokon.

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.

489. sor:

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

<math>T[i]=\max _{j ~~\le~~ i-1}\left\{T[j]+a_{i}\right\}</math>

578. sor:

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

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

627. sor:

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

@@ 43. sor: / 43. sor: @@
 Melyik állítás igaz az alábbiak közül?
 {{Kvízkérdés|típus=egy|válasz=1}}
-# Ha <math>x \le 3 </math> akkor az <math>E C</math> élet biztosan nem választja be az algoritmus a minimális feszítőfába.
+# 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.
@@ 69. sor: / 69. sor: @@
 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 \checkmark</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>
@@ 85. sor: / 85. sor: @@
 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] \le 0 </math> akkor <math>P[1]=0</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] \le 0</math> akkor <math>P[i]=0</math> és <math>N[i]=P[i-1]+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=4}}
+{{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.
@@ 195. sor: / 195. sor: @@
 == 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=2}}
+{{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.
@@ 442. sor: / 442. sor: @@
 # 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) ==
+== 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>
@@ 452. sor: / 452. sor: @@
 == 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 mindencsomópontba el lehessen jutni kizárólag felújított útszakaszokon.
+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.
@@ 489. sor: / 489. sor: @@
 és <math>1 \le i \leq n</math> esetén:
-<math>T[i]=\max _{j \le i-1}\left\{T[j]+a_{i}\right\}</math>
+<math>T[i]=\max _{j <i-1}\left\{T[j]+a_{i}\right\}</math>
 <math>S[i]=\max _{j \leq i}\{T[j]\}</math>
@@ 578. sor: / 578. sor: @@
 == 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}}
-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.
@@ 627. sor: / 627. sor: @@
 # <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.