АСП1/К2 2017

Zadaci na sajtu predmeta

1. zadatak

Postavka

Napisati u pseudokodu iterativnu funkciju koja određuje širinu binarnog stabla na čiji koren pokazuje pokazivač root. Širina stabla se definiše kao najveća širina svih njegovih nivoa. Funkcija treba da ispiše sve čvorove na nivou najveće širine i vrati određenu širinu. Dozvoljena je upotreba gotovih linearnih struktura podataka

Rešenje

BIN TREE WIDTH(root)
curr_width = max_width = 0
tail = head = GETNODE(root)
next(head) = GETNODE(nil)
head = next(head)
max_level = curr_level = tail
t = nil
while tail ≠ nil do
    if value(tail) = nil then
        if curr_width > max_width then
            while max_level ≠ curr_level do
                t = max_level
                max_level = next(max_level)
                FREENODE(t)
            end_while
            max_width = curr_width
        end_if
        curr_width = 0
        if tail ≠ head then
            curr_level = next(tail)
            next(head) = GETNODE(nil)
            head = next(head)
        end_if
    else
        curr_width = curr_width + 1
        if left(value(tail)) ≠ nil then
            next(head) = GETNODE(left(value(tail)))
            head = next(head)
        end_if
        if right(value(tail)) ≠ nil then
            next(head) = GETNODE(right(value(tail)))
            head = next(head)
        end_if
    end_if
end_while
while value(max_level) ≠ nil do
    OUTPUT(symbol(value(max_level)))
    t = max_level
    max_level = next(max_level)
    FREENODE(t)
end_while
while max_level ≠ nil do
    t = max_level
    max_level = next(max_level)
    FREENODE(t)
end_while
return max_width
GETNODE(value)
ALLOCATE(node)
next(node) = nil
value(node) = value
return node
FREENODE(node)
DEALLOCATE(node)

2. zadatak

Postavka

Posmatra se jedno binarno stablo.

1. Objasniti šta su eksterni čvorovi stabla i za zadato binarno stablo odrediti broj eksternih čvorova. Eksterne čvorove docrtati na zadatom stablu.
2. Izvesti i objasniti vezu između broja eksternih čvorova binarnog stabla $e$ i čvorova stabla $n$.

Rešenje

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

1. Eksterni čvorovi su imaginarni čvorovi na koje pokazuju nezauzeti pokazivači internih čvorova stabla. U ovom stablu gde je $n = 6$ ima ih 7.
2. Po gornjoj definiciji, broj eksternih čvorova jednak je broju nezauzetih pokazivača internih čvorova. Broj svih pokazivača $p$ je duplo veći od broja čvorova, jer svaki čvor ima dva pokazivača u binarnom stablu ($m = 2$). Broj zauzetih pokazivača $z$ jednak je broju grana jer jedna grana zauzima jedan pokazivač, a za broj grana znamo da je za jedan manji od broja čvorova. Odatle dobijamo:

   $p = e + z = 2n$

   $z = n - 1$

   $e = p - z = 2n - n + 1 = n + 1$

3. zadatak

Postavka

Primenom LZW algoritma, prikazati postupak kodiranja poruke ANTANANARIVE, za dati početni sadržaj tabele simbola. Napisati kodiranu poruku i izgled tabele simbola nakon postupka kodiranja

Rešenje

• Kodirana sekvenca: 0 1 2 7 10 3 4 5 6
• Tabela kodova:

Simbol	Kôd
A	0
N	1
T	2
R	3
I	4
V	5
E	6
AN	7
NT	8
TA	9
ANA	10
ANAR	11
RI	12
IV	13
VE	14

4. zadatak

Postavka

Korišćenjem dinamičkog Huffman algoritma dekodirati sledeću poruku 00001010010001101101 ako je poznato da su simbolima A, B i C dodeljeni kodovi fiksne dužine 00, 01 i 10 respektivno. Za dobijenu sekvencu karaktera predložiti njihov drugačiji raspored takav da se pri kodiranju izmenjene sekvence dobije što veća ušteda u memoriji (kraći kod). Izbor obrazložiti.

Rešenje

• Dekodovana poruka: ABBCCAA
• Dinamičko Huffman stablo:

  7
 / \
A   4
3  / \
  2   C
 / \  2
NYT B
 0  2

