Data Structure and Algorithm Quiz
44 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Hvad er den primære fordel ved at anvende en god hash funktion?

  • At reducere hukommelsesforbruget
  • At øge datatypers kompleksitet
  • At undgå dynamisk hukommelsesallokering
  • At opnå hurtigere udregning af index (correct)

Open-address hash maps er mest effektive, når størrelsen på maps er mindre end det forventede antal key-value par.

False (B)

Hvad er en heap?

Et binært træ med specifikke properties.

En minHeap sikrer, at data i en node er ______ noderne i dens undertræer.

<p>mindre end</p> Signup and view all the answers

Match operationer med deres formål:

<p>get() = Returnerer det mindste element insert() = Indsætter et element remove() = Fjerner det øverste element percolate-up() = Sikrer korrekt placering af elementer</p> Signup and view all the answers

Hvad er tidskompleksiteten for funktionen insert() i en heap?

<p>O(n * log(n)) (D)</p> Signup and view all the answers

En maxHeap sikrer, at data i en node er mindre end noderne i dens undertræer.

<p>False (B)</p> Signup and view all the answers

Hvad kendetegner en heap med hensyn til struktur?

<p>Det er et komplet binært træ.</p> Signup and view all the answers

Hvilken algoritme anvendes til at finde den korteste sti i en vægtet graf?

<p>Dijkstra’s algoritme (A)</p> Signup and view all the answers

Merge sort er en rekursiv sorteringsalgoritme.

<p>True (A)</p> Signup and view all the answers

Hvad stand for BFS i forbindelse med grafer?

<p>Breadth-First Search</p> Signup and view all the answers

Prim's algoritme bruges til at finde en __________ i en vægtet graf.

<p>minimum spanning tree</p> Signup and view all the answers

Match de følgende algoritmer med deres primære anvendelse:

<p>Dijkstra’s algoritme = Find den korteste sti i en graf Kruskal’s algoritme = Find minimum spanning tree Merge sort = Sortering af lister Breadth-First Search = Traversal af grafer</p> Signup and view all the answers

Hvilket begreb henviser til den proces, hvor man fjerner et element fra en datastruktur?

<p>Remove (A)</p> Signup and view all the answers

Hvilken funktioner er vigtige for datastrukturen Linked List?

<p>insert(), remove(), copy()</p> Signup and view all the answers

Hvad er den gennemsnitlige tidskompleksitet for søgning i en Skip List?

<p>O(log(n)) (D)</p> Signup and view all the answers

Skip Lists kræver altid at alle noder eksisterer på samme niveau.

<p>False (B)</p> Signup and view all the answers

Hvad er formålet med 'coin toss'-metoden i Skip Lists?

<p>At bestemme niveauet for noder, så halvdelen af noderne har et højere niveau.</p> Signup and view all the answers

I den værste configuration kan tidskompleksiteten for en søgning i Skip Lists være _____ .

<p>O(n)</p> Signup and view all the answers

Match funktionen til dens beskrivelse:

<p>Søgning = Find den rigtige position for en node. Indsættelse = Placer en ny node i listen. Coin toss = Bestem niveauet for nye noder. Tidskompleksitet = Mål for operationens effektivitet.</p> Signup and view all the answers

En Skip List er en datastruktur, der altid er usorteret.

<p>False (B)</p> Signup and view all the answers

Hvilken tidskompleksitet har søgning i et binary search tree (BST) i værste fald?

<p>O(d) (C)</p> Signup and view all the answers

I et binary search tree er alle knuder til højre for en given knude mindre end knuden.

<p>False (B)</p> Signup and view all the answers

For at fjerne en node fra et BST, skal man først ___ efter noden, der skal fjernes.

<p>søge</p> Signup and view all the answers

Match operationerne med deres tidskompleksitet:

<p>Søgning = O(d) Indsæt = O(d) Fjern = O(d) Søgning i en sorteret liste = O(logn)</p> Signup and view all the answers

Hvilket udsagn beskriver bedst reglerne i et binary search tree?

<p>Alle til venstre er mindre eller lig, alle til højre er større. (C)</p> Signup and view all the answers

En node kan fjernes uden at overveje strukturen i et binary search tree.

<p>False (B)</p> Signup and view all the answers

Under indsættelse i et BST, indsættes nye noder som ___ .

<p>blade</p> Signup and view all the answers

