АСП1/К2 2017
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
2. zadatak
Postavka
Posmatra se jedno binarno stablo.
- Objasniti šta su eksterni čvorovi stabla i za zadato binarno stablo odrediti broj eksternih čvorova. Eksterne čvorove docrtati na zadatom stablu.
- Izvesti i objasniti vezu između broja eksternih čvorova binarnog stabla e i čvorova stabla n.
Rešenje
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
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
5. zadatak
Postavka
Ako za neko binarno stablo preorder obilazak daje poredak NMCOLAGFBDPRSHQ, a inorder obilazak COALGMBFNPHSRQD, rekonstruisati zadatog stabla.
Rešenje
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.
- 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.
- 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
7. zadatak
Postavka
Dato je odgovarajuće binarno stablo dobijeno konverzijom stabla višeg reda:
- Predložiti kako u stablo ugraditi informaciju koja omogućava kretanje uz stablo od listova ka korenu.
- Na osnovu gornjeg predloga napisati funkciju koja za čvor sa zadatom adresom adr vraća njegov nivo u stablu.
Rešenje
8. zadatak
Postavka
Na kraju svake knjige postoji lista referenci na druge knjige.
- Predložiti memorijsku predstavu grafa koji predstavlja referenciranje knjiga tako da je olakšano nalaženje broja referenci na neku knjigu.
- Na osnovu gornjeg predloga napisati funkciju koja za zadatu knjigu nalazi broj referenci na nju.