„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés

	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

← Régebbi szerkesztés Újabb szerkesztés →

VizuálisWikiszöveges

A lap 2023. december 11., 22:51-kori változata

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

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$

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

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

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.

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.

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

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

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

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

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?

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

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

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.

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

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.

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.

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

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

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)

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

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

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

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.

@@ 29. sor: / 29. sor: @@
 # <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>
+== 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?
+{{Kvízkérdés|típus=egy|válasz=1}}
+# 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) ==
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 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) ==
+[[Fájl:2022 jun info zv adatb fagraf.png|keretnélküli]]
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <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>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> ?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 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) ==
+[[Fájl:2022 jun info zv algoritmusok graf.png|keretnélküli]]
+{{Kvízkérdés|típus=egy|válasz=1}}
+# <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.
+# 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).
+# 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.

Bejelentkezés

Keresés

„Záróvizsga kvíz - Algoritmusok” változatai közötti eltérés

Névterek

Több

Lapműveletek

A lap 2023. december 11., 22:51-kori változata

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)

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

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

A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (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 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)

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)

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)

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)

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

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

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” változatai közötti eltérés

A lap 2023. december 11., 22:51-kori változata

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)

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

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

A megadottak közül melyik egy topologikus sorrendje az ábrán látható gráfnak? (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 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)

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)

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

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)

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

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

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)

Navigáció

Wikieszközök

Eszközök

Kategóriák

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

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)

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)

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)

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)

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