# 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.

- **Canonical URL:** https://flashcards.world/flashcards/sets/02deac5c-d0a5-45e3-a1bd-3f1870738916/
- **Markdown URL:** https://flashcards.world/flashcards/sets/02deac5c-d0a5-45e3-a1bd-3f1870738916.md
- **Category:** Computer Science
- **Level:** basic
- **Languages:** nl → nl
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | 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. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/02deac5c-d0a5-45e3-a1bd-3f1870738916/).
