opća pitanja, IK

Question 1

Najbrži algoritam za sortiranje niza podataka je SELECT SORT algoritam. (T ili N)

Answer 1

Netočno

Question 2

Vremenska složenost O(n) je bolja (brži algoritam) od vremenske složenosti O(n*logn). (T ili N)

Answer 2

Točno

Question 3

Sortirani niz se može pretvoriti u nesortirani niz u vremenu O( 1 ). (T ili N)

Answer 3

Točno

Question 4

Neka je zadan niz od 49842 podataka. Koliko će biti ponavljanja petlje kod algoritma binarnog pretraživanja?

Answer 4

16

Question 5

Za “Veliko O”, O-notaciju vrijedi:

• To je funkcija rasta vremena izvršavanja ili potrebnog prostora s obzirom na ulazni broj podataka
• To je matematička formulacija koja definira vremensku i prostornu složenost algoritma
• Ova notacija definira točnost našeg algoritma
• To je mjera efikasnosti (učinkovitosti) algoritma/programa
• Prikazuje ponašanje algoritma u najkraćem, tj. najboljem slučaju izvršavanja

Answer 5

• To je funkcija rasta vremena izvršavanja ili potrebnog prostora s obzirom na ulazni broj podataka
• To je mjera efikasnosti (učinkovitosti) algoritma/programa

Question 6

Zadan je dio programa u C-u koji je napisan prema algoritmu binarnog pretraživanja. Napisani su i brojevi linija. Međutim, u jednoj liniji se nalazi greška. U kojoj?

1. dg = 0;
2. gg = N-1;
3. for (;;) {
4. s = (dg+gg)/2;
5. if (V[s]==x) {
6. printf( “%d Pronadjen! Na %d. poziciji u nizu.\n”, x, s );
7. exit( 0 );
8. }
9. if (V[s]<x) gg = s-1;
10. if (V[s]<x) dg = s+1;
11. if (dg>=gg) {
12. printf( “%d nije pronadjen!\n”, x );
13. exit( 1 );
14. }
15. }

Answer 6

9

Question 7

Ako povezana lista ima pokazivače na prvog i na zadnjeg, onda možemo trenutačno (u vremenu O(1)) dodati novi podatak na kraj. (T ili N)

Answer 7

Točno

Question 8

Neka je povezana lista definirana strukturom u C-u:

struct oe_ {

float x;

struct oe_ *sljedeci;

} prvi = NULL;

Zadan je dio programa u C-u koji je napisan prema algoritmu obilaska (ispisa) povezane liste. Napisani su i brojevi linija. Međutim, u jednoj liniji se nalazi greška. U kojoj? Uzeti u obzir da je lista već popunjena podacima, da je t deklariran kao pokazivač na osnovni element liste, te da je i cjelobrojna varijabla.

1. t = prvi; i = 1;
2. for (;;) {
3. if (t==NULL) break;
4. printf( “Element %d. je %f\n”, i++, t->x );
5. prvi = prvi->sljedeci;
6. }

Answer 8

5

Question 9

Povežite algoritam s povezanim listama s njegovom složenosti. Neka lista ima n podataka i neka ima samo pokazivač na prvi podatak.
- Dodavanje novog podatka u sredinu povezane liste.
- Dodavanje novog podatka na početak povezane liste.
- Brisanje prvog podatka u povezanoj listi.
- Pristup prvom elementu.
- Obilazak povezane liste.

Answer 9

• Dodavanje novog podatka u sredinu povezane liste. O(n)
• Dodavanje novog podatka na početak povezane liste. O(1)
• Brisanje prvog podatka u povezanoj listi. O(1)
• Pristup prvom elementu. O(1)
• Obilazak povezane liste. O(n)

Question 10

Ako imamo sortiranu povezanu listu onda ju možemo pretraživati algoritmom binarnog pretraživanja. (T ili N)

Answer 10

Netočno

Question 11

Na nekom računalu se dodavanje elementa na početak povezane liste izvršava za 50ns. Koliko će nanosekundi biti potrebno za dodavanje 462 elemenata u takvu povezanu listu.

