Träd & grafer

Question 1

Vad är några karakteristiska drag för ett träd som datastruktur?

Answer 1

Ett träd har en root node (ingång).
Data lagras hierarkiskt.
Alla noder har en förälder (utom root).
Varje nod kan ha noll eller flera barn.
Noder utan barn kallas “löv”.

Question 1

Ge exempel på hur träd används i olika sammanhang.

Answer 1

Träd används för att representera:

Linux filsystem
If-satsernas syntax i programmering
SQL-syntax för SELECT-satser
Strukturering av naturligt språk
Organisationshierarkier

Question 2

Vad är ett träd inom IT?

Answer 2

Ett träd är en av de vanligaste abstrakta datastrukturerna inom IT. Det är en hierarkisk struktur med termer som kommer från genealogi, t.ex. root, node, parent, children och leaves.

Question 3

Vilka är några användningsområden för trädstrukturer?

Answer 3

Träd används inom:

Filsystem
Kompilatorer (för att analysera programmeringsspråks syntax)
Naturligt språkbehandling
Organisationshierarkier
Sorteringsalgoritmer
m.m

Question 4

Vilka är vanliga operationer på träd?

Answer 4

Skapa ett träd (create)
Lägg till en ny nod (insert)
Räkna antal noder (size)
Räkna längsta väg (height)
Sök efter en viss nod
Traversera trädet (flera sätt)

Question 5

Vad är ett binärt träd?

Answer 5

Ett binärt träd är en typ av träd där varje nod har högst två barn. Det används ofta för sortering och parsning.

Question 6

Hur ser trädet ut efter att noderna 78, 44, 101, 97, 222 har insatts?

Answer 6

Trädet byggs upp enligt följande struktur:

78 är root.
44 är vänster barn till 78.
101 är höger barn till 78.
97 är vänster barn till 101.
222 är höger barn till 101.

Question 7

Vad gör funktionen ascending_write(node)?

Answer 7

Funktionen traverserar trädet in-order (vänster, root, höger) och skriver ut nodernas data i stigande ordning.

Question 8

Hur fungerar insättning av noder i ett träd?

Answer 8

Insättningen börjar från root och jämför varje nods värde för att avgöra om den ska placeras till vänster (mindre värde) eller till höger (större värde).

Question 8

Hur representeras en nod i ett träd med Python?

Answer 8

En nod representeras av en klass Tree med tre attribut: data, left, och right. left och right pekar på barnnoderna.

Question 9

Hur ser trädet ut efter att noderna 78, 44, 101, 97, 222 har insatts?

Answer 9

Trädet byggs upp enligt följande struktur:

78 är root.
44 är vänster barn till 78.
101 är höger barn till 78.
97 är vänster barn till 101.
222 är höger barn till 101.

Question 16

Vad består en graf av?

Answer 16

En graf består av:

Noder (vertices): Punkterna i grafen.
Bågar (edges): Linjer som binder samman noderna.

Question 17

Vilka olika typer av grafer finns det?

Answer 17

Riktade grafer (directed): Bågarna har en riktning.
Oriktade grafer (undirected): Bågarna har ingen riktning.
Viktade grafer (weighted): Bågarna har vikter (kostnader) associerade med sig.
Cykliska grafer (cyclic): Grafer som innehåller cykler.
Acykliska grafer (acyclic): Grafer som inte innehåller cykler.

Question 18

Hur ser en riktad graf ut?

Answer 18

En riktad graf är en graf där varje båge har en riktning. Exempel på en riktad graf:

Noder: A, B, C, D, E
Bågar: A → B, B → C, C → D, D → E

Question 19

Hur ser en oriktad graf ut?

Answer 19

En oriktad graf är en graf där bågarna inte har någon riktning. Exempel på en oriktad graf:

Noder: A, B, C, D, E
Bågar: A – B, B – C, C – D, D – E

Question 20

Vad är en viktad graf och hur används den?

Answer 20

En viktad graf är en graf där varje båge har en vikt (kostnad) associerad med sig. Exempel på användning är att representera avstånd mellan städer. Exempelgraf:

Noder: A (Alingsås), G (Göteborg), J (Jönköping), M (Malmö), S (Stockholm)
Bågar: Alingsås → Göteborg (46), Göteborg → Jönköping (154), etc.

Question 20

Vad kan grafer användas till?

Answer 20

Grafer kan representera en mängd olika problem. Några exempel:

“Travelling Salesman” problem: Hitta den kortaste rundan som besöker varje stad en gång.
Trafiksignalproblem: Optimering av trafikflöden.
Tillverkningsindustri: Processmodulering och simulering.

Question 21

Vad är “Travelling Salesman” problem?

Answer 21

Det är ett klassiskt optimeringsproblem där en säljare ska besöka ett antal städer, var och en exakt en gång, och återvända till startstaden på det sätt som ger den kortaste möjliga totalsträckan.

Question 22

Vad handlar trafiksignalproblemet om?

Answer 22

Trafiksignalproblemet handlar om att använda modeller för att lösa komplexa problem som involverar trafikflöden och optimering av trafiksignaler.

Question 23

Vilka metoder finns för att söka i grafer?

Answer 23

Djupet-först sökning (DFS): Utforskar så långt ner i grafen som möjligt innan den backar och utforskar nästa väg.
Bredden-först sökning (BFS): Utforskar alla grannar till en nod innan den går vidare till nästa nivå.

Question 24

Vad är Colossal Cave?

Answer 24

Colossal Cave är det första textbaserade äventyrsspelet, utvecklat 1975. Det anses vara roten till äventyrsspelsgenren och involverar att utforska ett grottsystem som representeras som en graf.

Question 25

Hur representeras ett grottsystem som en graf?

Answer 25

Ett grottsystem kan representeras som en graf där varje rum är en nod, och varje gång eller passage mellan rum är en båge. Exempelvis kan noderna representera rum och bågarna representerar möjliga vägar mellan rummen.

Question 26

Hur kan ett grottsystem implementeras i Python?

Answer 26

Genom att skapa en Room-klass som innehåller information om rummet, dess anslutningar (norr, söder, öst, väst), rumsinformation och objekt i rummet. Dessa anslutningar kan representera bågarna i grafen.

Question 27

Vilka funktioner kan användas för att manipulera ett grottsystem i Python?

Answer 27

Exempel på funktioner:

make_temp_dict(file): Skapar ett temporärt dictionary från filen.
create_graph(temp_dict): Skapar grafen från dictionaryt.
move(direction, location): Flyttar till en annan plats baserat på användarens kommando.

Question 28

Hur fungerar huvudloopen i grottsystemets Python-implementering?

Answer 28

Huvudloopen körs kontinuerligt och lyssnar på användarens kommando. Baserat på kommandot kan användaren flytta runt i grottsystemet, få hjälp, eller avsluta spelet.