Záróvizsga kvíz - Algoritmusok

	Kvízek használata,; importálása, fejlesztése.
Statisztika
Átlagteljesítmény
Eddigi kérdések	0
Kapott pontok	0
Alapbeállított pontozás	(-)
Beállítások
Minden kérdés látszik
Véletlenszerű sorrend

Egy város úthálózatát a $G$ egyszerú, irányítatlan, összefüggő gráf írja le, a gráf csúcsai a csomópontok, az élek az ezeket összekötőútszakaszokat jelölik. (2021 jan)

Az utak sajnos eléggé rossz állapotúak, minden élre adott, hogy azt az útszakaszt mennyiért lehetne felújítani. A város vezetése azt szeretné megtudni, hogy mely útszakaszokat újitassa fel, ha a célja az, hogy a $v$ csúccsal jelzett főtérről mindencsomópontba el lehessen jutni kizárólag felújított útszakaszokon. A következő ötletek merültek fel a legolcsóbb ilyen felújitás megtalálására: A: Dijkstra algoritmusával határozzák meg a legrövidebb utakat $v$ -ből az összes többi csúcsba. B: A Bellman-Ford-algoritmussal határozzák meg a legrövidebb utakat $v$ -ből az összes többi csúcsba. C: Kruskal algoritmusával határozzanak meg egy minimális feszítófát a gráfban. Melyik ad helyes eredményt a feladatra?

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

Csak az A módszer.
Csak a B módszer.
Csak a C módszer
Csak az A és a B módszer.
Mindhárom módszer

Pozitív egész számokat szeretnénk tárolni valami adatszerkezet segítségével úgy, hogy $n$ tárolt elem esetén tetszőleges $x$ egész számról $O (\log n)$ lépésben meg tudjuk mondani, hogy igaz-e rá, hogy $x$ a tárolt számok között van, de sem $x - 1$ , sem $x + 1$ nincsen. (2022 jun)

Melyik adatszerkezettel valósítható ez meg?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

2-3 fa
rendezett lista
nyílt címzésú hash
(nem feltétlenül kiegyensúlyozott) bináris keresőfa

Adott egy $n$ hosszú számsorozat, $a_{1}, a_{2}, \dots, a_{n}$ . (2021 jan)

Definiáljuk a $T$ és $S$ tömböt a következőképpen:

$T [0] = S [0] = 0, T [1] = a_{1}$

és $1 \leq i \leq n$ esetén:

$T [i] = \max_{j \leq i - 1} {T [j] + a_{i}}$

$S [i] = \max_{j \leq i} {T [j]}$

Legyen most a számsorozat olyan, hogy ha $i$ hárommal osztható, akkor $a_{i} = 3$ , különben meg $a_{i} = 1$ .

Az alábbiak közül melyik állítás helyes?

Típus: egy. Válasz: 5. Pontozás: nincs megadva.

$T [10] = 10$
$T [4] = 4$
$S [10] = 9$
$S [3 n] = 3 n$
$T [36] = 37$

A $G$ 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: $G$ minden minimális feszítőfája tartalmazza a legkisebb súlyú élt. B: $G$ minden minimális feszítőfája tartalmazza a második legkisebb súlyú élt. C: $G$ 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?

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

Csak az $A$ állítás igaz, a másik kettő nem
Az $A$ , a $B$ és a $C$ állítás is igaz.
Csak az $A$ és a $B$ állítás igaz, a $C$ nem.
Csak az $A$ és a $C$ állítás igaz, a $B$ nem.

Legyen $X$ az az eldöntési probléma, melynek inputja egy irányított $G$ gráfból, ezen gráf egy $s$ csúcsából és egy $k$ pozitív egészből áll és azt szeretnénk eldönteni, hogy igaz-e hogy $G$ -ben $s$ -ből minden más csúcsba vezet legfeljebb $k$ élből álló út. Legyen továbbá $Y$ a tanult $3 - S Z$ IíN eldöntési feladat. (2023 jan)

Mi igaz az alábbiak közül, ha feltételezzük, hogy $P \neq N P$ ?

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

$X$ sem Karp-redukálható $Y$ -ra és $Y$ sem Karp-redukálható $X$ -re.
$X$ Karp-redukálható $Y$ -ra, de $Y$ nem Karp-redukálható $X$ -re.
$X$ Karp-redukálható $Y$ -ra és $Y$ is Karp-redukálható $X$ -re.
$X$ nem Karp-redukálható $Y$ -ra, de $Y$ Karp-redukálható $X$ -re. $X$

Adott egy $3 n$ 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)

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

$\frac{n!}{2} * n!$
$n! * n! * n!$
$2 * n! * n!$
$n! * (2 n)!$

Melyik állítás igaz az alábbi négy függvény nagyságrendjére? (2021 jan)

(a) $100 \cdot \frac{n (n - 1)}{n - 2} \cdot \log_{2} n + 17 n - 32$

(b) $2 \cdot n^{2} \cdot \sqrt{n} + 44 n^{2} + 13$

