АСП1/К2 2019

Zadaci

1. zadatak

Postavka

Neka je skoro kompletno ili kompletno binarno stablo predstavljeno sekvencijalnom memorijskom reprezentacijom (nizom). Na osnovu prosleđenog niza u kome su smeštene celobrojne vrednosti koje predstavljaju informacioni sadržaj čvorova, formirati ekvivalentno binarno stablo ulančane reprezentacije.

Rešenje

FORM TREE(arr, n)
ALLOCATE(nodes[n])
if n = 0 then
    return nil
end_if
j = 1
nodes[1] = GETNODE(arr[1])
for i = 1 to n do
    if j < n then
        j = j + 1
        nodes[j] = GETNODE(arr[j])
        left(nodes[i]) = nodes[j]
    end_if
    if j < n then
        j = j + 1
        nodes[j] = GETNODE(arr[j])
        right(nodes[i]) = nodes[j]
    end_if
end_for
return nodes[1]

GETNODE(value)
ALLOCATE(node)
left(node) = nil
right(node) = nil
value(node) = value
return node

Rešenje broj 2

FORM TREE(arr, n)
if n = 0 then
    return nil
end_if
for i = 1 to floor(n/2) do
    node = GETNODE
    info(node) = arr[i]
    if i = 1 then
        root = node
    left(node) = GETNODE
    info(left(node)) = arr[2 * i]
    if 2 * i + 1 <= n then
        right(node) = GETNODE
        info(right(node)) = arr[2 * i + 1]
return root

GETNODE
ALLOCATE(node)
info(node) = nil
left(node) = nil
right(node) = nil
return node

2. zadatak

Postavka

Primenom LZW algoritma prikazati postupak kodiranja znakovnog niza KUKURIKU, ako je data početna tabela sa kodovima simbola. Napisati kodiranu poruku i izgled tabele simbola nakon postupka kodiranja.

Rešenje

Kodovano: 014234

Simbol	Kôd
K	0
U	1
R	2
I	3
KU	4
UK	5
KUR	6
RI	7
IK	8

3. zadatak

Postavka

Za neko binarno stablo preorder obilazak daje poredak HBIKCFDAEJG, a inorder obilazak HBIADJEGFCK. Odrediti poredak koji se dobija level-order obilaskom i objasniti postupak.

Rešenje

  H
   \
    B
     \
      I
       \
        K
       /
      C
     /
    F
   /
  D
 / \
A   E
   / \
  J   G

Level-order obilazak: HBIKCFDAEJG. Postupak se svodi na to da idemo po svakom nivou binarnog stabla i čitamo sadržaj tog nivoa sleva na desno.

4. pitanje

Postavka

Dato je stablo formirano primenom statičkog Huffman-ovog algoritma. Implementirati funkciju FIND_CODES koja za takvo stablo na čiji koren pokazuje pokazivač root vraća simbole čiji su kodovi dužine tačno k.

Rešenje

FIND CODES(root, k)
if (root = nil) or (k ≤ 0) then
    return nil
end_if
symbols = nil
node = nil
depth = 0
symb_node = nil
p = symbols
QUEUE_INIT(Q1)
QUEUE_INIT(Q2)
QUEUE_INSERT(Q1, root)
QUEUE_INSERT(Q2, 0)
while not QUEUE_EMPTY(Q1) do
    node = QUEUE_DELETE(Q1)
    depth = QUEUE_DELETE(Q2)
    if depth = k then
        if symbol(node) ≠ nil then
            symb_node = GETNODE
            value(symb_node) = symbol(node)
            if symbols = nil then
                symbols = p = symb_node
            else
                next(p) = symb_node
                p = next(p)
            end_if
        end_if
    else
        if left(node) ≠ nil then
            QUEUE_INSERT(Q1, left(node))
            QUEUE_INSERT(Q2, depth + 1)
        end_if
        if right(node) ≠ nil then
            QUEUE_INSERT(Q1, right(node))
            QUEUE_INSERT(Q2, depth + 1)
        end_if
    end_if
