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

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

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

Welke datastructuur wordt gebruikt voor een level-order-doorloop van een boom?

  1. AQueue
  2. BHashtabel
  3. CPrioriteitswachtrij
  4. DStack
3.Makkelijk

Wat bevat elke knoop in een dubbel gekoppelde lijst?

  1. ATwee kopieën van de data en één pointer
  2. BData en twee pointers, één naar de volgende knoop en één naar de knoop daarna
  3. CData, een pointer naar de volgende knoop en een pointer naar de vorige knoop
  4. DData en alleen een pointer naar de volgende knoop
4.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 bestaande sleutels worden ter plaatse gesorteerd
  4. DDe oudste sleutels worden verwijderd om ruimte te maken
5.Gemiddeld

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(1)
6.Gemiddeld

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

  1. AO(E)
  2. BO(V)
  3. CO(1)
  4. DO(log V)
7.Moeilijk

Aan welke eigenschap moet een rood-zwartboom voldoen?

  1. ARode knopen moeten rode kinderen hebben, dus rode knopen vormen altijd ononderbroken ketens tot de bladeren
  2. BElk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  3. CElke knoop moet rood zijn
  4. DDe wortel moet rood zijn
8.Moeilijk

Met welke structuur bereken je het maximum van elk venster van grootte k in een array in totaal O(n)?

  1. AEen gesorteerde array die door verschuiven wordt bijgewerkt
  2. BEen min-heap die voor elk venster opnieuw wordt opgebouwd
  3. CEen deque met indices in afnemende volgorde van waarde
  4. DEen enkelvoudig gekoppelde lijst van de elementen in het venster

Antwoordenblad

  1. 1. A · In de wortel
  2. 2. A · Queue
  3. 3. C · Data, een pointer naar de volgende knoop en een pointer naar de vorige knoop
  4. 4. A · Er wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd
  5. 5. D · O(1)
  6. 6. C · O(1)
  7. 7. B · Elk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
  8. 8. C · Een deque met indices in afnemende volgorde van waarde

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