„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés
Ugrás a navigációhoz
Ugrás a kereséshez
(kérdések hozzáadása) |
|||
| 29. sor: | 29. sor: | ||
# <math>\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)</math> | # <math>\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)</math> | ||
# <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math> | # <math>\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}</math> | ||
| + | |||
| + | == Egy <math>n \times n</math>-es táblázat mezőin akarunk eljutni a bal felső cellából az utolsó sorba (itt mindegy, hogy a soron belül melyik oszlopba érkezünk). (2022 jun) == | ||
| + | A szabályok a következők: | ||
| + | * Az első oszlop első mezőjéről kell indulnunk és a végén az utolsó sor tetszőleges mezőjére kell érkeznünk. | ||
| + | * Egy lépésben vagy egy cellát mehetünk lefele (és maradunk ugyanabban az oszlopban) vagy egy cellát megyünk jobbra (és maradunk ugyanabban a sorban) vagy átlósan lépünk egyet lefele jobbra (azaz egy sort lefele és egy oszlopnyit jobbra). | ||
| + | Jelölje <math>T[i, j](1 \leq i, j \leq n</math> esetén) azt, hogy az <math>i</math>-edik sor <math>j</math>-edik oszlopában levő mezőbe hányféleképpen juthatok el a bal felső cellából. | ||
| + | Inicializáljuk a kezdeti értékeket így: mivel az első sor minden cellájába egyféleképpen juthatunk, ezért <math>T[1, j]=1</math> minden <math>1 \leq j \leq n</math> esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért <math>T[i, 1]=1</math> minden <math>1 \leq i \leq n</math> esetén. | ||
| + | Melyik rekurziós képlet a helyes a többi <math>T[i, j]</math> érték meghatározására? | ||
| + | {{Kvízkérdés|típus=egy|válasz=1}} | ||
| + | # <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]</math> | ||
| + | # <math>T[i, j]=\max \{T[i-1, j], T[i, j-1], T[i-1, j-1]\}</math> | ||
| + | # <math>T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]+1</math> | ||
| + | # <math>T[i, j]=T[i-1, j-1]+1</math> | ||
| + | |||
| + | Az előző feladat folytatása: | ||
| + | |||
| + | A teljesen kitöltött <math>T</math> táblázat segítségével hogyan kaphatjuk meg azt, hogy hányféleképpen lehet eljutni a bal felső cellából a legalsó sorba? | ||
| + | {{Kvízkérdés|típus=egy|válasz=5}} | ||
| + | # <math>\max _{1 < i < n} T[i, n]</math> adja meg ezt. | ||
| + | # <math>\Sigma_{i=1}^{n} T[i, n]</math> adja meg ezt. | ||
| + | # <math>T[n, n]</math> adja meg ezt. | ||
| + | # <math>\max _{1 \leq j \leq n} T[n, j]</math> adja meg ezt | ||
| + | # <math>\Sigma_{j=1}^{n} T[n, j]</math> adja meg ezt. | ||
| + | |||
| + | == A <math>G</math> egyszerű, irányítatlan gráf élei súlyozottak. Tegyük fel, hogy az élek súlyai különbözőek és hogy van legalább három éle a gráfnak. (2022 jun) == | ||
| + | Tekintsük a következő állításokat: | ||
| + | A: <math>G</math> minden minimális feszítőfája tartalmazza a legkisebb súlyú élt. | ||
| + | B: <math>G</math> minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt. | ||
| + | C: <math>G</math> egyik minimális feszítőfája sem tartalmazza a legnagyobb súlyú élt. | ||
| + | Melyik a helyes az alábbi lehetőségek közül? | ||
| + | {{Kvízkérdés|típus=egy|válasz=3}} | ||
| + | # Csak az <math>A</math> állítás igaz, a másik kettő nem | ||
| + | # Az <math>A</math>, a <math>B</math> és a <math>C</math> állítás is igaz. | ||
| + | # Csak az <math>A</math> és a <math>B</math> állítás igaz, a <math>C</math> nem. | ||
| + | # Csak az <math>A</math> és a <math>C</math> állítás igaz, a <math>B</math> nem. | ||
| + | |||
| + | == Legyen <math>X</math> a <math>2SZÍN</math> eldöntési probléma, azaz ahol egy egyszerü, irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy ki lehet-e színezni a csúcsait két színnel úgy, hogy azonos színú csúcsok közőtt ne menjen él. Az <math>Y</math> eldöntési problémában pedig azt kell eldöntenünk <math>n</math> darab pozitív egész számról, hogy van-e ezeknek a számoknak egy olyan részhalmaza, hogy a részhalmazban levő számok összege megegyezik a részhalmazba be nem vett számok összegével. (2022 jun) == | ||
| + | Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ? | ||
| + | {{Kvízkérdés|típus=egy|válasz=4}} | ||
| + | # <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re. | ||
| + | # <math>X</math> Karp-redukálható <math>Y</math>-ra és <math>Y</math> is Karp-redukálható <math>X</math>-re. | ||
| + | # <math>X</math> sem Karp-redukálható <math>Y</math>-ra és <math>Y</math> sem Karp-redukálható <math>X</math>-re. | ||
| + | # <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re. | ||
| + | |||
| + | == Tekintsük azt a <math>K_{20,40}</math> teljes páros gráfot, melynek <math>A=\left\{a_{1}, a_{2}, \ldots, a_{20}\right\}</math> és <math>B=\left\{b_{1}, b_{2}, \ldots, b_{40}\right\}</math> a két osztálya. Hány maximális (azaz tovább nem bővíthető) párosítás van ebben a gráfban? (Két párosítás különböző, ha nem pontosan ugyanazokból az <math>\left(a_{i}, b_{j}\right)</math> élekből áll.) (2022 jun) == | ||
| + | {{Kvízkérdés|típus=egy|válasz=1}} | ||
| + | # <math>\left(\begin{array}{l}40 \\ 20\end{array}\right) \cdot 20</math> ! | ||
| + | # <math>\left(\begin{array}{l}40 \\ 20\end{array}\right)</math> | ||
| + | # <math>40^{20}</math> | ||
| + | # <math>40!</math> | ||
| + | |||
| + | == Az <math>1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16</math> tömböt rendezzük a szokásos (módosítás nélkül futtatott) öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jun) == | ||
| + | {{Kvízkérdés|típus=egy|válasz=4}} | ||
| + | # 0 | ||
| + | # 64 | ||
| + | # <math>\left(\begin{array}{c}16 \\ 2\end{array}\right)</math> | ||
| + | # 32 | ||
| + | |||
| + | == Az <math>\mathcal{A}</math> algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, <math>n</math>-nek a függvényében <math>O\left(n^{2}\right)</math>. (2022 jun) == | ||
| + | Melyik nem igaz az alábbiak közül? | ||
| + | {{Kvízkérdés|típus=egy|válasz=2}} | ||
| + | # Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n^{3}</math>. | ||
| + | # Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n^{3}</math>. | ||
| + | # Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma kisebb, mint <math>n</math>. | ||
| + | # Minden <math>n</math> pozitív számhoz lehet olyan <math>n</math> hosszú bemenet, amelyiken <math>\mathcal{A}</math> lépésszáma nagyobb, mint <math>n</math>. | ||
== Egy csupa különböző egész számot tartalmazó bináris keresőfában egy keresés során az alábbi értékeket látjuk (x értéke nem ismert): <math>10, 5, x, 7, 8</math>. Az alábbiak közül mi igaz x értékére? (2022 jan) == | == 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) == | ||
A lap 2023. december 11., 15:26-kori változata
Tartalomjegyzék
- 1 Tekintsük az alábbi két függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jun)
- 2 Egy bináris keresőfa preorder bejárása a csúcsokat [math]5, 2, 4, 12, 8, 7, 10, 20[/math] sorrendben látogatja meg. (2023 jun)
- 3 [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)
- 4 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)
- 5 A [math]G[/math] egyszerű, irányítatlan gráf élei súlyozottak. Tegyük fel, hogy az élek súlyai különbözőek és hogy van legalább három éle a gráfnak. (2022 jun)
- 6 Legyen [math]X[/math] a [math]2SZÍN[/math] eldöntési probléma, azaz ahol egy egyszerü, irányítatlan [math]G[/math] gráfról azt szeretnénk eldönteni, hogy ki lehet-e színezni a csúcsait két színnel úgy, hogy azonos színú csúcsok közőtt ne menjen él. Az [math]Y[/math] eldöntési problémában pedig azt kell eldöntenünk [math]n[/math] darab pozitív egész számról, hogy van-e ezeknek a számoknak egy olyan részhalmaza, hogy a részhalmazban levő számok összege megegyezik a részhalmazba be nem vett számok összegével. (2022 jun)
- 7 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)
- 8 Az [math]1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16[/math] tömböt rendezzük a szokásos (módosítás nélkül futtatott) öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jun)
- 9 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)
- 10 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)
- 11 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)
- 12 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)
- 13 Adott egy [math]3n[/math] csúcsú teljes gráf, a csúcsok számozottak, az 1, 2,…, n számozású csúcsok pirosra vannak színezve, a többi csúcs színtelen. Hány olyan különböző Hamilton-út van a gráfban, amelyben az első n csúcs piros? (2022 jan)
- 14 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)
- 15 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)
- 16 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)
- 17 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)
- 18 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)
- 19 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)
Tekintsük az alábbi két függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jun)
[math]f(n)=2023 \cdot n^2 \cdot \log n-100 \cdot \sqrt{n}[/math]
[math]g(n)=\frac{1}{10^{10}} \cdot n^3+82 \cdot n \cdot \log n[/math]
Az alábbiak közül melyik állítás igaz?
- [math]f(n) \in O(g(n))[/math], mert mindkét függvényre igaz, hogy [math]O\left(n^3\right)[/math]
- [math]f(n) \in O(g(n))[/math], mert [math]f(n) \in O\left(n^2\right)[/math] és [math]g(n) \in O\left(n^3\right)[/math]
- [math]f(n) \in O(g(n))[/math], de az előző két indoklás egyike sem helyes
- [math]f(n) \notin O(g(n))[/math]
Egy bináris keresőfa preorder bejárása a csúcsokat [math]5, 2, 4, 12, 8, 7, 10, 20[/math] sorrendben látogatja meg. (2023 jun)
Melyik igaz az alábbi állítások közül a keresőfára?
- A 7 a 12 egyik részfájában van.
- A 8 a gyökérben van.
- A 10 a 2 egyik részfájában van.
- A 2 egy levélben van.
[math]2n[/math] darab különböző csokiból hányféleképpen tudunk kiválasztani [math]n[/math] darabot úgy, hogy a három kedvenc csokink a kiválasztottak között legyen? (2023 jun)
- [math]\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot\left(\begin{array}{l}n \\ 3\end{array}\right)[/math]
- [math](2 n-3) \cdot(2 n-4) \cdot \ldots \cdot(n-2)[/math]
- [math]\left(\begin{array}{c}2 n-3 \\ n\end{array}\right)[/math]
- [math]\left(\begin{array}{c}2 n \\ n\end{array}\right) \cdot \frac{1}{3 !}[/math]
Egy [math]n \times n[/math]-es táblázat mezőin akarunk eljutni a bal felső cellából az utolsó sorba (itt mindegy, hogy a soron belül melyik oszlopba érkezünk). (2022 jun)
A szabályok a következők:
- Az első oszlop első mezőjéről kell indulnunk és a végén az utolsó sor tetszőleges mezőjére kell érkeznünk.
- Egy lépésben vagy egy cellát mehetünk lefele (és maradunk ugyanabban az oszlopban) vagy egy cellát megyünk jobbra (és maradunk ugyanabban a sorban) vagy átlósan lépünk egyet lefele jobbra (azaz egy sort lefele és egy oszlopnyit jobbra).
Jelölje [math]T[i, j](1 \leq i, j \leq n[/math] esetén) azt, hogy az [math]i[/math]-edik sor [math]j[/math]-edik oszlopában levő mezőbe hányféleképpen juthatok el a bal felső cellából. Inicializáljuk a kezdeti értékeket így: mivel az első sor minden cellájába egyféleképpen juthatunk, ezért [math]T[1, j]=1[/math] minden [math]1 \leq j \leq n[/math] esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért [math]T[i, 1]=1[/math] minden [math]1 \leq i \leq n[/math] esetén. Melyik rekurziós képlet a helyes a többi [math]T[i, j][/math] érték meghatározására?
- [math]T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1][/math]
- [math]T[i, j]=\max \{T[i-1, j], T[i, j-1], T[i-1, j-1]\}[/math]
- [math]T[i, j]=T[i-1, j]+T[i, j-1]+T[i-1, j-1]+1[/math]
- [math]T[i, j]=T[i-1, j-1]+1[/math]
Az előző feladat folytatása:
A teljesen kitöltött [math]T[/math] táblázat segítségével hogyan kaphatjuk meg azt, hogy hányféleképpen lehet eljutni a bal felső cellából a legalsó sorba?
- [math]\max _{1 \lt i \lt n} T[i, n][/math] adja meg ezt.
- [math]\Sigma_{i=1}^{n} T[i, n][/math] adja meg ezt.
- [math]T[n, n][/math] adja meg ezt.
- [math]\max _{1 \leq j \leq n} T[n, j][/math] adja meg ezt
- [math]\Sigma_{j=1}^{n} T[n, j][/math] adja meg ezt.
A [math]G[/math] egyszerű, irányítatlan gráf élei súlyozottak. Tegyük fel, hogy az élek súlyai különbözőek és hogy van legalább három éle a gráfnak. (2022 jun)
Tekintsük a következő állításokat: A: [math]G[/math] minden minimális feszítőfája tartalmazza a legkisebb súlyú élt. B: [math]G[/math] minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt. C: [math]G[/math] egyik minimális feszítőfája sem tartalmazza a legnagyobb súlyú élt. Melyik a helyes az alábbi lehetőségek közül?
- Csak az [math]A[/math] állítás igaz, a másik kettő nem
- Az [math]A[/math], a [math]B[/math] és a [math]C[/math] állítás is igaz.
- Csak az [math]A[/math] és a [math]B[/math] állítás igaz, a [math]C[/math] nem.
- Csak az [math]A[/math] és a [math]C[/math] állítás igaz, a [math]B[/math] nem.
Legyen [math]X[/math] a [math]2SZÍN[/math] eldöntési probléma, azaz ahol egy egyszerü, irányítatlan [math]G[/math] gráfról azt szeretnénk eldönteni, hogy ki lehet-e színezni a csúcsait két színnel úgy, hogy azonos színú csúcsok közőtt ne menjen él. Az [math]Y[/math] eldöntési problémában pedig azt kell eldöntenünk [math]n[/math] darab pozitív egész számról, hogy van-e ezeknek a számoknak egy olyan részhalmaza, hogy a részhalmazban levő számok összege megegyezik a részhalmazba be nem vett számok összegével. (2022 jun)
Mi igaz az alábbiak közül, ha feltételezzük, hogy [math]P \neq N P[/math] ?
- [math]X[/math] nem Karp-redukálható [math]Y[/math]-ra, de [math]Y[/math] Karp-redukálható [math]X[/math]-re.
- [math]X[/math] Karp-redukálható [math]Y[/math]-ra és [math]Y[/math] is Karp-redukálható [math]X[/math]-re.
- [math]X[/math] sem Karp-redukálható [math]Y[/math]-ra és [math]Y[/math] sem Karp-redukálható [math]X[/math]-re.
- [math]X[/math] Karp-redukálható [math]Y[/math]-ra, de [math]Y[/math] nem Karp-redukálható [math]X[/math]-re.
Tekintsük azt a [math]K_{20,40}[/math] teljes páros gráfot, melynek [math]A=\left\{a_{1}, a_{2}, \ldots, a_{20}\right\}[/math] és [math]B=\left\{b_{1}, b_{2}, \ldots, b_{40}\right\}[/math] a két osztálya. Hány maximális (azaz tovább nem bővíthető) párosítás van ebben a gráfban? (Két párosítás különböző, ha nem pontosan ugyanazokból az [math]\left(a_{i}, b_{j}\right)[/math] élekből áll.) (2022 jun)
- [math]\left(\begin{array}{l}40 \\ 20\end{array}\right) \cdot 20[/math] !
- [math]\left(\begin{array}{l}40 \\ 20\end{array}\right)[/math]
- [math]40^{20}[/math]
- [math]40![/math]
Az [math]1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16[/math] tömböt rendezzük a szokásos (módosítás nélkül futtatott) öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jun)
- 0
- 64
- [math]\left(\begin{array}{c}16 \\ 2\end{array}\right)[/math]
- 32
Az [math]\mathcal{A}[/math] algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, [math]n[/math]-nek a függvényében [math]O\left(n^{2}\right)[/math]. (2022 jun)
Melyik nem igaz az alábbiak közül?
- Minden [math]n[/math] pozitív számhoz lehet olyan [math]n[/math] hosszú bemenet, amelyiken [math]\mathcal{A}[/math] lépésszáma kisebb, mint [math]n^{3}[/math].
- Minden [math]n[/math] pozitív számhoz lehet olyan [math]n[/math] hosszú bemenet, amelyiken [math]\mathcal{A}[/math] lépésszáma nagyobb, mint [math]n^{3}[/math].
- Minden [math]n[/math] pozitív számhoz lehet olyan [math]n[/math] hosszú bemenet, amelyiken [math]\mathcal{A}[/math] lépésszáma kisebb, mint [math]n[/math].
- Minden [math]n[/math] pozitív számhoz lehet olyan [math]n[/math] hosszú bemenet, amelyiken [math]\mathcal{A}[/math] lépésszáma nagyobb, mint [math]n[/math].
Egy csupa különböző egész számot tartalmazó bináris keresőfában egy keresés során az alábbi értékeket látjuk (x értéke nem ismert): [math]10, 5, x, 7, 8[/math]. Az alábbiak közül mi igaz x értékére? (2022 jan)
- x lehet 1 is és 9 is
- 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 1, 2,…, n számozású csúcsok pirosra vannak színezve, a többi csúcs színtelen. Hány olyan különböző Hamilton-út van a gráfban, amelyben az első n csúcs piros? (2022 jan)
- [math]\frac{n!}{2} * n![/math]
- [math]n! * n! * n![/math]
- [math]2 * n! * n![/math]
- [math]n! * (2n)![/math]
A [math]4, 3, 2, 1, 5, 6, 7, 8[/math] tömböt rendezzük öszefésüléses rendezéssel. Hány összehasonlítás történik a rendezés teljes futása alatt? (2022 jan)
- 12
- 7
- 4
- 8
Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű [math]\{a,b,c,d\}[/math] ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan)
- 1 ládarendezést használunk [math]4^5[/math] ládával.
- 5 ládarendezést használunk, mindegyik esetben 4 ládával.
- 4 ládarendezést használunk, mindegyik esetben 5 ládával.
- 1 ládarendezést használunk 20 ládával.
Tekintsük az alábbi három függvényt (itt a [math]log[/math] függvény mindig kettes alapú logaritmust jelöl): (2022 jan)
[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 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ő, [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]