Hvem opfandt Dijkstra’s algoritme?

<p>Edgar Dijkstra (D)</p> Signup and view all the answers

Dijkstra’s algoritme kan ikke håndtere negative vægte på kanter.

<p>False (B)</p> Signup and view all the answers

Hvilken funktion minimerer A* algoritmen for at vælge den næste node?

<p>f(n) = g(n) + h(n)</p> Signup and view all the answers

Dijkstra’s algoritme kan godt fungere med en ______ kø, men er hurtigere med en priority queue.

<p>FIFO</p> Signup and view all the answers

Match følgende begreber med deres definitioner:

<p>g(n) = Omkostningen fra startnode til noden n h(n) = Heurestikken mellem noden n og målnoden T A*-algoritmen = Pathfinding algoritme der bruger heurestik Dijkstra’s algoritme = Algoritme til at finde den korteste vej uden negative cykler</p> Signup and view all the answers

Hvilken heurestik anvendes til 4-vejs bevægelse?

<p>Manhattan (C)</p> Signup and view all the answers

A*-algoritmen udelukker brugen af heurestik i dens procedure.

<p>False (B)</p> Signup and view all the answers

Hvad symboliserer prisen tilføjet til alle noder i Dijkstra’s algoritme?

<p>Omkostningen for at komme fra startnoden til den enkelte node.</p> Signup and view all the answers

Hvilken tidskompleksitet har Insertion sort for et allerede sorteret array?

<p>O(n) (C)</p> Signup and view all the answers

Selection sort har altid en tidskompleksitet på O(n).

<p>False (B)</p> Signup and view all the answers

Hvad er det primære princip bag Merge sort?

<p>Divide and combine</p> Signup and view all the answers

Tidskompleksiteten for Merge sort er O(n * ______).

<p>log n</p> Signup and view all the answers

Match de følgende sorteringsalgoritmer med deres tidskompleksitet:

<p>Insertion sort = O(n) når sorteret Selection sort = O(n^2) Merge sort = O(n log n) Quick sort = O(n log n)</p> Signup and view all the answers

Hvilken algorithm bruger en 'swap' metode for at sortere?

<p>Selection sort (D)</p> Signup and view all the answers

Rekursive sorteringsalgoritmer som Merge sort bruger altid in-place sortering.

<p>False (B)</p> Signup and view all the answers

Hvad sker der, hvis størrelsen på arrayet er 1 i Merge sort?

<p>Sorteringen er fuldendt.</p> Signup and view all the answers

Flashcards

Lænket liste

En datastruktur hvor hvert element har en reference til det efterfølgende element i listen.

insert()

En operation, der indsætter et nyt element i en liste, på en specifik position.

remove()

En operation, der fjerner et element fra en liste, på en specifik position.

copy()

En operation, der kopierer indholdet af en liste til en ny liste.

Signup and view all the flashcards

Heap

En datastruktur der opfylder to egenskaber: Heap-egenskaben, Hvor data i en node er mindre end noderne i nodens undertræer (kun hvis der er tale om en minHeap) og Shape-egenskaben, der sikrer at heapen er et komplet binært træ.

Signup and view all the flashcards

MinHeap

En heap hvor det mindste element altid er øverst

Signup and view all the flashcards

MaxHeap

En heap hvor det største element altid er øverst

Signup and view all the flashcards

insert() (heap)

En operation der indsætter et element i en heap, og opretholder heap-egenskaberne. Elementer flyttes opad i heapen indtil heap-egenskaben opfyldes.

Signup and view all the flashcards

remove() (heap)

En operation der fjerner det øverste element i en heap, og opretholder heap-egenskaberne. Elementer flyttes nedad i heapen indtil heap-egenskaben opfyldes

Signup and view all the flashcards

Chained hash map

En hash map struktur, hvor der er et fixed antal slots (eller buckets), og hvor hvert slot indeholder en kæde/liste af key-value par,

Signup and view all the flashcards

Open-address hash map

En hash map struktur, hvor der er et fixed antal slots (eller buckets), og hvor der kun er et key-value par i hvert slot.

Signup and view all the flashcards

Alpha (α)

Forholdet mellem antallet af key-value par i en hash map og antallet af slots i hash mappen.

Signup and view all the flashcards

Hvad er et binært søgetræ (BST)?

En datasammenhæng, der er organiseret som et træ med en række formelle regler, som gør det muligt at søge meget effektivt i træet.

