Nederlands
Menu

Datastructuren en algoritmen

Leer met meerkeuzevragen over tijdcomplexiteit en O-notatie, arrays en gelinkte lijsten, stacks en wachtrijen, hashtabellen, binair zoeken, de werking en stabiliteit van sorteeralgoritmen, binaire zoekbomen en heaps, zoeken in grafen en kortste paden, en recursie, dynamisch programmeren en gretige algoritmen, inclusief hun verband met caches en GPU's.

Oefen 10 vragenWillekeurige vragen uit dit onderwerp · ongeveer 5 minuten Dit onderwerp oefenenAlle vragen over dit onderwerp in willekeurige volgorde Zwakke vragenAlleen de laatst fout beantwoorde vragen opnieuw oefenen

Datastructuren en algoritmen: kernpunten

Programma's die hetzelfde probleem oplossen, kunnen bij groeiende hoeveelheden gegevens ordes van grootte in snelheid verschillen, afhankelijk van de datastructuren en algoritmen die ze gebruiken. Met de tijdcomplexiteit inschatten hoe het werk groeit, en structuren kiezen die passen bij hoe de gegevens worden gebruikt, is het startpunt voor snelle programma's.

U leert elementaire datastructuren zoals arrays en gelinkte lijsten, stacks en wachtrijen, hashtabellen, binaire zoekbomen en heaps en de weergave van grafen, samen met binair zoeken; sorteeralgoritmen zoals bubblesort, selection sort, insertion sort, mergesort, quicksort en heapsort; breedte-eerst zoeken, diepte-eerst zoeken en het algoritme van Dijkstra; en recursie, dynamisch programmeren en gretige algoritmen, vooral aan de hand van rekenvragen die elke stap volgen. Dat helpt ook bij het algoritmedeel van IT-certificeringsexamens. Daarnaast komt het verband met de prestaties van de hardware aan bod, zoals cachevriendelijke gegevensindelingen en parallel sorteren op GPU's.