(c) $\frac{1}{1 0^{10}} \cdot \frac{4^{n}}{2^{n}}$

(d) $4 n^{2} + 37 n - 12$

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

Az (a) függvény $O (2^{n})$ , a (b) függvény $O (n^{2})$
$A z$ (a) és a (d) függvény is $O (n^{2})$
$A z$ (b) függvény $O (n^{n})$ , a (c) függvény $O (n^{2})$
A négy függvény közül csak a (d) függvény $O (n^{2})$
A (b), a (c) és a (d) függvény is $O (n^{2})$

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)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

2 helyett álljon 4
7 helyett álljon 8
5 helyett álljon 1
10 helyett álljon 1

Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű ${a, b, c, d}$ ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan)

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

1 ládarendezést használunk $4^{5}$ 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.

A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk $C = 10$ -es hátizsák kapacitással. A táblázat $i = 7$ -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ő, $i = 8$ -as sor $V [8, b]$ értékeire az alábbiak közül, ha a 8. tárgy $w_{8}$ súlya $5$ , $v_{8}$ értéke pedig $6$ ? ( $V [i, b]$ jelentése: az első $i$ tárgyból $b$ hátizsák kapacitás mellett elérhető maximális érték.)

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

$V [8, 4] = 8 és V [8, 9] = 17$
$V [8, 3] = 7 és V [8, 8] = 13$
$V [8, 4] = 8 és V [8, 8] = 12$
$V [8, 4] = 5 és V [8, 8] = 12$

A $4, 3, 2, 1, 5, 6, 7, 8$ 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)

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

12
7
4
8

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 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ 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 ?

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

$3 \cdot 26 + 2 \cdot 10$
$2 6^{3} \cdot 1 0^{2}$
$2 6^{3} + 1 0^{2}$
$3 \cdot 2 \cdot 26 \cdot 10$

Egy $k$ és egy $ℓ$ 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)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

$k \cdot ℓ$
$k + ℓ - 1$
$\max {k, ℓ}$
$k + ℓ x$

Az alábbi állítások közül pontosan egy hamis. Válassza ki a HAMIS állítást! (2021 jan)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

Előfordulhat, hogy egy bináris keresőfában végrehajtott keresés belső csúcsban (azaz nem levélben) ér véget.
Bináris keresőfában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.
Bináris keresőfában a tárolt értékek közül a középsőt 1 lépésben meg lehet találni, mert az mindig a gyökérben van.
Piros-fekete fában a legkisebb értéket tartalmazó csúcsnak legfeljebb egy gyereke lehet.

Egy csupa különböző egész számot tartalmazó $T$ tömbben akarjuk eldönteni egy adott $x$ elemről, hogy igaz-e, hogy $x$ és $2 \cdot x$ is szerepel $T$ -ben. Az alábbi négy állítás közül melyek igazak? (2023 jan)

A: Ez megtehető $O (n)$ lépésben, ha a tömb rendezett.

B: Ez megtehető $O (\log n)$ lépésben, ha a tömb rendezett.

C: Ez megtehető $O (n)$ lépésben tetszőleges tömb esetén.

D: Ez megtehető $O (\log n)$ lépésben tetszőleges tömb esetén.

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

Csak az $A, B$ állítások igazak.
Csak az $A, B, C$ állítások igazak.
Mind a négy igaz.
Csak az $A, C$ állítások igazak.

A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun)

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

$A, B, D, E, F, G, H, C$
$A, D, F, G, H, C, E, B$
$A, B, C, D, E, F, G, H$
$A, D, F, E, B, G, H, C$

Radix rendezéssel rendezzük az alábbi sorozatot: $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$ (a karakterek mindegyik pozícióban a 3-elemű ${a, b, c}$ ábécéből kerülnek ki). (2023 jun)

Melyik állítás igaz a rendezés folyamatára?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

$s_{5} = c a c b$ soha nem előzi meg az $s_{1} = a b a c$ szót.
Van olyan fázis, amikor $s_{3} = b c a c$ megelőzi az $s_{1} = a b a c$ szót.
$s_{3} = b c a c$ és $s_{4} = b b b b$ sorrendje pontosan kétszer változik.
Van olyan fázis, amikor $s_{3} = b c a c$ megelőzi az $s_{2} = a c b c$ szót.

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)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

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.

Tekintsük azt az eldöntési feladatot, ahol egy irányított $G$ gráfról azt szeretnénk eldönteni, hogy van-e két olyan $s$ és $t$ csúcsa, hogy $s$ -ből van irányított út $t$ -be, de $t$ -ből nincsen irányított út $s$ -be (2022 jan)

Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy $P \neq N P$ ?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

A probléma $P$ -ben és $N P$ -ben is benne van.
A probléma $P$ -ben van, de nincs $N P$ -ben.
A probléma $N P$ -teljes és nincs $P$ -ben.
A probléma $P$ -ben van és $N P$ -teljes.

Az $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16$ 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)

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

