ch 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
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))
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-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å
Två typer av specialiserade listor är stack och kö, beskriv hur de skiljer sig från varandra!
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)
