Datastructuren, Complexiteitsanalyse (Big-O) en Kernalgoritmen

Herhaling op bachelorniveau waarvoor basiskennis van programmeren nodig is: 32 kaarten over arrays, lijsten, hashing, bomen, heaps, tries, Union–Find, Bloomfilters en complexiteit.

Category
Computer Science
Level
basic
Languages
nl → nl
Cards
32
Markdown
Datastructuren, Complexiteitsanalyse (Big-O) en Kernalgoritmen (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Wat doen find en union in een datastructuur voor disjuncte verzamelingen?find(x) geeft de vertegenwoordiger van de verzameling van x. union(x,y) voegt hun verzamelingen samen als ze verschillen; behoren ze al tot dezelfde, dan blijft de partitie gelijk.
2Wat kost het van onderaf opbouwen van een heap uit n items?O(n). De meeste knopen liggen dicht bij de bladeren en hoeven weinig te zakken; optellen van het werk naar knoophoogte geeft een lineair totaal.
3Welke antwoorden kan een Bloomfilter geven dat alleen invoegen toestaat?Negatief betekent dat het item niet is ingevoegd; positief dat dit mogelijk wel is gebeurd. Hashes zetten bits in een bitarray. Fout-positieven zijn mogelijk, fout-negatieven niet zolang de toestand intact is.
4Hoe werkt een stapel en wanneer kosten zijn bewerkingen O(1)?LIFO: het laatst toegevoegde element wordt het eerst verwijderd. Bij de kop van een gekoppelde lijst kosten toevoegen, verwijderen en bekijken O(1); vergroten van een array kan één toevoeging O(n) laten kosten.
5Waarom kan een dubbel gekoppelde lijst een gegeven knoop in O(1) verwijderen?De verwijzingen naar voorganger en opvolger verbinden de buren direct opnieuw. Werk kop en staart zo nodig bij; zoeken naar de voorganger is niet nodig.
6Welke kleurregels houden een rood-zwarte BST in balans?Knopen zijn rood of zwart; wortel en NIL-bladeren zijn zwart. Rode knopen hebben geen rode kinderen. Elk pad van een knoop naar een afstammend NIL-blad bevat evenveel zwarte knopen. Dit begrenst de hoogte tot O(log n).
7Hoe hangen zoeken, invoegen en verwijderen in een BST af van hoogte h?Ze kosten O(h). Een gebalanceerde boom heeft h = O(log n), een keten h = O(n). Verwacht O(log n) vereist aannames zoals een willekeurige invoegvolgorde.
8Wat is een trie en wanneer kost zoeken naar een sleutel met L tekens O(L)?Een prefixboom bewaart sleutels langs tekenpaden, met markeringen voor volledige sleutels. Zoeken kost O(L) als elke overgang naar het volgende teken O(1) kost.
9Welke ordeningsinvariant definieert een binaire zoekboom (BST) met verschillende sleutels?Bij elke knoop zijn alle sleutels in de linkerdeelboom kleiner en alle in de rechterdeelboom groter. De regel geldt recursief.
10Wat levert in-order doorlopen van een BST met verschillende sleutels op?Alle sleutels in strikt stijgende volgorde, met bezoek aan n knopen in O(n).
11Hoe verschillen lineair en kwadratisch sonderen bij open adressering?Items blijven in de array. Bij tabelgrootte m en beginindex h worden respectievelijk (h+i) mod m en (h+c₁i+c₂i²) mod m geprobeerd. Kwadratisch sonderen vereist geschikte parameters.
12Wat kosten invoegen, de wortel verwijderen en de wortel bekijken in een binaire heap?Respectievelijk O(log n), O(log n) en O(1), zolang de arraygrootte niet hoeft te veranderen. Zo'n wijziging kan O(n) kosten.
13Hoe verschillen padcompressie, vereniging naar rang en vereniging naar grootte?Padcompressie verwijst bezochte knopen door naar de wortel. Naar rang komt de wortel met lagere rang onder die met hogere rang; naar grootte de kleinere verzameling onder de grotere. Rang hoeft niet gelijk te zijn aan de huidige hoogte.
14Wat is de AVL-balansvoorwaarde?Bij elke knoop geldt hoogte(links) − hoogte(rechts) ∈ {−1, 0, 1}. De boom voldoet ook aan de BST-ordeningsinvariant.
15Hoe voorkomt een wachtrij in een circulaire array verschuiven na verwijdering?De voor- en achterindices lopen rond modulo de capaciteit. Verwijderen verhoogt de voorindex; vrijgekomen vakken zijn herbruikbaar zonder andere elementen te verplaatsen.
16Waar staan ouder en kinderen van knoop i in een heaparray met lengte n en indices vanaf nul?Ouder: ⌊(i−1)/2⌋ voor i>0. Kinderen: 2i+1 en 2i+2, alleen als die indices kleiner zijn dan n. Index 0 heeft geen ouder.
17Wat is het verschil tussen O, Ω en Θ?Ze geven respectievelijk asymptotische boven-, onder- en strakke grenzen. Ze beschrijven een bepaalde kostenfunctie; O betekent op zichzelf niet het slechtste geval.
18Hoe lost afzonderlijke ketenvorming hashbotsingen op?Elke bucket bevat een verzameling items met die bucketindex, vaak een gekoppelde lijst. Verschillende sleutels in dezelfde bucket blijven afzonderlijke items.
19Welke twee eigenschappen definiëren een binaire min-heap?Het is een complete binaire boom en elke oudersleutel is hoogstens zo groot als de sleutels van zijn kinderen. De wortel bevat dus een minimum.
20Rangschik deze groeisnelheden van langzaam naar snel voor n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.Asymptotisch: 1 < log n < n < n log n < n² < 2ⁿ < n!.
21Wat zijn de bezoekvolgorden van pre-order, in-order en post-order bij een binaire boom?Pre-order: knoop → links → rechts. In-order: links → knoop → rechts. Post-order: links → rechts → knoop.
22Wat is de beladingsfactor van een hashtabel en waarom kan haar grootte veranderen?α = n/m: n opgeslagen items en m buckets of vakken. Een implementatiespecifieke drempel overschrijden kan vergroten en opnieuw hashen veroorzaken; 0,75 is niet universeel.
23Wat zijn de verwachte en slechtste kosten voor een hashtabel met afzonderlijke ketens?Bij begrensde belasting, goed gespreide hashes en constante sleutelbewerkingen kosten zoeken/verwijderen verwacht O(1). Invoegen met geometrische groei kost verwacht geamortiseerd O(1). Een keten van n botsende sleutels kan O(n) veroorzaken.
24Hoe herstel je een links-rechts-onbalans na een AVL-invoeging?Roteer eerst het linkerkind naar links, daarna de ongebalanceerde knoop naar rechts.
25Wat betekent f(n) ∈ O(g(n)) voor niet-negatieve functies f en g?Er bestaan constanten c > 0 en n₀ ≥ 0 zodat f(n) ≤ c·g(n) voor alle n ≥ n₀.
26Wat kost toevoegen aan het einde van een dynamische array geamortiseerd als de capaciteit steeds verdubbelt?O(1) per toevoeging. Vergroten kan O(n) kosten, maar n toevoegingen vanuit een lege array kosten samen O(n).
27Hoe wordt een binaire boom per niveau doorlopen?Een FIFO-wachtrij verwerkt telkens één diepteniveau. Plaats het linkerkind vóór het rechterkind in de rij voor de volgorde van links naar rechts.
28Welke eigenschappen moet een hashfunctie hebben voor zoeken in een tabel?Ze moet deterministisch zijn en verwachte sleutels goed spreiden. Een sleutel met vaste grootte hashen kan O(1) kosten; een nieuwe tekenreeks van L tekens hashen kost meestal O(L).
29Vergelijk invoegen vooraan en indextoegang bij een enkelvoudig gekoppelde lijst en een dynamische array.Lijst: vooraan invoegen O(1), indextoegang O(n). Array: vooraan invoegen O(n), indextoegang O(1); vooraan invoegen verschuift elementen.
30Waarom kost toegang via een index in een array met vaste grootte O(1)?Even grote vakken liggen aaneengesloten: adres(i) = basis + i·vakgrootte. Hierbij wordt aangenomen dat adresberekeningen constante tijd kosten.
31Welke toegangsregel en gebruikelijke bewerkingskosten heeft een wachtrij?FIFO: achteraan toevoegen, vooraan verwijderen. Beide kosten O(1) met kop-/staartverwijzingen of een ringbuffer met vaste capaciteit; een array verschuiven maakt verwijderen O(n).
32Wat kosten union/find met padcompressie en vereniging naar rang geamortiseerd?O(α(n)) per bewerking, met α de inverse Ackermannfunctie en n het aantal elementen. Initialiseren kost O(n); de grens geldt voor een reeks, niet als constante slechtste kosten van elke afzonderlijke aanroep.