Test z ADŠ 2015/2016

  1. Pre všetky nasledujúce funkcie odhadnite časovú zložitosť: ku každej pripíšte jedno z písmen AF.

    def fun1(n):
        x = 0
        for i in range(n):
            x += 1
        return x
    
    def fun2(n):
        x = 0
        for i in range(n):
            for j in range(i):
                x += 1
        return x
    
    def fun3(n):
        if n == 0: return 1
        x = 0
        for i in range(n):
            x += fun3(n-1)
        return x
    
    def fun4(n):
        if n == 0: return 0
        return fun4(n//2) + fun1(n) + fun4(n//2)
    
    def fun5(n):
        x, i = 0, n
        while i > 0:
            x += fun1(i)
            i //= 2
        return x
    
    def fun6(n):
        if n == 0: return 1
        return fun6(n-1) + fun6(n-1)
    
    def fun7(n):
        if n == 1: return 0
        return 1 + fun7(n//2)
    

  1. Binárny strom sme reprezentovali nie pomocou smerníkov na ľavý a pravý podstrom ale v jednorozmernom poli: koreň (jeho dátová časť) sa nachádza v nultom prvku poľa, pre každý vrchol na indexe i sú jeho ľavý a pravý syn na indexoch 2*i+1 a 2*i+2 (neexistujúci vrchol má index mimo poľa). Napíšte metódu postorder, ktorá vráti postupnosť navštívených vrcholov ako generátor.

    class BinTree:
        def __init__(self):
            self.pole = []
    
        def postorder(self):
    
    
    
           ...
    

  1. Napíšte metódu hlbky, ktorá rekurzívne prejde všetky vrcholy binárneho stromu v poradí preorder a pre každý vrchol vygeneruje (yield) dvojicu (data, hĺbka). Metóda hlbky môže mať definovanú svoju vnorenú pomocnú funkciu.

    class BinTree:
        class Node:
            def __init__(self, data, left=None, right=None):
                self.data, self.left, self.right = data, left, right
    
        def __init__(self):
            self.root = None
    
        def hlbky(self):
           ...
           yield node.data, hlbka
    

  1. Prioritný front sme realizovali pomocou utriedeného spájaného zoznamu. Dopíšte mu metódy add a remove_min:

    class SortedPriorityQueue:
        class Item:
            def __init__(self, key, value, next=None):
                self.key = key
                self.value = value
                self.next = next
    
        def __init__(self):
            self.data = None       # zaciatok spajaneho zoznamu
    
        def add(self, key, value):
            ...
    
        def remove_min(self):
            if ...:
                raise Empty('priority queue is empty')
            ...
    

  1. Definujte metódy triedu Set (množina) pomocou štandardnej triedy dict:

    class Set:
        def __init__(self):
            self.slovnik = dict()
    
        def __contains__(self, key):
            ...
    
        def add(self, key):
            ...
    
        def remove(self, key):
            ...
    
        def __len__(self):
            ...
    
        def __iter__(self):
            ...
    

    Telo každej z týchto metód zapíšte len jediným riadkom!


  1. Nakreslite všetky binárne vyhľadávacie stromy, v ktorých sú uložené kľúče {1, 2, 3, 4} a spĺňajú podmienku AVL stromov.

    .
    
    
    .
    

  1. Pri riešení úlohy mincovka pomocou dynamického programovania sa vytvára tabuľka, ktorá obsahuje minimálne počty mincí, ktoré je treba pre danú sumu (suma je index do tabuľky). Doplňte tabuľku, ak ju vytvárame pre mince [1, 3, 5, 9]:

    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |  0 |  1 |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    

  1. Toto je algoritmus rýchleho triedenia z prednášky – druhý parameter sa zatiaľ nepoužíva:

    def quick_sort(pole, key=None):
        if len(pole) < 2:
            return pole
        pivot = pole[0]
        mensie = [prvok for prvok in pole if prvok < pivot]
        rovne = [prvok for prvok in pole if prvok == pivot]
        vacsie = [prvok for prvok in pole if prvok > pivot]
        return quick_sort(mensie) + rovne + quick_sort(vacsie)
    

    Upravte program tak, aby mal 2. parameter rovnakú úlohu ako v štandardnej funkcii sorted. Napr. volanie

    quick_sort(pole, key=lambda x:abs(x-50))
    

    neporovnáva prvky poľa, ale hodnoty, ktoré sa z prvkov vypočítajú pomocou funkcie key. Ak má tento parameter hodnotu None, triedi sa rovnako ako doteraz.


  1. Pri riešenie problému UNION-FIND môžeme algoritmus UNION(p, q) implementovať pomocou stromov:

    def UNION(p, q):
        r1 = FIND(p)
        r2 = 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
    

    Nakreslite výsledok, ak pre stromy na obrázku zavoláme UNION(0, 2) a UNION(1, 9).

    _images/test15_1.png

  1. Predpokladajme, že tento huffmanov strom vznikol zo správy, ktorá sa skladala z písmen A, B, C, D, E:

    _images/test15_2.png

    Ku každému z nasledovných tvrdení dopíšte, či je „pravdivé“, „nepravdivé“, alebo „nedá sa rozhodnúť“ (napríklad, závisí od konkrétnej správy):

    • Frekvencia písmena A musí byť menšia ako frekvencia B. ……………………
    • Frekvencia písmena C musí byť väčšia alebo rovná ako frekvencia A. ……………………
    • Frekvencia písmena D musí byť väčšia ako frekvencia A ……………………
    • Frekvencia písmena D musí byť väčšia alebo rovná ako súčet frekvencií A, B a C. ……………………
    • Frekvencia písmena E musí byť menšia ako súčet frekvencií A, B a C. ……………………


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