Puggespørsmål Flashcards
Hva slags datastruktur er vanlig å bruke i binærsøk?
Hva slags kjøretidskompleksitet?
Hvordan er pseudokoden?
Array
log n
Hva er dybden til roten i et tre?
Hva er pseudokoden for å finne dybden til en node?
Roten har dybde 0
Hvordan ser pseudokoden ut for å regne ut høyden til en node i et tre?
Hva slags egenskaper har trær?
Binære trær?
Binære søketrær?
A) Inneholder ikke sykler / 0+ pekere til barn / 1peker til foreldrenode (bortsett fra rot)
B) Tre med maks 2 barn
C) Binært tre der alle noder i venstre subtre er mindre enn
og
alle noder i høyre subtre er større enn
Hva er kjøretidskompleksiteten for innsetting i et BST?
Hva hvis BSTet er balansert?
Hvordan ser pseudokoden ut?
O(n)
O(log n)
Hvordan skal vi slette fra et binærtre hvis treet har
A) ingen barn?
B) ett barn?
C) to barn?
Pseudokode?
A) Fjern fra forelderen til noden
B) Peker fra F->BB og BB->F
C) Ersatt Barn med minste elementet i Høyre subtre
Hvilke operasjoner må en prioritetskø støtte?
Hva er kjøretiden på disse for
a) Usortert lenket liste
b) Sortert lenket liste
c) BST
push(e) / pop
a) O(1) /O(n)
b) O(n) / O(1)
c) log (n) / log (n)
Hvilke 2 egenskaper må en binær heap oppfylle (i tillegg til å være et binærtre) ?
Hvordan legger man til i binære heaps?
Hvordan sletter man fra binære heap?
Hva er kjøretidskompleksiteten på innsetting og sletting?
a) hver node er større enn foreldrenoden (min-heap)
b) komplett
Man legger til på neste ledige plass og så bubble up
Sletter rotnode, replaces med siste node og så bubble down
O(log n) og O(log n)
Hva er pseudokoden for hjelpeprosedyrene til
ParentOf
LeftOf
RightOf
for binære heaps?
Parent: (i-1) / 2
Left: 2i+1
Right: 2i+2
Hva er pseudokoden for innsetting i binær heap?
Hva er pseudokoden for fjern minste i binær heap?
Hva er beste / gj.snitt / verste kjøretidskompleksitet på
Bubble Sort
Selection Sort
Insertion Sort
Heap Sort
Merge Sort
Quick Sort
Bucket Sort
Radix Sort ?
Hva er?
Hva er kjøretidskompleksiteten og den sentral datastrukturen for følgende algoritmer:
DFS
BFS
TopSort
Dijkstra (IS)
Dijkstra (S)
Bellman-Ford
Prim
Kosaraju?