0
64
$(\begin{array}{c} 16 \\ 2 \end{array})$
32

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)

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

2
1
7
3

Kruskal algoritmusát futtatjuk az alábbi gráfon. (2023 jun)

Melyik állítás igaz az alábbiak közül?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

Ha $x \leq 3$ akkor az $E C$ élet biztosan nem választja be az algoritmus a minimális feszítőfába.
Az $A C$ élet biztosan beválasztja az algoritmus a minimális feszítőfába, bármi is $x$ értéke.
Az $A C$ élet biztosan nem választja be az algoritmus a minimális feszítőfába, bármi is $x$ értéke.
Az algoritmus biztosan beválaszt legalább egy 3 súlyú élet a minimális feszítőfába.

Egy $n \times n$ -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 $T [i, j] (1 \leq i, j \leq n$ esetén) azt, hogy az $i$ -edik sor $j$ -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 $T [1, j] = 1$ minden $1 \leq j \leq n$ esetén és hasonlóan, mivel az első oszlop minden cellájába is egy út vezet, ezért $T [i, 1] = 1$ minden $1 \leq i \leq n$ esetén. Melyik rekurziós képlet a helyes a többi $T [i, j]$ érték meghatározására?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

$T [i, j] = T [i - 1, j] + T [i, j - 1] + T [i - 1, j - 1]$
$T [i, j] = \max {T [i - 1, j], T [i, j - 1], T [i - 1, j - 1]}$
$T [i, j] = T [i - 1, j] + T [i, j - 1] + T [i - 1, j - 1] + 1$
$T [i, j] = T [i - 1, j - 1] + 1$

Az előző feladat folytatása:

A teljesen kitöltött $T$ 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?

Típus: egy. Válasz: 5. Pontozás: nincs megadva.

$\max_{1 < i < n} T [i, n]$ adja meg ezt.
$Σ_{i = 1}^{n} T [i, n]$ adja meg ezt.
$T [n, n]$ adja meg ezt.
$\max_{1 \leq j \leq n} T [n, j]$ adja meg ezt
$Σ_{j = 1}^{n} T [n, j]$ adja meg ezt.

Tekintsük az alábbi három függvényt (itt a $l o g$ függvény mindig kettes alapú logaritmust jelöl): (2022 jan)

$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$

Az alábbiak közül melyik állítás igaz ezen három függvény nagyságrendjére?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

$f (n) \notin O (h (n))$ és $g (n) \in O (h (n))$
$f (n) \in O (h (n))$ és $g (n) \notin O (h (n))$
$f (n) \in O (h (n))$ és $g (n) \in O (h (n))$
$f (n) \notin O (h (n))$ és $g (n) \notin O (h (n))$

Adott egy egész számokat tartalmazó $A [1 : n]$ tömb, melyben nem szerepel 0. (2023 jun)

Az $A [1 : n]$ tömb alapján egy $P [1 : n]$ és egy $N [1 : n]$ tömböt töltünk ki a következőképpen:

ha $A [1] > 0$ akkor $P [1] = A [1]$ és $N [1] = A [1]$ .
ha $A [1] \leq 0$ akkor $P [1] = 0$ és $N [1] = A [1]$

A további értékeket $(i > 2)$ így számoljuk:

ha $A [i] > 0$ akkor $P [i] = P [i - 1] + A [i]$ és $N [i] = \max {N [i - 1] + A [i], A [i]}$
ha $A [i] \leq 0$ akkor $P [i] = 0$ és $N [i] = P [i - 1] + A [i]$

Melyik állítás igaz az alábbiak közül a kiszámolt $P [i]$ és $N [i]$ értékek jelentésére?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

$N [i]$ megadja a legnagyobb összeget, amit valamelyik, legfeljebb egy negatív számot tartalmazó $A [j : i]$ résztömbből ( $1 \leq j \leq i)$ kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
$P [i]$ megadja a legnagyobb összeget, amit valamelyik $A [j : i]$ résztömbből $(1 \leq j \leq i)$ kaphatunk úgy, ha a résztömb minden elemét összeadjuk.
$N [i]$ megadja az $A [1 : i]$ tömbben szereplö összes negatív szám összegét
$P [i]$ megadja az $A [1 : i]$ tömbben szereplö összes szám összegét

Az $X$ eldöntési problémáról azt tudjuk, hogy $N P$ -ben van, az $Y$ eldöntési problémáról pedig azt, hogy $N P$ -teljes. (2023 jun)

Mi igaz az alábbiak közül, ha feltételezzük, hogy $P \neq N P$ ?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

Minden olyan eldöntési probléma, ami Karp-redukálható $Y$ -ra, az Karp-redukálható $X$ -re is.
$Y$ biztosan Karp-redukálható $X$ -re. $^{X}$
Ha $X$ Karp-redukálható $Y$ -ra, akkor $X$ nincsen $P$ -ben.
Ha $Y$ Karp-redukálható $X$ -re, akkor az $X$ probléma $N P$ -teljes.

