Test z ADŠ 2016/2017

  1. Pre všetky nasledujúce algoritmy odhadnite časovú zložitosť. Veľkosť poľa pole označíme ako n.

    def fun1(n, x=None):
        if x is None:
            n, x = 1, n
        if n < x:
            return fun1(2 * n, x // 2) + 1
        return 0
    
    def fun2(m, n):
        if m == 0:
            return n
        if m > n:
            return fun2(n, m)
        return fun2(m, n-m)
    
    def fun3(pole):
        vysl = i = j = 0
        while i < len(pole):
            if i < len(pole)-1:
                vysl += pole[i] - pole[i+1]
                i += 1
            else:
                i = j = j+1
        return vysl
    
    def fun4(pole):
        vysl = 0
        for i in range(len(pole)):
            j = 1
            while j < len(pole):
                if pole[i] < pole[j]:
                    vysl += 1
                j += j
        return vysl
    
    def fun5(pole):
        return sum(i**2 for i in pole)
    
    def fun6(pole):
        if len(pole) == 1:
            return pole[0]
        i = len(pole) // 2
        return fun6(pole[:i]) + fun6(pole[i:])
    

  1. Binárny strom sme reprezentovali pomocou smerníkov na ľavý a pravý podstrom. Napíšte metódu breadth_first, ktorá vráti postupnosť navštívených vrcholov (algoritmus do šírky) ako generátor.

    class BinTree:
        root = None
    
        class Node:
            def __init__(self, data, left, right):
                self.data, self.left, self.right = data, left, right
    
        def breadth_first(self):
           ...
    

  1. Realizujte zásobník tak, aby obe operácie push() aj pop() mali konštantnú (t.j. nie len amortizovane konštantnú) časovú zložitosť.

    class Stack:
    
    
    
        def __init__(self):
            ...
    
        def push(self, hodnota):
            ...
    
        def pop(self):     # vyvolá TypeError pri prázdnom zásobníku
            ...
    
        def is_empty(self):
            ...
    

  1. Z rôznych čísel 1 až 10 vytvorte haldu (v koreni s indexom 0. je minimum) v 10-prvkovom poli tak, aby:

    1. v prvku poľa s indexom 4 bola maximálne možná hodnota
    2. v prvku poľa s indexom 4 bola minimálne možná hodnota

    Pre obe podúlohy vypíšte dva riadky tabuľky, pričom v prvom bude vytvorená halda a v druhom zrealizujte operáciu remove_min().


  1. Hašovaciu tabuľku vytvárame v 7-prvkovom poli, pričom kolízie riešime pomocou vedierok, ktoré realizujeme jednorozmerným poľom (prvky pridávame na koniec). Kľúčmi sú celé čísla (asociované hodnoty si teraz nevšímame), pričom hašovacia funkcia počíta zvyšok po delení veľkosťou tabuľky. Postupne vložte do tabuľky tieto čísla:

    17, 36, 76, 76, 9, 52, 40, 24, 29, 26, 68, 7, 89, 76, 80, 59, 59, 2
    

    zapíšte tieto kľúče do príslušných vedierok (na začiatku sú všetky prázdne):

       +----+
    0  |    |
       +----+
    1  |    |
       +----+
    2  |    |
       +----+
    3  |    |
       +----+
    4  |    |
       +----+
    5  |    |
       +----+
    6  |    |
       +----+
    

  1. Máme daný vyhľadávací strom, o ktorom nevieme, či spĺňa podmienku AVL stromov. Dopíšte ku každému vrcholu jeho balans (rozdiel výšok podstromov) a vyznačte, ktoré vrcholy nespĺňajú podmienku AVL.

    _images/test16_1.png

  1. Ručne zrealizujte nerekurzívny algoritmus merge_sort zdola nahor. V 16-prvkovom poli máme 16 celočíselných hodnôt (prvý riadok tejto tabuľky). Do druhého riadku zapíšte, ako sa zmení obsah poľa po prvom prechode triedenia, t.j. pri porovnávaní susedných prvkov v dvojiciach. Do tretieho riadku zapíšte, ako sa zmení obsah po druhom prechode triedenia, t.j. po zlúčení prvkov v dvojiciach a vytvorením utriedených štvoríc. Ďalšie dva riadky by mali obsahovať zmeny po 3. a 4. prechode triedenia.

    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    | 86 | 68 |  3 | 71 |  8 | 90 | 31 | 85 | 45 |  2 | 22 | 73 | 36 | 66 | 25 | 97 |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    

  1. Naprogramujte algoritmus rýchleho hľadania k-teho najmenšieho prvku v neutriedenom poli. Využite rekurzívnu ideu algoritmu quick_sort:

    def select(pole, k):
    
    
    
    
    
    
    
    
    
    
    
        ...
    

    Zrejme pre k=0 funkcia vráti minimálny prvok, t.j. pole[0].


  1. Ručne vytvorte LCS-tabuľku pre reťazce 'babkabraba' a 'abrakadabra':

      a b r a k a d a b r a
     0 0 0 0 0 0 0 0 0 0 0 0
    b 0
    a 0
    b 0
    k 0
    a 0
    b 0
    r 0
    a 0
    b 0
    a 0
    

    Aký najdlhší spoločný podreťazec dostávame z tejto tabuľky?.


  1. Z daného poľa hodnôt vytvorte huffmanov strom a z neho pre každú z rôznych hodnôt vytvorte kódovaciu tabuľku (pre číselnú hodnotu zodpovedajúcu postupnosť 0 a 1)

    57, 62, 57, 57, 11, 57, 64, 96, 62, 96, 79, 62, 96, 64, 11, 64, 57, 57, 64, 64
    


© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.