Zimný semester, semestrálny test

• Semestrálny test bude v stredu 11.12. 18:10 v posluchárňach F1 a F2.
• 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.

Príklady o binárnych vyhľadávacích stromoch a lexikografických stromoch (príklady 7 a 8 nižšie) na riadnom termíne testu nebudú, môžu sa však vyskytnúť na opravnom termíne.

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 prefixový 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: