Binarna stabla i njihova svojstva
26 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Što predstavlja visina čvora u binarnom stablu?

  • Broj čvorova u stablu
  • Broj listova u stablu
  • Broj lukova od čvora do korijena (correct)
  • Broj lukova najdužeg puta od čvora do lista

Koja od navedenih karakteristika definira balansirano binarno stablo?

  • Svi čvorovi imaju samo jedno dijete
  • Visina lijevog i desnog podstabla se razlikuje za najviše 1 (correct)
  • Svaki čvor ima dva ili više djece
  • Visina lijevog i desnog podstabla se razlikuje za najviše 2

Koji od navedenih tipova binarnih stabala garantira da svaki list ima istu dubinu?

  • Kompletno binarno stablo (correct)
  • Balansirano binarno stablo
  • Skoro potpuno binarno stablo
  • Binarno stablo pretraživanja

Kako je organizirano stablo za binarno pretraživanje?

<p>Manji elementi su lijevo, a veći desno od svakog čvora (D)</p> Signup and view all the answers

Što je višak u skoro potpuno binarnom stablu?

<p>Posljednja razina ne mora biti do kraja popunjena (C)</p> Signup and view all the answers

Koja tvrdnja o binarnim stablima je točna?

<p>Jedan skup podataka može imati više različitih stabala (B)</p> Signup and view all the answers

Kako se naziva binarno stablo gdje su visine lijevog i desnog podstabla ujednačene?

<p>Balansirano binarno stablo (C)</p> Signup and view all the answers

Koji kriterij ne definira potpuno binarno stablo?

<p>Sva stabla su balansirana (A)</p> Signup and view all the answers

Što je topologijsko sortiranje?

<p>Uređivanje čvorova tako da svaki čvor dolazi prije svojih sljedbenika. (B)</p> Signup and view all the answers

Za koji tip grafova je definirano topologijsko sortiranje?

<p>Usmjereni aciklični grafovi. (A)</p> Signup and view all the answers

Koji je prvi korak u algoritmu za topološko sortiranje?

<p>Pozvati DFS za dobivanje završnih vremena. (B)</p> Signup and view all the answers

Koji od sljedećih koraka dolazi nakon dovršetka čvora u topološkom sortiranju?

<p>Dodaje se na vrh povezane liste. (B)</p> Signup and view all the answers

Koju vremensku složenost ima algoritam za topološko sortiranje?

<p>Θ(V + E) (C)</p> Signup and view all the answers

Kako se može koristiti topološko sortiranje u stvarnom svijetu?

<p>Za planiranje i organizaciju aktivnosti sa ovisnostima. (B)</p> Signup and view all the answers

Što se događa ako graf koji se sortira topološki nije acikličan?

<p>Topološko sortiranje neće biti moguće. (A)</p> Signup and view all the answers

Koja se oznaka koristi za čvorove u trenutku kada su otkriveni tijekom DFS-a?

<p>SIVO (D)</p> Signup and view all the answers

Što je topološko sortiranje u kontekstu grafa?

<p>Redoslijed čvorova u kojem se svaki čvor pojavljuje prije svojih nasljednika. (B)</p> Signup and view all the answers

Koje od sljedećih svojstava mora imati graf da bi se moglo primijeniti topološko sortiranje?

<p>Graf mora biti usmjeren i acikličan. (B)</p> Signup and view all the answers

Koji postupak se koristi za provođenje topološkog sortiranja?

<p>Određivanje čvorova bez ulaznih lukova i njihovo dodavanje u rezultat. (D)</p> Signup and view all the answers

Koja od sljedećih primjena koristi topološko sortiranje?

<p>Planiranje zadataka gdje su neki zadaci ovisni o drugima. (D)</p> Signup and view all the answers

Koji algoritam je povezan s topološkim sortiranjem?

<p>Algoritam za obilazak u dubinu (DFS). (D)</p> Signup and view all the answers

Što se događa ako graf sadrži cikluse prilikom pokušaja topološkog sortiranja?

<p>Nema mogućnosti topološkog sortiranja. (A)</p> Signup and view all the answers

Kako se topološko sortiranje može primijeniti u računalstvu?

<p>Za izvođenje zadaća u redoslijedu koji zadovoljava ovisnosti. (B)</p> Signup and view all the answers

Koji problem može nastati tijekom topološkog sortiranja?

