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

  1. Máme daný slovník:

    d = {'bum' :7, 'bom':3, 'bam' :5, 'bim' :6, 'bem' :2}
    

    Zistite, čo vráti tento kód:

    '.'.join(b for a, b in sorted((d[x],x) for x in d))
    

  1. Vrchol spájaného zoznamu je definovaný takto:

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

    Napíšte funkciu kopia, ktorá dostáva ako parameter začiatok nejakého zoznamu a vráti nový zoznam, ktorý je kópiou pôvodného:

    def kopia(zoznam):
        ...
    

  1. Do triedy Zoznam dopíšte metódu vyhod2(), ktorá z momentálneho zoznamu vyhodí každý druhý vrchol:

    class Vrchol:
        def __init__(self, data, next):
            self.data = data
            self.next = next
    
    class Zoznam:
        def __init__(self):
            self.zac = None
    
        def vyhod2(self):
            pom = self.zac
            while ________________________________________:
                _____________________
                pom = pom.next
    

  1. Na začiatku bol zásobník prázdny. Potom sme vykonali niekoľko operácií push a pop.

    Zistite, čo sa vypíše po spustení:

    print('pre zasobnik:')
    for x in 7, 3, 5, 11, 3, 8, 4:
        push(x)
    for x in range(6):
        print(pop(), pop(), end=' ')
        push(x)
    print(pop())
    

    Na začiatku bol rad prázdny. Potom sme vykonali niekoľko operácií enqueue a dequeue.

    Zistite, čo sa vypíše po spustení:

    print('pre rad:')
    for x in 7, 3, 5, 11, 3, 8, 4:
        enqueue(x)
    for x in range(6):
        print(dequeue(), dequeue(), end=' ')
        enqueue(x)
    print(dequeue())
    

  1. Máme dané dva výpisy toho istého binárneho stromu. Nakreslite tvar tohto stromu a vypíšte aj strom.preorder():

    >>> print(strom.inorder())
    3 5 10 2 1 6 7 9 4 8
    >>> print(strom.postorder())
    3 10 2 5 7 6 1 8 4 9
    

  1. Dopíšte do stromu na obrázku čísla z postupnosti range(20) tak, aby vznikol binárny vyhľadávací strom:

    _images/test2015c_1.png

  1. Nakreslite aritmetický strom, pre ktorý je táto postupnosť postorderom:

    4 5 + 22 7 / 9 - *
    

  1. Máme daný algoritmus quick sort:

    def quick_sort(pole):
        def rozdel(z, k):
            pivot, index = pole[z], z
            for i in range(z + 1, k + 1):
                if pole[i] < pivot:
                    index += 1
                    pole[i], pole[index] = pole[index], pole[i]
            pole[z], pole[index] = pole[index], pole[z]
            return index
    
        def quick_sort1(z, k):
            if z < k:
                index = rozdel(z, k)
                quick_sort1(z, index - 1)
                quick_sort1(index + 1, k)
    
        quick_sort1(0, len(pole) - 1)
    

    Zapíšte obsah poľa po každom návrate z funkcie rozdel, pričom na začiatku boli v poli:

    68

    58

    25

    32

    88

    82

    37

    86

    95

    15

    Prvok v riadku tabuľky, ktorý bol pritom pivotom, zakrúžkujte.


  1. Nakreslite orientovaný ohodnotený graf, ktorý sme zapísali pomocou asociatívneho poľa vrcholov s asociatívnymi poľami susedov:

    graf = {15: {14: 'ke', 10: 'bl'}, 4: {17: 'sc', 14: 'pk'}, 10: {14: 'nz'},
            17: {10: 'ma'}, 14: {10: 'ds'}}
    

  1. Na daný graf sme spustili algoritmus do šírky, pričom sa nevypisovalo poradové číslo vrcholu ale hodnota uložená vo vrchole (jednoznakový reťazec v premennej meno). Ako boli uložené hodnoty vo vrcholoch grafu, keď sa presne v tomto poradí vypísali znaky 'p r o g r a m u j e p y t h o n' a pritom prehľadávanie začalo vo vrchole 10.

    _images/test2015c_2.png
    def vypis_dosirky(v):
        queue = [v]
        visited = set()
        while len(queue) != 0:
            v = queue.pop(0)
            if v not in visited:
                visited.add(v)
                print(pole[v].meno, end=' ')
                for i in sorted(pole[v].sus):
                    if i not in visited:
                        queue.append(i)