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

A VIK Wikiből
← Régebbi szerkesztésÚjabb szerkesztés →
VizuálisWikiszöveges
kérdések hozzáadása
a válasz javítása
68. sor: 68. sor:


== Legyen <math>X</math> az az eldöntési probléma, ahol egy irányítatlan <math>G</math> páros gráfról és egy <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> élű párosítás és legyen <math>Y</math> az a kérdés, ahol egy irányítatlan <math>G</math> gráfról és egy számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> pontból álló klikk (azaz teljes gráf). (2022 jan) ==
== Legyen <math>X</math> az az eldöntési probléma, ahol egy irányítatlan <math>G</math> páros gráfról és egy <math>k</math> számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> élű párosítás és legyen <math>Y</math> az a kérdés, ahol egy irányítatlan <math>G</math> gráfról és egy számról azt szeretnénk eldönteni, hogy van-e <math>G</math>-ben <math>k</math> pontból álló klikk (azaz teljes gráf). (2022 jan) ==
{{Kvízkérdés|típus=egy|válasz=3}}
{{Kvízkérdés|típus=egy|válasz=1}}
Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq NP</math>?
Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq NP</math>?
# <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re.
# <math>X</math> Karp-redukálható <math>Y</math>-ra, de <math>Y</math> nem Karp-redukálható <math>X</math>-re.
85. sor: 85. sor:
Mi igaz a következő, <math>i = 8</math>-as sor <math>V[8,b]</math> értékeire az alábbiak közül, ha a 8. tárgy <math>w_8</math> súlya <math>5</math>, <math>v_8</math> értéke pedig <math>6</math>?
Mi igaz a következő, <math>i = 8</math>-as sor <math>V[8,b]</math> értékeire az alábbiak közül, ha a 8. tárgy <math>w_8</math> súlya <math>5</math>, <math>v_8</math> értéke pedig <math>6</math>?
(<math>V[i,b]</math> jelentése: az első <math>i</math> tárgyból <math>b</math> hátizsák kapacitás mellett elérhető maximális érték.)
(<math>V[i,b]</math> jelentése: az első <math>i</math> tárgyból <math>b</math> hátizsák kapacitás mellett elérhető maximális érték.)
{{Kvízkérdés|típus=egy|válasz=3}}
{{Kvízkérdés|típus=egy|válasz=2}}
# <math>V[8,4]=8 \text { és } V[8,9]=17</math>
# <math>V[8,4]=8 \text { és } V[8,9]=17</math>
# <math>V[8,3]=7 \text { és } V[8,8]=13</math>
# <math>V[8,3]=7 \text { és } V[8,8]=13</math>
# <math>V[8,4]=8 \text { és } V[8,8]=12</math>
# <math>V[8,4]=8 \text { és } V[8,8]=12</math>
# <math>V[8,4]=5 \text { és } V[8,8]=12</math>
# <math>V[8,4]=5 \text { és } V[8,8]=12</math>

A lap 2023. december 4., 21:09-kori változata

ZVAlgo
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 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≠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.

Adott egy 3n csúcsú teljes gráf, a csúcsok számozottak, az 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ő csúcs piros? (2022 jan)

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

  1. n!2*n!
  2. n!*n!*n!
  3. 2*n!*n!
  4. n!*(2n)!


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)

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

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

  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 a é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 w8 súlya 5, v8 é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 és V[8,9]=17
  2. V[8,3]=7 és V[8,8]=13
  3. V[8,4]=8 és V[8,8]=12
  4. 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.

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

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⋅n2⋅log⁡n+7⋅ng(n)=log⁡n+1000+n⋅(log⁡n)2h(n)=n⋅n+11000⋅n2−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)∉O(h(n)) és g(n)∈O(h(n))
  2. f(n)∈O(h(n)) és g(n)∉O(h(n))
  3. f(n)∈O(h(n)) és g(n)∈O(h(n))
  4. f(n)∉O(h(n)) és g(n)∉O(h(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 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

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.

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 45 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.
A lap eredeti címe: „https://vik.wiki/index.php?title=Záróvizsga_kvíz_-_Algoritmusok&oldid=204972”