АСП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:
• Tablica kodova:

Simbol	Kôd
A	0
B	1
C	2

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

VERTEX IN DEG(G, n, i)

VERTEX OUT DEG(G, n, i)

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.

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)