• Predložena sekvenca: AAABBCC (kodirano sa 00 1 1 001 01 0010 001, odnosno četiri koda manje)
• Obrazloženje: Očigledno je da slova A ima najviše u sekvenci i da se ono treba kodirati sa najmanje bitova. Umesto da redom ubacujemo kodove i očekujemo da se "bore" za zauzimanje mesta koje se kodira sa najmanje bitova najlogičnije je da ih postavimo u poziciju u kojoj će biti kodirani sa najlogičnijim brojem bitova. U ovom slučaju to je 1 bit za A, 2 bita za B i 3 bita za C.

5. zadatak

Postavka

Ako za neko binarno stablo preorder obilazak daje poredak NMCOLAGFBDPRSHQ, a inorder obilazak COALGMBFNPHSRQD, rekonstruisati zadatog stabla.

Rešenje

        N
    /       \
   M         D
 /   \      /
C     F    P
 \   /      \
  O B        R
   \        / \
    L      S   Q
   / \    /
  A   G  H

6. zadatak

Postavka

Dato je binarno stablo na čiji koren pokazuje pokazivač root. Treba pronaći čvor koji je k-ti po preorder poretku, ali tako da se zapravo obiđe što manje čvorova.

1. Dozvoljeno je uvođenje jednog dodatnog polja u čvor stabla, pored postojećih polja left i right, radi što efikasnijeg iterativnog algoritma. Ukratko objasniti svrhu tog polja i algoritam za nalaženje k-tog čvora.
2. Napisati u pseudokodu funkciju koja vraća pokazivač na k-ti čvor po preorder poretku na što je moguće efikasniji način.

Rešenje

Uvodimo polje kojem nam govori koliko se u levom podstablu tog čvora nalazi čvorova. Na taj način možemo da, kad dođemo do nekog čvora, odlučimo da li dalje idemo u njegovo levo ili desno podstablo u zavisnosti od toga da li je broj čvorova u levom podstablu veći ili manji od trenutnog broja traženih čvorova. Na početku procesiranja svakog čvora smanjujemo trenutno traženi broj čvorova i vraćamo trenutni čvor ukoliko je jednak 1.

PREORDER K NODE(root, k)
next = root
n = k
loop
    n = n - 1
    if n = 0 then
        return next
    end_if
    if n ≤ left_size(next) then
        next = left(next)
    else
        next = right(next)
        n = n - left_size(next)
    end_if
end_loop

7. zadatak

Postavka

Dato je odgovarajuće binarno stablo dobijeno konverzijom stabla višeg reda:

1. Predložiti kako u stablo ugraditi informaciju koja omogućava kretanje uz stablo od listova ka korenu.
2. Na osnovu gornjeg predloga napisati funkciju koja za čvor sa zadatom adresom adr vraća njegov nivo u stablu.

Rešenje

Možemo da, nalik povezanim stablima, uvedemo rf bit koji će biti postavljen na 1 ukoliko desni pokazivač pokazuje na brata trenutnog čvora ili postavljen na 0 ukoliko pokazuje na prvog brata svog roditelja, i zatim sve neiskorišćene desne pokazivače (osim korena) povežemo na prvu braću svojih roditelja. Na taj način svi čvorovi jednog nivoa imaće pristup svim čvorovima narednog nivoa.

NODE LEVEL(adr)
level = 1
next = adr
while right(next) ≠ nil do
    if rf(next) = 0 then
        level = level + 1
    end_if
    next = right(next)
end_while
return level

8. zadatak

Postavka

Na kraju svake knjige postoji lista referenci na druge knjige.

1. Predložiti memorijsku predstavu grafa koji predstavlja referenciranje knjiga tako da je olakšano nalaženje broja referenci na neku knjigu.
2. Na osnovu gornjeg predloga napisati funkciju koja za zadatu knjigu nalazi broj referenci na nju.

Rešenje

Graf koji nam je potreban je netežinski usmeren graf u kojem čvorovi predstavljaju knjige a grane reference na knjige, gde grana od A ka B označava da knjiga A sadrži referencu na knjigu B. Optimalna memorijska predstava bi bila preko inverzne liste susednosti, gde je dodatna optimizacija čuvanje dužine te liste u njenom zaglavlju. Pseudokod ispod ne računa tu optimizaciju:

REF COUNT(k)
ref_number = 0
p = IAL[k]
while p ≠ nil do
    ref_number = ref_number + 1
    p = next(p)
end_while
return ref_number