<p>Moguće je dobiti više od jednog rješenja koja su validna. (B)</p> Signup and view all the answers

U kojem slučaju topološko sortiranje neće biti moguće?

<p>Kada graf sadrži cikluse. (A)</p> Signup and view all the answers

Kojoj vrsti grafova je topološko sortiranje primjenjivo?

<p>Usmjereni aciklični grafovi. (D)</p> Signup and view all the answers

Flashcards

Rub stabla (engl. tree edge, T)

Lȗk koji se koristi za otkrivanje novog čvora u grafu. Ovaj lȗk povezuje čvor iz kojeg se trenutno obavlja pretraga u dubinu s čvorom koji nikada nije bio posjećen.

Povratni lȗk (engl. back edge, B)

Lȗk koji povezuje čvor s čvorom koji je bio posjećen ranije tijekom pretrage u dubinu, i taj čvor je prethodnik trenutnog čvora u stablu pretrage.

Preskočni lȗk (engl. forward edge, F)

Lȗk koji povezuje trenutni čvor s čvorom koji je već posjećen, ali nije mu prethodnik u stablu pretrage. Ovaj čvor je sljedbenik trenutnog čvora u stablu pretrage.

Poprečni lȗk (engl. cross edge, C)

Lȗk koji povezuje čvor s čvorom koji nije niti njegov sljedbenik niti prethodnik.

Signup and view all the flashcards

Pretraga u dubinu (engl. Depth First Search, DFS)

Algoritam koji se koristi za pretraživanje grafova tako što se sustavno obilaze čvorovi u dubinu.

Signup and view all the flashcards

Stablo obilaska u dubinu (engl. Depth First Search Tree)

Stablo koje se konstruira tijekom obilaska grafa u dubinu. Sastoji se od rubova stabla (T) i povratnih rubova (B).

Signup and view all the flashcards

Vremenska složenost pretrage u dubinu

Vrijeme potrebno za obilazak grafa ovisi o broju čvorova (V) i broju rubova (E) u grafu.

Signup and view all the flashcards

Topologijsko sortiranje

Algoritam koji uređuje čvorove u grafu tako da ako postoji lȗk (u, v), onda se u nalazi prije v u uređenom poretku.

Signup and view all the flashcards

Graf

Graf je matematički objekt koji se sastoji od skupa čvorova (vrhova) i skupa lukova (bridova) koji povezuju čvorove.

Signup and view all the flashcards

Usmjereni graf

Usmjereni graf je graf u kojem su lukovi usmjereni od jednog čvora do drugog.

Signup and view all the flashcards

Neusmjereni graf

Neusmjereni graf je graf u kojem lukovi nisu usmjereni, već povezuju dva čvora obostrano.

Signup and view all the flashcards

BFS (Breadth-First Search)

Algoritam za obilazak u širinu (BFS) je algoritam za pretraživanje grafa koji sistematski prolazi kroz čvorove u grafu, počevši od određenog polaznog čvora.

Signup and view all the flashcards

DFS (Depth-First Search)

Algoritam za obilazak u dubinu (DFS) je algoritam za pretraživanje grafa koji sistematski prolazi kroz čvorove u grafu, slijedeći duboke grane.

Signup and view all the flashcards

Čvrsto povezane komponente

Čvrsto povezane komponente u grafu su skupovi čvorova u kojima je svaki čvor povezan s bilo kojim drugim čvorom u istoj komponenti.

Signup and view all the flashcards

Ciklus u grafu

Ciklus u grafu je put koji počinje i završava u istom čvoru.

Signup and view all the flashcards

Najkraći put u grafu

Najkraći put u grafu je put koji vodi od polaznog čvora do ciljnog čvora i ukljucjuje najmanji mogući broj lukova.

Signup and view all the flashcards

Minimum spanning tree (MST)

Minimum spanning tree (MST) je podgraf u grafu koji uključuje sve čvorove i ima minimalnu ukupnu težinu lukova.

Signup and view all the flashcards

Binarno pretraživanje

Traženje elementa u sortiranom nizu. Prosuđuju se polovice niza, smanjujući pretraživačko područje u svakom koraku.

Signup and view all the flashcards

Stablo za binarno pretraživanje (SBP)

Stablo u kojem se elementi manji od čvora nalaze lijevo, a veći desno. Ovo ubrzava pretraživanje.

Signup and view all the flashcards

Visina stabla

