Test z ADŠ 2017/2018

  1. Zistiť zložitosť funkcií:

    def f1(pole1, pole2):
        if len(pole2) == 0:
            return 0
        if len(pole2) == 1:
            return int(pole2[0] in pole1)
        stred = len(pole2) // 2
        return f1(pole1, pole2[:stred]) + f1(pole1, pole2[stred:])
    
    def f2(n):
        if n == 0:
            return 1
        return n * f2(n - 1)
    
    def f3(pole):
        i = len(pole)
        while i > 0:
            for j in range(i):
                for k in range(j, 10**5):
                    pole[j] += 1
            i -= 2
    
    def f4(n, mem={}):
        if n in mem:
            return mem[n]
        if n < 2:
            res = n
        else:
            res = f4(n-1) + f4(n-2)
        mem[n] = res
        return res
    
    def f5(pole):
        return len(pole) == len(set(pole))
    

  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:

    8, 13, 7, 10, 5, 15, 12, 17, 9, 14, 4, 11, 18, 16, 6
    

    vytvorte haldu v 15-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. Zapíšte metódy triedy MultiSet (množina s viacnásobnými výskytmi prvkov), ktorú budete realizovať pomocou pythonovského asociatívneho poľa (dict):

    class MultiSet:
        def __init__(self):
            self.data = {}
    
        def __contains__(self, key):
            return ...
    
        def add(self, key):        # pridá do množiny, zapamätá si počet výskytov tejto hodnoty
            ...
    
        def discard(self, key):    # ak je v množine, vyhodí jedeb výskyt
            ...
    
        def __len__(self):         # počet aj viacnásobných výskytov
            return ...
    
        def __iter__(self):        # aj viacnásobné výskyty
            yield from ...
    

  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. Dopíšte:

    def bucket_sort(pole):
        p = [[] for i in range(100000)]        # inicializácia prázdnych vedierok
        for key, value in pole:
            _________________________________
        res = []
        for key in range(len(p)):
            _________________________________
        return res
    

  1. Zapíšte nerekurzívnu verziu komb1(n, k), ktorá najprv skonštruuje dvojrozmernú tabuľku pre n riadkov a k stĺpcov a na základe nej vráti výsledok:

    def komb1(n, k):
        # ... vytvorte dvojrozmernú tabuľku veľkosti n x k, kde tab[i][j] = hodnota komb(i, j)
        # ... tabuľku vytvorte metódou zdola nahor, t.j. najprv pre malé i a j
        return tab[n][k]
    

  1. V tejto štruktúre máme už skonštruovaný Huffmanov strom:

    class Node:
        def __init__(self, data, lavy=None, pravy=None):
            self.data = data
            self.child = [lavy, pravy]
    

    Dopíšte funkciu, ktorá rozkóduje zadanú postupnosť 0 a 1:

    def rozkoduj(root, sequence):
        res = ''
        seq = list(sequence)
        while seq:
            node = root
            while ____________________:
    
                node = _______________________
    
            res = _____________________
        return res
    

    Napr. pre

    >>> strom = Node('', Node('a'), Node('', Node('b'), Node('c')))
    >>> rozkoduj(strom, (0, 1, 0, 0, 1, 1, 0))
    'abaca'
    

    Predpokladáme, že strom aj postupnosť sú zadané korektne.


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

    {auto, aula, ano, body, byk, boja, balet, cop, cap, cip, cakan}
    

  1. UNION-FIND realizujeme poľom reprezentantov:

    def FIND(p):
        return tab[p]
    
    def UNION(p, q):
        r1 = FIND(p)
        r2 = FIND(q)
        if r1 != r2:
            for v in vsetky_prvky_pola:
                if tab[v] == r2:
                    tab[v] = r1
    

    Zistite, aký bude obsah deväťprvkového poľa po zjednocovaní týchto dvojíc:

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


© 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.