SI Wiki - Кориснички доприноси [sr]

ОО2/Јун 2021

2021-06-08T22:05:48Z

Иван Цветић: Dodat 6. zadatak za G4

{{tocright}}
* Za pitanja sa više odgovora, tačni odgovori su <span class="solution-example">podebljani i uokvireni</span>.
* Za pitanja za koje se odgovori unose, tačni odgovori su podvučeni i sakriveni: <span class="spoiler-example">ovako</span>.
* Pritisnite na sledeće dugme kako biste ih sakrili ili otkrili: <span class="unhide-spoilers unhide-solutions"></span>

== G1/G2 ==
=== 1. zadatak ===
Koja od sledećih tvrđenja su tačna za programski jezik Java?
<div class="abc-list">
# <span class="solution">Moguće je imenovati promenljive u izvornom kodu napisanom na jeziku Java koristeći srpsko ćirilično pismo.</span>
# Veličina primitivnog podatka tipa <code>char</code> u programskom jeziku Java je tačno 8 bita.
# <span class="solution">Izvorni kod napisan na programskom jeziku Java koristeći ASCII način kodiranja translira se pre prevođenja koristeći UTF-16 način kodiranja.</span>
# <span class="solution">Java koristi UTF-16 način kodiranja za kodiranje znaka (<code>char</code>).</span>
# Java koristi isključivo ASCII način kodiranja za kodiranje znaka (<code>char</code>).
</div>

=== 2. zadatak ===
Koja od sledećih tvrđenja su tačna za glavni metod (funkciju <code>main</code> koja predstavlja ulaznu tačku programa) na programskom jeziku Java?
<div class="abc-list">
# <span class="solution">Glavni metod mora biti javno dostupan.</span>
# <span class="solution">Glavni metod mora biti statički metod.</span>
# Glavni metod može da ima proizvoljan broj parametara proizvoljnog tipa.
# <span class="solution">Povratna vrednost glavnog metoda mora biti tipa <code>void</code>.</span>
# <span class="solution">Svaka od više klasa koje obrazuju program može da definiše metod <code>main</code>, sa odgovarajućom deklaracijom glavnog metoda i različitim telom, od kojih svaki može da bude glavni metod u različitim pokretanjima programa.</span>
</div>

=== 3. zadatak ===
Koja od sledećih tvrđenja su tačna na programskom jeziku Java?
<div class="abc-list">
# <span class="solution">Paketi rešavaju problem konflikta imena tipova.</span>
# <span class="solution">Paketi ostvaruju koncept prostora imena sličan konceptu <code>namespace</code> u jeziku C++.</span>
# Po konvenciji, imena paketa se pišu isključivo velikim slovima.
# <span class="solution">Paket predstavlja skup logički povezanih tipova objekata (na primer, klasa, interfejsa).</span>
# <span class="solution">Paketi utiču na pravo pristupa sadržanim tipovima i članovima tipova.</span>
</div>

=== 4. zadatak ===
Šta ispisuje sledeći program na programskom jeziku Java? Upisati simbol <code>x</code> ukoliko se program ne prevodi.
<syntaxhighlight lang="java">
interface I {
static void m() {
System.out.print(1);
}
}

class B {
public static void m() {
System.out.print(2);
}
}

class D extends B implements I {
public D() {
m();
B.m();
}
}

public class Test {
public static void main(String args[]) {
new D();
}
}
</syntaxhighlight>
Odgovor: <span class="spoiler">22</span>

Objašnjenje: <span class="spoiler">Poziv <code>m()</code> poziva nasleđeni metod klase <code>B</code> jer se statički metod interfejsa mora pozvati eksplicitno preko naziva interfejsa.</span>

=== 5. zadatak ===
Šta može da stoji umesto #### da bi se sledeći izvorni kod napisan na programskom jeziku Java uspešno preveo?
<syntaxhighlight lang="java">
public class Test {
public static void main(String[] args) {
try {
####
} catch (Exception e) {}
}
}
</syntaxhighlight>
<div class="abc-list">
# <syntaxhighlight lang="java" inline>throw 1;</syntaxhighlight>
# <syntaxhighlight lang="java" inline>throw new Throwable();</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>throw new Exception();</syntaxhighlight></span>
# <syntaxhighlight lang="java" inline>throw;</syntaxhighlight>
# <syntaxhighlight lang="java" inline>throw new Object();</syntaxhighlight>
</div>
Objašnjenje: <span class="spoiler">Izuzetak koji se baca kroz <code>throw</code> na programskom jeziku Java mora biti izveden iz <code>Throwable</code>. Bacanje <code>Throwable</code> se ovde neće prevesti jer metoda ne hvata niti deklariše u <code>throws</code> klauzuli <code>Throwable</code>.</span>

=== 6. zadatak ===
Koja od sledećih tvrđenja su tačna za programski jezik Java?
<div class="abc-list">
# <span class="solution">Lokalnu klasu moguće je definisati unutar metoda klase.</span>
# <span class="solution">Lokalnu klasu moguće je definisati unutar konstruktora klase.</span>
# <span class="solution">Lokalnu klasu moguče je definisati unutar inicijalizacionog bloka klase.</span>
# Lokalnu klasu moguće je definisati unutar definicije klase, van bilo kog bloka koda.
# <span class="solution">Lokalnu klasu moguće je definisati unutar main funkcije.</span>
</div>

=== 7. zadatak ===
Dat je sledeći programski kod napisan na programskom jeziku Java.
<syntaxhighlight lang="java">
class Brojac {
private int br = 0;
public void inkrement() { br++; }
public int dajBroj() { return br; }
}

public class Test {
public static void main(String args[]) throws InterruptedException {
Brojac brojac = new Brojac();
Thread[] niti = new Thread[10];

for (int i = 0; i < niti.length; i++) niti[i] = new Thread(() -> { brojac.inkrement(); });
for (int i = 0; i < niti.length; i++) niti[i].start();
for (int i = 0; i < niti.length; i++) niti[i].join();
System.out.print(brojac.dajBroj());
}
}
</syntaxhighlight>
Koje od sledećih tvrdnji su tačne za prikazani kod?

