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 slaat een map (dictionary) op?

  1. AAlleen waarden in volgorde van invoegen
  2. BSleutel-waardeparen met unieke sleutels
  3. CWaarden gesorteerd op grootte
  4. DParen van gelijke sleutels
2.Makkelijk

Een graaf bestaat uit:

  1. AAlleen een wortel en bladeren
  2. BRijen en kolommen
  3. CKnopen (vertices) verbonden door kanten
  4. DAlleen sleutels en hashes
3.Makkelijk

Wat doet een hashfunctie in een hashtabel?

  1. AVersleutelt de waarden in de tabel
  2. BSorteert de sleutels in de tabel
  3. CBeeldt een sleutel af op een index in de tabel
  4. DTelt hoeveel sleutels er zijn opgeslagen
4.Gemiddeld

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

  1. A1 2 4 5 3
  2. B4 2 5 1 3
  3. C5 4 3 2 1
  4. D4 5 2 3 1
5.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(E²)
  4. DO(V × E)
6.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

  1. AO(1 + α), waarbij α = n / m
  2. BO(m)
  3. CO(log n)
  4. DO(n)
8.Moeilijk

Waarom worden B-bomen gebruikt in databases en bestandssystemen?

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

Antwoordenblad

  1. 1. B · Sleutel-waardeparen met unieke sleutels
  2. 2. C · Knopen (vertices) verbonden door kanten
  3. 3. C · Beeldt een sleutel af op een index in de tabel
  4. 4. D · 4 5 2 3 1
  5. 5. B · O(V + E)
  6. 6. A · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  7. 7. A · O(1 + α), waarbij α = n / m
  8. 8. A · Hun hoge vertakkingsgraad houdt de boom ondiep, wat trage schijflezingen vermindert

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