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

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

VizuálisWikiszöveges

@@ 98. sor: / 98. sor: @@
 # <math>P[i]</math> megadja az <math>A[1: i]</math> tömbben szereplö összes szám összegét
+== 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: <math>AB, AC, AD, CE, DF, EH, FG</math>. (2023 jan) ==
+Melyik csúcs lehet szomszédja az <math>F</math> csúcsnak a gráfban?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# A
+# B
+# C
+# E
+== Tekintsük az alábbi három függvényt (itt a log függvény kettes alapú logaritmust jelöl): (2023 jan) ==
+<math>f(n)=n !+10 \cdot n^{2}-3</math>
+<math>g(n)=\frac{1}{8} n^{n}+9 \cdot \log n</math>
+<math>h(n)=10^{1000} \cdot n^{1000}+37 \cdot n^{3}+42</math>
+Az alábbiak közül melyik állitás igaz ezen három függvény nagyságrendjére?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>f(n) \in O(g(n)) \text { és } g(n) \in O(h(n))</math>
+# <math>f(n) \in O(g(n)) \text { és } g(n) \notin O(h(n))</math>
+# <math>f(n) \notin O(g(n)) \text { és } g(n) \in O(h(n))</math>
+# <math>f(n) \notin O(g(n)) \text { és } g(n) \notin O(h(n))</math>
+== 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) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+# 2 helyett álljon 4
+# 7 helyett álljon 8
+# 5 helyett álljon 1
+# 10 helyett álljon 1
+== Egy <math>k</math> és egy <math>\ell</math> 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) ==
+{{Kvízkérdés|típus=egy|válasz=3}}
+<math>k \cdot \ell</math>
+<math>k+\ell-1</math>
+<math>\max \{k, \ell\}</math>
+<math>k+\ell x</math>
+== Egy csupa különböző egész számot tartalmazó <math>T</math> tömbben akarjuk eldönteni egy adott <math>x</math> elemről, hogy igaz-e, hogy <math>x</math> és <math>2 \cdot x</math> is szerepel <math>T</math>-ben. Az alábbi négy állítás közül melyek igazak? (2023 jan) ==
+A: Ez megtehető <math>O(n)</math> lépésben, ha a tömb rendezett.
+B: Ez megtehető <math>O(\log n)</math> lépésben, ha a tömb rendezett.
+C: Ez megtehető <math>O(n)</math> lépésben tetszőleges tömb esetén.
+D: Ez megtehető <math>O(\log n)</math> lépésben tetszőleges tömb esetén.
+{{Kvízkérdés|típus=egy|válasz=2}}
+# Csak az <math>A, B</math> állítások igazak.
+# Csak az <math>A, B, C</math> állítások igazak.
+# Mind a négy igaz.
+# Csak az <math>A, C</math> állítások igazak.
+== 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 <math>0,1,2,3,4,5,6,7,8,9</math> 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 ?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>3 \cdot 26+2 \cdot 10</math>
+# <math>26^{3} \cdot 10^{2}</math>
+# <math>26^{3}+10^{2}</math>
+# <math>3 \cdot 2 \cdot 26 \cdot 10</math>
+== Adott egy 200 elemű <math>T[1: 200]</math> tömb, amiben <math>T[3 i]=i</math> minden <math>1 \leq i \leq 66</math> esetén, minden egyéb esetben (azaz amikor az index nem többszöröse a 3-nak) pedig <math>T[j]=-1</math>. (2023 jan) ==
+Definiáljuk az <math>A</math> tömböt a következőképpen:
+<math>A[1]=T[1]</math>
+és <math>1 \le j \leq 200</math> esetén <math>A[j]=\max \{A[j-1]+T[j], T[j]\}</math>.
+Mennyi <math>A[4]</math> értéke?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# 1
+# <math>-1</math>
+# <math>-2</math>
+# 0
+Az előző feladat folytatása:
+Mi igaz az alábbiak közül a kitöltött <math>A[1: 200]</math> tömb elemeire?
+{{Kvízkérdés|típus=egy|válasz=3}}
+# <math>A[j]=A[j-1]</math> teljesül legalább 50 esetben
+# <math>A[j]=T[j]</math> teljesül legalább 50 esetben
+# <math>A[j]>0</math> teljesül legalább 50 esetben <math>\checkmark</math>
+# <math>A[200]</math> a legnagyobb érték az <math>A[1: 200]</math> tömbben.
+== Egy ország térképe egy élsúlyozott, irányítatlan <math>G</math> 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 <math>A</math> csomópont, ahol éppen tartózkodunk és tudjuk hogy <math>B</math> liter benzinünk van. Melyik tanult algoritmussal lehet meghatározni, hogy az ország mely városaiba tudunk eljutni tankolás nélkül?
+{{Kvízkérdés|típus=egy|válasz=4}}
+# BFS-t, azaz szélességi bejárást kell futtatni az <math>A</math> csúcsból.
+# Kruskal algoritmust kell futtatni a gráfon.
+# DFS-t, azaz mélységi bejárást kell futtatni az <math>A</math> csúcsból.
+# Dijkstra algoritmust kell futtatni az <math>A</math> csúcsból.
+== Legyen <math>X</math> az az eldöntési probléma, melynek inputja egy irányított <math>G</math> gráfból, ezen gráf egy <math>s</math> csúcsából és egy <math>k</math> pozitív egészből áll és azt szeretnénk eldönteni, hogy igaz-e hogy <math>G</math>-ben <math>s</math>-ből minden más csúcsba vezet legfeljebb <math>k</math> élből álló út. Legyen továbbá <math>Y</math> a tanult <math>3-S Z</math> IíN eldöntési feladat. (2023 jan) ==
+Mi igaz az alábbiak közül, ha feltételezzük, hogy <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# <math>X</math> sem Karp-redukálható <math>Y</math>-ra és <math>Y</math> sem 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.
+# <math>X</math> Karp-redukálható <math>Y</math>-ra és <math>Y</math> is Karp-redukálható <math>X</math>-re.
+# <math>X</math> nem Karp-redukálható <math>Y</math>-ra, de <math>Y</math> Karp-redukálható <math>X</math>-re. <math>X</math>
+== Tekintsük azt az eldöntési feladatot, ahol egy irányítatlan <math>G</math> gráfról azt szeretnénk eldönteni, hogy hozzá lehet-e adni legfeljebb 5 élet <math>G</math>-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 <math>P \neq N P</math> ?
+{{Kvízkérdés|típus=egy|válasz=2}}
+# A probléma <math>P</math>-ben van, de nincs <math>NP</math>-ben.
+# A probléma <math>NP</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.
 == 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) ==