Grafy - kartkówka

Co to jest graf?

• Graf to struktura danych składająca się z wierzchołków bez krawędzi.

• Graf to rodzaj papieru używanego do rysowania diagramów.

• Graf to jednostka miary stosowana w matematyce.

• Graf to struktura danych składająca się z wierzchołków połączonych krawędziami.

Co to jest graf nieskierowany?

• Graf nieskierowany to graf, w którym krawędzie mają określony kierunek.

• Graf nieskierowany to graf, w którym krawędzie mają różne długości.

• Graf nieskierowany to graf, w którym krawędzie są zawsze prostopadłe.

• Graf nieskierowany to graf, w którym krawędzie nie posiadają określonego kierunku.

Jakie są różne sposoby reprezentacji grafu?

• Graf euklidesowy

• Drzewo przeszukiwania

• Macierz sąsiedztwa, lista sąsiedztwa, lista krawędzi, macierz incydencji

• Macierz incydencji

Co znaczy skrót BFS?

• Breadth-First Search

• Backward-First Search

• Best-First Search

• Binary-First Search

Na czym polega przeszukiwanie grafu w algorytmie BFS?

• Losowe odwiedzanie wierzchołków grafu

• Wybieranie wierzchołków do odwiedzenia na podstawie ich identyfikatorów

• Przechodzenie do sąsiadujących wierzchołków dopiero po odwiedzeniu wszystkich wierzchołków na danym poziomie

• Odwiedzanie wszystkich sąsiadujących wierzchołków danego wierzchołka przed przejściem do kolejnego poziomu grafu.

Strukturą pomocniczą przeszukiwania wszerz - BFS jest?

• Kopiec

• Drzewo

• Stos

• Kolejka

Na czym polega przeszukiwanie wgłąb?

• Przechodzenie poziomów grafu bez odwiedzania wszystkich wierzchołków

• Odwiedzanie wszystkich wierzchołków w danym grafie przed przejściem do kolejnego poziomu

• Losowe wybieranie wierzchołków do odwiedzenia

• Wybieranie tylko wierzchołków o najmniejszej wartości

Strukturą pomocniczą przeszukiwania wgłąb jest?

• Kolejka

• Tablica

• Kopiec

• Stos

Kto jest autorem algorytmu Dijkstry?

• Edsger Dijkstra

• Grace Hopper

• 
  Alan Turing

• Donald Knuth

Do czego służy algorytm Dijkstry?

• Rozpoznawanie obrazów

• Sortowanie danych

• Wyznaczanie najkrótszych ścieżek w grafie

• Kompresja plików