АСП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

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

TREE ORDER BIN(root)

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.

8. zadatak

Postavka

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

Rešenje

INVERSE INORDER T(root)