Chapter 8 - Databstraktioner Flashcards
Vad är en abstrakt datatyp (abstract data type)?
En datatype 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) (”binärt sökträd”)?
Att varje nod i trädet har två eller färre subträd (barnnoder), att alla noder i det vänstra subträdet innehåller värden lägre än innehållet i den aktuella noden, och att alla noder i det högra subträdet innehåller värden högre än innehållet i den aktuella noden.
Vilka är de fyra grundläggande datastrukturerna (basic data structures) 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, vilket en dynamisk datastruktur kan göra.
Vad kännetecknar ett binärt träd?
Ett binärt träd är en trädstruktur där varje nod kan ha maximalt två barn-noder.
Vad kallas den grundläggande datastruktur som består av ett block av dataelement av samma datatyp och storlek, och där varje dataelement direkt nås via ett index?
Arrayer (arrays).
Vad kallas den grundläggande datastruktur som består av ett block av dataelement av vanligtvis olika datatyper och storlek, och där de enskilda dataelementen nås via namn?
Aggregattyp (aggregate typ) / struct / post (record).
Kan en lista implementeras som en statisk eller dynamisk datastruktur, både och, eller varken eller? Motivera ditt svar!
En lista kan både implementeras som en statisk datastruktur, t.ex. som en array, och som en dynamisk datastruktur bestående av element och pekare.
Beskriv de grundläggande datastrukturerna stack (stack) och kö (queue)?
En stack är en lista där man lägger till och tar bort element i samma ände enligt principen ”last-in-first- out” (LIFO).
En kö är en lista där man lägger till i ena änden och tar bort i den andra änden enligt principen ”first-in-first-out” (FIFO).
Kan lågnivå-datastrukturen array användas för att implementera en kö (queue)? Motivera ditt svar!
Ja, där elementen i arrayen beskriver en cirkulär kö, och man har en pekare till köns huvud (start) och en pekare till dess svans (ände).
Vad är en abstrakt datastruktur? Vad är skillnaden mot en record/struct?
En abstrakt datastruktur beskriver en datatyp och dess operationer, alltså både vad som lagras och vad man kan göra med det.
En record/struct är en sammansatt datastruktur som är en samling av data som kan vara av olika datatyper.
Ge ett exempel på en datastruktur som använder principen LIFO och en datastruktur som använder principen FIFO?
- LIFO: Det senast tillagda elementet tas bort först -> Stack
- FIFO: Det först tillagda elementet tas bort först -> Kö (Queue)
Förklara vad en pekare (pointer) är?
En pekare är en variabel som innehåller minnesadressen till det som den pekar på.
Vad kännetecknar en aggregattyp (struct/record)?
Ett block av data där olika element kan vara av olika datatyp, elementen kallas fält och nås med namn.
Vad kännetecknar rotnoden i en träd-datastruktur?
Att den inte har någon förälder (förändra-nod).