Signup and view all the flashcards

Hvad er reglerne for et binært søgetræ?

Alle knuder til venstre for en given knude har data mindre eller lig knuden. Alle knuder til højre for en given knude har data større end knuden.

Signup and view all the flashcards

Hvad er søgetiden for et binært søgetræ?

Den værste tilfælde søgetid for et binært søgetræ er O(d), hvor d er træets dybde. Dette skyldes at man i værste tilfælde skal søge gennem hele træet.

Signup and view all the flashcards

Hvordan søger man i et binært søgetræ?

Start ved roden af træet. Er dette den node, du søger? Hvis nej: Gå til højre hvis noden du søger er større end den aktuelle node, ellers venstre. Gentag proces indtil noden findes eller dybden er nået.

Signup and view all the flashcards

Hvad er indsættelsestiden for et binært søgetræ?

Den værste tilfælde indsættelsestid for et binært søgetræ er O(d), hvor d er træets dybde. Nye noder indsættes som blade i træet.

Signup and view all the flashcards

Hvordan indsætter man en node i et binært søgetræ?

Start ved roden. Er den node, du indsætter større, da gå til højre. Ellers venstre. Gentag processen indtil du ikke kan gå længere. Indsæt den nye node på det sted.

Signup and view all the flashcards

Hvad er fjernelsestiden for et binært søgetræ?

Den værste tilfælde fjernelsestid for et binært søgetræ er O(d), hvor d er træets dybde. Dette skyldes at man skal sikre at strukturen af træet opretholdes efter fjernelsen.

Signup and view all the flashcards

Hvordan fjerner man en node i et binært søgetræ?

Find noden, der skal fjernes. Hvis noden ikke er et blad, udskift noden med en anden node, der er lettere at fjerne. Fjern den duplikerede knude.

Signup and view all the flashcards

Hvad er en Skip List?

Skip List er en datastruktur, der tillader søgning, indsættelse og sletning af elementer effektivt i en sorteret liste.

Signup and view all the flashcards

Hvordan er niveauerne i en Skip List organiseret?

Hvert niveau i en Skip List indeholder en delmængde af noderne fra niveauet nedenunder, og der er færre noder på hvert højere niveau.

Signup and view all the flashcards

Hvordan fungerer søgning i en Skip List?

En Skip List bruger 'fast lanes' til at springe over noder på lavere niveauer, hvilket forbedrer søgehastigheden.

Signup and view all the flashcards

Hvad er tidskompleksiteten for søgning i en Skip List?

En Skip List har en gennemsnitlig tidskompleksitet på O(log(n)) for søgning, hvilket betyder, at søgetiden stiger logaritmisk med antallet af noder.

Signup and view all the flashcards

Hvordan vælges niveauet for en indsat node i en Skip List?

En Skip List bruger en møntkast til at afgøre, om en indsat node skal indsættes på et højere niveau. Dette sikrer en sandsynlighedsfordeling af noder på niveauerne.

Signup and view all the flashcards

Hvad er den værste tidskompleksitet for søgning i en Skip List?

En Skip List kan i ekstreme tilfælde have alle noder på samme niveau, hvilket kan føre til en worst-case tidskompleksitet på O(n). Dette er dog meget usandsynligt.

Signup and view all the flashcards

Hvordan indsættes en node i en Skip List?

For at indsætte en node i en Skip List, søges der fra højeste niveau efter den givne værdi, som skal indsættes.

Signup and view all the flashcards

Hvad er formålet med 'update' vektor under indsættelse?

Under indsættelse af en node i en Skip List, Gemmes en peger til den node længst til højre af level i eller højere, som er til venstre for indsættelsespositionen.

Signup and view all the flashcards

Korteste vej

Den korteste vej mellem to punkter i en graf, hvor summen af vægtede kanter er minimal.

Signup and view all the flashcards

Dijkstra's algoritme

En algoritme, der finder den korteste sti mellem to punkter i en graf ved at udforske noder og kanter systematisk.

Signup and view all the flashcards

Dijkstra's med negative vægte

En ændring af Dijkstra's algoritme, der tillader negative vægte, så længe grafen ikke indeholder cykler.

Signup and view all the flashcards

Kant-til-selv scenarie

Dijkstra's algoritme kan håndtere et kant-til-selv scenarie, hvor en node har en kant til sig selv.