$2 n$ darab különböző csokiból hányféleképpen tudunk kiválasztani $n$ darabot úgy, hogy a három kedvenc csokink a kiválasztottak között legyen? (2023 jun)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

$(\begin{array}{c} 2 n \\ n \end{array}) \cdot (\begin{array}{l} n \\ 3 \end{array})$
$(2 n - 3) \cdot (2 n - 4) \cdot \dots \cdot (n - 2)$
$(\begin{array}{c} 2 n - 3 \\ n \end{array})$
$(\begin{array}{c} 2 n \\ n \end{array}) \cdot \frac{1}{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: $A B, B D, A F, F E, E C, F G, G H$ . Mi igaz a csúcs fokszámára az alábbiak közül? (2022 jan)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

$H$ fokszáma lehet 1 vagy 2, és más nem lehet
$H$ fokszáma lehet 1, 2, 3 vagy 4, és más nem lehet
$H$ fokszáma lehet 1, 2 vagy 3, és más nem lehet
$H$ fokszáma lehet 1, 2, 3, 4 vagy 5, és más nem lehet

Tekintsük az alábbi három függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jan)

$f (n) = n! + 10 \cdot n^{2} - 3$

$g (n) = \frac{1}{8} n^{n} + 9 \cdot \log n$

$h (n) = 1 0^{1000} \cdot n^{1000} + 37 \cdot n^{3} + 42$

Az alábbiak közül melyik állitás igaz ezen három függvény nagyságrendjére?

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

$f (n) \in O (g (n)) és g (n) \in O (h (n))$
$f (n) \in O (g (n)) és g (n) \notin O (h (n))$
$f (n) \notin O (g (n)) és g (n) \in O (h (n))$
$f (n) \notin O (g (n)) és g (n) \notin O (h (n))$

Egy ország térképe egy élsúlyozott, irányítatlan $n$ csúcsú $G$ 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 $k$ érték esetén azt szeretnénk eldönteni, hogy igaz-e, hogy bármelyik településről van $k$ 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 $O (n^{2})$ lépésben?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

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.

Adott egy 200 elemű $T [1 : 200]$ tömb, amiben $T [3 i] = i$ minden $1 \leq i \leq 66$ esetén, minden egyéb esetben (azaz amikor az index nem többszöröse a 3-nak) pedig $T [j] = - 1$ . (2023 jan)

Definiáljuk az $A$ tömböt a következőképpen: $A [1] = T [1]$

és $1 \leq j \leq 200$ esetén $A [j] = \max {A [j - 1] + T [j], T [j]}$ .

Mennyi $A [4]$ értéke?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

1
$- 1$
$- 2$
0

Az előző feladat folytatása: Mi igaz az alábbiak közül a kitöltött $A [1 : 200]$ tömb elemeire?

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

$A [j] = A [j - 1]$ teljesül legalább 50 esetben
$A [j] = T [j]$ teljesül legalább 50 esetben
$A [j] > 0$ teljesül legalább 50 esetben $✓$
$A [200]$ a legnagyobb érték az $A [1 : 200]$ tömbben.

Nézzük a következő két problémát: (2021 jan)

Legközelebbi pár: Adott $n$ szám egy rendezetlen tömbben. Határozzuk meg, hogy melyik két elem értéke van legközelebb egymáshoz. Legtávolabbi pár: Adott $n$ szám egy rendezetlen tömbben. Határozzuk meg, hogy melyik két elem értéke van legtávolabb egymástól. A megengedett lépések legyenek: két elem összehasonlítása, két elem távolságának (azaz különbségének) a meghatározása, két elemcseréje a tömbben.

Tekintsük a követkető állításokat:

A: A Legközelebbi pár feladat megoldható a cseréken túl $O (n \log n)$ lépésben.

B: A Legközelebbi pár feladat megoldható a cseréken túl $O (n^{2})$ lépésben.

C: A Legtávolabbi pár feladat megoldható a cseréken túl $O (n)$ lépésben.

D: A Legtávolabbi pár feladat megoldható a cseréken túl $O (n \log n)$ lépésben.

Melyik helyes az alábbiak közül?

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

Csak az A.
Mind a négy igaz.
Csak az A, a B és a D.
Csak a B és a D.

Adott $n$ tárgy, tudjuk, hogy az $i$ -ediknek a súlya $s_{i}$ kilogramm, az értéke $v_{i}$ forint, az $s_{i}, v_{i}$ számok pozitív egészek. (2021 jan)

Azt szeretnénk eldönteni, hogy ki lehet-e közülük választani néhányat úgy, hogy ezek berakhatók legyenek egy összesen 100 kg teherbírású zsákba, és a kiválasztott tárgyak értékeinek összege legalább 2021 Ft legyen. Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy $P \neq N P$ ?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

A probléma $P$ -ben és $N P$ -ben is benne van.
A probléma $P$ -ben van és $N P$ -teljes.
A probléma $N P$ -teljes és nincs $P$ -ben.
A probléma $P$ -ben van, de nincs $N P$ -ben.

