„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés
(kérdések hozzáadása) |
|||
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=2}} | ||
+ | # 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) == |
A lap 2023. december 11., 21:37-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 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)
- 5 Kruskal algoritmusát futtatjuk az alábbi gráfon. (2023 jun)
- 6 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)
- 7 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)
- 8 Eldöntési feladatok (2023 jun)
- 9 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)
- 10 Adott egy egész számokat tartalmazó [math]A[1: n][/math] tömb, melyben nem szerepel 0. (2023 jun)
- 11 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)
- 12 Tekintsük az alábbi három függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jan)
- 13 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)
- 14 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)
- 15 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)
- 16 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)
- 17 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)
- 18 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)
- 19 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)
- 20 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)
- 21 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)
- 22 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)
- 23 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)
- 24 Tekintsük azt a feladatot, ahol egy [math]n\gt 100[/math] csúcsú irányított [math]G[/math] 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)
- 25 A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun)
- 26 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)
- 27 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)
- 28 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)
- 29 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)
- 30 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)
- 31 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)
- 32 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)
- 33 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)
- 34 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)
- 35 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)
- 36 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)
- 37 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)
- 38 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)
- 39 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)
- 40 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)
- 41 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é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]\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]
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?
- [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)
Melyik állítás igaz az alábbiak közül?
- Ha [math]x \le 3 [/math] akkor az [math]E C[/math] élet biztosan nem választja be az algoritmus a minimális feszítőfába.
- 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)
- [math]G[/math] komplementerében nincsen kör.
- [math]G[/math]-ben van kör.
- [math]G[/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?
- 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] ?
- [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] ?
- 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]\gt 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\gt 2)[/math] így számoljuk: - ha [math]A[i]\gt 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?
- [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
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?
- 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?
- [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)
- 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)
[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.
- 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 ?
- [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?
- 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?
- [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]\gt 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?
- 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] ?
- [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] ?
- 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)
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 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)
- [math]5,9,1,7,3,4[/math]
- [math]5,7,4,9,3,1[/math]
- [math]5,3,4,9,1,7[/math]
- [math]5,4,7,3,9,1[/math]
Tekintsük azt a feladatot, ahol egy [math]n\gt 100[/math] csúcsú irányított [math]G[/math] 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 [math]P \neq N P[/math] ?
- 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]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 megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun)
- [math]A, B, D, E, F, G, H, C[/math]
- [math]A, D, F, G, H, C, E, B[/math]
- [math]A, B, C, D, E, F, G, H[/math]
- [math]A, D, F, E, B, G, H, C[/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]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?
- [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]