35 Questions
Polovljenjem veličine problema složenost funkcije se izražava kao
O(log2n)
Što radi selection sort?
Nađe najmanji član niza i zamjeni ga s prvom.
Kojim principom radi bubble sort?
Na principu zamjene susjednih članova, ako nisu u dobrom redoslijedu.
Što je najgori slučaj kod selection sorta?
Naopako sortiran niz
Koja je složenost selection sorta?
O(n^2)
Koje je vrijeme izvođenja (najgori slučaj) za dodavanje novog elementa u gomilu?
O(nlog2n)
Složenost heap sort algoritma je bolja od O(nlog2n).
False
Dodavanje novog elementa u gomilu vrši se?
na dnu gomile
Šta je Eulerov graf?
skup vrhova V i ivica E
Jedinstvena zatvorena putanja u Eulerovom grafu postoji ako i samo ako je?
stepen svakog vrha paran
Kod _________________ grafova parovi vrhova (u,v) i (v,u) predstavljaju ____________________.
neusmjerenih; istu ivicu
Graf ne smije imati ivicu sa vrha v koja vodi na isti vrh v tj.ivice oblika (v,v).
True
Šta je višestruki graf?
višestruki; multigraf
Šta je potpuni usmjereni graf?
To je graf sa n vrhova i n(n-1) ivica.
Potpuni neusmjereni graf sa n vrhova ima?
n(n-1)/2 ivica
Šta sadrži pokazivač inicijaliziran na varijablu tipa float?
adresu varijable
Varijablu a na koju pokazuje pokazivač p moguće je izmijeniti:
preko naziva varijable i pokazivača
Pokazivač može pokazivati na varijablu drugog tipa u odnosu na tip pokazivača.
False
Kako se vrši inicijalizacija/postavljanje vrijednosti pokazivača p na varijablu a?
tip *p = &a;
Pokazivač koji je deklarisan, ali ne i inicijaliziran:
važeći je isključivo za pisanje
Kako je moguće vršiti prosljeđivanje varijabli u funkciju?
po vrijednosti (kopiraju se vrijednosti) i po referenci (kopiraju se adrese)
Vrijednost pokazivača je uvijek adresa varijable.
False
Kako je moguće mijenjati vrijednost varijable lokalne za drugu funkciju?
prosljeđivanjem pokazivača na tu varijablu u funkciju iz koje se mijenja.
Vrijednost inicijaliziranog pokazivača je adresa varijable na koju je inicijaliziran.
True
Za dinamičko dodjeljivanje memorije u C jeziku koriste se funkcije:
malloc, realloc i free
A priori analiza algoritma vrši se prije implementacije algoritma u programskom jeziku. TAČNO NETAČNO?
TAČNO
A posteriori analiza algoritma vrši se ___________ implementacije algoritma u programskom jeziku i dobija se _____________.
nakon; mjerenjem na računaru;
A priori analiza vrši se neovisno od vrste računara, programskog jezika i kompajlera. TAČNO NETAČNO?
False
O-notacijom složenosti algoritma predstavlja se:
najgore vrijeme izvođenja
Ako je algoritam ovisan o ulaznom argumentu n oblika polinoma m-tog stepena, onda je vrijeme izvođenja za taj algoritam ________.
O(nm)
Vrijeme izvođenja algoritma ne ovisi o najvećoj vremenskoj konstanti. TAČNO NETAČNO?
False
Složenost O(1) znači da je vrijeme izvođenja:
ograničeno konstantom
Za složenost O(2^n) postoje tačno 2 polinoma koja ga mogu ograničiti i time riješiti u razumnom vremenu. TAČNO NETAČNO?
False
U odnosu na složenost O(n) jednostavnija je:
O(logn)
Ω - notacijom složenosti algoritama predstavlja se:
najbolje vrijeme izvođenja
Study Notes
Here are the study notes for the provided text:
Strukture Podataka
- Pokazivač inicijaliziran na varijablu tipa float sadrži adresu varijable.
- Varijablu a na koju pokazuje pokazivač p moguće je izmjeniti preko naziva varijable i pokazivača.
- Pokazivač koji je deklarisan, ali ne i inicijaliziran, važeći je isključivo za pisanje.
Dinamičko Dodjeljivanje Memorije
- Funkcije za dinamičko dodjeljivanje memorije nalaze se u zaglavlju malloc.h.
- Malloc i realloc funkcije vraćaju univerzalni pokazivač na dinamički dodjeljeni blok memorije.
- Realloc funkcija kao argument prima pokazivač i novu veličinu dinamički dodjeljenog bloka memorije.
Algoritmi
- Algoritam je konačan skup naredbi koji, ukoliko se prati, završava određeni zadatak.
- Kriteriji koje svaki algoritam treba zadovoljiti su: ulaz, izlaz, određenost, konačnost i učinkovitost.
- Algoritam se sastoji od početnih objekata, završnih objekata (rezultata) i instrukcija.
- Analiza složenosti algoritama obuhvaća a priori i a posteriori analizu.
Analiza Složenosti Algoritama
- A priori analiza algoritama vrši se prije implementacije algoritma u programskom jeziku.
- A posteriori analiza algoritama vrši se nakon implementacije algoritma u programskom jeziku i dobija se mjerenjem na računaru.
- Složenost O(1) znači da je vrijeme izvođenja ograničeno konstantom.
- Složenost O(n) znači da je vrijeme izvođenja proporcionalno broju elemenata ulaza.
Pretraživanje Podataka
- Serijsko pretraživanje zapisa ne moraju biti sortirani.
- Binarno pretraživanje je bolje od serijskog, ali lošije od direktne pretrage.
- Binarno pretraživanje zasniva se na polovljenju niza za pretragu.
Indeksiranje Datoteke
- Prednost indeksiranja datoteke je brže pretraživanje podataka.
- Hash funkcija je postupak transformacije ključa zapisa u adresu ili neki drugi broj.
Raspršeno Adresiranje
- Raspršeno adresiranje je postupak transformacije ključa zapisa u adresu ili neki drugi broj.
- Idealnom transformacijom u hash funkciji za M zapisa vjerovatnoća da će se pojaviti 2 različita ključa sa istom adresom je 1/M.
- Raspršeno adresiranje je pogodno za brzo i često pretraživanje podataka.
Ovaj kviz pokriva osnove strukture podataka i funkcije dinamičkog dodjeljivanja memorije u programiranju. Provjerite vaše znanje o pokazivačima, varijablama i rezerviranju memorije.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free