Legyen $X$ az az eldöntési probléma, ahol egy irányítatlan $G$ páros gráfról és egy $k$ számról azt szeretnénk eldönteni, hogy van-e $G$ -ben $k$ élű párosítás és legyen $Y$ az a kérdés, ahol egy irányítatlan $G$ gráfról és egy számról azt szeretnénk eldönteni, hogy van-e $G$ -ben $k$ pontból álló klikk (azaz teljes gráf). (2022 jan)

Mi igaz az alábbiak közül, ha feltételezzük, hogy $P \neq N P$ ?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

$X$ Karp-redukálható $Y$ -ra, de $Y$ nem Karp-redukálható $X$ -re.
$X$ nem Karp-redukálható $Y$ -ra, de $Y$ Karp-redukálható $X$ -re.
$X$ Karp-redukálható $Y$ -ra és $Y$ is Karp-redukálható $X$ -re.
$X$ sem Karp-redukálható $Y$ -ra és $Y$ sem Karp-redukálható $X$ -re.

Egy bináris keresőfa preorder bejárása a csúcsokat $5, 2, 4, 12, 8, 7, 10, 20$ sorrendben látogatja meg. (2023 jun)

Melyik igaz az alábbi állítások közül a keresőfára?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

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.

Az alábbi bináris keresőfa csúcsait a posztorder és a preorder bejárás szerinti sorrendben is kiírjuk. (2021 jan)

TODO kép Melyik álítás igaz?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

A 3 előbb jön, mint a 27 mindkét sorrendben.
A 15 megelőzi a 4-et a preorder sorrendben, mert a 15 belső csúcsban van, a 4 pedig levélben.
A 27 megelőzi a 9-et a posztorder sorrendben, mert a 27 levélben van, a 9 pedig belső csúcsban.
A számok növekvő sorrendben vannak a két sorrend egyike szerint.
A 3 után közvetlenül a 4 következik a két sorrend valamelyikében.

Tudjuk, hogy az $𝒜$ probléma $N P$ -teljes, a $ℬ$ probléma pedig $N P$ -beli, de nem feltétlenül $N P$ -teljes. (2021 jan)

Tekintsük a következő álításokat:

A: Ha az $𝒜$ problémára van polinom idejü algoritmus, akkor $P = N P$ .

B: Ha a $ℬ$ problémára van polinom idejú algoritmus, akkor $P = N P$ .

C: Ha az $𝒜$ problémára van polinom idejú algoritmus, akkor a $ℬ$ problémára is van polinom idejú algoritmus.

Melyik helyes az alábbiak közül?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

Csak az A és a C igaz.
Csak az A igaz.
Az A, B, C mindegyike igaz.
Csak a B igaz.
Csak az A és a B igaz.

Az $n$ csúcsú $G = (V, E)$ irányítatlan gráfra igaz, hogy bárhogyan is sorolunk fel $(v_{1}, v_{2}, \dots, v_{k})$ csupa különböző $G$ -beli csúcsokat, ahol $3 \leq k \leq n$ a ${v_{1}, v_{2}}, {v_{2}, v_{3}}, \dots, {v_{k - 1}, v_{k}}$ és ${v_{k}, v_{1}}$ párok közül legalább az egyik benne van $G$ élhalmazában. Melyik állítás igaz az alábbiak közül? (2023 jun)

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

$G$ komplementerében nincsen kör.
$G$ -ben van kör.
$G$ -ben nincsen $k$ méretű független ponthalmaz.
$G$ komplementerében nincsen $k$ -as klikk.

Az $𝒜$ algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, $n$ -nek a függvényében $O (n^{2})$ . (2022 jun)

Melyik nem igaz az alábbiak közül?

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken $𝒜$ lépésszáma kisebb, mint $n^{3}$ .
Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken $𝒜$ lépésszáma nagyobb, mint $n^{3}$ .
Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken $𝒜$ lépésszáma kisebb, mint $n$ .
Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken $𝒜$ lépésszáma nagyobb, mint $n$ .

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)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

$5, 9, 1, 7, 3, 4$
$5, 7, 4, 9, 3, 1$
$5, 3, 4, 9, 1, 7$
$5, 4, 7, 3, 9, 1$

Legyen $G (V, E)$ egy egyszerú, irányítatlan gráf. Tekintsük a következő tulajdonságot: (2021 jan)

Vannak olyan $X \subseteq V$ és $Y \subseteq V$ nemüres halmazok, melyekre igaz, hogy

$X \cap Y = \emptyset$
$X \cup Y = V$
bármely ${u, v} \in E$ él esetén az ${u, v} \cap X$ halmaz egy elemú.

Az alábbiak közül melyik írja le pontosan a megadott tulajdonságú gráfokat?

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

Nincsen egyetlen éle sem a gráfnak.
A gráf páros gráf, de nem feltétlenül teljes páros gráf
A gráf teljes páros gráf
A gráf teljes gráf.
A gráfban van teljes párosítás