Answer 11

23100

Question 12

Ako imamo dvostruko povezanu listu onda možemo pristupiti svakom podatku trenutačno O(1). (T ili N)

Answer 12

Netočno

Question 13

Rekurzivne funkcije ili procedure mogu pozivati samu sebe samo jednom. (T ili N)

Answer 13

Netočno

Question 14

Funkcija int fakt( int n ), može izračunati točno fakt( 12 ) = 479001600. Zašto ova funkcija ne može točno izračunati fakt( n ), za n>12?

• Faktorijel nije niti definiran za n>12
• Zato što računalo nema dovoljno memorije
• Rezultat prelazi izvan opsega vrijednosti 32-bitnog tipa podataka int
• Funkcija može točno izračunati i za n>12
• Za n>12 računanje predugo traje

Answer 14

Rezultat prelazi izvan opsega vrijednosti 32-bitnog tipa podataka int

Question 15

Kod problema povrh(a,b), ako je a=861, koliko treba biti b, da bi izvršavanje ove funkcije trajalo najduže?

Answer 15

430

Question 16

Složenost rekurzivne funkcije int fakt( int n ) koja računa faktorijel je O( n ). (T ili N)

Answer 16

Točno

Question 17

Rekurzivna funkcija ili procedura uvijek mora sadržavati osnovni slučaj koji je nerekurzivan.

Answer 17

Točno

Question 18

Neka je zadana rekurzivna funkcija koja računa faktorijele. Napišite u kojoj liniji koda se pojavljuje greška.

1. int fakt( int n );
2. {
3. if (n<=1) return 1;
4. else return n*fakt( n-1 );
5. }

Answer 18

1

Question 19

Stablo se u memoriji prikazuje pomoću jednog niza i jednog pokazivača. (T ili N)

Answer 19

Netočno

Question 20

Na kojem mjestu se nalazi roditeljski čvor od čvora na mjestu 20713 kod potpunog binarnog stabla?

Answer 20

10356

Question 21

Obilasci binarnog stabla po dubini se mogu riješiti rekurzivnom funkcijom. (T ili N)

Answer 21

Točno

Question 22

Svaki čvor binarnog stabla može imati najviše dva nasljednika. (T ili N)

Answer 22

Točno

Question 23

U stablu na slici koji po redu se ispisuje čvor 11 kod ‘Inorder’ obilaska?

                        11
                      /       \
                    6         19
                  /    \       /     \
                4      8   17     43
                   \       \         /     \
                    5      10   31     49

Answer 23

6

Question 24

Binarno stablo se može efikasno prikazati u računalu:

• Pomoću dinamičke strukture koja sadrži vrijednost čvora i pokazivač na sljedeće čvor
• Pomoću jedne povezane liste.
• Pomoću dinamičke strukture koja koristi vrijednost čvora, i pokazivače ne lijevi i desni nasljednik
• Pomoću matrice s tri stupca
• Pomoću 3 matrice

Answer 24

• Pomoću dinamičke strukture koja koristi vrijednost čvora, i pokazivače ne lijevi i desni nasljednik
• Pomoću matrice s tri stupca

Question 25

Hrpa ima 6398 čvorova. Koliko razina ima ovakva hrpa?

Answer 25

13

Question 26

Za hrpu (gomilu) vrijede slijedeće tvrdnje:

• Svaki čvor hrpe mora imati vrijednost usporedivu s vrijednostima ostalih čvorova.
• Hrpa je nelinearna struktura podataka.
• Hrpa uvijek ima manje razina nego čvorova.
• Hrpa se efikasno ostvaruje koristeći matricu s tri stupca u memoriji računala.
• Hrpa može imati čvor koji ima samo jednog nasljednika.

Answer 26

• Svaki čvor hrpe mora imati vrijednost usporedivu s vrijednostima ostalih čvorova.
• Hrpa je nelinearna struktura podataka.
• Hrpa može imati čvor koji ima samo jednog nasljednika.

Question 27

