Záverečný test z Programovania (2)


  1. Čísla od 0 do 255 sú uložené v jednom bajte (8 bitov). Čísla do 65535 sú uložené v dvoch bajtoch (16 bitov). Máme napísať funkciu bajty(cislo), ktorá z daného čísla vráti postupnosť bajtov. Zrejme posledný bajt vypočíta ako cislo % 256 a zvyšné bajty sú potom cislo // 256 - toto sa bude opakovať, kým nebude cislo nula. Doplňte chýbajúce časti:

    def bajty(cislo):
        vysl = []
        while ___________________:
    
            ______________________________________
            cislo //= 256
        return [cislo] + vysl
    

  1. Zadaný aritmetický výraz:

    2 * (2 + 1) * (3 + 2 + 1) * (4 + 3 + 2 + 1)
    

    prepíšte do

    1. prefixového zápisu

    2. postfixového zápisu

    Operácie s rovnakou prioritou sa vyhodnocujú zľava doprava. Ak by sme pre tento výraz nakreslili aritmetický strom (aj tu sa operácie s rovnakou prioritou vyhodnocujú zľava doprava), potom treba ešte zistiť

    1. počet vnútorných vrcholov

    2. počet listov

    3. výšku stromu


  1. Funkcia krat2(stack) všetky hodnoty v zásobníku vynásobí 2. Doplňte chýbajúce časti:

    def krat2(stack):
        pom = Stack()
        i = 1
        while not stack.is_empty():
    
            pom.push(________________________________________)
            i = 3 - i
        while not pom.is_empty():
            stack.push(pom.pop() * i)
    
            ________________________________________
    

    Malo by fungovať napr.

    >>> s = Stack()
    >>> for x in 1, 2, 9, 6, 10:
            s.push(x)
    >>> krat2(s)
    >>> while s:
            print(s.pop(), end=' ')
    20 12 18 4 2
    

  1. Pre nasledovnú metódu corobi():

    class SpajanyZoznam:
    
        ...
    
        def corobi(self):
            vysl = 0
            p = self.zac
            while p and p.next:
                vysl += p.data == p.next.data
                p = p.next
            return vysl
    

    zistite, čo sa vypíše:

    >>> z = SpajanyZoznam([x//3 for x in range(100)])
    >>> print(z.corobi())
    

  1. Nakreslite všetky rôzne binárne stromy, ktoré sa skladajú zo štyroch vrcholov s hodnotami 'x' a ich výška je 2.


  1. Funkciu vytvor_uplny(n) by mala vrátiť vygenerovaný úplný binárny strom: jeho najvyššia úroveň je n a hodnoty vo všetkých vrcholoch sú 0. Použili sme rekurziu: úplný strom úrovne n sa skladá z ľavého úplného stromu úrovne n-1, z pravého úplného stromu tiež úrovne n-1 a z koreňa, ktorý má tieto dva podstromy. Dopíšte chýbajúci výraz:

    def vytvor_uplny(n):
        if n < 0:
            return None
        return Vrchol(________________________________________________________)
    

  1. Pre daný binárny strom:

    strom = BinarnyStrom()
    v = strom.Vrchol
    strom.root = v('p', v('r', v('o'), v('g', v('r'))),
                   v('a', v('m', v('o'), v('v', v('a'))),
                     v('n', v('i'), v('e'))))
    

    vypíšte postupnosti:

    1. preorder

    2. inorder

    3. postorder

    4. po úrovniach


  1. Nakreslite binárny vyhľadávací strom, ktorý je úplný strom s hodnotami vo vrcholoch range(13, 28).


  1. Máme túto verziu triedenia quick sort, do ktorej sme pridali jednu kontrolnú tlač:

    def quick_sort(zoz):
        if len(zoz) < 2:
            return zoz
        pivot = zoz[0]
        print(pivot)                                # <== výpis
        mensie = [prvok for prvok in zoz if prvok < pivot]
        rovne =  [prvok for prvok in zoz if prvok == pivot]
        vacsie = [prvok for prvok in zoz if prvok > pivot]
        return quick_sort(mensie) + rovne + quick_sort(vacsie)
    

    Zistite, aké hodnoty pivota sa vypíšu pre vstupný zoznam:

    z = [23, 32, 12, 66, 19, 75, 29, 50]
    quick_sort(z)
    

  1. Graf mame zadaný pomocou reprezentácie matica susedností s váhami:

    a,b,c,d,e,f,g,h = range(8)
    _ = None       # označuje, že tu nie je hrana
    
    graf = [[_,_,2,4,_,7,_,2],
            [_,_,_,_,_,_,2,_],
            [2,_,_,_,_,_,4,_],
            [_,_,_,_,_,_,5,_],
            [_,_,_,_,_,_,3,_],
            [7,_,_,_,_,_,_,1],
            [1,2,_,5,3,_,_,_],
            [2,_,_,_,_,_,_,_],
            ]
    

    prepíšte ho do reprezentácie asociatívne pole asociatívnych polí susedností, v ktorej sú menami vrcholov reťazce 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'.