''(Izaberite jedan odgovor)''
<div class="abc-list">
# Programski kod se uspešno prevodi i izvršava. Prilikom izvršavanja programa na standardnom izlazu uvek se ispisuje vrednost 10.
# <span class="solution">Programski kod se uspešno prevodi i izvršava. Prilikom izvršavanja programa na standardnom izlazu može se, ali ne mora, ispisati vrednost 10.</span>
# Programski kod se ne prevodi uspešno.
# Programski kod se uspešno prevodi i izvršava. Prilikom izvršavanja programa na standardnom izlazu uvek se ispisuje vrednost 0.
# Programski kod se uspešno prevodi, ali se prilikom izvršavanja emituje izuzetak ''InterruptedException''.
</div>
Objašnjenje: <span class="spoiler">Metodi klase <code>Brojac</code> nisu sinhronizovani, tako da je tehnički moguće da <code>br++</code> zapravo prvo dohvati vrednost <code>br</code>, onda bude prekinuta od strane neke druge niti, pa pri povratku uveća pročitanu vrednost za 1 i upiše u <code>br</code>, time gazeći vrednost koje su prethodne niti posle prekida upisale.</span>

=== 8. zadatak ===
Klasa <code>Menu</code> izvedena je direktno iz klase:
<div class="abc-list">
# <code>MenuContainer</code>
# <code>MenuComponent</code>
# <code>MenuBar</code>
# <code>Component</code>
# <span class="solution"><code>MenuItem</code></span>
</div>

=== 9. zadatak ===
Koja od sledećih tvrdnji je tačna?

''(Izabrati više odgovora)''
<div class="abc-list">
# <span class="solution">Programi pisani za izvršenje na platformi .NET se prevode u međukod MSIL.</span>
# <span class="solution">Jedna od ciljnih karakteristika radnog okvira .NET je integracija sistema korišćenjem otvorenih standarda za razmenu podataka kakav je XML.</span>
# <span class="solution">Izvršni sklop (''assembly'') za .NET može biti u samo jednom ili više fajlova.</span>
# Izvršno okruženje (CLR) radnog okvira .NET izvršava program iz fajla koji sadrži prevedeni C++ program na mašinski jezik računara domaćina.
# Jezik Java je standard međunarodne organizacije za standardizaciju ISO, za razliku od jezika C# koji nije standardizovan.
</div>

=== 10. zadatak ===
Šta ispisuje sledeći program na jeziku C#?
<syntaxhighlight lang="csharp">
class Program {
static void M1(ref int i) { System.Console.Write(i++ + " "); }
static void M2(ref int i) { System.Console.Write(i/2 + " "); }
static void M3(ref int i) { System.Console.Write(i-- + " "); }

public delegate void Delegat(ref int i);

public static void Main(string[] args) {
Delegat d1 = new Delegat(M1);
Delegat d2 = new Delegat(M2);
Delegat da = d1 + d2;
Delegat d = da + d1;
d += new Delegat(M3) + da;
d -= d1;
d -= d2;
d -= new Delegat(M3);
int i = 3;
d(ref i);
}
}
</syntaxhighlight>
Odgovor: <span class="spoiler">3 2 4</span>

Objašnjenje: <span class="spoiler">U <code>d</code> se pri stvaranju dodaju <code>M1</code> i <code>M2</code> (iz <code>da</code>) pa ponovo <code>M1</code>. Zatim se dodaju <code>M3</code> i ponovo <code>M1</code> i <code>M2</code> (iz <code>da</code>). Onda se uklanjaju <code>M1</code>, <code>M2</code> i <code>M3</code> sa kraja liste poziva pa ostaju samo <code>M1</code>, <code>M2</code> i <code>M1</code> u delegatu. Posle izvršavanja prvog <code>M1</code> ispis je 3 a vrednost je 4, posle <code>M2</code> ispis je 2 a vrednost ostaje ista, i posle drugog <code>M1</code> ispis je 4 i vrednost je 3.</span>

== G3/G4 ==
=== 1. zadatak ===
Koje od sledećih tvrđenja je tačno na programskom jeziku Java?
<div class="abc-list">
# Veličina tipa <code>double</code> je zavisna od implementacije.
# Veličina tipa <code>double</code> je uvek ista i iznosi 32 bita.
# <span class="solution">Veličina tipa <code>double</code> je uvek ista i iznosi 64 bita.</span>
# Veličina tipa <code>double</code> je uvek ista i iznosti 128 bita.
# ...
</div>

=== 2. zadatak ===
Koja od sledećih tvrđenja su tačna na programskom jeziku Java?
<div class="abc-list">
# <span class="solution">Potpis funkcije se sastoji iz imena, broja argumenata i njihovih tipova.</span>
# <span class="solution">Deklaracija sadrži potpis, tip rezultata i <code>throws</code> klauzulu.</span>
# <span class="solution">U jednoj klasi može postojati više metoda sa istim potpisom.</span>
# Ako se u klasi nađe više metoda sa istom deklaracijom, njihova implementacija se u vreme prevođenja spaja u jednu metodu.
# ...
</div>

=== 3. zadatak ===
Koja od sledećih tvrđenja su tačna na programskom jeziku Java?
<div class="abc-list">
# <span class="solution">Jedan paket se može prostirati na više fajlova.</span>
# <span class="solution">Svaki fajl sa izvornim kodom koji je deo nekog paketa mora sadržati naredbu <code>package imePaketa;</code>.</span>
# <span class="solution">Različite metode sa istom deklaracijom se mogu nalaziti u dva različita paketa.</span>
# <span class="solution">Naredba <code>package imePaketa</code> mora biti prva naredba u fajlu.</span>
# Jedan fajl može biti sadržan u više paketa.
</div>

=== 4. zadatak ===
Šta ispisuje sledeći program na programskom jeziku Java? Upisati simbol <code>x</code> ukoliko se program ne prevodi.
<syntaxhighlight lang="java">
interface I {
static void m() {
System.out.print(1);
}
}

class B {
public static void m() {
System.out.print(2);
}
}

class D extends B implements I {
public D() {
I.m();
B.m();
}
}

public class Test {
public static void main(String args[]) {
new D();
}
}
</syntaxhighlight>
Odgovor: <span class="spoiler">12</span>

=== 5. zadatak ===
Šta može da stoji umesto #### da bi se sledeći izvorni kod napisan na programskom jeziku Java uspešno preveo?
<syntaxhighlight lang="java">
class Izuzetak extends Exception {}

