Werkblad Datastructuren met antwoorden

Gratis printbaar werkblad Datastructuren: 8 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

  1. AHet aantal knopen in de lijst
  2. BHet adres van de eerste knoop
  3. CNull (geen knoop)
  4. DHet adres van de vorige knoop
2.Makkelijk

Wat is de max-heap-eigenschap?

  1. ADe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer
  2. BDe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  3. CAlle bladeren bevatten de maximale sleutel
  4. DDe sleutels zijn van links naar rechts gesorteerd
3.Makkelijk

Wat zijn broer- of zusknopen (siblings) in een boom?

  1. AKnopen op dezelfde diepte in verschillende subbomen
  2. BEen knoop en zijn ouder
  3. CKnopen die dezelfde ouder hebben
  4. DKnopen zonder kinderen
4.Gemiddeld

Waar staat in een binaire heap die in een array vanaf index 0 is opgeslagen de ouder van de knoop op index i?

  1. AOp index i − 1
  2. BOp index 2i + 1
  3. COp index ⌊i / 2⌋ + 1
  4. DOp index ⌊(i − 1) / 2⌋
5.Gemiddeld

Hoe wordt een nieuw element in een binaire heap ingevoegd?

  1. APlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  2. BPlaats het in de wortel en laat het omlaag zakken (sift down)
  3. CBouw de hele heap opnieuw op
  4. DVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
6.Gemiddeld

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

  1. AHeaps bevatten nooit meer dan 100 elementen
  2. BAlle sleutels in een heap zijn gelijk
  3. CArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
  4. DHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
7.Moeilijk

Welk paar doorlopen bepaalt altijd een unieke binaire boom met verschillende sleutels?

  1. APreorder en postorder
  2. BPreorder en inorder
  3. CAlleen preorder
  4. DAlleen level-order
8.Moeilijk

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

  1. AEen FIFO-queue van de laatste k waarden
  2. BEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
  3. CEen gesorteerde array van alle n waarden
  4. DEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

Antwoordenblad

  1. 1. C · Null (geen knoop)
  2. 2. B · De sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  3. 3. C · Knopen die dezelfde ouder hebben
  4. 4. D · Op index ⌊(i − 1) / 2⌋
  5. 5. A · Plaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
  6. 6. D · Het is een complete binaire boom, dus posities volgen eenvoudige indexformules
  7. 7. B · Preorder en inorder
  8. 8. D · Een max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.