Záróvizsga kvíz - Algoritmusok

ZVAlgo

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

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}{10^{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.

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

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.

1. A 7 a 12 egyik részfájában van.
2. A 8 a gyökérben van.
3. A 10 a 2 egyik részfájában van.
4. A 2 egy levélbe n van.

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

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

1. $\left({\begin{array}{c}2n\\n\end{array}}\right)\cdot \left({\begin{array}{l}n\\3\end{array}}\right)$
2. $(2n-3)\cdot (2n-4)\cdot \ldots \cdot (n-2)$
3. $\left({\begin{array}{c}2n-3\\n\end{array}}\right)$
4. $\left({\begin{array}{c}2n\\n\end{array}}\right)\cdot {\frac {1}{3!}}$

Radix rendezéssel rendezzük az alábbi sorozatot: $s_{1}=abac,s_{2}=acbc,s_{3}=bcac,s_{4}=bbbb,s_{5}=cacb$ (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.

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

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.

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

Az $n$ csúcsú $G=(V,E)$ irányítatlan gráfra igaz, hogy bárhogyan is sorolunk fel $\left(v_{1},v_{2},\ldots ,v_{k}\right)$ csupa különböző $G$ -beli csúcsokat, ahol $3\leq k\leq n$ a $\left\{v_{1},v_{2}\right\},\left\{v_{2},v_{3}\right\},\ldots ,\left\{v_{k-1},v_{k}\right\}$ és $\left\{v_{k},v_{1}\right\}$ 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.

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

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\left(n^{2}\right)$ lépésben?

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

1. 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.
2. Minden csúcsból futtatunk egy szélességi bejárást (BFS) a legrövidebb utak megkeresésésére.
3. Minden csúcsból lefuttatjuk Dijktsra algoritmusát a legrövidebb utak megkeresésére.
4. 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 $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 NP$ ?

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

1. $X_{1}\in P$ és $X_{2}\in NP\backslash P\checkmark$
2. $X_{1}\in P$ és $X_{2}\in P$
3. $X_{1}\in \operatorname {coN} P$ de $X_{1}\notin P$
4. $X_{1}\in P$ de $X_{1}\notin NP$

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)

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

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

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

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.

1. $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.
2. $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.
3. $N[i]$ megadja az $A[1:i]$ tömbben szereplö összes negatív szám összegét
4. $P[i]$ megadja az $A[1:i]$ tömbben szereplö összes szám összegét

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.

1. 2-3 fa
2. rendezett lista
3. nyílt címzésú hash
4. (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)

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

1. 2
2. 1
3. 7
4. 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)

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

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

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

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

1. A probléma $P$ -ben van, de nincs $NP$ -ben.
2. A probléma $NP$ -teljes és nincs $P$ -ben.
3. A probléma $P$ -ben van és $NP$ -teljes.
4. A probléma $P$ -ben és $NP$ -ben is benne van.

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.

1. $A,B,D,E,F,G,H,C$
2. $A,D,F,G,H,C,E,B$
3. $A,B,C,D,E,F,G,H$
4. $A,D,F,E,B,G,H,C$

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:

1. 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.
2. 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.

1. $T[i,j]=T[i-1,j]+T[i,j-1]+T[i-1,j-1]$
2. $T[i,j]=\max\{T[i-1,j],T[i,j-1],T[i-1,j-1]\}$
3. $T[i,j]=T[i-1,j]+T[i,j-1]+T[i-1,j-1]+1$
4. $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.

1. $\max _{1<i<n}T[i,n]$ adja meg ezt.
2. $\Sigma _{i=1}^{n}T[i,n]$ adja meg ezt.
3. $T[n,n]$ adja meg ezt.
4. $\max _{1\leq j\leq n}T[n,j]$ adja meg ezt
5. $\Sigma _{j=1}^{n}T[n,j]$ adja meg ezt.

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.

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

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

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

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

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

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

1. $\left({\begin{array}{l}40\\20\end{array}}\right)\cdot 20$ !
2. $\left({\begin{array}{l}40\\20\end{array}}\right)$
3. $40^{20}$
4. $40!$

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.

1. 0
2. 64
3. $\left({\begin{array}{c}16\\2\end{array}}\right)$
4. 32

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

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

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

1. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ lépésszáma kisebb, mint $n^{3}$ .
2. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ lépésszáma nagyobb, mint $n^{3}$ .
3. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ lépésszáma kisebb, mint $n$ .
4. Minden $n$ pozitív számhoz lehet olyan $n$ hosszú bemenet, amelyiken ${\mathcal {A}}$ 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)

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

1. x lehet 1 is és 9 is
2. x lehet 6 is és 9 is
3. x lehet 1 is és 6 is
4. 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)

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

1. Az 1 levélben van.
2. A fának 7 szintje van.
3. A legutoljára beszúrt érték levélben van.
4. 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: $AB,BD,AF,FE,EC,FG,GH$ . 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.

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

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)

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

1. ${\frac {n!}{2}}*n!$
2. $n!*n!*n!$
3. $2*n!*n!$
4. $n!*(2n)!$

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.

1. 12
2. 7
3. 4
4. 8

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. 1 ládarendezést használunk $4^{5}$ ládával.
2. 5 ládarendezést használunk, mindegyik esetben 4 ládával.
3. 4 ládarendezést használunk, mindegyik esetben 5 ládával.
4. 1 ládarendezést használunk 20 ládával.

Tekintsük az alábbi három függvényt (itt a $log$ 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.

1. $f(n)\notin O(h(n))$ és $g(n)\in O(h(n))$
2. $f(n)\in O(h(n))$ és $g(n)\notin O(h(n))$
3. $f(n)\in O(h(n))$ és $g(n)\in O(h(n))$
4. $f(n)\notin O(h(n))$ és $g(n)\notin O(h(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 NP$ ?

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

1. A probléma $P$ -ben és $NP$ -ben is benne van.
2. A probléma $P$ -ben van, de nincs $NP$ -ben.
3. A probléma $NP$ -teljes és nincs $P$ -ben.
4. A probléma $P$ -ben van és $NP$ -teljes.

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

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

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

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.

1. $V[8,4]=8{\text{ és }}V[8,9]=17$
2. $V[8,3]=7{\text{ és }}V[8,8]=13$
3. $V[8,4]=8{\text{ és }}V[8,8]=12$
4. $V[8,4]=5{\text{ és }}V[8,8]=12$