Signup and view all the flashcards

BFS lignende

Dijkstra's algoritme vil fungere som BFS, hvis alle kanter i grafen har samme vægt.

Signup and view all the flashcards

A*-algoritmen

En algoritme, der finder den mest optimale sti mellem to punkter i en graf ved at bruge en heuristisk funktion til at vælge den næste node at undersøge.

Signup and view all the flashcards

Heuristisk funktion

En funktion, der vurderer den omtrentlige afstand mellem en given node og mål-noden.

Signup and view all the flashcards

Heurestik

En metode til at vælge den optimale sti mellem noder baseret på en vurdering af afstanden til målet.

Signup and view all the flashcards

Insertion Sort

Insertion sort fungerer ved at indsætte det første usorterede element i rækken af sorterede elementer i hver iteration, indtil den usorterede del er tom.

Signup and view all the flashcards

Selection Sort

Selection sort finder det mindste usorterede element og swapper det med det første element i den usorterede del i hver iteration.

Signup and view all the flashcards

Divide and Combine

Divide and combine princippet indebærer at dividere problemet i mindre dele, løse disse dele rekursivt, og derefter kombinere løsningerne.

Signup and view all the flashcards

Merge Sort

Merge Sort fungerer ved at dividere arrayet i to lige store dele, sortere dem rekursivt, og derefter fusionere dem til et sorteret resultat.

Signup and view all the flashcards

Rekursive Sorteringsalgoritmer

Rekursive sorteringsalgoritmer fungerer ved at kalde sig selv med mindre dele af arrayet, indtil de har nået et basis tilfælde og derefter kombinere løsningerne.

Signup and view all the flashcards

In-place vs Ikke-in-place

En sorteringsalgoritme der opererer in-place ændrer ikke dataen, mens en algoritme, der ikke opererer in-place, kopierer data til en ny placering.

Signup and view all the flashcards

Tidskompleksitet

Tidskompleksiteten for en algoritme er en måling af den tid, der kræves for at udføre algoritmen som en funktion af inputstørrelsen.

Signup and view all the flashcards

O-notation

O-notation bruges til at beskrive tidskompleksiteten af en algoritme. For eksempel er O(n) lineær tidskompleksitet og O(n ∗ log(n)) log-linear.

Signup and view all the flashcards

Study Notes

Generelle noter om eksamensmateriale

  • Eksamensnoterne er fra januar 2018.
  • Forfatterne er Patrick Gobbenobber Bjerregaard, Jonas Andersen og Malthe Jensen.
  • Noterne omhandler DOA (ikke specificeret hvad DOA står for).
  • Noterne dækker forskellige datastrukturer og algoritmer.
  • Noterne indeholder en række kodeeksempler.

Emne: Lineære datastrukturer

  • Introduktion: Dækker emnerne Linked Lists, Stacks og Queues.
  • Linked Lists: Beskrivelse af den generelle opbygning og almindelige operationer som insert(), remove() og copy(). Indeholder kodeeksempler.
  • Stacks: En LIFO-struktur (Last-In, First-Out) dvs. de senest indsatte elementer er de første der fjernes.
  • Queues: En FIFO-struktur (First-In, First-Out) dvs. de første indsatte elementer er de første der fjernes.

Emne: Rekursion

  • Introduktion: Begrebet rekursion som problemløsningsmetode, hvor et problem løses ved at løse mindre tilfælde/cases.
  • Hvad er rekursion?: Rekursive problemer kan inddeles i to typer:
    • Base case (tilfælde, hvor rekursionen stopper).
    • Rekursiv case (tilfælde, hvor rekursionen fortsætter ved at kalde sig selv).
  • Den rekursive opskrift: Procedure til at formele et problem ud fra dets størrelse, indsætte base case, den rekursive case og finde belæg for, at den rekursive case nærmer sig base-case for at løse problemet.
  • Eksempler: Eksempler på rekursive algoritmer som sum og fakultet.
  • Hvornår bør man bruge rekursion?: Diskuterer fordele og ulemper.

Emne: Maps

  • Introduktion: Datastruktur, der opslaeger data i key-value par.
  • Hash Maps: Datastruktur til at indekser data hurtigt vha. en hash funktion og open-address hash maps.
  • Hash Funktion: Funktionen der mappes til et index.
  • Collisions and Clustering: Hvordan man håndterer kollisioner (når flere keys mapper til samme index).
  • Probing: Mekanisme til at finde en ledig placering.
  • Load Faktor: Hvor fuldt et hash map er, og hvordan det påvirker ydeevne.

