datastrukturer listor träd

Vad är en lista?

En lista är en sekvens av element som kan vara av olika typer. Den är dynamisk och kan ändras.

Lista vs Array?

Lista: Dynamisk storlek, kan ändras. Array: Fast storlek, oförändrad efter skapande.

Hur skapar man en lista i Python?

Använd syntaxen: `min_lista = [1, 2, 3]`.

Vad är indexering?

Indexering refererar till att hämta eller manipulera element i en lista baserat på deras position, börjar på 0.

True eller False: Listor kan innehålla olika datatyper.

True. Listor kan innehålla flera olika datatyper samtidigt.

Hur lägger man till ett element i en lista?

Använd `append()` metoden: `min_lista.append(4)`.

Vad gör funktionen `remove()`?

Tar bort det första förekomsten av ett specificerat element från listan.

Vad är skärning (slicing) av listor?

Att extrahera en del av en lista med syntaxen: `lista[start:end]`.

Exempel på skärning: `lista = [0, 1, 2, 3, 4]`. Vad ger `lista[1:3]`?

[1, 2]. Den inkluderar index 1 men exkluderar 3.

Hur sorterar man en lista?

Använd `sort()` metoden för att sortera listan i stigande ordning.

Vad är en tom lista?

En lista utan element, skapad med `tom_lista = []`.

Vad är längden på en lista?

Använd funktionen `len()`: `len(min_lista)` ger antalet element i listan.

Vad gör `insert(index, element)`?

Lägger till ett element på en specifik plats i listan.

True eller False: Listor är immutabla.

False. Listor är muterbara, vilket innebär att de kan ändras.

Vad skiljer en lista från en tupel?

Lista: Muterbar. Tupel: Immuterbar. Kombinationer av datatyper är möjliga i båda.

Vad ger `min_lista[::-1]`?

En omvänd version av listan. Slicing med negativa steg.

Vad är ett träd inom datastrukturer?

Ett träd är en hierarkisk datastruktur med noder som är kopplade. En nod har en förälder och kan ha flera barn.

Vad kallas den översta noden i ett träd?

Rotnod. Den har ingen förälder och är utgångspunkten för trädet.

Fyll i: En _ är en nod utan barn.

Lövnod.

Vad är skillnaden mellan binära träd och allmänna träd?

- Binära träd har max 2 barn per nod. - Allmänna träd kan ha ett godtyckligt antal barn.

Är träd en typ av graf?

Sant. Träd är en speciell typ av graf som är acykliska och sammanhängande.

Vad innebär traversering av ett träd?

Att besöka varje nod i trädet på ett systematiskt sätt, exempelvis pre-order, in-order, eller post-order.

Ge ett exempel på en användning av träd.

Arkivsystem, filhantering, kompilatorer (syntaxträd).

Vad är ett binärt sökträd?

Ett binärt träd där vänster barn är mindre och höger barn är större än föräldern, vilket underlättar sökningar.

Vad är hjärtat av ett AVL-träd?

Balansering. AVL-träd är självbalanserande binära sökträd för att hålla söktiden O(log n).

Vad är en nods djup?

Antalet kanter från rot till noden. Roten har djup 0.

Vad är en nods höjd?

Längden på den längsta vägen från noden till en lövnod.

Ge ett exempel på trädtraversering.

In-order traversering: vänster, rot, höger. Används för att få sorterade värden.

Vad är ett fullständigt träd?

Ett träd där alla nivåer, utom möjligtvis den sista, är helt fyllda.

Vilken typ av träd används ofta för databaser?

B-träd. Används för att hålla data sorterade och möjliggöra snabb sökning, insättning och borttagning.

Vad innebär en trädstruktur i JSON?

JSON representerar hierarkiska data och kan ses som ett träd av nyckel-värde-par.

Vad är ett n-ary träd?

Ett träd där varje nod kan ha upp till n barn. Används i olika applikationer som filsystem.

Vad är en graf?

En graf är en samling av noder (vertices) och kanter (edges) som kopplar noder. Används för att representera relationer.

Skillnad mellan riktad och oriktad graf?

Riktad graf: kanter har riktning. Oriktad graf: kanter har ingen riktning. - Riktade används för flöden.

Vad är ett binärt sökträd?

Ett träd där varje nod har högst två barn, vänster barn < nod < höger barn. Används för effektiv sökning.

Fyll i det tomma: AVL-träd är en _________.

självbalanserande binär sökträd.

Vad används heap för?

Heap används för att implementera prioritetskön. Max-heap och min-heap är vanliga typer.

Sant eller falskt: Träd är cykliska datastrukturer.

Falskt. Träd är acykliska, vilket innebär att de inte har några cykler.

Vad är en trie?

En trie är en speciell typ av träd som används för att lagra en dynamisk uppsättning av strängar. Används ofta i ordlistor.

Hur fungerar en hash-tabell?

En hash-tabell använder en hash-funktion för att mappa nycklar till värden. Kan ge konstant tidskomplexitet för sökning, insättning.

Skillnad mellan B-träd och binärt sökträd?

B-träd kan ha fler än två barn per nod och är avsett för databaser. Binärt sökträd har två barn och används för snabb sökning.

Fördelar med att använda länkade listor?

Dynamisk storlek, enklare insättning och borttagning av noder jämfört med arrayer, ingen överflödesrisk.

Vad är en död nod i ett träd?

En död nod är en nod utan barn. Den kan inte bidra till trädets struktur.

Vad är Dijkstra's algoritm?

En algoritm för att hitta den kortaste vägen i en graf. Använder en prioritetskön.

Vad är en segmentträd?

Ett segmentträd används för att lagra intervall och stödja intervallfrågor. Snabb uppdatering och frågekomplexitet.

Vad är skillnaden mellan BFS och DFS?

BFS (bredden-först-sökning) utforskar nivåer. DFS (djupet-först-sökning) går djupt innan den backar.

Ge ett exempel på en användning av en graf.

Sociala nätverk där noder representerar personer och kanter representerar relationer.

Vad är en cykel i en graf?

En cykel är en väg som börjar och slutar på samma nod utan att återbesöka noder.