АСП1/К2 2016
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
Kodirana poruka glasi: 10 001 1 01 0011 10000 1001 01 01 11 10 0. Ilustracija postupka se nalazi na sledećoj slici:
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:
- Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom Huffman-ovom algoritmu.
- 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
- 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)