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 is de wortel van een boom?

  1. ADe bovenste knoop zonder ouder
  2. BEen willekeurige knoop in het midden
  3. CDe knoop met de grootste waarde
  4. DEen knoop zonder kinderen
2.Makkelijk

Waar vind je het kleinste element van een binaire min-heap?

  1. AOp de laatste positie in de array
  2. BIn de wortel
  3. CIn het meest linkse blad
  4. DIn een willekeurig blad, dat moet worden gezocht
3.Makkelijk

Hoe heet de queuebewerking die het element vooraan verwijdert?

  1. APush
  2. BDequeue
  3. CInsert
  4. DEnqueue
4.Gemiddeld

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

  1. AO(V²)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(E²)
5.Gemiddeld

Bij welke methode voor het oplossen van botsingen worden botsende sleutels in een lijst in dezelfde bucket opgeslagen?

  1. ADubbel hashen (double hashing)
  2. BSeparate chaining (ketenen)
  3. CKwadratisch proberen (quadratic probing)
  4. DLineair proberen (linear probing)
6.Gemiddeld

Hoe werkt extract-min in een binaire min-heap?

  1. AVerwijder de wortel en schuif alle elementen één plaats naar links
  2. BVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  3. CZoek in alle bladeren naar het nieuwe minimum
  4. DVerwijder het laatste element van de array
7.Moeilijk

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

  1. AHem te verwisselen met de wortel
  2. BDe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
  3. CDe hele subboom te verwijderen
  4. DHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
8.Moeilijk

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

  1. ADe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
  2. BDe map geeft een fout op het moment dat het veld verandert
  3. CEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start
  4. DHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat

Antwoordenblad

  1. 1. A · De bovenste knoop zonder ouder
  2. 2. B · In de wortel
  3. 3. B · Dequeue
  4. 4. C · O(V + E)
  5. 5. B · Separate chaining (ketenen)
  6. 6. B · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  7. 7. D · Hem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
  8. 8. D · Het object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat

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