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

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?

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.

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)

12
7
4
8

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)

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

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 [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?

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

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

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

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.

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?

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.

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

$(\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 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)

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

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?

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

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)

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.

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.

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.)

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

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)

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

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

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

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

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

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)

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

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

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

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

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)

$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

Bejelentkezés

Keresés

Záróvizsga kvíz - Algoritmusok

Névterek

Több

Lapműveletek

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)

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 $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 két függvényt (itt a log függvény kettes alapú logaritmust jelöl): (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)

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)

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

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)

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)

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)

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)

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)

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

Navigáció

Navigáció

Egyetem

Wikieszközök

Wikieszközök

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

Bejelentkezés

Keresés

Záróvizsga kvíz - Algoritmusok

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)

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)

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)

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 két függvényt (itt a log függvény kettes alapú logaritmust jelöl): (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)

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)

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)

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)

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

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)

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)

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)

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)

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

Navigáció

Wikieszközök

Eszközök

Kategóriák

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)

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

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)

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

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)

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)

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)

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