Tekintsük azt a $K_{20, 40}$ teljes páros gráfot, melynek $A = {a_{1}, a_{2}, \dots, a_{20}}$ és $B = {b_{1}, b_{2}, \dots, b_{40}}$ 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 $(a_{i}, b_{j})$ élekből áll.) (2022 jun)

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

$(\begin{array}{l} 40 \\ 20 \end{array}) \cdot 20$ !
$(\begin{array}{l} 40 \\ 20 \end{array})$
$4 0^{20}$
$40!$

Legyen $X$ egy $n$ elemú véges halmaz, $n > 0$ . Hány páratlan elemú részhalmaza van $X$ -nek? (2021 jan)

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

$n$
$2^{⌊ n / 2 ⌋}$
$2^{n - 1}$
$2^{n}$
Más a formula attól függően, hogy $n$ páros vagy páratlan.

Tekintsük azt az eldöntési feladatot, ahol egy irányítatlan $G$ gráfról azt szeretnénk eldönteni, hogy hozzá lehet-e adni legfeljebb 5 élet $G$ -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 $P \neq N P$ ?

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

A probléma $P$ -ben van, de nincs $N P$ -ben.
A probléma $N P$ -teljes és nincs $P$ -ben.
A probléma $P$ -ben van és $N P$ -teljes.
A probléma $P$ -ben és $N P$ -ben is benne van.

Eldöntési feladatok (2023 jun)

Az $X_{1}$ eldöntési feladatban egy irányítatlan $G$ gráfról azt szeretnénk eldönteni, hogy van-e $G$ -ben pontosan 4 élü kör. Az $X_{2}$ eldöntési feladatban egy irányítatlan $G$ gráfról és egy pozitív egész $k$ számról azt szeretnénk eldönteni, hogy van-e $G$ -ben pontosan $k$ élü kör. Melyik állítás igaz az alábbiak közül, ha feltesszük, hogy $P \neq N P$ ?

Típus: egy. Válasz: 1. Pontozás: nincs megadva.

$X_{1} \in P$ és $X_{2} \in N P ∖ P ✓$
$X_{1} \in P$ és $X_{2} \in P$
$X_{1} \in coN P$ de $X_{1} \notin P$
$X_{1} \in P$ de $X_{1} \notin N P$

Tekintsük azt a feladatot, ahol egy $n > 100$ csúcsú irányított $G$ 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 $P \neq N P$ ?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

A probléma $P$ -ben van, de nincs $N P$ -ben.
A probléma $N P$ -teljes és nincs $P$ -ben.
A probléma $P$ -ben van és $N P$ -teljes.
A probléma $P$ -ben és $N P$ -ben is benne van.

Legyen $X$ a Értelmezés sikertelen (formai hiba): {\displaystyle 2SZÍN} eldöntési probléma, azaz ahol egy egyszerü, irányítatlan $G$ 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 $Y$ eldöntési problémában pedig azt kell eldöntenünk $n$ 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 $P \neq N P$ ?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

$X$ nem Karp-redukálható $Y$ -ra, de $Y$ Karp-redukálható $X$ -re.
$X$ Karp-redukálható $Y$ -ra és $Y$ is Karp-redukálható $X$ -re.
$X$ sem Karp-redukálható $Y$ -ra és $Y$ sem Karp-redukálható $X$ -re.
$X$ Karp-redukálható $Y$ -ra, de $Y$ nem Karp-redukálható $X$ -re.

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: $A B, A C, A D, C E, D F, E H, F G$ . (2023 jan)

Melyik csúcs lehet szomszédja az $F$ csúcsnak a gráfban?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

A
B
C
E

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): $10, 5, x, 7, 8$ . Az alábbiak közül mi igaz x értékére? (2022 jan)

Típus: egy. Válasz: 2. Pontozás: nincs megadva.

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

Tekintsük az alábbi két függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jun)

$f (n) = 2023 \cdot n^{2} \cdot \log n - 100 \cdot \sqrt{n}$

$g (n) = \frac{1}{1 0^{10}} \cdot n^{3} + 82 \cdot n \cdot \log n$

Az alábbiak közül melyik állítás igaz?

Típus: egy. Válasz: 3. Pontozás: nincs megadva.

$f (n) \in O (g (n))$ , mert mindkét függvényre igaz, hogy $O (n^{3})$
$f (n) \in O (g (n))$ , mert $f (n) \in O (n^{2})$ és $g (n) \in O (n^{3})$
$f (n) \in O (g (n))$ , de az előző két indoklás egyike sem helyes
$f (n) \notin O (g (n))$

Egy ország térképe egy élsúlyozott, irányítatlan $G$ 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 $A$ csomópont, ahol éppen tartózkodunk és tudjuk hogy $B$ liter benzinünk van. Melyik tanult algoritmussal lehet meghatározni, hogy az ország mely városaiba tudunk eljutni tankolás nélkül?

Típus: egy. Válasz: 4. Pontozás: nincs megadva.

