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

  1. Turingov stroj je zadaný tabuľkou:

    start

    jeden

    dva

    x

    > jeden

    > dva

    > start

    y

    > start

    > jeden

    > dva

    _

    = stop

    Stavy sú: start, jeden, dva, stop (koncový) a symboly na páske: x, y, _ (prázdny).

    Zistite, ktoré z uvedených reťazcov budú týmto turingovým strojom akceptované?

    1. xyxyxyx

    2. yyxyyxy

    3. xyyyyyx

    4. xxxxxxx


  1. Zistite, čo vypíše táto funkcia:

    def test(slovo):
        queue = Queue()
        for znak in slovo:
            try:
                p = queue.dequeue()
                queue.enqueue(znak)
                queue.enqueue(p)
            except EmptyError:
                queue.enqueue(znak)
        while not queue.empty():
            print(queue.dequeue(), end='')
        print()
    
    test('abcdef')
    

    Výpis:


  1. Zadaný aritmetický výraz:

    1 + (2 + 3) * 4 / (5 - 6) + 7 * 8
    

    prepíšte do

    1. prefixového zápisu

    2. postfixového zápisu

    Operácie s rovnakou prioritou sa vyhodnocujú zľava doprava.


  1. Napíšte funkciu vyhod_posledny(zoznam), v ktorej parametrom je referencia na začiatok zoznamu typu Vrchol (alebo None). Funkcia vráti referenciu na pôvodný zoznam, ktorý už bude bez posledného prvku:

    class Vrchol:
        def __init__(self, data, next=None):
            self.data, self.next = data, next
    
    def vyhod_posledny(zoznam):
    
    
    
    
        return zoznam
    

  1. Rekurzívna funkcia vytvor_uplny() by mala vrátiť úplný binárny strom, v ktorom v listoch budú 0, v ich predkoch budú 1, v každej úrovni bližšie ku koreňu bude o 1 väčšie číslo, až v koreni by teda mala byť výška celého stromu - teda n:

    class Vrchol:
        def __init__(self, data, left=None, right=None):
            self.data, self.left, self.right = data, left, right
    
    def vytvor_uplny(n, cislo=0):
        if cislo > n:
            return 0
        lavy = pravy = vytvor_uplny(n - 1, cislo + 1)
        koren = Vrchol(n - cislo, lavy, pravy)
        return koren
    

    Opravte všetky (štyri) chyby v tele funkcie.


  1. Pre daný strom vpíšte do vrcholov hodnoty tak, aby výpisom pre postupnosť postorder bolo 'programovanie'.

    _images/test2016c_1.png

  1. Pre daný prefixový zápis

    * + / a b - c d + e f
    

    nakreslite príslušný aritmeticky strom.


  1. Tento strom možno nespĺňa podmienky BVS (binárny vyhľadávací strom). Označte minimálny počet vrcholov stromu, ktorým keby sme navzájom vymenili ich hodnoty, dostaneme BVS.

    _images/test2016c_2.png

  1. Táto verzia triedenia vkladaním v niektorých situáciách vypisuje momentálny obsah celého zoznamu. Vypíšte tieto kontrolné výpisy:

    def insert_sort(zoz):
        for i in range(len(zoz) - 1):
            prvok = zoz.pop(i + 1)
            while i >= 0 and zoz[i] > prvok:
                i -= 1
            zoz.insert(i + 1, prvok)
            print(zoz)
    
    p = [5, 9, 4, 3, 6, 10, 1, 8, 2, 7]
    insert_sort(p)
    

    riadky výpisu:


  1. Označte písmenami vrcholy grafu na obrázku

    _images/test2016c_3.png

    ak poznáte túto jeho reprezentáciu:

    A

    B

    C

    D

    E

    F

    A

    0

    1

    0

    1

    0

    1

    B

    1

    0

    0

    1

    1

    0

    C

    0

    0

    0

    0

    0

    1

    D

    1

    1

    0

    0

    0

    1

    E

    0

    1

    0

    0

    0

    1

    F

    1

    0

    1

    1

    1

    0