Emne: Priority Queues

  • Introduktion: Datastruktur hvor elementer har en prioritet.
  • Heap: En binær træ datastruktur, der tilfredsstiller heap-property som sørger for at den højeste prioritet er øverst. Indeholder operationer for indsættelse (insert) og fjernelse (remove).
  • Tidskompleksitet: O(n log(n)) for insert og remove.

Emne: Søgning - Tree Structures

  • Introduktion: Diskussion af forskellige træstrukturer til søgning.
  • Træstrukturer generelt: Generel beskrivelse af træstrukturer med noder, børn og root noder.
  • Søgning: Diskusion af lineær og binær søgning.
  • Binary search trees (BST): Træstruktur hvor værdierne i venstre undertræ af en knude er mindre end værdien i knuden, og værdierne i højre undertræ af en knude er større.
  • AVL trees: Selvbælanserede binære søgetræer der opretholder en balance i træet vha. rotationer.
  • Treaps: En træstruktur (binært søgetræ) der bruger prioriteter for hvert element for at holde balancen.

Emne: Søgning - Skip Lists

  • Introduktion: Introduktion til Skip Lists som et probabilistisk alternativ til balancerede træer.
  • Skip Lists generelt: En datastruktur hvor elementer gemmes på forskellige niveauer med pointere, hvilket hurtigt kan finde elementer på grund af "fast lanes" hvor elementerne kommer til udtryk.
  • Insert: Procedure til indsættelse af et element med en probabilistisk metode for at finde den bedste placering.
  • Remove: Procedure til fjernelse af et element. Der omorganiseres pointere i listen.
  • Sammenligning med AVL/Treap: Fordele og ulemper ved Skip Lists sammenlignet med andre balancerede træer.

Emne: Sortering

  • Introduktion: Diskussion af sorteringsalgoritmer.
  • Kvadratiske sorteringsalgoritmer: Bubble sort, Insertion sort, Selection sort.
  • Rekursive sorteringsalgoritmer: Merge sort, Quick sort , diskuteres divide-and-conquer.
  • Radix sort: En non-comparative sorteringsalgoritme.
  • Tidskompleksitet: Best-case, worst-case og average-case tidskompleksitet for de forskellige sorteringsalgoritmer.

Emne: Grafer - Pathfinding

  • Grafer generelt: Introduktion til grafer med knuder og kanter. Inddelt i rettede eller urettede grafer, med eller uden vægte.
  • Pathfinding: At finde den bedste vej mellem to noder i en graf.
  • Breadth-First Search (BFS): En algoritme til at finde den korteste vej/sti. Begynder med at udforske den nærmeste nabo til en given aktuel knude, og fortsætter med dens naboer til at bestemme den korteste sti.
  • Dijkstra's algoritme: En algoritme til at finde den korteste vej i en weighted graf. Vægtene af kanterne indikerer afstand eller omkostninger.
  • A-algoritmen:* En pathfinding algoritme til at finde den korteste vej i en weighted grafer, der tager højde for en heurestik function (estimation of remaining distance) for at optimere den path finding proces for at finde den optimale sti.

Emne: Grafer - Andre algoritmer

  • Maximum Flow: At finde det maksimale flow gennem en netværksgraf.
  • Minimum Spanning Tree (MST): At finde et træ, der udspænder alle noder, men har den mindst mulige sum af vægtede kanter.
  • Prim's algoritme: En algoritme til at finde et MST.
  • Kruskal's algoritme: En alternativ algoritme til at finde et MST.
  • Matching: At matche to noder fra forskellige sæt af noder som opfylder givne forhold.
  • Stable Matching Problem: At finde en stabil matchning mellem to sæt af noder hvor hver node har prioriteret andre noder fra det andet sæt.
  • Gale og Sharpley's algoritme: En algoritme for at finde en stabil matchning.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

DOA Examination Notes PDF

Description

Test din viden om datastrukturer som heaps og hash maps samt grundlæggende algoritmer. Denne quiz dækker emner som tidskompleksitet, søgningsteknikker og graf-algoritmer. Svar på spørgsmål om specifikke funktioner og anvendelser af forskellige datastrukturer.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser