WorksheetsProgramování - opakování
Total questions: 8
Worksheet time: 9mins
V rámci kterých datových struktur dokážeme najít prvek v nejhorším případě v čase:
O(log(N))
Halda (heap)
Seznam (List)
Binární vyhledávací strom
AVL strom
Spojový seznam (Linked-list)
Které odpovědi se v Pythonu vyhodnotí jako `True`?
[1] == [1]
[2] is [2]
x = [3]
x is x
x = [4]
x[:] == x
x = [5]
x[:] is x
Které odpovědi obsahují validní kód v Pythonu?
Nechť:
tup = (1, 2, 3)
lis = [1, 2, 3]
tup[0] = 1
tup[-1] = 2
lis[1] = 3
lis[-2] = 4
lis[0] = "ahoj"
Co platí o tomto stromu (s kořenem v 5)?
Je to binární strom
Je to úplný binární strom
Je to binární vyhledávací strom
Je to halda
Co tento program vypíše?
10, 20, 10
10, 20, 20
20, 20, 20
10, 10, 10
Která tvrzení platí o asymptotické časové složitosti?
n∈O(n2)
n2∈O(n)
5n∈O(n)
n∈O(5n)
log(n)∈O(n)
Označte pravdivá tvrzení:
DFS = prohledávání do hloubky
BFS = prohledávání do šířky
BFS v grafech s hranami bez ohodnocení vrátí nejkratší cestu
DFS používá zásobník.
Pokud mezi dvěma vrcholy existuje cesta, tak BFS i DFS jí najde.
BFS v grafech s ohodnocenými hranami vrátí nejkratší cestu
DFS a Dijkstrův algoritmus se chovají stejně v grafech s hranami ohodnocenými 1.
Jakou datovou strukturou lze nejlépe "nahradit" rekurzivní volání funkce?
Nápověda: Při rekurzivním volání funkce si (ve většině případů) musíme stále pamatovat hodnoty proměnných ve všech tělech funkcí. V debugeru třeba můžeme najít "call xyz".
O(log(N))
Halda (heap)
Seznam (list)
Zásobník (stack)
Fronta (queue)
