Nederlands
Menu

Datastructuren en algoritmen

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]?

  1. AKinderen a[9] en a[10], ouder a[1]
  2. BKinderen a[8] en a[9], ouder a[2]
  3. CKinderen a[9] en a[10], ouder a[2]
Antwoord en toelichting tonen

Antwoord: A. Kinderen a[9] en a[10], ouder a[1]

Met de wortel in a[0] zijn de kinderen van a[i] de elementen a[2i+1] en a[2i+2], en is de ouder a[(i−1) ÷ 2, naar beneden afgerond]. Voor i = 4 zijn de kinderen a[9] en a[10] en is de ouder a[(4−1) ÷ 2] = a[1]. Met de wortel in a[1] zijn de kinderen a[2i] en a[2i+1] en is de ouder a[i ÷ 2]; het is dus belangrijk na te gaan welke conventie wordt gebruikt. Omdat een heap een complete binaire boom is, kan hij zonder pointers in een array worden opgeslagen, en worden ouders en kinderen alleen met indexberekeningen gevonden.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

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