Test z ADŠ 2014/2015

  1. Metóda height pre triedu Strom počíta výšku stromu pomocou metódy depth (hĺbky konkrétneho vrcholu, t.j. vzdialenosť vrcholu od koreňa):

    def depth(self, p):
        if self.is_root(p):
            return 0
        else:
            return 1 + self.depth(p.parent)
    
    def height(self):
        return max(self.depth(p) for p in self. preorder() if self.is_leaf(p))
    

    Odhadnite zložitosť (najhoršieho prípadu) metódy height pre strom s n vrcholmi.


  1. Funkcia podmnoziny vráti zoznam všetkých podmnožín nejakej množiny:

    def podmnoziny(mnozina):
        zoznam = [set()]
        for prvok in mnozina:
            for mn in zoznam[:]:
                zoznam.append(mn | {prvok})
        return zoznam
    

    Zistite, koľkokrát sa v tejto funkcii vykoná operácia zjednotenia:

    mn | {prvok}
    

  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. Trieda BS popisuje zjednodušený binárny strom:

    class BS:
        def __init__(self, info=0, l=None, p=None):
            self.info = info
            self.l = l
            self.p = p
    
        def daj(self):
            if self.l:
                self.l.daj()
            if self.p:
                self.p.daj()
            print(self.info, end=' ')
    

    Zistite, čo vypíše:

    BS('x',BS('a',BS('c'),BS('d')),BS('b',BS('e'),BS('f'))).daj()
    

  1. Prepíšte metódu daj() z predchádzajúceho príkladu (4) tak, aby nevypisovala žiadne hodnoty, ale vrátila iterátor, t.j. vygenerovala postupnosť hodnôt.

    def daj(self):
    
    
    
    
    
        ...
    

    teda, aby sme pomocou tohto zápisu dostali rovnaký výsledok ako v príklade (4):

    print(*list(BS('x',BS('a',BS('c'),BS('d')),BS('b',BS('e'),BS('f'))).daj()))
    

  1. Odhadnite, ako dlho bude trvať (zložitosť) odstránenie (log n) najmenších prvkov z haldy, ktorá má n-prvkov. Na odstraňovanie sa použije metóda remove_min():

    def remove_min(self):
        if self.is_empty():
            raise Empty('Priority queue is empty.')
        self._swap(0, len(self._data) - 1)    # daj minimálny prvok na koniec
        item = self._data.pop()               # a vyhoď ho zo zoznamu
        self._downheap(0)                     # a oprav koreň
        return (item._key, item._value)
    

    teda, ak máme v halde 1024 prvkov, zaujíma nás, koľko bude trvať odstránenie 10 najmenších prvkov.


  1. Odhadnite, aká je zložitosť najhoršieho prípadu vkladania n dvojíc (key, value) do prázdneho asociatívneho poľa, ktoré je realizované pomocou triedy UnsortedTableMap.

    def __setitem__(self, k, v):
        for item in self._table:
            if k == item._key:
                item._value = v
                return
        self._table.append(self._Item(k,v))
    

  1. Do koľkých rôznych binárnych vyhľadávacích stromov vieme uložiť kľúče {1, 2, 3, 4}? Koľko z nich nespĺňa podmienku AVL stromov?

    .
    .
    .
    

  1. Uvádzali sme tento algoritmus merge-sort:

    def merge_sort(pole):
    
        def merge(p1, p2):
            result,i1,i2 = [],0,0
            while i1 < len(p1) or i2 < len(p2):
                if i1 < len(p1) and (i2 == len(p2) or p1[i1] < p2[i2]):
                    result.append(p1[i1])
                    i1 += 1
                else:
                    result.append(p2[i2])
                    i2 += 1
            return result
    
        if len(pole) <= 1:
            return pole
        stred = len(pole)//2
        return merge(merge_sort(pole[:stred]),merge_sort(pole[stred:]))
    

    Zistite, či je tento algoritmus stabilné triedenie, t.j. ak sme triedili dvojice (kľúč, hodnota) a v pôvodnom poli mali dve dvojice rovnaký kľúč, teda (kľúč,hodnota1) a (kľúč,hodnota2), pričom prvá dvojica bola pred druhou dvojicou, tak aj v utriedenom poli bude pre obe dvojice platiť rovnaký vzťah, teda, že prvá dvojica sa nachádza pred druhou. Ak toto triedenie nie je stabilné, navrhnite 8-prvkové pole, na ktorom sa to potvrdí.


  1. Huffmanov kódovací algoritmus pracuje na tomto princípe:

    Algoritmus Huffman(X):
      Input: reťazec X dĺžky n
      Output: kódovací strom pre X
    Vypočítaj frekvenčnú tabuľku ft(c) pre každý znak c z X
    Initializuj prioritný front Q
    for each znak c in X do
        Vytvor binárny strom T s jediným vrcholom a s info c
        Vlož T do Q s kľúčom ft(c)
    while len(Q) > 1 do
        (f1,T1) = Q.remove min()     # remove min() vráti dvojicu (kľúč,hodnota)
        (f2,T2) = Q.remove min()
        Vytvor nový binárny strom T, ktorého ľavý podstrom je T1 a pravý T2
        Vlož T do Q s kľúčom f1+f2
    (f,T) = Q.remove min()
    return strom T
    

    Nakreslite Huffmanov kódovací strom pre reťazec:

    meno+" programuje v programovacom jazyku python"
    

    kde meno je vaše meno a priezvisko (malými písmenami bez diakritiky, s jednou medzerou).

    Potom pomocou tohto kódovacieho stromu zakódujte reťazec:

    "peter je prvy"
    

    Kódom bude postupnosť 0 a 1: každé písmeno zodpovedá ceste v strome k danému písmenu, pričom ľavý smer v ceste je 0 a pravý 1. Rôzne písmená budú mať rôzne dlhé kódy.



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