Test z ADŠ 2019/2020


  1. Zapíš funkciu mix(gen1, gen2), ktorá generuje prvky oboch generatorov gen1 a gen2 na striedačku. Ak v jednom z nich skončí skôr, tak už berie len zvyšné z druhého. Ulohu rieš bez pomocného zoznamu len pomocou štandardných funkcií iter() a next():

    def mix(gen1, gen2):
    
    
    
    
    .
    

  1. Z daného zoznamu vyrob haldu algoritmom heapify:

    zoz = [8, 13, 7, 10, 5, 15, 12, 17, 9, 14, 4, 11, 18, 16, 6]
    heapify(zoz)
    

    Tento algoritmus zrejme prerába zoznam od konca. Do prvého riadku tabuľky zapíš obsah zoznamu po spracovaní prvku s hodnotou 15 a do druhého riadku výslednú haldu:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    po hodnote 15

    výsledná halda


  1. Do hashovacej tabulky sa postupne vkladali kľúče (2, 3, 5, 7, 11, 22, 23, 25, 27, 31, 42, 43, 45, 47, 51). Tabuľka má veľkosť n=20. Zaplň túto tabuľku, ak funkcia hash = lambda x: x%n:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    kľúče


  1. Koľko roznych AVL stromov existuje, ktoré sú zložené len z prvkov {1, 2, 3, 4, 5, 6} a v ktorých je vrchol s hodnotou 3 v koreni stromu? Nakresli tieto AVL stromy.



  1. Algoritmus quick-sort sme prepísali na nerekurzivnu funkciu (na stack sme použili pythonovský list):

    def quick_sort(pole):
        stack = __________________________
        while __________________________:
            z, k = __________________________
            if z < k:
                index = z
                pivot = pole[z]
                for i in range(z+1, k+1):
                    if pole[i] < pivot:
                        index += 1
                        pole[index], pole[i] = pole[i], pole[index]
                pole[index], pole[z] = pole[z], pole[index]
                stack.__________________________
                stack.__________________________
    

    Doplň chýbajúce časti. Aká je zložitosť tohto algoritmu pre pole = [5] * n? Aká je pamäťová zložitosť algoritmu v tomto prípade (teda maximálna veľkosť zásobníka)?


  1. Zakresli binárny strom, ktorý vznikne pri huffmanovom kódovaní. Tiež pre každý symbol zapíš jeho výsledný kód (postupnosť 0 a 1), ak frekvencie vyskytov symbolov sú:

    a=1, b=2, c=4, d=8, e=16
    


  1. Máme danú funkciu:

    def fun(n):
        if n < 2:
            return n
        return fun(n-1) + 2 * fun(n-2)
    

    Potrebujeme ju vylepšiť pomocou memoizácie. Lenže namiesto asociatívneho poľa mem tu využijeme množinu. Zapíš takúto memoizáciu, ale nepouži žiadnu ďalšiu pomocnú štruktúru:

    def fun(n, mem=set()):
    
    
    
    
    
    .
    

    Aká je zložitosť tejto funkcie?


  1. Nakresli zhusteny sufixovy strom zo slova 'kolokolo'.



  1. Spustili sme Dijkstrov algoritmus (ten vypočítal hodnoty d) a do každého vrcholu grafu sme teraz zapísali takto vypočítanú hodnotu:

    _images/test19_1.png

    Zakresli do grafu najkratšiu cestu z ľavého horného vrcholu do pravého spodného, ktorú vypočítal dijkstrov algoritmus.


  1. Disjunktné množíny sme reprezentovali pomocou „stromčekov“. Momentálny stav disjunktných množín je:

    _images/10_4.png

    Vykonali sme tieto dve operácie: UNION(1,5) a UNION(2,5). Zakresli, ako sa teraz zmenili tieto „stromčeky“. Použili sme tento algoritmus:

    def FIND(p):
        while p != p.parent: p = p.parent
        return p
    
    def UNION(p, q):
        r1, r2 = FIND(p), FIND(q)
        if r1 != r2:
            if r1.rank > r2.rank: r2.parent = r1
            else:
                r1.parent = r2
                if r1.rank == r2.rank: r2.rank += 1