class Klasa {
public m() throws Izuzetak {
####
}
}
</syntaxhighlight>
<div class="abc-list">
# <syntaxhighlight lang="java" inline>throw;</syntaxhighlight>
# <syntaxhighlight lang="java" inline>throw 1;</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>throw new RuntimeException();</syntaxhighlight></span>
# <syntaxhighlight lang="java" inline>throw new Exception();</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>throw new Izuzetak();</syntaxhighlight></span>
</div>
Odgovor: <span class="spoiler">Moguće je baciti <code>Izuzetak</code> jer je naznačen u <code>throws</code> klauzuli i <code>RuntimeException</code> jer je neproveren.</span>

=== 6. zadatak ===
Navesti koja su tvrđenja tačna za lokalne klase:
<div class="abc-list">
# <span class="solution">Lokalne klase definisane u nestatičkom okruženju okružujuće klase sadrže pokazivač na objekat okružujuće klase.</span>
# Referenca na lokalnu klasu se može koristiti van bloka u kome je lokalna klasa definisana.
# <span class="solution">Referenca na lokalnu klasu se može proslediti kao povratna vrednost metoda.</span>
# <span class="solution">Referenca na lokalnu klasu se može proslediti kao argument metodu.</span>
</div>

=== 7. zadatak ===
Isti kao [[#7. zadatak|za G1/G2]].

=== 8. zadatak ===
Koje klase su izvedene iz <code>Component</code>?
<div class="abc-list">
# <code>BorderLayout</code>
# <span class="solution"><code>Panel</code></span>
# <code>Graphics</code>
# <code>MenuBar</code>
# <span class="solution"><code>TextField</code></span>
# <span class="solution"><code>Checkbox</code></span>
# <span class="solution"><code>Choice</code></span>
# <span class="solution"><code>Button</code></span>
</div>

=== 9. zadatak ===
Koje od sledećih tvrdnji su tačne u vezi sa izvršnim okruženjem u .NET (CLR)?
<div class="abc-list">
# <span class="solution">CLR je odgovoran za sigurnost i zaštitu.</span>
# CLR ne podržava više jezika.
# <span class="solution">CLR podržava višenitno izvršavanje.</span>
# CLR ne podržava JIT prevođenje.
# <span class="solution">CLR upravlja memorijom programa.</span>
</div>

=== 10. zadatak ===
Neki kod sa delegatima. ''(Nedostaje tekst zadatka.)''

[[Категорија:Рокови]]
[[Категорија:ОО2]]

ОО2/К2 2021

2021-05-07T22:57:15Z

Иван Цветић: /* G3 */ Dodati zadaci za G3 grupu na drugom kolokvijumu iz OOP2 2021.

{{tocright}}
* Za pitanja sa više odgovora, tačni odgovori su <span class="solution-example">podebljani i uokvireni</span>.
* Za pitanja za koje se odgovori unose, tačni odgovori su podvučeni i sakriveni: <span class="spoiler-example">ovako</span>.
* Pritisnite na sledeće dugme kako biste ih sakrili ili otkrili: <span class="unhide-spoilers unhide-solutions"></span>

== G1 ==
=== 1. zadatak ===

=== 2. zadatak ===

=== 3. zadatak ===

=== 4. zadatak ===

=== 5. zadatak ===

=== 6. zadatak ===

=== 7. zadatak ===

=== 8. zadatak ===

=== 9. zadatak ===

=== 10. zadatak ===

== G2 ==
=== 1. zadatak ===
Označiti tačna tvrđenja na programskom jeziku Java:
<div class="abc-list">
# Eksplicitni ili implicitni poziv konstruktora nadklase se može izbeći ako se u konstruktoru izvedene klase pozove neki drugi konstruktor te iste klase.
# <span class="solution">Ako se koristi, poziv drugog konstruktora iste klase mora biti prva naredba u konstruktoru.</span>
# <span class="solution">Konstrukcija objekta se može delegirati pozivom jednog konstruktora iz drugog konstruktora.</span>
# <span class="solution">Rekurziju u delegiranju konstruktora detektuje prevodilac.</span>
# Dozvoljeno je u konstruktoru prvo pozvati konstruktor nadklase a zatim delegirati konstrukciju nekom drugom konstruktoru.
</div>

=== 2. zadatak ===
Označiti tačna tvrđenja na programskom jeziku Java:
<div class="abc-list">
# <span class="solution">Referenca na neki interfejs može pokazivati na literal '''null'''.</span>
# Svi interfejsi su izvedeni iz klase ''Interface'' u paketu '''java.lang'''.
# <span class="solution">Referenci na neki interfejs može se dodeliti objekat bilo koje klase koja proširuje<ref>Ovo nije bila navlakuša, već je trebalo da piše "implementira".</ref> taj interfejs.</span>
# Referenci na interfejs se može dodeliti objekat koji se dobije kada se sa druge strane alokatora <code>new</code> nađe naziv tog interfejsa.
# <span class="solution">Referenca na neki interfejs se može dodeliti referenci tipa ''Object''.</span>
</div>

=== 3. zadatak ===
Šta ispisuje sledeći kod na programskom jeziku Java? Ukoliko se program ne kompajlira, upisati 0.
<syntaxhighlight lang="java">
interface A { default void m() { System.out.println("A.m()"); } }
class C { public void m() { System.out.println("C.m()"); } }
public class Test extends C implements A {
public static void main(String[] arguments) {
Test t = new Test();
t.m();
}
}
</syntaxhighlight>
Odgovor: <span class="spoiler">C.m</span>

=== 4. zadatak ===
Anonimna klasa na programskom jeziku Java može sadržati:
<div class="abc-list">
# konstruktor
# <span class="solution">nestatičke metode</span>
# statičke metode
# <span class="solution">nestatička polja</span>
# statička polja
</div>

=== 5. zadatak ===
Šta se može napisati umesto <code>###</code> kako bi se sledeći kod na programskom jeziku Java prevodio ispravno?
<syntaxhighlight lang="java">
interface Calc {
int m(int a, int b);
}
public class Test {
public static void main(String[] arguments) {
###
}
}
</syntaxhighlight>
<div class="abc-list">
# <span class="solution"><syntaxhighlight lang="java" inline>Calc c = (int a, int b) -> a + b;</syntaxhighlight></span>
# <syntaxhighlight lang="java" inline>Calc c = (int a, int b) -> { a + b };</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>Calc c = (int a, int b) -> { int r = a + b; return r; };</syntaxhighlight></span>
# <syntaxhighlight lang="java" inline>Calc c = (int a, int b) -> return a + b;</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>Calc c = (int a, int b) -> { return a + b; };</syntaxhighlight></span>
</div>

=== 6. zadatak ===
Šta se može napisati umesto <code>$$$</code> kako bi se sledeći kod na programskom jeziku Java ispravno izvršavao i ispisivao 2?
<syntaxhighlight lang="java">
class Spoljna {
int x = 1;
class Unutrasnja {
int x = 2;
public void m(int x) {
System.out.println($$$);
}
}
}

public class Main {
public static void main(String[] arguments) {
new Spoljna().new Unutrasnja().m(3);
}
}
</syntaxhighlight>
<div class="abc-list">
# <syntaxhighlight lang="java" inline>x</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>this.x</syntaxhighlight></span>
# <syntaxhighlight lang="java" inline>super.x</syntaxhighlight>
# <syntaxhighlight lang="java" inline>Spoljna.this.x</syntaxhighlight>
# <syntaxhighlight lang="java" inline>Spoljna.x</syntaxhighlight>
</div>

=== 7. zadatak ===
Označiti tačna tvrđenja na programskom jeziku Java:
<div class="abc-list">
# <span class="solution">''finally'' blok može da postoji bez ''catch'' bloka.</span>
# ''finally'' blok se izvršava samo ukoliko se u ''catch'' bloku baci izuzetak.
# ''finally'' blok se izvršava samo ukoliko se u ''catch'' bloku ne baci izuzetak.
# <span class="solution">''finally'' blok se izvršava bez obzira na to da li je u ''catch'' bloku bačen izuzetak.</span>
# <span class="solution">''finally'' blok se izvršava iako ne dođe do greške.</span>
</div>

=== 8. zadatak ===
Označiti tačna tvrđenja na programskom jeziku Java:
<div class="abc-list">
# Metoda ''start'' ponovo pokreće nit ukoliko je završena.
# <span class="solution">Ponovni poziv ''start'' nakon završetka niti je greška.</span>
# <span class="solution">Poziv metode ''start'' stavlja nit nad kojom je pozvana u red spremnih niti.</span>
# Nit koja poziva ''start'' se blokira.
# <span class="solution">Nit koja poziva ''start'' se ne blokira.</span>
</div>

=== 9. zadatak ===
Označiti tačna tvrđenja na programskom jeziku Java:
<div class="abc-list">
# <span class="solution">Poziv ''interrupt'' nad blokiranom niti izaziva izuzetak ''InterruptedException''.</span>
# Poziv ''interrupt'' nad blokiranom niti izaziva izuzetak ''ThreadDeath''.
# <span class="solution">Poziv ''interrupt'' nad blokiranom niti je deblokira.</span>
# ...
# <span class="solution">Poziv ''interrupt'' nad blokiranom niti ne postavlja ''interrupted'' status.</span>
</div>

=== 10. zadatak ===
Šta je tačno za sledeći kod na programskom jeziku Java?
<syntaxhighlight lang="java">
public class Test {
public static void main(String[] arguments) {
Thread t1 = new Thread(() -> { while (true); });
t1.setDaemon(true);
t1.start();
}
}
</syntaxhighlight>
<div class="abc-list">
# <span class="solution">Referenca ''t1'' pokazuje na demonsku nit.</span>
# <span class="solution">Java virtuelna mašina (JVM) završava svoj rad nakon završetka glavne funkcije.</span>
# Linija sa ''setDaemon'' u kodu ne menja demonski status niti na koju pokazuje ''t1''.
# Nakon izvršenja glavne funkcije se ne izlazi iz programa jer ima još korisničkih niti za izvršavanje.
# Referenca ''t1'' ne pokazuje na demonsku nit.
</div>

== G3 ==
=== 1. zadatak ===
Šta će sledeći program ispisati? Napisati 0 ukoliko se program ne prevodi.
<syntaxhighlight lang="java">
interface A { default void m() { System.out.print("A.m()"); } }
interface B { default void m() { System.out.print("B.m()"); } }
public class X implements A, B {
public void f() { System.out.print("X.f()"); A.super.m(); B.super.m(); }
public static void main (String[] args) {
X x = new X();
x.f();
}
}
</syntaxhighlight>
Odgovor: <span class="spoiler">0</span>

Objašnjenje: <span class="spoiler">Klasa X implementira interfejse koji imaju podrazumevanu metodu istog naziva, a pritom je ne redefiniše kao svoj metod, što je u Javi greška i takav program se neće prevoditi.</span>

=== 2. zadatak ===
Koji su iskazi tačni za metod <code>wait</code>:
<div class="abc-list">
# <span class="solution">Ukoliko se pozove ''interrupt'' za nit za koju je prethodno pozvano ''wait'', takva nit će se deblokirati.</span>
# <span class="solution">Ukoliko se pozove ''interrupt'' za nit za koju je prethodno pozvano ''wait'', baciće se izuzetak ''InterruptedException''.
# Ukoliko se pozove ''interrupt'' za nit za koju je prethodno pozvano ''wait'', baciće se izuzetak ''ThreadDeath''.</span>
# <span class="solution">Ukoliko se pozove ''interrupt'' za nit za koju je prethodno pozvano ''wait'', neće se promeniti status prekida.</span>
</div>

=== 3. zadatak ===
Koji su iskazi tačni za metod <code>join</code>:
<div class="abc-list">
# <span class="solution">Pozivom metoda ''join'' bez argumenata za neku nit, nit koja poziva metod čeka da nit za koju je metod pozvan završi izvršavanje.</span>
# <span class="solution">Metod ''join'' se može pozvati bez argumenata.</span>
# Pozivom metoda ''join'' za neku nit sa zadatim vremenom u milisekundama čekaće se bar toliko vremena, bez obzira na to da li je nit završila izvršavanje pre isteka vremena.
# <span class="solution">Metod ''join'' ne može da se nadjača u izvedenim klasama.</span>
# Pozivom metoda ''join'' podrazumevano se završava nit za koju je pozvan metod.
</div>

=== 4. zadatak ===
Šta važi za anonimne klase:
<div class="abc-list">
# <span class="solution">Anonimne klase mogu pristupati nestatičkim poljima okružujuće klase.</span>
# <span class="solution">Anonimne klase mogu pristupati statičkim poljima okružujuće klase.</span>
# <span class="solution">Anonimne klase mogu pristupati nepromenljivim parametrima metoda koji ih okružuje.</span>
# <span class="solution">Anonimne klase mogu pristupati lokalnim promenljivama okružujućeg metoda kojima se ne menja vrednost.</span>
# Anonimne klase mogu pristupati svim lokalnim promenljivama okružujućeg metoda, kao i njegovim parametrima, bez obzira na to da li im se menja vrednost.
</div>

=== 5. zadatak ===
Šta važi za interfejse:
<div class="abc-list">
# <span class="solution">Podrazumevano su polja interfejsa javna, statička i konačna.</span>
# <span class="solution">Podrazumevano su metodi interfejsa apstraktni i javni.</span>
# <span class="solution">Interfejsi mogu definisati podrazumevane metode.</span>
# <span class="solution">Interfejsi mogu definisati statičke metode.</span>
# Interfejsi mogu imati modifikator final.
</div>

=== 6. zadatak ===
Navesti šta je tačno za demonske niti:
<div class="abc-list">
# <span class="solution">Demonstvo se nasleđuje od niti iz koje je kreirana data nit.</span>
# Demonstvo može da se menja nakon pokretanja niti.
# <span class="solution">Pokušaj promene demonstva nakon pokretanja baciće ''IllegalStateException''.</span>
# Demonske niti će nastaviti izvršavanje nakon završetka svih ostalih niti.
# <span class="solution">Demonstvo se može menjati samo pre pokretanja niti.</span>
</div>

=== 7. zadatak ===
<syntaxhighlight lang="java">
interface Calc {
int f(int x);
}

public class Test {
public static void main(String[] args) {
Test test = new Test();
###
}
}
</syntaxhighlight>
Šta treba da stoji umesto <code>###</code> da bi program korektno završio?
<div class="abc-list">
# <span class="solution"><syntaxhighlight lang="java" inline>Calc c = (a) -> a * a;</syntaxhighlight></span>
# <span class="solution"><syntaxhighlight lang="java" inline>Calc c = a -> a * a;</syntaxhighlight></span>
# <syntaxhighlight lang="java" inline>Calc c = a -> { a*a; }</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>Calc c = b -> b * b;</syntaxhighlight></span>
# <span class="solution"><syntaxhighlight lang="java" inline>Calc c = (int a) -> a * a;</syntaxhighlight></span>
</div>

=== 8. zadatak ===
Koje su tvrdnje tačne za podrazumevani ugrađeni konstruktor:
<div class="abc-list">
# <span class="solution">Ukoliko nije definisan nijedan drugi konstruktor, prevodilac ga automatski obezbeđuje.</span>
# <span class="solution">Podrazumevano će samo pozvati podrazumevani konstruktor natklase.</span>
# Neće pozvati podrazumevani konstruktor natklase samo u slučaju da je klasa direktno izvedena iz klase Object.
# <span class="solution">Ukoliko je klasa javna, i on je podrazumevano javan.</span>
# ''??? svakako nešto netačno''
</div>

=== 9. zadatak ===
<syntaxhighlight lang="java">
public class Spoljna {
int x = 1;
class Unutrasnja {
int x = 2;
void m(int x) {
System.out.print(###);
}
}
public static void main(String[] args) {
new Spoljna().new Unutrasnja().m(3);
}
}
</syntaxhighlight>
Šta može sve stajati umesto <code>###</code> da bi program korektno završio i ispisao 1?
<div class="abc-list">
# <syntaxhighlight lang="java" inline>this.x</syntaxhighlight>
# <syntaxhighlight lang="java" inline>x</syntaxhighlight>
# <span class="solution"><syntaxhighlight lang="java" inline>Spoljna.this.x</syntaxhighlight></span>
# <syntaxhighlight lang="java" inline>Outer.x</syntaxhighlight>
# <syntaxhighlight lang="java" inline>super.x</syntaxhighlight>
</div>

=== 10. zadatak ===
Navesti tačne tvrdnje za izuzetke:
<div class="abc-list">
# Svi izuzeci u Javi moraju biti izvedeni iz klase Exception.
# <span class="solution">Svi izuzeci koji se bacaju u metodu moraju se navesti u njegovoj throws klauzuli.</span>
# <span class="solution">Prevodilac može da proveri tipove izuzetaka navedenih u throws klauzuli.</span>
# Metod može baciti izuzetak isključivo eksplicitnim navođenjem uz throw.
</div>

== Napomene ==
<references />

[[Категорија:Рокови]]
[[Категорија:ОО2]]

Основи електронике

2020-07-13T21:34:11Z

Иван Цветић: Додата је страница за Основе електронике и убачени материјали са предавања и вежби.

== Предавања и вежбе ==
У следеће три датотеке пронаћи ћете одрађене све задатке са папира са вежби из основа електронике, као и исписану теорију са предавања уз нека додатна објашњења и коментаре, затим и неке задатке са вежби који се не налазе у штампаним материјалима са сајта. Треба додати препоруку да је боље задатке из појачавача радити тако што се препознају врсте појачавача унутар кола, уместо на начин на који су овде одрађени, јер је на тај начин брже.
* 1. део: [https://si.kocka.tech/images/8/81/OE_Re%C5%A1avanje_kola.pdf Решавање кола]
* 2. део: [https://si.kocka.tech/images/8/8e/OE_Kompleksne_struje%2C_diode%2C_poja%C4%8Dava%C4%8Di.pdf Комплексне струје, диоде и појачавачи]
* 3. део: [https://si.kocka.tech/images/b/b1/OE_Tranzistori.pdf Транзистори]

[[Категорија:Први семестар]]

Датотека:OE Tranzistori.pdf

2020-07-13T21:20:54Z

Иван Цветић:

Датотека:OE Kompleksne struje, diode, pojačavači.pdf

2020-07-13T21:20:36Z

Иван Цветић:

Датотека:OE Rešavanje kola.pdf

2020-07-13T21:20:07Z

Иван Цветић:

Датотека:M1 K3 - Malešević (P4) - Neprekidnost, izvodi, primene izvoda.pdf

2020-07-13T20:59:20Z

Иван Цветић:

Датотека:M1 K2 - Malešević (P4) - Granične vrednosti.pdf

2020-07-13T20:59:02Z

Иван Цветић:

Датотека:M1 K1 - Malešević (P4) - Algebarske strukture, matrice.pdf

2020-07-13T20:57:53Z

Иван Цветић:

Математика 1

2020-07-13T15:47:58Z

Иван Цветић: /* Предавања */ Додати су документи са предавања проф. др Бранка Малешевића.

== Предавања ==
Следећа три документа покривају градиво које је испредавао проф. др Бранко Малешевић на својим предавањима у групи П4 током 2019/20. школске године. Први документ покрива градиво првог колоквијума (алгебарске структуре и матрице), други документ градиво другог колоквијума (граничне вредности низова и функција) и трећи документ покрива део градива другог и градиво трећег колоквијума (непрекидност, изводи и примена извода).
* K1: [[https://uploads.kocka.tech/M1%20K1%20-%20Male%C5%A1evi%C4%87%20(P4).pdf М1 К1 - Малешевић (П4)]]
* K2: [[https://uploads.kocka.tech/M1%20K2%20-%20Male%C5%A1evi%C4%87%20(P4).pdf М2 К2 - Малешевић (П4)]]
* K3: [[https://uploads.kocka.tech/M1%20K3%20-%20Male%C5%A1evi%C4%87%20(P4).pdf М3 К3 - Малешевић (П4)]]

== Вежбе ==
== Домаћи ==
== Испитни рокови ==
[[Математика 1: Фебруар 2020.]]

[[Category:Обавезни предмети]]
[[Category:Први семестар]]

АСП1/К2 2016

2020-05-14T16:14:17Z

Иван Цветић: /* Rešenje */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI1AS1_K2_1516.pdf 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.
<u>CHECK_SYMMETRIC(''root'', ''node'')</u>
''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: ABABABBAABABABAB
* Tablica kodova:
{| class="wikitable"
! Simbol
! Kôd
|-
| A
| 0
|-
| B
| 1
|-
| C
| 2
|-
| AB
| 3
|-
| BA
| 4
|-
| ABA
| 5
|-
| ABB
| 6
|-
| BAA
| 7
|-
| ABAB
| 8
|-
| BAB
| 9
|-

|}

== 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 ===
Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.
<u>VERTEX IN DEG(''G'', ''n'', ''i'')</u>
in_deg = 0
for k = 1 to n do
curr = next(G[k])
while (curr ≠ '''nil''') do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg

<u>VERTEX OUT DEG(''G'', ''n'', ''i'')</u>
out_deg = 0
curr = next(G[i])
while (curr ≠ '''nil''') do
out_deg = out_deg + 1
curr = next(curr)
end_while
return out_deg

== 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

=== Rešenje ===
Kodirana poruka glasi: 10 001 1 01 0011 10000 1001 01 01 11 10 0.
Ilustracija postupka se nalazi na sledećoj slici:
[[Датотека:Scan 14.05.2020..pdf|оквир|Ilustracija postupka]]

== 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 ===
Funkcija koristi red za čekanje kao dodatnu strukturu pri implementaciji. U red se ređaju najlevlji sinovi, a next ide desno, po braći, i broji koliko se čvorova nalazi povezano desno za dati čvor (to su mu upravo njegova braća). Izlaz funkcije biće maksimalni broj braće pri nekom od prolazaka, što i jeste red stabla.
<u>TREE ORDER BIN(''root'')</u>
INIT_QUEUE(Q)
m = 0
next = root
INSERT(Q, next)
while (not QUEUE_EMPTY(Q)) do
m_curr = 0
next = DELETE(Q)
while (next ≠ '''nil''') do
m_curr = m_curr + 1
if (left(next) ≠ '''nil''') then
INSERT(Q, left(next))
end_if
next = right(next)
end_while
if (m_curr > m) then m = m_curr
end_if
end_while
return m

== 7. zadatak ==
=== Postavka ===
Pitanja:
<div class="abc-list">
# Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom ''Huffman''-ovom algoritmu.
# Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji ''preorder'' obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.
</div>

=== Rešenje ===
<div class="abc-list">
# Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
# Dubina steka direktno zavisi od broja desnih podstabala u stablu. U oba slučaja razmatramo stablo najveće dubine - degenerisano stablo. U slučaju da su svi čvorovi redom sa leve strane u ovakvom stablu, na stek se stavlja samo koren i ništa drugo, te je za ovakvo stablo dovoljan stek veličine '''1''', nezavisno od broja čvorova u stablu. Nasuprot tome, ako su svi čvorovi redom sa desne strane u ovakvom stablu, svaki čvor bi se po jednom morao staviti na stek pa skinuti sa njega, te je potreban stek one veličine koliko ima i čvorova - '''n'''.
</div>

== 8. zadatak ==
=== Postavka ===
Dato je binarno stablo <u>povezano</u> po ''inorder''-u. Napisati i objasniti pseudokod algoritma obilaska po '''inverznom''' ''inorder'' poretku.

=== Rešenje ===
<u>INVERSE INORDER T(''root'')</u>

[[Категорија:Рокови]]

АСП1/К2 2016

2020-05-14T15:47:57Z

Иван Цветић: /* Rešenje */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI1AS1_K2_1516.pdf 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.
<u>CHECK_SYMMETRIC(''root'', ''node'')</u>
''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: ABABABBAABABABAB
* Tablica kodova:
{| class="wikitable"
! Simbol
! Kôd
|-
| A
| 0
|-
| B
| 1
|-
| C
| 2
|-
| AB
| 3
|-
| BA
| 4
|-
| ABA
| 5
|-
| ABB
| 6
|-
| BAA
| 7
|-
| ABAB
| 8
|-
| BAB
| 9
|-

|}

== 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 ===
Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.
<u>VERTEX IN DEG(''G'', ''n'', ''i'')</u>
in_deg = 0
for k = 1 to n do
curr = next(G[k])
while (curr ≠ '''nil''') do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg

<u>VERTEX OUT DEG(''G'', ''n'', ''i'')</u>
out_deg = 0
curr = next(G[i])
while (curr ≠ '''nil''') do
out_deg = out_deg + 1
curr = next(curr)
end_while
return out_deg

== 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

=== Rešenje ===
Kodirana poruka glasi: 10 001 1 01 0011 10000 1001 01 01 11 10 0.
Ilustracija postupka se nalazi na sledećoj slici:
[[Датотека:Scan 14.05.2020..pdf|оквир|Ilustracija postupka]]

== 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 ===
Funkcija koristi red za čekanje kao dodatnu strukturu pri implementaciji. U red se ređaju najlevlji sinovi, a next ide desno, po braći, i broji koliko se čvorova nalazi povezano desno za dati čvor (to su mu upravo njegova braća). Izlaz funkcije biće maksimalni broj braće pri nekom od prolazaka, što i jeste red stabla.
<u>TREE ORDER BIN(''root'')</u>
INIT_QUEUE(Q)
m = 0
next = root
INSERT(Q, next)
while (not QUEUE_EMPTY(Q)) do
m_curr = 0
next = DELETE(Q)
while (next ≠ '''nil''') do
m_curr = m_curr + 1
if (left(next) ≠ '''nil''') then
INSERT(Q, left(next))
end_if
next = right(next)
end_while
if (m_curr > m) then m = m_curr
end_if
end_while
return m

== 7. zadatak ==
=== Postavka ===
Pitanja:
<div class="abc-list">
# Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom ''Huffman''-ovom algoritmu.
# Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji ''preorder'' obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.
</div>

=== Rešenje ===
<div class="abc-list">
# Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
</div>

== 8. zadatak ==
=== Postavka ===
Dato je binarno stablo <u>povezano</u> po ''inorder''-u. Napisati i objasniti pseudokod algoritma obilaska po '''inverznom''' ''inorder'' poretku.

=== Rešenje ===
<u>INVERSE INORDER T(''root'')</u>

[[Категорија:Рокови]]

АСП1/К2 2016

2020-05-14T15:29:21Z

Иван Цветић: /* Rešenje */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI1AS1_K2_1516.pdf 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.
<u>CHECK_SYMMETRIC(''root'', ''node'')</u>
''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: ABABABBAABABABAB
* Tablica kodova:
{| class="wikitable"
! Simbol
! Kôd
|-
| A
| 0
|-
| B
| 1
|-
| C
| 2
|-
| AB
| 3
|-
| BA
| 4
|-
| ABA
| 5
|-
| ABB
| 6
|-
| BAA
| 7
|-
| ABAB
| 8
|-
| BAB
| 9
|-

|}

== 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 ===
Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.
<u>VERTEX IN DEG(''G'', ''n'', ''i'')</u>
in_deg = 0
for k = 1 to n do
curr = next(G[k])
while (curr ≠ '''nil''') do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg

<u>VERTEX OUT DEG(''G'', ''n'', ''i'')</u>
out_deg = 0
curr = next(G[i])
while (curr ≠ '''nil''') do
out_deg = out_deg + 1
curr = next(curr)
end_while
return out_deg

== 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

=== Rešenje ===
Kodirana poruka glasi: 10 001 1 01 0011 10000 1001 01 01 11 10 0.
Ilustracija postupka se nalazi na sledećoj slici:
[[Датотека:Scan 14.05.2020..pdf|оквир|Ilustracija postupka]]

== 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 ===
<u>TREE ORDER BIN(''root'')</u>

== 7. zadatak ==
=== Postavka ===
Pitanja:
<div class="abc-list">
# Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom ''Huffman''-ovom algoritmu.
# Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji ''preorder'' obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.
</div>

=== Rešenje ===
<div class="abc-list">
# Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
</div>

== 8. zadatak ==
=== Postavka ===
Dato je binarno stablo <u>povezano</u> po ''inorder''-u. Napisati i objasniti pseudokod algoritma obilaska po '''inverznom''' ''inorder'' poretku.

=== Rešenje ===
<u>INVERSE INORDER T(''root'')</u>

[[Категорија:Рокови]]

АСП1/К2 2016

2020-05-14T15:24:11Z

Иван Цветић: /* Rešenje */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI1AS1_K2_1516.pdf 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.
<u>CHECK_SYMMETRIC(''root'', ''node'')</u>
''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: ABABABBAABABABAB
* Tablica kodova:
{| class="wikitable"
! Simbol
! Kôd
|-
| A
| 0
|-
| B
| 1
|-
| C
| 2
|-
| AB
| 3
|-
| BA
| 4
|-
| ABA
| 5
|-
| ABB
| 6
|-
| BAA
| 7
|-
| ABAB
| 8
|-
| BAB
| 9
|-

|}

== 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 ===
Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.
<u>VERTEX IN DEG(''G'', ''n'', ''i'')</u>
in_deg = 0
for k = 1 to n do
curr = next(G[k])
while (curr ≠ '''nil''') do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg

<u>VERTEX OUT DEG(''G'', ''n'', ''i'')</u>
out_deg = 0
curr = next(G[i])
while (curr ≠ '''nil''') do
out_deg = out_deg + 1
curr = next(curr)
end_while
return out_deg

== 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

=== Rešenje ===
Kodirana poruka glasi: 10 001 1 01 0011 10000 1001 01 01 11 10 0.
[[Датотека:Scan 14.05.2020..pdf|оквир|Ilustracija postupka]]

== 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 ===
<u>TREE ORDER BIN(''root'')</u>

== 7. zadatak ==
=== Postavka ===
Pitanja:
<div class="abc-list">
# Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom ''Huffman''-ovom algoritmu.
# Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji ''preorder'' obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.
</div>

=== Rešenje ===
<div class="abc-list">
# Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
</div>

== 8. zadatak ==
=== Postavka ===
Dato je binarno stablo <u>povezano</u> po ''inorder''-u. Napisati i objasniti pseudokod algoritma obilaska po '''inverznom''' ''inorder'' poretku.

=== Rešenje ===
<u>INVERSE INORDER T(''root'')</u>

[[Категорија:Рокови]]

АСП1/К2 2016

2020-05-14T15:18:27Z

Иван Цветић: /* Rešenje */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI1AS1_K2_1516.pdf 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.
<u>CHECK_SYMMETRIC(''root'', ''node'')</u>
''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: ABABABBAABABABAB
* Tablica kodova:
{| class="wikitable"
! Simbol
! Kôd
|-
| A
| 0
|-
| B
| 1
|-
| C
| 2
|-
| AB
| 3
|-
| BA
| 4
|-
| ABA
| 5
|-
| ABB
| 6
|-
| BAA
| 7
|-
| ABAB
| 8
|-
| BAB
| 9
|-

|}

== 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 ===
Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.
<u>VERTEX IN DEG(''G'', ''n'', ''i'')</u>
in_deg = 0
for k = 1 to n do
curr = next(G[k])
while (curr ≠ '''nil''') do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg

<u>VERTEX OUT DEG(''G'', ''n'', ''i'')</u>
out_deg = 0
curr = next(G[i])
while (curr ≠ '''nil''') do
out_deg = out_deg + 1
curr = next(curr)
end_while
return out_deg

== 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

=== Rešenje ===
Kodirana poruka glasi: 10 001 1 01 0011 10000 1001 01 01 11 10 0.
[[Датотека:Ilustracija..pdf|мини|Ilustracija postupka]]

== 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 ===
<u>TREE ORDER BIN(''root'')</u>

== 7. zadatak ==
=== Postavka ===
Pitanja:
<div class="abc-list">
# Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom ''Huffman''-ovom algoritmu.
# Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji ''preorder'' obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.
</div>

=== Rešenje ===
<div class="abc-list">
# Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
</div>

== 8. zadatak ==
=== Postavka ===
Dato je binarno stablo <u>povezano</u> po ''inorder''-u. Napisati i objasniti pseudokod algoritma obilaska po '''inverznom''' ''inorder'' poretku.

=== Rešenje ===
<u>INVERSE INORDER T(''root'')</u>

[[Категорија:Рокови]]

АСП1/К2 2016

2020-05-14T10:37:22Z

Иван Цветић: /* Rešenje */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI1AS1_K2_1516.pdf 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.
<u>CHECK_SYMMETRIC(''root'', ''node'')</u>
''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: ABABABBAABABABAB
* Tablica kodova:
{| class="wikitable"
! Simbol
! Kôd
|-
| A
| 0
|-
| B
| 1
|-
| C
| 2
|-
| AB
| 3
|-
| BA
| 4
|-
| ABA
| 5
|-
| ABB
| 6
|-
| BAA
| 7
|-
| ABAB
| 8
|-
| BAB
| 9
|-

|}

== 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 ===
Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.
<u>VERTEX IN DEG(''G'', ''n'', ''i'')</u>
in_deg = 0
for k = 1 to n do
curr = next(G[k])
while (curr ≠ '''nil''') do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg

<u>VERTEX OUT DEG(''G'', ''n'', ''i'')</u>
out_deg = 0
curr = next(G[i])
while (curr ≠ '''nil''') do
out_deg = out_deg + 1
curr = next(curr)
end_while
return out_deg

== 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

=== Rešenje ===

== 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 ===
<u>TREE ORDER BIN(''root'')</u>

== 7. zadatak ==
=== Postavka ===
Pitanja:
<div class="abc-list">
# Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom ''Huffman''-ovom algoritmu.
# Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji ''preorder'' obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.
</div>

=== Rešenje ===
<div class="abc-list">
# Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
</div>

== 8. zadatak ==
=== Postavka ===
Dato je binarno stablo <u>povezano</u> po ''inorder''-u. Napisati i objasniti pseudokod algoritma obilaska po '''inverznom''' ''inorder'' poretku.

=== Rešenje ===
<u>INVERSE INORDER T(''root'')</u>

[[Категорија:Рокови]]

АСП1/К2 2016

2020-05-14T10:36:39Z

Иван Цветић: /* Rešenje */

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI1AS1_K2_1516.pdf 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.
<u>CHECK_SYMMETRIC(''root'', ''node'')</u>
''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: ABABABBAABABABAB
* Tablica kodova:
{| class="wikitable"
! Simbol
! Kôd
|-
| A
| 0
|-
| B
| 1
|-
| C
| 2
|-
| AB
| 3
|-
| BA
| 4
|-
| ABA
| 5
|-
| ABB
| 6
|-
| BAA
| 7
|-
| ABAB
| 8
|-
| BAB
| 9
|-

|}

== 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 ===
Rešenje zadatka je teorijski opisano na 159. strani knjige. Polazi se od pretpostavke da G predstavlja niz ulančanih lista, pa se sa G[i] uzima lista susednosti čvora i.
<u>VERTEX IN DEG(''G'', ''n'', ''i'')</u>
in_deg = 0
for i = 1 to n do
curr = next(G[i])
while (curr ≠ '''nil''') do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg

<u>VERTEX OUT DEG(''G'', ''n'', ''i'')</u>
out_deg = 0
curr = next(G[i])
while (curr ≠ '''nil''') do
out_deg = out_deg + 1
curr = next(curr)
end_while
return out_deg

== 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

=== Rešenje ===

== 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 ===
<u>TREE ORDER BIN(''root'')</u>

== 7. zadatak ==
=== Postavka ===
Pitanja:
<div class="abc-list">
# Komentarisati strategiju obrade istih prioriteta u prioritetnom redu primenjenom u statičkom ''Huffman''-ovom algoritmu.
# Kolika je minimalna, a kolika maksimalna dubina steka korišćenog u iterativnoj realizaciji ''preorder'' obilaska binarnog stabla sa n čvorova. Nacrtati takva stabla.
</div>

=== Rešenje ===
<div class="abc-list">
# Bolje rezultate ćemo dobiti ako dajemo veći prioritet "starijim" članovima reda, tj stablima manje visine. Biranjem nižih stabala dobijamo kraće kodove te je algoritam efikasniji.
</div>

== 8. zadatak ==
=== Postavka ===
Dato je binarno stablo <u>povezano</u> po ''inorder''-u. Napisati i objasniti pseudokod algoritma obilaska po '''inverznom''' ''inorder'' poretku.

=== Rešenje ===
<u>INVERSE INORDER T(''root'')</u>

[[Категорија:Рокови]]

АСП1/К2 2016

2020-05-14T10:28:25Z

Иван Цветић: /* Rešenje */