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 een gewogen graaf?

  1. AEen graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
  2. BEen graaf met meer kanten dan knopen
  3. CEen graaf die op schijf is opgeslagen
  4. DEen graaf waarin sommige knopen zwaarder zijn dan andere doordat ze meer kanten hebben
2.Makkelijk

Wat is een blad in een boom?

  1. AEen knoop zonder kinderen
  2. BDe knoop met de grootste waarde
  3. CEen knoop zonder ouder
  4. DEen knoop met precies één kind
3.Makkelijk

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

  1. AHet aantal kinderen van de wortel
  2. BHet totale aantal knopen in de boom, inclusief de wortel en elk blad
  3. CHet aantal kanten op het langste pad van de wortel naar een blad
  4. DHet aantal bladeren in de boom
4.Gemiddeld

Hoe lang duurt het zoeken naar een woord met lengte L in een trie met een vast alfabet?

  1. AO(L), onafhankelijk van hoeveel woorden er zijn opgeslagen
  2. BO(log n), waarbij n het aantal woorden is
  3. CO(L × n)
  4. DO(n), waarbij n het aantal woorden is
5.Gemiddeld

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

  1. AEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  2. BAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
  3. CDe oudste sleutels worden verwijderd om ruimte te maken
  4. DDe bestaande sleutels worden ter plaatse gesorteerd
6.Gemiddeld

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

  1. Ai + 1 en i + 2
  2. B2i en 2i + 1
  3. C2i + 1 en 2i + 2
  4. Di/2 en i/2 + 1
7.Moeilijk

Wat zijn de tijd- en extra geheugenkosten van het ter plaatse omkeren van een enkelvoudig gekoppelde lijst?

  1. AO(1) tijd en O(1) extra geheugen
  2. BO(n log n) tijd en O(1) extra geheugen
  3. CO(n) tijd en O(n) extra geheugen
  4. DO(n) tijd en O(1) extra geheugen
8.Moeilijk

Welke datastructuur maakt een LRU-cache (least recently used) met get en put in O(1) mogelijk?

  1. AAlleen een binaire zoekboom
  2. BAlleen een stack
  3. CEen hashmap gecombineerd met een dubbel gekoppelde lijst
  4. DEén gesorteerde array

Antwoordenblad

  1. 1. A · Een graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
  2. 2. A · Een knoop zonder kinderen
  3. 3. C · Het aantal kanten op het langste pad van de wortel naar een blad
  4. 4. A · O(L), onafhankelijk van hoeveel woorden er zijn opgeslagen
  5. 5. A · Er wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  6. 6. C · 2i + 1 en 2i + 2
  7. 7. D · O(n) tijd en O(1) extra geheugen
  8. 8. C · Een hashmap gecombineerd met een dubbel gekoppelde lijst

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