Dataabstraktion kap 8 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 en abstrakt datatyp (abstract data type)?
En datatype som innehåller både data och operationer för att hantera datat.
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).
Vad är skillnaden mellan en statisk (static) och en dynamisk (dynamic) datastruktur (data structure)?
Form och storlek (strukturen) av en statisk datastruktur förändras inte över tiden, även om innehållet
kan förändras, medan form och storlek (strukturen) av en dynamisk datastruktur kan förändras.
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-firstout” (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)
