„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés
a typo |
a elemú -> elemű, valamint (feltételezhetően véletlenül bemásolt) pipa eltüntetése a helyes válaszból |
||
| (14 közbenső módosítás, amit 4 másik szerkesztő végzett, nincs mutatva) | |||
| 43. sor: | 43. sor: | ||
Melyik állítás igaz az alábbiak közül? | Melyik állítás igaz az alábbiak közül? | ||
{{Kvízkérdés|típus=egy|válasz=1}} | {{Kvízkérdés|típus=egy|válasz=1}} | ||
# Ha <math>x | # 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 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 <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> ? | 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}} | {{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>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 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 \operatorname{coN} P</math> de <math>X_{1} \notin P</math> | ||
| 84. sor: | 84. sor: | ||
== Adott egy egész számokat tartalmazó <math>A[1: n]</math> tömb, melyben nem szerepel 0. (2023 jun) == | == 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: | 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: | 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? | 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= | {{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>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>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. | ||
| 98. sor: | 98. sor: | ||
# <math>P[i]</math> megadja az <math>A[1: i]</math> tömbben szereplö összes 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) == | == 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) == | ||
| 133. sor: | 235. sor: | ||
== A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun) == | == 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}} | {{Kvízkérdés|típus=egy|válasz=1}} | ||
# <math>A, B, D, E, F, G, H, C</math> | # <math>A, B, D, E, F, G, H, C</math> | ||
| 158. sor: | 260. sor: | ||
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? | 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}} | {{Kvízkérdés|típus=egy|válasz=5}} | ||
# <math>\max _{1 | # <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>\Sigma_{i=1}^{n} T[i, n]</math> adja meg ezt. | ||
# <math>T[n, n]</math> adja meg ezt. | # <math>T[n, n]</math> adja meg ezt. | ||
| 249. sor: | 351. sor: | ||
== 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) == | == 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? | Az alábbiak közül melyik állítás igaz ezen három függvény nagyságrendjére? | ||
| 293. sor: | 395. sor: | ||
# <math>V[8,4]=8 \text { és } V[8,8]=12</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> | # <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. | |||