Zimný semester, semestrálny test

• Semestrálny test bude v stredu 13.12. 18:10.
• Môžete si priniesť ťahák v rozsahu 1 listu A4.
• Prineste si aj preukaz študenta a písacie potreby.
• Test bude trvať 90 minút.
• Z testu je potrebné získať aspoň polovicu bodov. Počas skúškového bude ešte opravný termín (bližšie v pravidlách predmetu).

Pokročilí, ktorí získali na úvodnom teste pre pokročilých 50% bodov, majú body z testu uznané aj ako body zo semestrálneho testu. Ak však chcete, môžete test znovu písať so spolužiakmi. Odovzdaním testu sa vám budú počítať body z tohto testu bez ohľadu na to, či si polepšíte alebo zhoršíte výsledok.

Na semestrálnom teste budú podobné typy príkladov, aké poznáte z teoretických cvičení, napríklad

• napíšte funkciu, ktorá robí zadanú činnosť
• doplňte chýbajúce časti funkcie
• zistite, čo funkcia robí (pre daný vstup alebo všeobecne)

Vyskytne sa však aj nový typ príkladov, kde je úlohou napísať, ako bude na nejakom vstupe fungovať algoritmus alebo dátová štruktúra z prednášky. Nižšie sú ukážky takýchto príkladov. Svoje odpovede si môžete skontrolovať na spodku stránky.

Môžete si pozrieť aj ukážkový test pre pokročilých, ktorý má podobné typy príkladov ako semestrálny test.

Ukážkové príklady z algoritmov na semestrálny test

• Príklad 1: Prepíšte výraz 8 3 4 * + 2 3 + / z postfixovej notácie do bežnej infixovej notácie. Aká je jeho hodnota? Nakreslite ho aj ako strom.

• Príklad 2: Prepíšte výraz ((2+4)/(3*5))/(1-2) do postfixovej a prefixovej notácie.

• Príklad 3: Vyhodnocujeme výraz 8 3 4 * + 2 3 - / v postfixovej notácii algoritmom z prednášky. Aký bude obsah zásobníka v čase, keď začneme spracovávať znamienko +?

• Príklad 4: Máme zásobník s a rad q, pričom obidve štruktúry uchovávajú dáta typu char. Aký bude ich obsah po nasledujúcej postupnosti príkazov?

init(s);
init(q);
push(s, 'A');
push(s, 'B');
push(s, 'C');
enqueue(q, pop(s));
enqueue(q, pop(s));
push(s, 'D');
push(s, dequeue(q));

• Príklad 5: Strom nižšie má v každom uzle uložené jedno písmeno (dáta typu char). V akom poradí budú vypísané jednotlivé písmená, ak použijeme inorder, preorder a postorder prehľadávanie?

         A
       /  \
      /    \
     B      C  
    / \    / \
   D   E  F   G
      / \
     H   I

• Príklad 6: Máme binárny strom, v ktorom má každý vrchol buď dve deti a v dátovom poli uložený znak '#' alebo nemá žiadne deti a v dátovom poli má uložený znak '*'. Keď tento strom vypíšeme v preorder poradí, dostaneme postupnosť ##*#*** Nakreslite, ako vyzerá tento strom.

• Príklad 7: Nakreslite binárny vyhľadávací strom, ktorý dostaneme, ak do prázdneho stromu postupne vkladáme záznamy s kľúčmi 3, 4, 1, 2, 5, 6 (v tomto poradí).

• Príklad 8: Nakreslite lexikografický strom s abecedou {a,b}, do ktorého sme vložili reťazce aba, aaab, baa, bab, ba. Vrcholy, ktoré zodpovedajú niektorému reťazcu zo vstupu, zvýraznite dvojitým krúžkom.

• Príklad 9 Ako bude vyzerať hašovacia tabuľka pri riešení kolízií pomocou spájaných zoznamov, ak hašovacia funkcia je |k| mod 5 a vkladáme prvky 13, -2, 0, 8, 10, 17?

Vzorové riešenia ukážkových príkladov na semestrálny test

• Príklad 1: (8+3*4)/(2+3), hodnota 4, strom:

         /
       /  \
      /    \
     +      +  
    / \    / \
   8   *  2   3
      / \
     3   4

• Príklad 2: postfix 2 4 + 3 5 * / 1 2 - / prefix: / / + 2 4 * 3 5 - 1 2
• Príklad 3: na zásobníku budú čísla 8 a 12 (8 je na spodku zásobníka). Číslo 12 vzniklo vynásobením 3 a 4.
• Príklad 4: na zásobníku budú znaky A, D, C (A na spodku zásobníka), v rade bude písmeno B
• Príklad 5:

Preorder:  ABDEHICFD
Postorder: DHIEBFGCA
Inorder:   DBHEIAFCG

• Príklad 6:

        #
       / \
      #   *
     /\
    *  #
      /\
     *  *

• Príklad 7:

        3
       / \
      1   4
      \    \
       2    5
             \
              6

• Príklad 8: (namiesto dvojitého krúžku používame *)

          .
         / \
        /   \
       /     \ 
      a       b
     / \     /
    a   b   a*
   /   /   / \
  a   a*  a*  b*
 /
b*

• Príklad 9:

Pre každý index tabuľky 0,..,4 uvádzame zoznam prvkov, ktoré sa do neho zahašujú. Tieto budú pospájané v zozname v uvedenom poradí.

0: 10, 0
1:
2: 17, -2
3: 8, 13
4: