„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés
A VIK Wikiből
kérdések hozzáadása |
kérd |
||
| 10. sor: | 10. sor: | ||
Az alábbiak közül melyik állítás igaz? | Az alábbiak közül melyik állítás igaz? | ||
{{Kvízkérdés|típus=egy|válasz=3}} | {{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 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> , 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) \in O(g(n))</math> , de az előző két indoklás egyike sem helyes | ||
# <math>f(n) \notin O(g(n))</math> | # <math>f(n) \notin O(g(n))</math> | ||
| 21. sor: | 21. sor: | ||
# A 8 a gyökérben van. | # A 8 a gyökérben van. | ||
# A 10 a 2 egyik részfájában van. | # A 10 a 2 egyik részfájában van. | ||
# A 2 egy | # 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>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) == | ||
| 30. sor: | 30. sor: | ||
# <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math> | # <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math> | ||
== 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) == | == 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 \le 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> math>-ben van kör. | |||
# <math>G</math> 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 \checkmark</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] \le 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> | |||
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}} | |||
# <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 | |||
== 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? | Melyik adatszerkezettel valósítható ez meg? | ||
{{Kvízkérdés|típus=egy|válasz=1}} | {{Kvízkérdés|típus=egy|válasz=1}} | ||
| 57. sor: | 126. 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=4}} | {{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>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>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 van és <math>N P</math> -teljes. | ||
# A probléma <math>P</math>-ben és <math>N P</math>-ben is benne van. | # 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) == | == A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun) == | ||
{{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> | ||
| 72. sor: | 141. sor: | ||
== 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) == | == 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: | 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. | # 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). | # 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. | 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. | 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? | Melyik rekurziós képlet a helyes a többi <math>T[i, j]</math> érték meghatározására? | ||
| 103. sor: | 172. sor: | ||
{{Kvízkérdés|típus=egy|válasz=3}} | {{Kvízkérdés|típus=egy|válasz=3}} | ||
# Csak az <math>A</math> állítás igaz, a másik kettő nem | # 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. | # 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>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. | # Csak az <math>A</math> és a <math>C</math> állítás igaz, a <math>B</math> nem. | ||
| 110. sor: | 179. sor: | ||
Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ? | 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}} | {{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> 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> 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> 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, 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) == | == 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) == | ||
| 129. sor: | 198. sor: | ||
# 32 | # 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) == | == 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? | Melyik nem igaz az alábbiak közül? | ||
{{Kvízkérdés|típus=egy|válasz=2}} | {{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 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 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 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>. | # 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) == | == 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}} | {{Kvízkérdés|típus=egy|válasz=2}} | ||
# x lehet 1 is és 9 is | # x lehet 1 is és 9 is | ||
| 151. sor: | 220. sor: | ||
# A középső érték, azaz a 64, a gyökérben 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) == | == 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}} | {{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 vagy 2, és más nem lehet | ||
| 180. sor: | 249. 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>\begin{aligned} | <math>\begin{aligned} | ||
& f(n)=2022 \cdot n^2 \cdot \log n+7 \cdot \sqrt{n} \\ | & f(n)=2022 \cdot n^2 \cdot \log n+7 \cdot \sqrt{n} \\ | ||
& g(n)=\log n+1000+n \cdot(\log n)^2 \\ | & g(n)=\log n+1000+n \cdot(\log n)^2 \\ | ||
| 193. sor: | 262. sor: | ||
# <math>f(n) \notin O(h(n))</math> és <math>g(n) \notin 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) == | == 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>? | 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}} | {{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 é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>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>NP</math> -teljes és nincs <math>P</math> -ben. | ||
# A probléma <math>P</math>-ben van és <math>NP</math>-teljes. | # 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) == | == 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>? | 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}} | {{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> 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> 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> 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> 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) == | == 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" | {| class="wikitable" | ||
|- | |- | ||
| 217. sor: | 286. sor: | ||
|} | |} | ||
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>? | 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[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}} | {{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,4]=8 \text { és } V[8,9]=17</math> | ||
A lap 2023. december 11., 23:13-kori változata
Eldöntési feladatok (2023 jun)
Az eldöntési feladatban egy irányítatlan gráfról azt szeretnénk eldönteni, hogy van-e -ben pontosan 4 élü kör. Az eldöntési feladatban egy irányítatlan gráfról és egy pozitív egész számról azt szeretnénk eldönteni, hogy van-e -ben pontosan élü kör. Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy ?
- és
- és
- de
- de
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.
darab különböző csokiból hányféleképpen tudunk kiválasztani darabot úgy, hogy a három kedvenc csokink a kiválasztottak között legyen? (2023 jun)
Tekintsük azt a feladatot, ahol egy csúcsú irányított 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 ?
- A probléma -ben van, de nincs -ben.
- A probléma -teljes és nincs -ben.
- A probléma -ben van és -teljes.
- A probléma -ben és -ben is benne van.
A 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: minden minimális feszítőfája tartalmazza a legkisebb súlyú élt. B: minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt. C: 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 állítás igaz, a másik kettő nem
- Az , a és a állítás is igaz.
- Csak az és a állítás igaz, a nem.
- Csak az és a állítás igaz, a nem.
Pozitív egész számokat szeretnénk tárolni valami adatszerkezet segítségével úgy, hogy tárolt elem esetén tetszőleges egész számról lépésben meg tudjuk mondani, hogy igaz-e rá, hogy a tárolt számok között van, de sem , sem 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 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
- 32
A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk -es hátizsák kapacitással. A táblázat -es sora az értékekkel így néz ki: (2022 jan)
| X | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 7 | 0 | 0 | 7 | 7 | 8 | 12 | 12 | 12 | 12 | 20 | 20 |
Mi igaz a következő, -as sor értékeire az alábbiak közül, ha a 8. tárgy súlya , értéke pedig ? ( jelentése: az első tárgyból hátizsák kapacitás mellett elérhető maximális érték.)
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): . Az alábbiak közül mi igaz x értékére? (2022 jan)
- x lehet 1 is és 9 is
- x lehet 6 is és 9 is
- x lehet 1 is és 6 is
- x lehet 2 is és 12 is
Legyen az az eldöntési probléma, ahol egy irányítatlan páros gráfról és egy számról azt szeretnénk eldönteni, hogy van-e -ben élű párosítás és legyen az a kérdés, ahol egy irányítatlan gráfról és egy számról azt szeretnénk eldönteni, hogy van-e -ben pontból álló klikk (azaz teljes gráf). (2022 jan)
Mi igaz az alábbiak közül, ha feltételezzük, hogy ?
- Karp-redukálható -ra, de nem Karp-redukálható -re.
- nem Karp-redukálható -ra, de Karp-redukálható -re.
- Karp-redukálható -ra és is Karp-redukálható -re.
- sem Karp-redukálható -ra és sem Karp-redukálható -re.
Tekintsük azt az eldöntési feladatot, ahol egy irányított gráfról azt szeretnénk eldönteni, hogy van-e két olyan és csúcsa, hogy -ből van irányított út -be, de -ből nincsen irányított út -be (2022 jan)
Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy ?
- A probléma -ben és -ben is benne van.
- A probléma -ben van, de nincs -ben.
- A probléma -teljes és nincs -ben.
- A probléma -ben van és -teljes.
Tekintsük azt a teljes páros gráfot, melynek és 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 élekből áll.) (2022 jun)
- !
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?
- , mert mindkét függvényre igaz, hogy
- , mert és
- , de az előző két indoklás egyike sem helyes
A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun)
Egy bináris keresőfa preorder bejárása a csúcsokat 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.
Radix rendezéssel rendezzük az alábbi sorozatot: (a karakterek mindegyik pozícióban a 3-elemű ábécéből kerülnek ki). (2023 jun)
Melyik állítás igaz a rendezés folyamatára?
- soha nem előzi meg az szót.
- Van olyan fázis, amikor megelőzi az szót.
- és sorrendje pontosan kétszer változik.
- Van olyan fázis, amikor megelőzi az szót.
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)
Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű á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 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.
Az algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, -nek a függvényében . (2022 jun)
Melyik nem igaz az alábbiak közül?
- Minden pozitív számhoz lehet olyan hosszú bemenet, amelyiken lépésszáma kisebb, mint .
- Minden pozitív számhoz lehet olyan hosszú bemenet, amelyiken lépésszáma nagyobb, mint .
- Minden pozitív számhoz lehet olyan hosszú bemenet, amelyiken lépésszáma kisebb, mint .
- Minden pozitív számhoz lehet olyan hosszú bemenet, amelyiken lépésszáma nagyobb, mint .
Az csúcsú irányítatlan gráfra igaz, hogy bárhogyan is sorolunk fel csupa különböző -beli csúcsokat, ahol a és párok közül legalább az egyik benne van élhalmazában. Melyik állítás igaz az alábbiak közül? (2023 jun)
- komplementerében nincsen kör.
- math>-ben van kör.
- math>-ben nincsen méretű független ponthalmaz.
- komplementerében nincsen -as klikk.
Az eldöntési problémáról azt tudjuk, hogy -ben van, az eldöntési problémáról pedig azt, hogy -teljes. (2023 jun)
Mi igaz az alábbiak közül, ha feltételezzük, hogy ?
- Minden olyan eldöntési probléma, ami Karp-redukálható -ra, az Karp-redukálható -re is.
- biztosan Karp-redukálható -re.
- Ha Karp-redukálható -ra, akkor nincsen -ben.
- Ha Karp-redukálható -re, akkor az probléma -teljes.
Adott egy 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)
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: . Mi igaz a csúcs fokszámára az alábbiak közül? (2022 jan)
- fokszáma lehet 1 vagy 2, és más nem lehet
- fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet
- fokszáma lehet 1, 2 vagy 3, és más nem lehet
- fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet
Egy -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 esetén) azt, hogy az -edik sor -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 minden esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért minden esetén. Melyik rekurziós képlet a helyes a többi érték meghatározására?
Az előző feladat folytatása:
A teljesen kitöltött 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?
- adja meg ezt.
- adja meg ezt.
- adja meg ezt.
- adja meg ezt
- adja meg ezt.
Kruskal algoritmusát futtatjuk az alábbi gráfon. (2023 jun)
Melyik állítás igaz az alábbiak közül?
- Ha akkor az élet biztosan nem választja be az algoritmus a minimális feszítőfába.
- Az élet biztosan beválasztja az algoritmus a minimális feszítőfába, bármi is értéke.
- Az élet biztosan nem választja be az algoritmus a minimális feszítőfába, bármi is értéke.
- Az algoritmus biztosan beválaszt legalább egy 3 súlyú élet a minimális feszítőfába.
A 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
Adott egy egész számokat tartalmazó tömb, melyben nem szerepel 0. (2023 jun)
Az tömb alapján egy és egy tömböt töltünk ki a következőképpen: - ha akkor és . - ha akkor és
A további értékeket így számoljuk: - ha akkor és - ha akkor és
Melyik állítás igaz az alábbiak közül a kiszámolt és értékek jelentésére?
- megadja a legnagyobb összeget, amit valamelyik, legfeljebb egy negatív számot tartalmazó résztömbből ( kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
- megadja a legnagyobb összeget, amit valamelyik résztömbből kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
- megadja az tömbben szereplö összes negatív szám összegét
- megadja az tömbben szereplö összes szám összegét
Tekintsük az alábbi három függvényt (itt a 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?
- és
- és
- és
- és
Legyen a Értelmezés sikertelen (formai hiba): {\displaystyle 2SZÍN} eldöntési probléma, azaz ahol egy egyszerü, irányítatlan 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 eldöntési problémában pedig azt kell eldöntenünk 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 ?
- nem Karp-redukálható -ra, de Karp-redukálható -re.
- Karp-redukálható -ra és is Karp-redukálható -re.
- sem Karp-redukálható -ra és sem Karp-redukálható -re.
- Karp-redukálható -ra, de nem Karp-redukálható -re.
Egy ország térképe egy élsúlyozott, irányítatlan csúcsú 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 érték esetén azt szeretnénk eldönteni, hogy igaz-e, hogy bármelyik településről van 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 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.