Visina čvora u stablu je broj lukova od tog čvora do lista najdužeg puta.

Signup and view all the flashcards

Balansirano binarno stablo

Stablo u kojem se visina lijevog i desnog podstabla za svaki čvor ne razlikuje za više od 1.

Signup and view all the flashcards

Potpuno binarno stablo

Stablo gdje svaki list ima istu dubinu, a svaki unutarnji čvor ima dva djeteta.

Signup and view all the flashcards

Skoro potpuno binarno stablo

Stablo gdje posljednja razina ne mora biti do kraja popunjena, ali svi listovi na toj razini su poslagani jedan do drugoga.

Signup and view all the flashcards

Study Notes

Graf - Struktura podataka

  • Graf je struktura podataka koja se sastoji od čvorova i lukova koji povezuju čvorove.
  • Čvorovi mogu biti samostalni.
  • Graf se koristi u raznim područjima STEM-a, uključujući računalne mreže, društvene mreže, kombinatornu optimizaciju i operacijska istraživanja.
  • Graf se također koristi kao model podataka u graf-bazama podataka.
  • Grafovi se mogu prikazati pomoću lista susjednih elemenata ili matrice susjednih elemenata, i mogu biti usmjereni ili neusmjereni, te ciklički ili aciklički.

Primjer grafova u Pythonu

  • Graf se može implementirati korištenjem rječnika (dictionary) u Pythonu.
  • Ključ rječnika predstavlja čvor, a vrijednost je lista susjednih čvorova.

Pretraživanje grafova

  • Postoje dva glavna načina pretraživanja grafova: pretraživanje u dubinu (DFS) i pretraživanje u širinu (BFS).

Vremenska složenost obilaska grafa

  • Vremenska složenost obilaska grafa, pretraživanja u dubinu i pretraživanja u širinu, ovisi o broju čvorova (V) i broju lukova (E) u grafu. Složenost je O(V + E).

Topologijsko sortiranje

  • Topologijsko sortiranje uređuje čvorove usmjerenog acikličkog grafa (DAG) tako da, ako postoji luk iz čvora u u čvor v, onda se u pojavljuje prije v u sortiranom redoslijedu.
  • Često se koristi za zadatke s ovisnostima među aktivnostima.
  • Postoje algoritmi za nalazenje topološkog sortiranja koristeći DFS.

Čvrsto povezane komponente

  • Čvrsto povezana komponenta grafa je maksimalni skup čvorova u grafu koji su međusobno povezani.
  • Čvorovi u jednoj čvrsto povezanoj komponenti su međusobno povezani putem puteva u grafu.
  • Ovaj pojam je bitan za usmjerene grafove.

Tablice raspršivanja (hash tables)

  • Tablice raspršivanja (Hash tables) generaliziraju tablice s direktnim adresiranjem.
  • Koriste se kada se ključevi ne moraju čuvati kao brojevi.
  • Izračunavanje indeksa pomoću funkcije raspršivanja (hash functions).
  • U većini implementacija funkcija raspršivanja vraća broj izrađen na osnovu ulaznog ključa.
  • Tablice raspršivanja su optimizirane za operacija dohvaćanja, dodavanja i brisanja elemenata, tako da u prosjeku postižu linearnu vremensku složenost O(1).
  • U slučajevima kolizija, tablice raspršivanja koriste različite tehnike za rješavanje kolizija, kao npr. ulančavanje ili otvoreno adresiranje.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

ASP Kolokvij 2 PDF

Description

Ovaj kviz ispituje tvoje znanje o binarnim stablima i njihovim karakteristikama. Odgovori na pitanja o visini čvorova, balansiranim stablima, te raznim tipovima binarnih stabala. Provjeri koliko znaš o organizaciji i svojstvima ovih važnih struktura podataka.

More Like This

Binary Trees Overview and Storage Methods
3 questions

Binary Trees Overview and Storage Methods

Binary Trees and Traversal
10 questions

Binary Trees and Traversal

HarmlessZircon8768 avatar
HarmlessZircon8768
Binary Trees Overview
13 questions

Binary Trees Overview

HonestIrony1328 avatar
HonestIrony1328
Data Structures - Multiple Choice Questions
24 questions

Data Structures - Multiple Choice Questions

AdventuresomeProsperity1645 avatar
AdventuresomeProsperity1645
Use Quizgecko on...
Browser
Open
Browser
Browser