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) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | Wat 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. | ||
| 2 | Wat 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. | ||
| 3 | Welke 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. | ||
| 4 | Hoe 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. | ||
| 5 | Waarom 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. | ||
| 6 | Welke 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). | ||
| 7 | Hoe 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. | ||
| 8 | Wat 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. | ||
| 9 | Welke 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. | ||
| 10 | Wat 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). | ||
| 11 | Hoe 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. | ||
| 12 | Wat 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. | ||
| 13 | Hoe 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. | ||
| 14 | Wat is de AVL-balansvoorwaarde? | Bij elke knoop geldt hoogte(links) − hoogte(rechts) ∈ {−1, 0, 1}. De boom voldoet ook aan de BST-ordeningsinvariant. | ||
| 15 | Hoe 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. | ||
| 16 | Waar 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. | ||
| 17 | Wat 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. | ||
| 18 | Hoe 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. | ||
| 19 | Welke 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. | ||
| 20 | Rangschik 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!. | ||
| 21 | Wat 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. | ||
| 22 | Wat 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. | ||
| 23 | Wat 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. | ||
| 24 | Hoe herstel je een links-rechts-onbalans na een AVL-invoeging? | Roteer eerst het linkerkind naar links, daarna de ongebalanceerde knoop naar rechts. | ||
| 25 | Wat 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₀. | ||
| 26 | Wat 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). | ||
| 27 | Hoe 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. | ||
| 28 | Welke 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). | ||
| 29 | Vergelijk 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. | ||
| 30 | Waarom 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. | ||
| 31 | Welke 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). | ||
| 32 | Wat 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. |