BFS-t, azaz szélességi bejárást kell futtatni az $A$ csúcsból.
Kruskal algoritmust kell futtatni a gráfon.
DFS-t, azaz mélységi bejárást kell futtatni az $A$ csúcsból.
Dijkstra algoritmust kell futtatni az $A$ csúcsból.

Statisztika

Kvízek használata, importálása, fejlesztése.
Átlagteljesítmény
Eddigi kérdések	0
Kapott pontok	0
Alapbeállított pontozás	(-)

Beállítások
Minden kérdés látszik
Véletlenszerű sorrend

Záróvizsga kvíz - Algoritmusok

Egy város úthálózatát a G egyszerú, irányítatlan, összefüggő gráf írja le, a gráf csúcsai a csomópontok, az élek az ezeket összekötőútszakaszokat jelölik. (2021 jan)

Pozitív egész számokat szeretnénk tárolni valami adatszerkezet segítségével úgy, hogy n tárolt elem esetén tetszőleges x egész számról O(log⁡n) lépésben meg tudjuk mondani, hogy igaz-e rá, hogy x a tárolt számok között van, de sem x−1 , sem x+1 nincsen. (2022 jun)

Adott egy n hosszú számsorozat, a1,a2,…,an. (2021 jan)

A G 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)

Adott egy 3n 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)

Melyik állítás igaz az alábbi négy függvény nagyságrendjére? (2021 jan)

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)

Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű {a,b,c,d} ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan)

A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk C=10 -es hátizsák kapacitással. A táblázat i=7 -es sora az értékekkel így néz ki: (2022 jan)

A 4,3,2,1,5,6,7,8 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)

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 0,1,2,3,4,5,6,7,8,9 halmazból. További megkötés nincs a rendszámokra. (2023 jan)

Egy k és egy ℓ 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)

Az alábbi állítások közül pontosan egy hamis. Válassza ki a HAMIS állítást! (2021 jan)

Egy csupa különböző egész számot tartalmazó T tömbben akarjuk eldönteni egy adott x elemről, hogy igaz-e, hogy x és 2⋅x is szerepel T-ben. Az alábbi négy állítás közül melyek igazak? (2023 jan)

A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (2022 jun)

Radix rendezéssel rendezzük az alábbi sorozatot: s1=abac,s2=acbc,s3=bcac,s4=bbbb,s5=cacb (a karakterek mindegyik pozícióban a 3-elemű {a,b,c} ábécéből kerülnek ki). (2023 jun)

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)

Tekintsük azt az eldöntési feladatot, ahol egy irányított G gráfról azt szeretnénk eldönteni, hogy van-e két olyan s és t csúcsa, hogy s -ből van irányított út t -be, de t -ből nincsen irányított út s -be (2022 jan)

Az 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 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)

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)

Kruskal algoritmusát futtatjuk az alábbi gráfon. (2023 jun)

Egy n×n -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)

Tekintsük az alábbi három függvényt (itt a log függvény mindig kettes alapú logaritmust jelöl): (2022 jan)

Adott egy egész számokat tartalmazó A[1:n] tömb, melyben nem szerepel 0. (2023 jun)

Az X eldöntési problémáról azt tudjuk, hogy NP -ben van, az Y eldöntési problémáról pedig azt, hogy NP -teljes. (2023 jun)

2n darab különböző csokiból hányféleképpen tudunk kiválasztani n darabot úgy, hogy a három kedvenc csokink a kiválasztottak között legyen? (2023 jun)

Tekintsük az alábbi három függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jan)

Egy ország térképe egy élsúlyozott, irányítatlan n csúcsú G 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)

Adott egy 200 elemű T[1:200] tömb, amiben T[3i]=i minden 1≤i≤66 esetén, minden egyéb esetben (azaz amikor az index nem többszöröse a 3-nak) pedig T[j]=−1. (2023 jan)

Nézzük a következő két problémát: (2021 jan)

Adott n tárgy, tudjuk, hogy az i-ediknek a súlya si kilogramm, az értéke vi forint, az si,vi számok pozitív egészek. (2021 jan)

Egy bináris keresőfa preorder bejárása a csúcsokat 5,2,4,12,8,7,10,20 sorrendben látogatja meg. (2023 jun)

Az alábbi bináris keresőfa csúcsait a posztorder és a preorder bejárás szerinti sorrendben is kiírjuk. (2021 jan)

Tudjuk, hogy az 𝒜 probléma NP-teljes, a ℬ probléma pedig NP-beli, de nem feltétlenül NP-teljes. (2021 jan)

Az 𝒜 algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, n -nek a függvényében O(n2) . (2022 jun)

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)

Legyen G(V,E) egy egyszerú, irányítatlan gráf. Tekintsük a következő tulajdonságot: (2021 jan)

Tekintsük azt a K20,40 teljes páros gráfot, melynek A={a1,a2,…,a20} és B={b1,b2,…,b40} 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 (ai,bj) élekből áll.) (2022 jun)

Legyen X egy n elemú véges halmaz, n>0. Hány páratlan elemú részhalmaza van X-nek? (2021 jan)

