АСП1/Јул 2020

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Prvi kolokvijum

1. zadatak

Postavka

Data je retka kvadratna matrica dimenzije 5. Navesti dva načina da se prikaže pomoću ulančanih lista.

Rešenje

2. zadatak

Postavka

Napisati pseudokod za osnovne operacije sa stekom implementiranog pomoću ulančanih lista sa zaglavljem, tako da se u konstantnoj složenosti može dobiti maksimalni element. Dozvoljeno je koristiti još jednu listu.

Rešenje

3. zadatak

Postavka

Prebaciti infiksni izraz A*(B-C)*(A-D!!)+F/G+K u postfiksni i popuniti tabelu ispod.

Operator Ulazni prioritet Stek prioritet Rang
+, - ? ? ?
*, / ? ? ?
! ? ? ?
( ? ? ?
) ? ? ?

Rešenje

4. zadatak

Postavka

Implementirati operacije za dodavanje elemenata na početak i kraj reda implementiranog preko kružnog vektora.

Rešenje

INSERT-BEFORE(Q, value)
INSERT-AFTER(Q, value)

Drugi kolokvijum

1. zadatak

Postavka

  1. Precizno definisati povezana stabla. Koja nova polja se moraju uvesti u normalno stablo kako bi postalo povezano?
  2. Napisati pseudokod funkcije koja prima čvor i izbacuje ga iz stabla povezanog po inorder-u ako je poznato da taj čvor nema levog sina.

Rešenje

2. zadatak

Postavka

Napisati pseudokod funkcije koja za svaki čvor u stablu proverava da li je suma vrednosti svih potomaka tog čvora jednaka vrednosti tog čvora za svaki čvor koji ima potomke.

Rešenje

3. zadatak

Postavka

Dinamički Hafman. (?) Uporediti dužinu karaktera sa dinamičkim Hafmanom i bez njega. (??)

Rešenje

4. zadatak

Postavka

  1. Objasniti postupak konverzije m-arnog stabla u binarno stablo.
  2. Na sledećem primeru m-arnog stabla prikazati postupak konverzije po koracima. (?)

Rešenje

Treći kolokvijum

1. zadatak

Postavka

Napisati funkciju koja iz datog grafa u matričnoj reprezentaciji i niza čvorova pronalazi sve čvorove grafa nedostižne iz čvorova u datom nizu.

Rešenje

GC(G, n, vars, nvars)

2. zadatak

Postavka

Definisati jako povezane komponente. Prikazati postupak njihovog nalaženja na sledećem grafu i nacrtati redukovani graf.

Rešenje

3. zadatak

Postavka

Naći obuhvatno stablo datog grafa (?) Primovim algoritmom. Da li je obuhvatno stablo jedinstveno? Ako nije, objasniti u kojem koraku se može formirati drugačije obuhvatno stablo.

Rešenje

4. zadatak

Postavka

  1. Definisati ekscentričnost čvora.
  2. Napisati pseudokod funkcije koja vraća niz ekscentričnosti svakog čvora grafa.
  3. Napisati pseudokod funkcije koja nalazi središte grafa.

Rešenje