Kartičky na Dynamické dátové štruktúry a algoritmy
Dynamické dátové štruktúry a algoritmy – Kompletný prehľad
Ťukni na otočenie · Potiahni na navigáciu
Dátové štruktúry
45 kartičiek
Kartička 1
Otázka: Čo je graf a ako je formálne definovaný v matematike?
Odpoveď: Graf je dátová štruktúra na reprezentáciu vzťahov medzi dvojicami objektov, formálne G=(V,E), kde V je množina vrcholov a E je množina hrán spájajúcic
Kartička 2
Otázka: Čo predstavuje vrchol a čo hrana v grafe?
Odpoveď: Vrchol predstavuje objekt a hrana predstavuje vzťah medzi dvoma vrcholmi.
Kartička 3
Otázka: Uveď príklad reálneho problému, ktorý možno modelovať grafom.
Odpoveď: Mestá ako vrcholy a cesty medzi nimi ako hrany.
Kartička 4
Otázka: Aký je rozdiel medzi neorientovaným grafom a orientovaným grafom?
Odpoveď: Neorientovaný graf má hrany bez smeru (spojenie oboma smermi), orientovaný graf (digraf) má hrany so smerom (usporiadané dvojice), spojenie z A do B n
Kartička 5
Otázka: Kde sa typicky používa neorientovaný graf?
Odpoveď: Pri cestných sieťach a mapách.
Kartička 6
Otázka: Kde sa typicky používa orientovaný graf?
Odpoveď: Pri závislostiach úloh, sociálnych sieťach a smerovaných sieťach.
Kartička 7
Otázka: Čo je zoznam susedov v reprezentácii grafu a aká má výhoda a nevýhoda?
Odpoveď: Každý vrchol obsahuje zoznam vrcholov, s ktorými je spojený. Výhoda: menšia pamäťová náročnosť. Nevýhoda: pomalšie zisťovanie konkrétnej hrany.
Kartička 8
Otázka: Ako funguje DFS (Depth First Search)?
Odpoveď: Najprv sa spracuje vrchol a potom sa rekurzívne pokračuje v prehľadávaní jeho susedov do hĺbky.
Kartička 9
Otázka: Ako funguje BFS (Breadth First Search)?
Odpoveď: Najprv sa prejdú všetky vrcholy priamo susedné s aktuálnym vrcholom (vzdialenosť 1), potom všetky vo vzdialenosti 2, atď.
Kartička 10
Otázka: Uveď oblasti použitia grafov uvedené v texte.
Odpoveď: Modelovanie dopravných sietí, sociálnych sietí, počítačových sietí, plánovanie úloh, vyhľadávanie najkratšej cesty.