Priebežný test z Programovania (2) 2021/2022 - Variant A


  1. Napíš funkciu urovne_trie_permutacii(mnozina), ktorá vráti zoznam (typ list) počtov vrcholov v jednotlivých úrovniach prefixového stromu, ktorý vznikol zo slov zo všetkých permutácii znakov v zadanej množine mnozina. Napríklad volanie urovne_trie_permutacii({'a', 'b'}) vráti zoznam [1, 2, 2] lebo permutácii z pismen {'a', 'b'} sú dve slova 'ab' a 'ba' a prefixový strom má teda v 0. úrovni jeden vrchol, v 1. úrovni 2 vrcholy a v 2. úrovni tiež 2 vrcholy.

    def urovne_trie_permutacii(mnozina):
        ...
    
  2. Napíš funkciu rovnaky_bvs(postupnost, mnozina), ktorá vrati BVS (binárny vyhľadávací strom). Tento strom vznikol zo zadanej postupnosti postupnost, pričom sa v ňom hodnoty vo vrcholoch nahradili prvkami zadanej množiny mnozina - samozrejme, že aj takto zmenený strom bude BVS. Môžeš predpokladať, že všetky prvky postupnosti sú rôzne, prvky množiny su rovnakého typu a teda sa dajú navzájom porovnávať. Zrejme postupnosť aj množina majú rovnaký počet prvkov. Napríklad volanie rovnaky_bvs(list('kate'), set(range(4))), by vytvorilo takýto strom:

       2
     /   \
    0     3
     \
      1
    

    Použi tieto deklarácie a definuj funkciu rovnaky_bvs, ktorá vráti referenciu na BVS:

    class BVS:
        class Vrchol:
            def __init__(self, data):
                self.data, self.left, self.right = data, None, None
        def __init__(self):
            self.root = None
    
    def rovnaky_bvs(postupnost, mnozina):
        ...
    

  1. Predpokladáme, že máme taký binárny strom, ktorý je buď úplný, alebo skoro úplný (len v poslednej úrovni môže obsahovať menej vrcholov a tie sú sústredené vľavo, podobne ako v halde). Z takéhoto stromu poznáme zoznam hodnôt vo vrcholoch. ktorý je vytvorený po úrovniach. Napíš funkciu pocet_vacsich(zoznam), ktorá zistí, koľko vrcholov v takomto strome má svojho bezprostredného predka väčšieho ako je on sám.

    def pocet_vacsich(zoznam):
        ...
    

  1. Daný je binárny strom:

    class BS:
        class Vrchol:
            def __init__(self, data):
                self.data, self.left, self.right = data, None, None
        def __init__(self):
            self.root = None
        def zisti(self):
            ...
    

    Napíš metódu zisti(), ktorá bude fungovať ako generátor: metóda vráti hodnoty v strome, ktoré sa v ňom vyskytli aspoň dvakrát. Generátor ich vráti v ľubovoľnom poradí, ale každú takúto hodnotu len raz. Napríklad, ak sú v strome vo vrcholoch len hodnoty 'x', generátor vráti jedinú hodnotu 'x'. Všetky hodnoty v strome sú nemeniteľné (immutable).


  1. Napíš funkciu postfixy(operandy, operacie), krorá vygeneruje všetky postfixy s tromi ciselnými operandami (v tomto poradí) a dvomi operáciami (v ľubovoľnom poradí), ktoré sú z {'+','-','*'}. Funkciav vráti asociatívne pole s prvkami v tavre {'vyraz': hodnota}. Napríklad volanie postfixy((1,2,3),('+','+')) vráti dvojprvkový slovník {'1 2 + 3 +': 6, '1 2 3 + +': 6}.

    def postfixy(operandy, operacie):
        ...
    

  1. Funkcia sort(zoznam) nejako usporiada prvky zadaného zoznamu. Navrhni taký vstup do tejto funkcie, aby výsledkom volania bol:

    1. zoz1 = [1, 2, 3, 4, 5]

    2. zoz2 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    3. zoz3 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q']

    Funkciu sort() nemeň:

    def sort(zoznam):
        pom = list(range(len(zoznam)))
        s = len(zoznam) // 2
        pom = pom[s+1:] + pom[s:s+1] + pom[:s]
        zoznam[:] = [zoznam[i] for i in pom[1::2]+pom[::2]]
    
    zoz1 = [...???...]
    sort(zoz1)
    print('zoz1 =', zoz1)
    

  1. Dana je funkcia vloz(stack, x), ktorá pomocou rekurzie urobí niečo so zásobníkom Stack. Oprav ju tak, aby fungovalo volanie test(zoznam) aj pre veľký zoznam. Deklaráciu triedy Stack ani terstovaciu funkciu test nemeň:

    class Stack:
        def __init__(self):   self._zoz = []
        def push(self, hodn): self._zoz.append(hodn)
        def pop(self):        return self._zoz.pop()
        def is_empty(self):   return self._zoz == []
    
    def test(zoznam):
        stack = Stack()
        for i in zoznam:
            vloz(stack, i)
        vysl = 0
        while not stack.is_empty(): vysl += stack.pop()
        return vysl
    

    Oprav túto funkciu:

    def vloz(stack, x):
        if stack.is_empty():
            stack.push(x)
        else:
            y = stack.pop()
            vloz(stack, x)
            stack.push(-y)
    


Riešenie odovzdaj v súbore test.py (môžeš si ho stiahnuť z L.I.S.T.u), pričom prvé tri riadky súboru budú obsahovať:

# test z programovania variant A 2021/2022
# student: Janko Hrasko
# datum: 25.4.2024

zrejme ako študenta uvedieš svoje meno.