АСП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
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:
- 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.
- Dubina steka direktno zavisi od broja desnih podstabala u stablu. U oba slučaja razmatramo stablo najveće dubine - degenerisano stablo. U slučaju da 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 su svi čvorovi redom sa desne strane u ovakvom stablu, svaki čvor bi se po jednom morao staviti na stek pa skinuti sa njega, te je potreban stek one veličine koliko ima i čvorova - n.
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)