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


  1. Napíš funkciu len_posledne(zoznam), ktorá z pôvodného spájaného zoznamu vyhodí prvky, ktoré sa v ňom vyskytujú viackrát - ponechá len ich posledné výskyty (ak tam bol len raz, tak ho tam ponechá). Funkcia vráti referenciu na začiatok tohto zmeneného zoznamu:

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

  1. Pre triedu BinarnyStrom napíš metódu do_listov(postupnost), ktorá zmení dátovú časť vo všetkých vrcholoch takto: do listov stromu postupne vkladá prvky z danej postupnosti (zľava doprava) - ak je prvkov postupnosti menej ako listov v strome, do zvyšných listov vkladá None. Do všetkých vnútorných vrcholov tiež vloží hodnotu None. Postupnosťou môže byť aj iterátor.

    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 do_listov(self, postupnost):
            ...
    

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


  1. V korektne vytvorenom binárnom vyhľadávacom strome celých čísel sme všetky listy nahradili hodnotou '?'. Napíš metódu oprav, ktorá opraví hodnoty v listoch tohto stromu (nahradí ich ľubovoľnou hodnotou, ktorá môže byť na danom mieste).

    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 oprav(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)

    • a tiež zoz4 (teraz by mali byť posledné štyri prvky zoznamu na svojom mieste)

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

    halda = [90, 88, 86, 70, 81, 57, 48, 50, 22, 71, 58, 39, 27, 33, 31, 28]
    zoz1 = []
    zoz2 = []
    zoz3 = []
    zoz4 = []
    

  1. Máme škonštruovaný prefixový strom z nejakej postupnosti slov. Do triedy Trie dopíš metódu prave_3(), ktorá zistí, koľko vrcholov v strome má práve 3 potomkov. Vo vrcholoch v atribúte child je zoznam potomkov v tvare dvojíc (znak, referencia na podstrom):

    class Trie:
        class Vrchol:
            def __init__(self):
                self.data, self.child = None, []
        def __init__(self):
            self.root = self.Vrchol()
        def prave_3(self):
            return ...
    

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


  1. Graf je zadaný vymenovaním všetkých neorientovaných hrán. Napíš funkciu min_k(hrany), ktorá zisti veľkosť najmenšieho komponentu. Funkcia vráti dvojicu: počet takýchto najmenších komponentov a ich veľkosť. Graf neobsahuje izolované vrcholy. Napríklad:

    >>> min_k({(3, 7), (6, 1), (2, 5), (4, 7), (8, 9)})
        (3, 2)
    

  1. Máme tento turingov stroj:

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

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

zrejme ako študenta uvedieš svoje meno.