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 elke knoop in een dubbel gekoppelde lijst?

  1. AData en alleen een pointer naar de volgende knoop
  2. BTwee kopieën van de data en één pointer
  3. CData en twee pointers, één naar de volgende knoop en één naar de knoop daarna
  4. DData, een pointer naar de volgende knoop en een pointer naar de vorige knoop
2.Makkelijk

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

  1. AInvoegen aan de kop
  2. BHet kopelement verwijderen
  3. CHet eerste element lezen
  4. DHet element op index i benaderen
3.Makkelijk

Welke datastructuur is het meest geschikt voor de functie "ongedaan maken" (undo) in een teksteditor?

  1. AHash-set
  2. BGraaf
  3. CStapel (stack)
  4. DWachtrij (queue)
4.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

  1. ADe hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  2. BAlle bladeren liggen op precies dezelfde diepte
  3. CBeide subbomen van elke knoop bevatten precies hetzelfde aantal knopen
  4. DElke knoop is rood of zwart gekleurd
5.Gemiddeld

AVL-bomen en rood-zwartbomen garanderen:

  1. ADat geen enkele knoop twee kinderen heeft
  2. BEen hoogte van O(log n) door herbalancering
  3. CZoeken in constante tijd in elk geval
  4. DDat sleutels in invoegvolgorde worden opgeslagen
6.Gemiddeld

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

  1. AEen stack
  2. BEen hashtabel
  3. CEen gebalanceerde binaire zoekboom
  4. DEen ongesorteerde gekoppelde lijst
7.Moeilijk

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(α(n))
8.Moeilijk

Waarom worden B-bomen gebruikt in databases en bestandssystemen?

  1. AZe gebruiken minder geheugen dan welke array dan ook, dus de hele index past altijd in het werkgeheugen
  2. BZe hebben geen herbalancering nodig
  3. CHun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert
  4. DZe slaan data ongesorteerd op

Antwoordenblad

  1. 1. D · Data, een pointer naar de volgende knoop en een pointer naar de vorige knoop
  2. 2. D · Het element op index i benaderen
  3. 3. C · Stapel (stack)
  4. 4. A · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  5. 5. B · Een hoogte van O(log n) door herbalancering
  6. 6. C · Een gebalanceerde binaire zoekboom
  7. 7. A · O(n)
  8. 8. C · Hun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert

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