Eldöntési feladatok (2023 jun)

Tekintsük azt a feladatot, ahol egy n>100 csúcsú irányított G 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)

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: AB,AC,AD,CE,DF,EH,FG. (2023 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): 10,5,x,7,8 . Az alábbiak közül mi igaz x értékére? (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)

Egy ország térképe egy élsúlyozott, irányítatlan G 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)

Egy város úthálózatát a $G$ egyszerú, irányítatlan, összefüggő gráf írja le, a gráf csúcsai a csomópontok, az élek az ezeket összekötőútszakaszokat jelölik. (2021 jan)

Adott egy $n$ hosszú számsorozat, $a_{1}, a_{2}, \dots, a_{n}$ . (2021 jan)

A $G$ 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)

Adott egy $3 n$ 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)

Radix rendezéssel rendezünk 5 hosszú karaktersorozatokat, ahol a karakterek mindegyik pozícióban a 4-elemű ${a, b, c, d}$ ábécéből kerülnek ki. Mi igaz ekkor a radix rendezés során használt ládarendezésekre? (2022 jan)

A hátizsák feladatra tanult dinamikus programozást használó algoritmust futtatjuk $C = 10$ -es hátizsák kapacitással. A táblázat $i = 7$ -es sora az értékekkel így néz ki: (2022 jan)

A $4, 3, 2, 1, 5, 6, 7, 8$ 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)

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 $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ halmazból. További megkötés nincs a rendszámokra. (2023 jan)

Egy $k$ és egy $ℓ$ 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)

Egy csupa különböző egész számot tartalmazó $T$ tömbben akarjuk eldönteni egy adott $x$ elemről, hogy igaz-e, hogy $x$ és $2 \cdot x$ is szerepel $T$ -ben. Az alábbi négy állítás közül melyek igazak? (2023 jan)

Radix rendezéssel rendezzük az alábbi sorozatot: $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$ (a karakterek mindegyik pozícióban a 3-elemű ${a, b, c}$ ábécéből kerülnek ki). (2023 jun)

Tekintsük azt az eldöntési feladatot, ahol egy irányított $G$ gráfról azt szeretnénk eldönteni, hogy van-e két olyan $s$ és $t$ csúcsa, hogy $s$ -ből van irányított út $t$ -be, de $t$ -ből nincsen irányított út $s$ -be (2022 jan)

Az $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16$ 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)

Egy $n \times n$ -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)

Tekintsük az alábbi három függvényt (itt a $l o g$ függvény mindig kettes alapú logaritmust jelöl): (2022 jan)

Adott egy egész számokat tartalmazó $A [1 : n]$ tömb, melyben nem szerepel 0. (2023 jun)

Az $X$ eldöntési problémáról azt tudjuk, hogy $N P$ -ben van, az $Y$ eldöntési problémáról pedig azt, hogy $N P$ -teljes. (2023 jun)

$2 n$ darab különböző csokiból hányféleképpen tudunk kiválasztani $n$ darabot úgy, hogy a három kedvenc csokink a kiválasztottak között legyen? (2023 jun)

Egy ország térképe egy élsúlyozott, irányítatlan $n$ csúcsú $G$ 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)

Adott egy 200 elemű $T [1 : 200]$ tömb, amiben $T [3 i] = i$ minden $1 \leq i \leq 66$ esetén, minden egyéb esetben (azaz amikor az index nem többszöröse a 3-nak) pedig $T [j] = - 1$ . (2023 jan)

Adott $n$ tárgy, tudjuk, hogy az $i$ -ediknek a súlya $s_{i}$ kilogramm, az értéke $v_{i}$ forint, az $s_{i}, v_{i}$ számok pozitív egészek. (2021 jan)

Egy bináris keresőfa preorder bejárása a csúcsokat $5, 2, 4, 12, 8, 7, 10, 20$ sorrendben látogatja meg. (2023 jun)

Tudjuk, hogy az $𝒜$ probléma $N P$ -teljes, a $ℬ$ probléma pedig $N P$ -beli, de nem feltétlenül $N P$ -teljes. (2021 jan)

Az $𝒜$ algoritmusról tudjuk, hogy lépésszáma a bemenet hosszának, $n$ -nek a függvényében $O (n^{2})$ . (2022 jun)

Legyen $G (V, E)$ egy egyszerú, irányítatlan gráf. Tekintsük a következő tulajdonságot: (2021 jan)

Legyen $X$ egy $n$ elemú véges halmaz, $n > 0$ . Hány páratlan elemú részhalmaza van $X$ -nek? (2021 jan)

Tekintsük azt a feladatot, ahol egy $n > 100$ csúcsú irányított $G$ 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)

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: $A B, A C, A D, C E, D F, E H, F G$ . (2023 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): $10, 5, x, 7, 8$ . Az alábbiak közül mi igaz x értékére? (2022 jan)

Egy ország térképe egy élsúlyozott, irányítatlan $G$ 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)