„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés
a (nyers referencia a feladatsorra) |
(kérdések hozzáadása) |
||
2. sor: | 2. sor: | ||
|cím=ZVAlgo|pontozás=- | |cím=ZVAlgo|pontozás=- | ||
}} | }} | ||
− | |||
== Egy csupa különböző egész számot tartalmazó bináris keresőfában egy keresés során az alábbi értékeket látjuk (x értéke nem ismert): <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}} | ||
45. sor: | 44. sor: | ||
# 4 ládarendezést használunk, mindegyik esetben 5 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. | # 1 ládarendezést használunk 20 ládával. | ||
+ | |||
+ | == Tekintsük az alábbi három függvényt (itt a <math>log</math> függvény mindig kettes alapú logaritmust jelöl): (2022 jan) == | ||
+ | <math>\begin{aligned} | ||
+ | & f(n)=2022 \cdot n^2 \cdot \log n+7 \cdot \sqrt{n} \\ | ||
+ | & g(n)=\log n+1000+n \cdot(\log n)^2 \\ | ||
+ | & h(n)=n \cdot \sqrt{n}+\frac{1}{1000} \cdot n^2-8 | ||
+ | \end{aligned}</math> | ||
+ | |||
+ | Az alábbiak közül melyik állítás igaz ezen három függvény nagyságrendjére? | ||
+ | {{Kvízkérdés|típus=egy|válasz=1}} | ||
+ | # <math>f(n) \notin O(h(n))</math> és <math>g(n) \in O(h(n))</math> | ||
+ | # <math>f(n) \in O(h(n))</math> és <math>g(n) \notin O(h(n))</math> | ||
+ | # <math>f(n) \in O(h(n))</math> és <math>g(n) \in O(h(n))</math> | ||
+ | # <math>f(n) \notin O(h(n))</math> és <math>g(n) \notin O(h(n))</math> | ||
+ | |||
+ | == Tekintsük azt az eldöntési feladatot, ahol egy irányított <math>G</math> gráfról azt szeretnénk eldönteni, hogy van-e két olyan <math>s</math> és <math>t</math> csúcsa, hogy <math>s</math>-ből van irányított út <math>t</math>-be, de <math>t</math>-ből nincsen irányított út <math>s</math>-be (2022 jan) == | ||
+ | Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy <math>P \neq NP</math>? | ||
+ | {{Kvízkérdés|típus=egy|válasz=1}} | ||
+ | # A probléma <math>P</math>-ben és <math>NP</math>-ben is benne van. | ||
+ | # A probléma <math>P</math>-ben van, de nincs <math>NP</math>-ben. | ||
+ | # A probléma <math>NP</math>-teljes és nincs <math>P</math>-ben. | ||
+ | # A probléma <math>P</math>-ben van és <math>NP</math>-teljes. | ||
+ | |||
+ | == Legyen <math>X</math> az az eldöntési probléma, ahol egy irányítatlan <math>G</math> páros gráfról és egy <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> élű párosítás és legyen <math>Y</math> az a kérdés, ahol egy irányítatlan <math>G</math> gráfról és egy számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> pontból álló klikk (azaz teljes gráf). (2022 jan) == | ||
+ | {{Kvízkérdés|típus=egy|válasz=3}} | ||
+ | Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq NP</math>? | ||
+ | # <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re. | ||
+ | # <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re. | ||
+ | # <math>X</math> Karp-redukálható <math>Y</math>-ra és <math>Y</math> is Karp-redukálható <math>X</math>-re. | ||
+ | # <math>X</math> sem Karp-redukálható <math>Y</math>-ra és <math>Y</math> sem Karp-redukálható <math>X</math>-re. | ||
+ | |||
+ | == A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk <math>C = 10</math>-es hátizsák kapacitással. A táblázat <math>i = 7</math>-es sora a értékekkel így néz ki: (2022 jan) == | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! X !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 | ||
+ | |- | ||
+ | | 7 || 0 || 0 || 7 || 7 || 8 || 12 || 12 || 12 || 12 || 20 || 20 | ||
+ | |} | ||
+ | |||
+ | Mi igaz a következő, <math>i = 8</math>-as sor <math>V[8,b]</math> értékeire az alábbiak közül, ha a 8. tárgy <math>w_8</math> súlya <math>5</math>, <math>v_8</math> értéke pedig <math>6</math>? | ||
+ | (<math>V[i,b]</math> jelentése: az első <math>i</math> tárgyból <math>b</math> hátizsák kapacitás mellett elérhető maximális érték.) | ||
+ | {{Kvízkérdés|típus=egy|válasz=3}} | ||
+ | # <math>V[8,4]=8 \text { és } V[8,9]=17</math> | ||
+ | # <math>V[8,3]=7 \text { és } V[8,8]=13</math> | ||
+ | # <math>V[8,4]=8 \text { és } V[8,8]=12</math> | ||
+ | # <math>V[8,4]=5 \text { és } V[8,8]=12</math> |
A lap 2023. december 4., 18:23-kori változata
Tartalomjegyzék
- 1 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)
- 2 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)
- 3 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)
- 4 Adott egy [math]3n[/math] csúcsú teljes gráf, a csúcsok számozottak, az 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ő csúcs piros? (2022 jan)
- 5 A [math]4, 3, 2, 1, 5, 6, 7, 8[/math] tömböt rendezzük öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jan)
- 6 Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű [math]\{a,b,c,d\}[/math] ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan)
- 7 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)
- 8 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)
- 9 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)
- 10 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 a értékekkel így néz ki: (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)
- 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
Egy kezdetben üres bináris keresőfába beszúrtuk az egész számokat valamilyen sorrendben (a sorrend nem ismert). Mi igaz biztosan az alábbiak közül? (2022 jan)
- Az 1 levélben van.
- A fának 7 szintje van.
- A legutoljára beszúrt érték levélben van.
- A középső érték, azaz a 64, a gyökérben van.
Egy irányítatlan nyolc csúcsú gráfon DFS-t (mélységi bejárást) futtatunk úgy, hogy ha döntési helyzetben vagyunk, akkor az ábécé szerinti sorrend szerint haladunk. A DFS fába az alábbi élek kerülnek be ebben a sorrendben: [math]AB, BD, AF, FE, EC, FG, GH[/math]. Mi igaz a csúcs fokszámára az alábbiak közül? (2022 jan)
- [math]H[/math] fokszáma lehet 1 vagy 2, és más nem lehet
- [math]H[/math] fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet
- [math]H[/math] fokszáma lehet 1, 2 vagy 3, és más nem lehet
- [math]H[/math] fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet
Adott egy [math]3n[/math] csúcsú teljes gráf, a csúcsok számozottak, az 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ő csúcs piros? (2022 jan)
- [math]\frac{n!}{2} * n![/math]
- [math]n! * n! * n![/math]
- [math]2 * n! * n![/math]
- [math]n! * (2n)![/math]
A [math]4, 3, 2, 1, 5, 6, 7, 8[/math] tömböt rendezzük öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jan)
- 12
- 7
- 4
- 8
Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű [math]\{a,b,c,d\}[/math] ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan)
- 1 ládarendezést használunk [math]4^5[/math] ládával.
- 5 ládarendezést használunk, mindegyik esetben 4 ládával.
- 4 ládarendezést használunk, mindegyik esetben 5 ládával.
- 1 ládarendezést használunk 20 ládával.
Tekintsük az alábbi három függvényt (itt a [math]log[/math] függvény mindig kettes alapú logaritmust jelöl): (2022 jan)
[math]\begin{aligned} & f(n)=2022 \cdot n^2 \cdot \log n+7 \cdot \sqrt{n} \\ & g(n)=\log n+1000+n \cdot(\log n)^2 \\ & h(n)=n \cdot \sqrt{n}+\frac{1}{1000} \cdot n^2-8 \end{aligned}[/math]
Az alábbiak közül melyik állítás igaz ezen három függvény nagyságrendjére?
- [math]f(n) \notin O(h(n))[/math] és [math]g(n) \in O(h(n))[/math]
- [math]f(n) \in O(h(n))[/math] és [math]g(n) \notin O(h(n))[/math]
- [math]f(n) \in O(h(n))[/math] és [math]g(n) \in O(h(n))[/math]
- [math]f(n) \notin O(h(n))[/math] és [math]g(n) \notin O(h(n))[/math]
Tekintsük azt az eldöntési feladatot, ahol egy irányított [math]G[/math] gráfról azt szeretnénk eldönteni, hogy van-e két olyan [math]s[/math] és [math]t[/math] csúcsa, hogy [math]s[/math]-ből van irányított út [math]t[/math]-be, de [math]t[/math]-ből nincsen irányított út [math]s[/math]-be (2022 jan)
Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy [math]P \neq NP[/math]?
- A probléma [math]P[/math]-ben és [math]NP[/math]-ben is benne van.
- A probléma [math]P[/math]-ben van, de nincs [math]NP[/math]-ben.
- A probléma [math]NP[/math]-teljes és nincs [math]P[/math]-ben.
- A probléma [math]P[/math]-ben van és [math]NP[/math]-teljes.
Legyen [math]X[/math] az az eldöntési probléma, ahol egy irányítatlan [math]G[/math] páros gráfról és egy [math]k[/math] számról azt szeretnénk eldönteni, hogy van-e [math]G[/math]-ben [math]k[/math] élű párosítás és legyen [math]Y[/math] az a kérdés, ahol egy irányítatlan [math]G[/math] gráfról és egy számról azt szeretnénk eldönteni, hogy van-e [math]G[/math]-ben [math]k[/math] pontból álló klikk (azaz teljes gráf). (2022 jan)
Mi igaz az alábbiak közül, ha feltételezzük, hogy [math]P \neq NP[/math]?
- [math]X[/math] Karp-redukálható [math]Y[/math]-ra, de [math]Y[/math] nem Karp-redukálható [math]X[/math]-re.
- [math]X[/math] nem Karp-redukálható [math]Y[/math]-ra, de [math]Y[/math] Karp-redukálható [math]X[/math]-re.
- [math]X[/math] Karp-redukálható [math]Y[/math]-ra és [math]Y[/math] is Karp-redukálható [math]X[/math]-re.
- [math]X[/math] sem Karp-redukálható [math]Y[/math]-ra és [math]Y[/math] sem Karp-redukálható [math]X[/math]-re.
A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk [math]C = 10[/math]-es hátizsák kapacitással. A táblázat [math]i = 7[/math]-es sora a é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ő, [math]i = 8[/math]-as sor [math]V[8,b][/math] értékeire az alábbiak közül, ha a 8. tárgy [math]w_8[/math] súlya [math]5[/math], [math]v_8[/math] értéke pedig [math]6[/math]? ([math]V[i,b][/math] jelentése: az első [math]i[/math] tárgyból [math]b[/math] hátizsák kapacitás mellett elérhető maximális érték.)
- [math]V[8,4]=8 \text { és } V[8,9]=17[/math]
- [math]V[8,3]=7 \text { és } V[8,8]=13[/math]
- [math]V[8,4]=8 \text { és } V[8,8]=12[/math]
- [math]V[8,4]=5 \text { és } V[8,8]=12[/math]