ASP1/K2 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])
j = 1
nodes[1] = GETNODE(arr[1])
for i = 1 to n do
    nodes[i] = GETNODE(arr[i])
    if j < n then
        j = j + 1
        left(nodes[i]) = GETNODE(arr[j])
    end_if
    if j < n then
        j = j + 1
        right(nodes[i]) = GETNODE(arr[j])
    end_if
end_for
return nodes[1]

GETNODE(value)
ALLOCATE(node)
left(node) = nil
right(node) = nil
value(node) = value
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
UKU	5
KUR	6
RI	7
IKU	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 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 10 110 0
• Krajnje kodirano: 000 0001 00010 0 100011 0 1100100 0 10 110 0
• Krajnje stablo:

  11
 /  \
A    6
5   / \
   B   4
   2  / \
     R   2
     2  / \
       1   K
      / \  1
    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.

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.

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.