Test z ADŠ 2018/2019

  1. Zistiť zložitosť funkcií:

    def fun1(pole):
        vysl = i = j = 0
        while i < len(pole):
            if i < len(pole)-1:
                vysl += pole[i] - pole[i+1]
                i += 1
            else:
                i = j = j+1
        return vysl
    
    def fun2(n):
        if n == 0:
            return 1
        return n * fun2(n - 1)
    
    def fun3(n):
        x, i = 0, n
        while i > 0:
            x += fun3(i)
            i //= 2
        return x
    
    def fun4(n, mem={}):
        if n in mem:
            return mem[n]
        if n < 2:
            res = n
        else:
            res = fun4(n-1) + fun4(n-2)
        mem[n] = res
        return res
    
    def fun5(n):
        if n == 0: return 1
        return fun5(n-1) + fun5(n-1)
    
    def fun6(n):
        if n == 1: return 0
        return 1 + fun6(n//2)
    

  1. Vyrobte iterátor z algoritmu prechádzania stromu do šírky (po úrovniach). Dopíšte dve vyznačené metódy tak, aby iterátor postupne vracal vrcholy v poradí po úrovniach. Nepoužite pritom yield.

    def breadthfirst(t):
        q = [t.root]
        while q:
            p = q.pop(0)
            print(p.data)
            for node in t.children(p):
                q.append(node)
    
    class Tree:
        root = None
        def __iter__(self):
            ...
        def __next__(self):
            ...
    

  1. Pre danú postupnosť hodnôt:

    7, 4, 10, 12, 5, 6, 3, 9, 11, 8, 2, 1
    

    vytvorte haldu v 13-prvkovom poli. Prvky vkladajte (add()) presne v tomto poradí:

    ...
    

    Teraz z nej postupne trikrát odstráňte minimálny prvok (remove_min()) a zakaždým vypíšte obsah haldy:

    ...
    ...
    ...
    

  1. Aký tvar budem mať strom Huffmanovho kódovania a aké budú potom bitové kódy pre každé písmeno, ak máme 9 písmen 'a''i' a kde 'a' a 'b' majú frekvenciu 10 a všetky ostatné písmená majú 1.

  1. Zostavte prefixový strom pre množinu slov:

    {pero, pes, para, por, ropa, rasa, rosa, rok, rak, samo, seno, seka, sal}
    

  1. Zapísali sme funkciu test(), ktorá pracuje s binárnymi stromami (s vrcholmi Node):

    class Node:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right
    
    def test(node):
        if node is None:
            return 0, True
        height1, test1 = test(node.left)
        height2, test2 = test(node.right)
        if not test1 or not test2:
            return 0, False
        return max(height1, height2) + 1, abs(height1 - height2) < 2
    

    Nakreslite tento strom a zistite, čo na ňom vráti volanie funkcie test():

    t = Node(0, Node(1, Node(3)), Node(2, Node(4, None, Node(6)), Node(5, Node(7), Node(8))))
    >>> test(t)
    

  1. Operácie enqueue a degueue pre dátovú štruktúru front (Queue) sme realizovali poľom: pridávaním na koniec a odoberaním prvého prvku poľa:

    class Queue:
        def __init__(self):
            self.__pole = []
    
        def enqueue(self, prvok):
            self.__pole.append(prvok)
    
        def dequeue(self):
            if self.is_empty():
                raise Empty('prázdny front pre dequeue')
            return self.__pole.pop(0)
    

    Vidíme, že dequeue má zložitosť O(n). Prepíšte tieto metódy: namiesto obyčajného poľa (pythonovský list) použijete asociatívne pole (pythonovský dict), o ktorom vieme, že jeho niektoré operácie majú zložitosť O(1). Operácie takéhoto frontu by mali mať zložitosť O(1).


  1. Máme danú rekurzívnu funkciu p(i, j):

    def p(i, j):
        if j == 0:
            return 0
        if i == 0:
            return 1
        return (p(i-1, j) + p(i, j-1)) * 2
    

    Prepíšte ju tak, aby ostala rekurzívna, ale aby využila asociatívne pole mem na memoizáciu výpočtu:

    def p(i, j, mem={}):
    
    
    
    
    
    
    
    .
    

  1. Pri riešenie problému UNION-FIND môžeme algoritmus UNION(p, q) implementovať pomocou stromov. Začneme s 10 jednoprvkovými množinami, ktoré reprezentujú vrcholy <0, 9>:

    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
    

    Postupne aplikujte Union pre tieto dvojice vrcholov:

    (3, 4), (7, 6), (4, 6), (9, 2), (5, 2), (1, 8), (8, 0), (9, 2), (5, 2), (2, 6), (4, 9), (9, 8)
    

    Nakreslite výsledné stromčeky.


  1. Dijkstrov algoritmus štartujeme pre graf na obrázku z vrcholu číslo 15:

    _images/test18_1.png

    Zapíšte do tabuľky priebežný obsah prioritného frontu na začiatku každého prechodu cyklu algoritmu. V každom prvku je buď '-' (označuje nekonečno) alebo je tam momentálna dĺžka (obsah poľa D[vrchol]) a číslo vrcholu:

    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |0/15|  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+
    |    |    |    |    |    |    |
    +----+----+----+----+----+----+
    |    |    |    |    |    |
    +----+----+----+----+----+
    |    |    |    |    |
    +----+----+----+----+
    |    |    |    |
    +----+----+----+
    |    |    |
    +----+----+
    |    |
    +----+
    


© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.