Programovanie (1) v C/C++
1-INF-127, ZS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · SVGdraw · Testovač · Skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Zapisovanie známok a konzultácie ohľadom výsledkov skúšku budú 8.1. 14:30-16:30 v miestosti M-163. Známky sa budú dať zapísať aj poobede po termíne 22.1.
· Tretia a štvrtá opravná písomka budú v stredu 17.1. o 13:00 a 14:30 v posluchárni B, treba sa prihlásiť cez AIS. Pozrite si tiež ukážkové príklady
· Riadne termíny skúšky pondelok 8.1. a pondelok 22.1., prvý opravný streda 31.1., druhý opravný vo februári (konflikty v termínoch nám dajte vedieť čím skôr).
· Do konca skúškového môžete vypĺňať študentskú anketu: https://anketa.uniba.sk/fmph/ Tešíme sa na konštruktívne návrhy, ktoré nám pomôžu zlepšiť predmet do budúcnosti.


Zimný semester, príklady na test

Z Programovanie
Prejsť na: navigácia, hľadanie

Na štvrtom teste budú podobné typy príkladov, aké poznáte z prvých troch testov, napríklad

  • napíšte funkciu, ktorá robí zadanú činnosť (napr. so stromom, zoznamom, zásobníkom, radom atď)
  • 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.

Ukážkové príklady na písomný 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: 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 6: Nakreslite binárny vyhľadávací strom, ktorý dostaneme, ak do prázdneho stromu postupne vkladáme záznamy s kľúčami 3, 4, 1, 2, 5, 6 (v tomto poradí).
  • Príklad 7: 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 8 Ako bude vyzerať hešovacia tabuľka pri riešení kolízií pomocou spájaných zoznamov, ak heš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 písomný 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:
        #
       / \
      #   *
     /\
    *  #
      /\
     *  *
  • Príklad 6:
        3
       / \
      1   4
      \    \
       2    5
             \
              6
  • Príklad 7: (namiesto dvojiteho krúžku používame *)
          .
         / \
        /   \
       /     \ 
      a       b
     / \     /
    a   b   a*
   /   /   / \
  a   a*  a*  b*
 /
b*
  • Príklad 8:

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

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