end_while
return symbols

5. zadatak

Postavka

Primenom algoritma dinamički Huffman kodirati poruku ABRAKADABRA, ukoliko su početni fiksni kodovi za slova A, B, R, K, D redom 000, 001, 010, 011 i 100. Proces kodiranja prikazati po koracima.

Rešenje

• Krajnje transmitovano: A 0B 00R 0 100K 0 1100D 0 110 110 0
• Krajnje kodirano: 000 0001 00010 0 100011 0 1100100 0 110 110 0
• Krajnje stablo:

   11
  /  \
 A     6
 5   /   \
    2     4
   / \   / \
  1   K R   B
 / \  1 2   2
NYT D
 0  1

6. zadatak

Postavka

Precizno objasniti kako se iterativni algoritam za obilazak po inorder-u može modifikovati tako da se zadato stablo transformiše u povezano (threaded) stablo po istom obilasku.

Rešenje

Može se modifikovati tako što čuvamo pokazivač na prethodno obrađeni čvor i pre procesiranja trenutnog čvora (P(node)) radimo sledeće:

if left(next) = nil then
    left(next) = prev
    lf(next) = 0
end_if
if prev ≠ nil and right(prev) = nil then
    right(prev) = next
    rf(prev) = 0
end_if
prev = next

7. zadatak

Postavka

U kakvom binarnom stablu interna dužina puta postiže maksimum za dati broj čvorova? Izvesti i objasniti izraz za izračunavanje maksimalne interne dužine puta u binarnom stablu sa n čvorova. Nacrtati primer takvog stabla sa 4 čvora i izračunati internu dužinu puta.

Rešenje

Interna dužina puta postiže maksimum u degenerisanom binarnom stablu u kojem ima jedan čvor po nivou, na primer (za n = 4):

      A
     /
    B
   /
  C
 /
D

Interna dužina puta je zbir dužina puteva od korena stabla do svakog internog čvora, što je u ovom slučaju $PI = 1 + 2 + 3 = 6$. Možemo primetiti da je do svakog internog čvora putanja za jedan kraća od nivoa na kojem se nalazi i da ima za jedan manje puteva od broja čvorova iz čega dobijamo da je interna dužina puta za binarno stablo sa $n$ čvorova jednaka $PI_n = 1 + 2 + 3 + ... + (n - 1) = \frac{(n-1) n}{2}$.

8. zadatak

Postavka

Na jednoj društvenoj mreži postoji simetrična relacija prijateljstva između korisnika i asimetrična relacija praćenja kod koje jedan korisnik prati aktivnosti drugog. Potrebno je posmatranu društvenu mrežu modelirati grafom.

1. Predložiti odgovarajući tip grafa i detaljno opisati njegove osobine.
2. Predložiti i obrazložiti odgovarajaću memorijsku reprezentaciju grafa, tako da se optimizuje određivanje ukupnog broja pratilaca nekog korisnika. Korisnikove aktivnosti mogu da prate i prijatelji i pratioci.
3. Napisati pseudkod funkcije koja za zadatog korisnika vraća ukupan broj pratilaca.

Rešenje

U rešenju se pretpostavlja da se u postavci zadatka implicira da su prijatelji ujedno i pratioci.

Ovu mrežu je moguće modelirati usmerenim netežinskim grafom gde čvorovi označavaju korisnike a grane označavaju relacije praćenja, gde grana od čvora A do čvora B označava da korisnik A prati korisnika B. Optimalna reprezentacija grafa u ovom slučaju jeste preko inverzne liste susednosti, jer na taj način mora proći kroz tačno onoliko pratilaca koliki će broj biti vraćen na kraju, a ako se čuva dužina inverzne liste susednosti u zaglavlju onda je složenost algoritma konstantna.

FOLLOWERS(G, i)
followers = 0
p = IAL[i]
while' p ≠ nil do
    followers = followers + 1
    p = next(p)
end_while
return followers