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

  1. Prepíšte do prefixového zápisu tento výraz:

    1 2 3 * + 4 5 * + 6 7 * +
    

    .


  1. Naprogramujte funkciu otoc_rad(queue), ktorá otočí poradie prvkov v danej dátovej štruktúre rad. Na otáčanie radu použite pomocný zásobník:

    def otoc_rad(queue):
        stack = Stack()
    
        while ______________________:
    
            stack._______________________
    
        while ______________________:
    
            queue._______________________
    

  1. Máme napísať funkciu spoj(zoz1, zoz2), ktorá na koniec spájaného zoznamu zoz1 pripojí spájaný zoznam zoz2 a ako výsledok vráti začiatok takéhoto nového zoznamu. Opravte chyby:

    def spoj(zoz1, zoz2):
        if zoz1 is None:
            return None
    
        while zoz1.next is not None:
            zoz1 = zoz1.next
        zoz1.next = zoz2
        return zoz1
    

  1. Metóda mapuj() postupne prejde všetky vrcholy spájaného zoznamu a každému (ktorý spĺňa podmienku) zmení hodnotu podľa zadanej funkcie:

    class SpajanyZoznam:
        ...
    
        def mapuj(self, podmienka, funkcia):
            pom = self.zac
            while pom is not None:
                if podmienka(pom.data):
                    pom.data = funkcia(pom.data)
                pom = pom.next
    

    Doplňte chýbajúce definície funkcií:

    >>> zoz = SpajanyZoznam(range(7))
    
    >>> pdm = lambda _____________________________
    
    >>> fun = lambda _____________________________
    >>> zoz.mapuj(pdm, fun)
    >>> zoz
    6 -> 5 -> 2 -> 3 -> 4 -> 1 -> 0 -> None
    

  1. Funkcia zisti(vrch) niečo zisťuje o neprázdnom binárnom strome:

    def zisti(vrch, h=0):
        if vrch.left is None:
            if vrch.right is None:
                return h
            return zisti(vrch.right, h+1)
        pom = zisti(vrch.left, h+1)
        if vrch.right is None:
            return pom
        return min(pom, zisti(vrch.right, h+1))
    

    Zistite, čo táto funkcia vráti pre tento binárny strom (funkciu voláme s koreňom stromu):

    _images/28_6.png

  1. Do daného stromu:

    _images/29_7.png

    vpíšte do vrcholov hodnoty tak, aby postorder-vypisom tohto stromu bola postupnosť písmen 'programovanie'.


  1. Inicializácia __init__() triedy BVS môže mať parameter, ktorý je postupnosťou hodnôt, z ktorej sa vytvorí binárny vyhľadávací strom postupným volaním metódy vloz(). Nakreslite strom, ktorý vznikne volaním:

    s = BVS('KE BB PO PE PK BA BS NI SC BL RK BR'.split())
    s.kresli()
    

  1. Aby sa nasledovný orientovaný graf stal neorientovaným, musíme niektorým hranám dodefinovať aj opačný smer:

    graf = [{2, 3},          # 0
            {3, 5},          # 1
            {0},             # 2
            {0, 1, 5},       # 3
            {6, 7, 8},       # 4
            {1, 2},          # 5
            {},              # 6
            {4},             # 7
            {3, 4}]          # 8
    

    Zadefinujte minimálny počet pridaných orientovaných hrán (vypíšte ich dvojice čísel vrcholov) tak, aby bola každá hrana orientovaná oboma smermi. V tomto grafe potom nájdite aj maximálny cyklus.


  1. Táto verzia triedenia vkladaním v niektorých situáciách vypíše momentálny obsah celého zoznamu. Odtrasujte tento algoritmus a vypíšte tieto kontrolné výpisy:

    def insert_sort1(zoz):
        for i in range(1, len(zoz)):
            j, t = i, zoz[i]
            while j > 0 and zoz[j-1] > t:
                zoz[j] = zoz[j-1]
                j -= 1
            if j < i:
                zoz[j] = t
                print(*zoz)
    
    z = [5, 9, 4, 3, 6, 10, 1, 8, 2, 7]
    insert_sort1(z)
    

    riadky výpisu:

    .

    .

    .

    .

    .

    .

    .

    .

    .


  1. Do triedy Graf dopíšte metódu max_komponent(), ktorá zistí veľkosť najväčšieho komponentu:

    def max_komponent(self):
    
        def dohlbky(v1):
            visited.add(v1)
            for v2 in self.vrcholy[v1].sus:
                if v2 not in visited:
                    dohlbky(v2)
    
        visited = set()
    
    
    
    
        return _____________