Programování - opakování

V rámci kterých datových struktur dokážeme najít prvek v nejhorším případě v čase:
 $O\left(\log\left(N\right)\right)$  

• 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\in O\left(n^2\right)$

• $n^2\in O\left(n\right)$

• $5n\in O\left(n\right)$

• $n\in O\left(5n\right)$

• $\log\left(n\right)\in O\left(n\right)$

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\left(\log\left(N\right)\right)$  

• Halda (heap)
  

• Seznam (list)
  

• Zásobník (stack)
  

• Fronta (queue)