Neka je zadana procedura void UHRPI(int i) koja uhrpljava čvor na i-tom mjestu prema algoritmu koji smo učili na predavanju i procedura zamjeni(..) koja zamjenjuje mjesta dva elementa u zadanom nizu V od N elemenata. NH je broj elemenata hrpe.

Prema algoritmu za soritranje koristeći hrpu dana je sljedeća procedura u C-u:

1. void HeapSort() {
2. int i;
3. NH = N;
4. for (i=NH/2; i>=0; i–) UHRPI( i );
5. for (i=NH-1; i>=1; i–) {
6. zamjeni( V[1], V[i] );
7. NH–;
8. UHRPI( 0 );
9. }}

Answer 27

6

Question 28

Novi čvor se uvijek dodaje kao zadnji element u hrpu i tamo ostaje. (T ili N)

Answer 28

Netočno

Question 29

Svaka hrpa je istovremeno i sortirani niz. (T ili N)

Answer 29

Netočno

Question 30

Algoritam za sortiranje BubbleSort je sporiji od algoritma za sortiranje koji koristi hrpu HeapSort. (T ili N)

Answer 30

Točno

Question 31

Kakvo je to binarno stablo?

Answer 31

Stablo čiji čvorovi mogu imati najviše dva nasljednika

Question 32

Koliko binarno stablo s i razina može imati čvorova?

Answer 32

2 na i čvorova

Question 33

Kako se binarno stablo može prikazati u memoriji?

Answer 33

Statički (kao matrica s 3 stupca) ili dinamički.

Question 34

Što je to obilazak po dubini?

Answer 34

Od korjena prema dnu stabla.

Question 35

Objasni preorder obilazak.

Answer 35

NLD ispis, Nadređeni -> Lijevi - > Desni

Question 36

Objasni inorder obilazak.

Answer 36

LND ispis, Lijevi - > Nadređeni -> Desni

Question 37

Objasni postorder obilazak.

Answer 37

LDN ispis, Lijevi -> Desni - > Nadređeni

Question 38

Što je to obilazak po širini?

Answer 38

obilazak po razinama s lijeva na desno, potrebna je struktura red

Question 39

Kakvo je to poredano binarno stablo?

Answer 39

lijevi nasljednik i njegova oznaka su strogo manji od nadređenog, a desni nasljednik i njegova oznaka su strogo veći od nadređenog.

Question 40

Kakvo je to izbalansirano stablo?

Answer 40

Stablo koje ima najmanju moguću visinu, tj. najmanji mogući broj razina.

Question 41

Kakvo je to potpuno binarno stablo?

Answer 41

Stablo u kojem su sve razine osim zadnje popunjene.

Question 42

Koliko na svakoj razini ima čvorova u potpunom binarnom stablu?

Answer 42

Ako se korjen označi s 0, onda na svakoj razini ima 2 na n čvorova (n - broj razina)

Question 43

Objasni redne brojeve čvorova u potpunom binarnom stablu

Answer 43

• lijevi nasljednik ima uvjek parni redni broj
• desni nasljednik ima uvjek neparni redni broj
• nadređeni čvor i-tom čvoru ima redni broj floor(i / 2)
• lijevi nasljednik i-tog čvora ima redni broj 2*i
• desni nasljednik i-tog čvora ima redni broj 2*i + 1

Question 44

Kako se u računalu može prikazati potpuno binarno stablo?

Answer 44

Pomoću niza koji se popunjava po razinama.

Question 45

Kakvo je to prošireno binarno stablo?

Answer 45

stablo kojem svaki čvor može imati ili 2 ili nijednog nasljednika

Question 46

Koliki je težinski put od i-tog vanjskog čvora do korjena u proširenom binarnom stablu?

Answer 46

težina(i) * razina(i)

Question 47

Kakvo je to Huffmanovo stablo?

Answer 47

Prošireno stablo s najmanjim težinskim putem (čvorovi s većim težinama su bliže korjenu).

Question 48

Što je to hrpa?

Answer 48

Potpuno binarno stablo za kojeg vrijedi da je vrijednost čvora manja ili jednaka vrijednosti njemu nadređenog čvora.