АСП1/К2 2016

Zadaci

1. zadatak

Postavka

Na slici je dato jedno nekompletno prikazano binarno stablo (desno. Ukoliko preorder obilazak takvog stabla daje poredak čvorova ACBDFE, nacrtati sve moguće izglede ovog stabla.

   A
 /   \
C     ...
 \
  B

Rešenje

Pogledajmo najpre obilazak A CB DFE

Levi deo je kompletan i D mora biti koren desnog podstabla. Odatle dolaze kombinacije:

   A          A          A          A          A
 /   \      /   \      /   \      /   \      /   \
C     D    C     D    C     D    C     D    C     D
 \   / \    \   /      \   /      \     \    \     \
  B F   E    B F        B F        B     F    B     F
              /            \              \        /
             E              E              E      E

2. zadatak

Postavka

Napisati u pseudokodu funkciju koja u binarnom stablu na čiji koren pokazuje pokazivač root utvrđuje da li postoji čvor čija pozicija u stablu (u odnosu na koren) je simetrična u odnosu na poziciju čvora na koji pokazuje pokazivač node. Smatrati da svaki čvor binarnog stabla pored informacionog sadržaja sadrži pokazivače na levo i desno podstablo i pokazivač na roditeljski čvor.

Rešenje

Rešenje se sastoji od toga da se vratimo unazad, pamteći put, i onda silazimo opet ali obrnutim putem. Ukoliko se isprazni ulančana lista (koja glumi stek), to znači da postoji simetrični član.

CHECK_SYMMETRIC(root, node)
path = nil
step = nil
parent = nil
p = node
while p ≠ root do
    step = GETNODE
    parent = parent(p)
    if left(parent) = p then
        info(step) = 0
    else
        info(step) = 1
    end_if
    p = parent
    next(step) = path
    path = step
end_while
while p ≠ nil do
    if path = nil then
        return true
    end_if
    if info(path) = 0 then
        p = right(p)
    else
        p = left(p)
    end_if
    step = path
    path = next(path)
    FREENODE(step)
end_while
return false

3. zadatak

Postavka

Dekodovati poruku 0 1 3 3 4 5 4 9 primenom LZW algoritma, za dati početni sadržaj tabele simbola.

Rešenje

• Dekodovana poruka: ABABABBAABABABAB
• Tablica kodova:

Simbol	Kôd
A	0
B	1
C	2
AB	3
BA	4
ABA	5
ABB	6
BAA	7
ABAB	8
BAB	9

4. zadatak

Postavka

Ukoliko je usmereni graf sa n čvorova predstavljen listom susednosti, napisati u pseudokodu funkcije za izračunavanje ulaznog i izlaznog stepena zadatog čvora i.

Rešenje

Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.

VERTEX IN DEG(G, n, i)
in_deg = 0
for k = 1 to n do 
   curr = next(G[k])
   while (curr ≠ nil) do
      if (info(curr) = i) then
          in_deg = in_deg + 1
      end_if
      curr = next(curr)
   end_while
end_for
return in_deg
VERTEX OUT DEG(G, n, i)
out_deg = 0
curr = next(G[i])
while (curr ≠ nil) do
   out_deg = out_deg + 1
   curr = next(curr)
end_while
return out_deg

5. zadatak

Postavka

Korišćenjem dinamičkih Huffman-ovih kodova, kodirati sekvencu simbola CBCBDAAABABA, ako se simboli A, B, C i D kodovima fiksne dužine kodiraju sa po dva bita 00, 01, 10, 11, respektivno

Rešenje

Postupak rešavanja petog zadatka.

Kodirana poruka glasi: 10 001 1 01 0011 10000 1001 01 01 11 10 0.

Ilustracija postupka se može videti na slici desno.

6. zadatak

Postavka

Dato je binarno stablo B, na čiji koren pokazuje pokazivač root. Stablo B dobijeno je konverzijom m-arnog stabla T u odgovarajuće binarno. Napisati u pseudokodu iterativnu funkciju koja određuje red stabla T.

Rešenje

Funkcija koristi red za čekanje kao dodatnu strukturu pri implementaciji. U red se ređaju najlevlji sinovi, a next ide desno, po braći, i broji koliko se čvorova nalazi povezano desno za dati čvor (to su mu upravo njegova braća). Izlaz funkcije biće maksimalni broj braće pri nekom od prolazaka, što i jeste red stabla.

TREE ORDER BIN(root)
INIT_QUEUE(Q)
m = 0
next = root
INSERT(Q, next)
while (not QUEUE_EMPTY(Q)) do
    m_curr = 0
    next = DELETE(Q)
    while (next ≠ nil) do
        m_curr = m_curr + 1
        if (left(next) ≠ nil) then
            INSERT(Q, left(next))
        end_if
        next = right(next)
    end_while
    if (m_curr > m) then
        m = m_curr
    end_if
end_while
return m

7. zadatak

Postavka

Pitanja:

1. Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom Huffman-ovom algoritmu.
2. Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji preorder obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.

Rešenje

1. Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj. stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
2. Dubina steka direktno zavisi od broja desnih podstabala u stablu. U prvom slučaju razmatramo stablo najveće dubine - degenerisano stablo. Kada su svi čvorovi redom sa leve strane u ovakvom stablu, na stek se stavlja samo koren i ništa drugo, te je za ovakvo stablo dovoljan stek veličine 1, nezavisno od broja čvorova u stablu. Nasuprot tome, ako u stablo degenerisano na levo dodamo desne čvorove na svaki čvor, na stek će pri svakom posećivanju levog deteta biti dodato desno dete pa će na kraju posećivanja sve leve dece na steku biti sva desna deca, što je ukupno $\left\lfloor\frac{n}{2}\right\rfloor$ čvorova.

8. zadatak

Postavka

Dato je binarno stablo povezano po inorder-u. Napisati i objasniti pseudokod algoritma obilaska po inverznom inorder poretku.

Rešenje

Videti rešenje šestog zadatka sa drugog kolokvijuma 2018. godine.