Kapitel 8 - instuderingsfrågor 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?
Lists, stacks, queues och träd
Vad är skillnaden mellan en dynamisk och en statisk datastruktur?
I en dynamisk datastruktur kan strukturen och storleken förändras, men inte i en statisk. (Däremot kan värdena förändras i en statisk).
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?
Aggregate type
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).
I en array hittas objekt genom index vilket innebär att nya element är lätta att lägga till i en kö. De blir helt enkelt ett större tal. Däremot att ta ut det första elementet kan vara svårt med hjälp av en array. Då måste alla andra index också flytta på sig.
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 används av stacks, och FIFO av köer.
Förklara vad en pekare (pointer) är?
En pekare är en variabel som innehåller minnesadressen till det som den pekar på. En pekare kan koppla samman objekt i till exempel listor genom att peka på föregående och nästkommande objekt. Det är i kontrast till att använda sig av index.
Vad skiljer en abstrakt datatyp (abstract data type) från en sammansatt datatyp (aggregate type / struct / record)?
En abstrakt datatyp beskriver en datatyp och dess operationer (metoder, procedurer,
funktioner), alltså både vad som lagras (data) 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, men innehåller inga operationer (metoder, procedurer, funktioner).
I en variant av listor lägger man till och tar bort element i samma ände, vad kallas den datastrukturen? I en annan variant lägger man till element i ena änden och tar bort i den andra, vad kallas den datastrukturen?
Det första är en stack, det andra är en kö.
Vad kännetecknar en array?
Ett block av data där alla element är av samma datatyp, och elementen nås genom index.
