Priebežný test z Programovania (2) 2022/2023 - Variant B


  1. Napíš funkciu aplikuj(zoznam, *funkcie), ktorá zmení všetky prvky spájaného zoznamu tak, že postupne na každý z nich aplikuje jednu so zadaných funkcií: na prvý prvok prvú funkciu, na druhý druhú, … Ak je funkcií menej ako prvkov v zozname, pokračuje od prvej funkcie. Ak sa na niektorú z hodnôt nedá aplikovať príslušná funkcia (spadlo by to na chybe), tak táto hodnota sa nezmení. Funkcia aplikuj nevracia žiadnu hodnotu, ale modifikuje vstupný zoznam:

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

  1. Pre triedu BinarnyStrom napíš metódu po_urovniach(), ktorá očísluje (zmení dátovú časť vo vrcholoch) všetky vrcholy po úrovniach takto: v koreni bude číslo 0, vrcholy v 1. úrovni budú mať 1, v každej ďalšej úrovni budú mať vrcholy hodnoty podľa príslušnej úrovni:

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

    Ak do triedy pridáš ďalšie metódy, tieto sa budú testovačom ignorovať.


  1. Napíš metódu kolko, ktorá v triede pre binárny vyhľadávací strom zistí počet vrcholov, ktoré nemajú práve dvoch potomkov:

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

    Ak do triedy pridáš ďalšie metódy, tieto sa budú testovačom ignorovať.


  1. Máme takéto triedenie heap_sort: najprv sa vytvorí halda, ktorá má v koreni maximálnu hodnotu a všetci potomkovia nemajú hodnotu väčšiu ako ich predkovia. Potom sa spustí niekoľko prechodov triedenia:

    • maximálny prvok v koreni sa vymení s posledným a halda (okrem posledného) sa upraví; takto dostaneš zoznam zoz1

    • teraz s touto novou haldou (okrem posledného prvku) urobíš to isté: koreň vymeníš s predposledným prvkom a haldu znovu (okrem posledných dvoch) upravíš; takto dostaneš zoz2

    • podobne vyrobíš aj zoz3 (teraz by mali byť posledné tri prvky zoznamu na svojom mieste)

    Tvojou úlohou je do premenných zoz1, zoz2 a zoz3 priradiť stav zoznamu s haldou po prvom, po druhom a po treťom prechode triedenia:

    halda = [89, 83, 79, 77, 62, 70, 58, 42, 41, 37, 57, 69, 41,
             55, 41, 23, 16, 30, 11, 13, 24, 45, 33, 59]
    zoz1 = []
    zoz2 = []
    zoz3 = []
    

  1. Máme takýto prefixový zápis: operátory má and, or, neq, eq a operandami sú premenné a a b a tiež hodnoty True a False. Napíš funkciu zisti(prefix), ktorá nájde všetky dvojice hodnôt premenných a a b (buď True alebo False), pre ktoré má zadaný prefixový výraz hodnotu True. Môžeš predpokladať, že prefixový výraz je zadaný korektne. Funkcia vráti zoznam dvojíc hodnôt, napríklad:

    >>> zisti('neq a b')
        [(False, True), (True, False)]
    

  1. Graf je zadaný vymenovaním všetkých neorientovaných hrán. Napíš funkciu max_k(hrany), ktorá zisti veľkosť najväčšieho komponentu. Graf neobsahuje izolované vrcholy. Napríklad:

    >>> max_k({(3, 7), (6, 1), (2, 5), (4, 7)})
        3
    

  1. Máme tento turingov stroj:

    (a, a)  ->  (c, >, a)
    (a, b)  ->  (a, >, b)
    (b, a)  ->  (b, >, b)
    (b, b)  ->  (a, >, a)
    (a, _)  ->  (a, <, b)
    (b, _)  ->  (c, <, end)
    

    Na začiatku bolo na páske 'bbbababaaababa'. Zisti, čo bude na páske po skončení tohto programu (bez prázdnych symbolov). Výsledok priraď to premennej:

    paska = '...'
    


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 B 2022/2023
# student: Janko Hrasko
# datum: 25.4.2024

zrejme ako študenta uvedieš svoje meno.