Alle vragen over Datastructuren en algoritmen (40)
  1. Wat is de tijdcomplexiteit van een bewerking die in een array van n elementen elk paar van twee verschillende elementen precies één keer vergelijkt (een dubbele lus die element i vergelijkt met alle elementen erna en i telkens één stap verder zet)?
  2. Een programma met tijdcomplexiteit O(n²) doet er 0,5 seconde over bij 1000 gegevens. Hoeveel seconden duurt het ongeveer bij 4000 gegevens?
  3. Lineair zoeken vergelijkt de elementen van een array met 100 verschillende waarden één voor één vanaf het begin om een gezochte waarde te vinden. De gezochte waarde staat altijd in de array en heeft op elke positie dezelfde kans. Wat is het gemiddelde aantal vergelijkingen?
  4. Welke beschrijving van een gelinkte lijst (een lijst waarin elk element een pointer naar het volgende element bevat) is juist in vergelijking met een array?
  5. Op een lege stack worden achtereenvolgens push 1, push 2, pop, push 3, push 4, pop, pop uitgevoerd. In welke volgorde komen de waarden die pop verwijdert eruit?
  6. In een lege wachtrij worden de elementen A, B en C in deze volgorde geplaatst. Daarna wordt er één element uitgehaald, wordt D toegevoegd en weer één uitgehaald, en wordt E toegevoegd en nog één uitgehaald. In welke volgorde worden de elementen uitgehaald?
  7. De expressie „3 4 + 2 * 5 −” in omgekeerde Poolse notatie (postfixnotatie) wordt geëvalueerd door elk getal op een stack te leggen en bij elke operator twee waarden eraf te halen, het resultaat te berekenen en dat weer op de stack te leggen. Wat is het resultaat? De linkeroperand van een operator is de waarde die het eerst op de stack is gelegd.
  8. Welke beschrijving van een botsing (collision) in een hashtabel is juist?
  9. De sleutels 10, 17, 24 en 3 worden in deze volgorde opgeslagen in een hashtabel van grootte 7 (posities 0 tot 6) met de hashfunctie h(k) = k mod 7. Botsingen worden opgelost met lineair proberen (linear probing): de positie schuift telkens één plaats op (na 6 komt 0) tot er een vrije plaats is gevonden. Op welke positie wordt sleutel 3 opgeslagen?
  10. Welke vergelijking van chaining (de elementen op dezelfde positie aan elkaar koppelen in een gelinkte lijst) en open adressering (een andere vrije positie in de tabel zoeken) als methoden om botsingen in een hashtabel af te handelen is juist? De bezettingsgraad (load factor) is het aantal opgeslagen elementen gedeeld door de grootte van de tabel.
  11. Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?
  12. Met binair zoeken wordt een waarde gezocht in 1000 verschillende waarden die oplopend gesorteerd zijn. Eén vergelijking laat zien of de waarden gelijk zijn of dat de ene kleiner of groter is. Wat is het maximale aantal vergelijkingen, voor zowel een geslaagde als een mislukte zoekactie?
  13. Binair zoeken zoekt 38 in de oplopende array a[0] tot a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Het zoekbereik begint met lo = 0 en hi = 9, en de middelste positie is (lo + hi) ÷ 2, naar beneden afgerond. Welke reeks geeft, in volgorde, de waarden van de elementen waarmee 38 wordt vergeleken?
  14. De array 5, 3, 8, 1, 4 wordt met bubblesort oplopend gesorteerd. Hoe ziet de array eruit na één doorgang (pass), waarin vanaf het begin tot het eind telkens twee buren worden vergeleken en verwisseld als het linkerelement groter is?
  15. De array 29, 10, 14, 37, 13 wordt met selection sort oplopend gesorteerd: het minimum van het ongesorteerde deel wordt gezocht en verwisseld met het eerste element van het ongesorteerde deel. Hoe ziet de array eruit nadat deze stap twee keer is uitgevoerd?
  16. Een array van 10 elementen wordt met insertion sort oplopend gesorteerd. Elk element vanaf het tweede wordt eruit gehaald en vergeleken met de elementen links ervan, te beginnen bij de linkerbuur, tot een element kleiner dan of gelijk aan de waarde is gevonden of het begin is bereikt. Hoeveel vergelijkingen zijn er nodig als de array al oplopend staat, en als hij aflopend staat?
  17. Welk sorteeralgoritme heeft ook in het slechtste geval tijdcomplexiteit O(n log n) en sorteert met nauwelijks extra geheugen, zoals een werkarray?
  18. De records (naam, score) (A, 80), (B, 70), (C, 80), (D, 70) staan in deze volgorde. In welke volgorde staan de namen als ze met een stabiel sorteeralgoritme oplopend op score worden gesorteerd?
  19. In welk typisch geval heeft quicksort tijdcomplexiteit O(n²)?
  20. Bij mergesort worden de twee gesorteerde reeksen 1, 4, 7, 9 en 2, 3, 8, 10 samengevoegd (merge) tot één reeks door herhaaldelijk de voorste elementen te vergelijken en het kleinste uit te voeren. Is één reeks leeg, dan wordt de rest van de andere zonder vergelijking uitgevoerd. Hoeveel vergelijkingen zijn er nodig?
  21. Een binaire heap wordt opgeslagen in een array a[0], a[1], a[2], … met de wortel in a[0], waarbij elk niveau van bovenaf van links naar rechts wordt gevuld. Wat zijn de kinderen en de ouder van a[4]?
  22. Een max-heap, waarin de waarde van elke ouder minstens zo groot is als die van zijn kinderen, wordt opgeslagen in een array met de wortel in a[0]. Aan de heap 50, 30, 40, 10, 20, 35 wordt 45 toegevoegd door de waarde achteraan te plaatsen en haar met haar ouder te verwisselen zolang ze groter is dan die ouder. Hoe ziet de array er daarna uit?
  23. Een binaire zoekboom wordt in in-order doorlopen (symmetrische volgorde: eerst de linkerdeelboom, dan de knoop zelf, dan de rechterdeelboom). In welke volgorde staan de waarden van de bezochte knopen? Neem aan dat alle waarden verschillend zijn.
  24. De waarden 50, 30, 70, 20, 40, 60, 80 worden in deze volgorde ingevoegd in een lege binaire zoekboom. In welke volgorde worden de knopen bezocht als de boom in post-order wordt doorlopen (eerst de linkerdeelboom, dan de rechterdeelboom, dan de knoop zelf)?
  25. De waarden 1, 2, 3, …, 1000 worden in deze volgorde ingevoegd in een lege binaire zoekboom (zonder herbalancering). Met hoeveel knopen wordt, vanaf de wortel, vergeleken voordat 1000 wordt gevonden?
  26. Wat is de belangrijkste reden dat voor indexen in databases en bestandssystemen vaak B-bomen (inclusief B+-bomen) worden gebruikt in plaats van binaire zoekbomen?
  27. Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?
  28. In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?
  29. In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?
  30. In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?
  31. Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?
  32. Voor de taken A tot E gelden de volgordebeperkingen „A vóór C”, „B vóór C”, „C vóór D”, „B vóór E” en „E vóór D”. Welke volgorde voldoet aan alle beperkingen (een resultaat van topologisch sorteren)?
  33. Een functie f(x, y) is gedefinieerd als „als y gelijk is aan 0, geef x terug; geef anders f(y, x mod y) terug”. Wat is de teruggegeven waarde van f(84, 36), en hoe vaak wordt f aangeroepen, de eerste aanroep meegerekend?
  34. Een functie fib(n) voor Fibonaccigetallen is met recursie gedefinieerd als „als n kleiner dan of gelijk aan 1 is, geef n terug; geef anders fib(n−1) + fib(n−2) terug”. Hoe vaak wordt fib aangeroepen als fib(5) wordt aangeroepen, de eerste aanroep meegerekend?
  35. Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?
  36. Een knapzak met capaciteit 8 wordt gevuld met voorwerpen gekozen uit vier voorwerpen met (gewicht, waarde) (2, 3), (3, 4), (4, 5) en (5, 6). Van elk voorwerp is er maar één, en voorwerpen kunnen niet worden gesplitst. Wat is de maximale totale waarde bij een totaal gewicht van hoogstens 8?
  37. Welke eigenschap van het Boyer-Moore-algoritme om een patroon in een tekenreeks te vinden is juist?
  38. Een dynamische array reserveert, als er een element wordt toegevoegd terwijl hij vol is, een nieuw gebied met de dubbele capaciteit en kopieert alle elementen daarheen. Hoeveel elementkopieën worden er in totaal gemaakt als 1000 elementen één voor één worden toegevoegd aan een lege array met capaciteit 1?
  39. Wat is de meest passende reden dat open adressering met lineair proberen bij een hashtabel met veel elementen en een bezettingsgraad van ongeveer 0,5 vaak sneller is dan chaining (elementen koppelen met gelinkte lijsten)?
  40. Voor sorteren op parallelle hardware zoals GPU's worden soms sorteermethoden met een vaste reeks vergelijk-en-verwisselstappen (sorteernetwerken) gebruikt, zoals bitonic sort. Waarom?

Andere onderwerpen in Computersystemen