Föreläsning 12: Chapter 8 - Data Abstractions

Vad är en abstrakt datatyp (abstract data type)?

En datatyp som innehåller både data och operationer för att hantera datat.

Vad kännetecknar ett sorterat binärt träd (sorted binary tree)?

Att varje nod i trädet har två eller färre subträd (barnnoder), alla noder i vänstra subträdet innehåller lägre värden än noden, och alla noder i högra subträdet innehåller högre värden än noden.

Vilka är de fyra grundläggande datastrukturerna utöver arrayer?

Listor, stackar, köer och träd.

Vad är skillnaden mellan en dynamisk och en statisk datastruktur?

En statisk datastruktur kan inte ändra form eller storlek över tid (endast innehåll kan ändras), medan en dynamisk datastruktur kan ändra form och storlek över tid.

Vad kännetecknar ett binärt träd?

En trädstruktur där varje nod kan ha maximalt två barn-noder.

Vad kallas datastrukturen som består av block av dataelement av samma typ?

Array.

Vad kännetecknar en array?

Ett block av data där alla element är av samma datatyp, och elementen nås genom index.

Vad kallas datastrukturen med element av olika typer, nås via namn?

Aggregattyp (struct/record/post).

Kan en lista implementeras som statisk eller dynamisk? Motivera.

En lista kan implementeras både statiskt (t.ex. med en array) och dynamiskt (med element och pekare).

Beskriv en stack.

En lista där man lägger till och tar bort element i samma ände enligt LIFO (Last In, First Out).

Vad kännetecknar en stack (LIFO)?

Det senaste elementet som lagts till tas bort först.

Vad är pushing och popping?

Pushing = lägga till element på stacken, Popping = ta bort element från stacken.

Beskriv en kö.

En lista där man lägger till i ena änden och tar bort i andra enligt FIFO (First In, First Out).

Vad kännetecknar en queue (FIFO)?

Det första elementet som lagts till tas bort först.

Vad är en enqueing och dequeing?

Enqueing = lägga till element i kön, Dequeing = ta bort element från kön.

Kan en array användas för att implementera en kö? Motivera.

Ja, genom att beskriva kön som cirkulär med pekare till huvud (start) och svans (slut).

Vad är en abstrakt datastruktur?

En abstrakt datastruktur beskriver en datatyp och dess operationer – vad som lagras och vad man kan göra med det.

Vad är en record/struct?

En sammansatt datastruktur som är en samling av data som kan vara av olika datatyper.

Skillnad mellan abstrakt datatyp och record/struct?

En abstrakt datatyp innehåller både data och operationer, medan en record/struct endast är en samling data (utan operationer).

Ge exempel på LIFO och FIFO datastrukturer.

LIFO = Stack, FIFO = Kö (Queue).

Vad är en pekare / reference (pointer)?

En variabel som innehåller minnesadressen till det den pekar på.

Vad kännetecknar en aggregattyp (struct/record)?

Ett block av data där olika element kan vara av olika datatyp, fälten nås med namn.

Vad kännetecknar en statisk datastruktur?

Strukturens form eller storlek kan inte förändras över tid (endast innehåll).

Vad kännetecknar en dynamisk datastruktur?

Strukturens form och storlek kan förändras över tid (kräver pekare).

Vad kännetecknar rotnoden i ett träd?

Att den inte har någon förälder.

Vad är skillnaden mellan en array och en lista?

Array = statisk, sekventiell lagring. Lista = dynamisk, högre abstraktionsnivå, hanterar minne via pekare.

Vad heter början respektive slutet på en lista?

Början = HEAD, slut = TAIL.

Vad är ett träd (tree)?

En hierarkisk datastruktur med root node högst upp och leaf nodes längst ned.

Vad är en root node, leaf node, subträd och sibling?

Root node = rot, Leaf node = löv (ingen barnnod), Subträd = träd inom ett träd, Siblings = noder med samma förälder.

Vad är ett binärt träd (binary tree)?

En trädstruktur där varje nod kan ha högst två barn (0, 1 eller 2).

Hur kan ett binärt träd representeras?

Med pekare (noder pekar på barn) eller med array (barnens index beräknas).

Hur implementeras arrays?

Alla element lagras i sekventiellt minne, åtkomst via index.

Hur implementeras aggregate types?

Element nås via namn; kan lagras i minne med kända storlekar eller via pekare.

Hur implementeras lists?

Med pekare där varje element pekar på nästa (dynamiskt), eller som array (statisk).

Hur implementeras stacks?

Med array (top-index) eller lista (pekare till top).

Hur implementeras queues?

Med array (cirkulär representation) eller lista med pekare till huvud och svans.

Hur implementeras binary trees med pekare och utan pekare?

Med pekare: varje nod pekar på sina barn. Utan pekare: representeras i array där index används för barnnoder.

Vad är user-defined / customized data types?

Användardefinierade datatyper som kan innehålla både data och operationer.

Vad är hög respektive låg abstraktionsnivå?

Hög = enklare, nära mänskligt språk (t.ex. Python). Låg = detaljerad, nära maskinens sätt att arbeta (t.ex. maskinkod).