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


  1. Napíš funkciu len_raz(zoznam), ktorá z prvkov pôvodného spájaného zoznamu vytvorí nový, v ktorom sa ale nebude žiadna hodnota opakovať (pozor na poradie prvkov - z opakujúcich sa hodnôt ponechaj prvý výskyt). Funkcia nemodifikuje vstupný zoznam, ale vráti referenciu na začiatok nového zoznamu:

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

  1. Pre triedu BinarnyStrom napíš metódu ocisluj(), 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 ocisluj(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ú súrodenca (teda vrcholov, ktorých predok má len jedného potomka):

    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 = [99, 95, 97, 89, 88, 50, 71, 48, 85, 29, 83, 36, 50, 22, 36, 12, 33, 49, 58, 16, 26, 12, 73, 20]
    zoz1 = []
    zoz2 = []
    zoz3 = []
    

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

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

  1. Graf je zadaný vymenovaním všetkých neorientovaných hrán. Napíš funkciu pocet_3(hrany), ktorá zisti počet komponentov, ktoré obsahujú presne 3 vrcholy. Graf neobsahuje izolované vrcholy. Napríklad:

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

  1. Máme tento turingov stroj:

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

    Na začiatku bolo na páske 'aaabbbabababb'. 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 A 2022/2023
# student: Janko Hrasko
# datum: 25.4.2024

zrejme ako študenta uvedieš svoje meno.