Nederlands
Menu

Datastructuren en algoritmen

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.

  1. AIn oplopende volgorde (kleinste eerst)
  2. BIn de volgorde waarin ze zijn ingevoegd
  3. CIn volgorde van afstand tot de wortel (minst diep eerst)
Antwoord en toelichting tonen

Antwoord: A. In oplopende volgorde (kleinste eerst)

In een binaire zoekboom zijn voor elke knoop alle waarden in de linkerdeelboom kleiner dan de knoop en alle waarden in de rechterdeelboom groter. Wie eerst de linkerdeelboom, dan de knoop en dan de rechterdeelboom bezoekt, bezoekt de waarden dus van klein naar groot, en het resultaat is oplopend. Knopen bezoeken in volgorde van afstand tot de wortel is een breedte-eerst doorloop (level-order), die per niveau van links naar rechts gaat. De invoegvolgorde bepaalt de vorm van de boom, maar komt niet overeen met de volgorde van een doorloop.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. 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)?
  2. 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?
  3. 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?
  4. 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?
  5. 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?