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 die op schijf is opgeslagen
  3. CEen graaf waarin sommige knopen zwaarder zijn dan andere doordat ze meer kanten hebben
  4. DEen graaf met meer kanten dan knopen
2.Makkelijk

Wat definieert een binaire boom?

  1. AElke knoop slaat een binair getal op
  2. BElke knoop heeft hoogstens twee kinderen
  3. CElke knoop heeft precies twee kinderen
  4. DDe boom heeft precies twee niveaus
3.Makkelijk

Wat is een cykel in een graaf?

  1. AEen knoop zonder kanten
  2. BEen pad dat elke knoop bezoekt
  3. CEen pad dat begint en eindigt in dezelfde knoop
  4. DEen kant met gewicht nul
4.Gemiddeld

Een knoop in een binaire zoekboom heeft een rechtersubboom. Waar staat zijn inorder-opvolger?

  1. AAltijd zijn ouder
  2. BDe meest linkse knoop van zijn rechtersubboom
  3. CAltijd zijn rechterkind
  4. DDe meest rechtse knoop van zijn linkersubboom
5.Gemiddeld

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

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

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

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

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

  1. AEen stack van alle bezochte kanten
  2. BEen max-heap geordend op uitgraad
  3. CEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd
  4. DEen queue (of een willekeurige verzameling) van knopen met ingraad 0
8.Moeilijk

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

  1. ABereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden
  2. BStrings alfabetisch te sorteren door elk voorvoegsel in een aparte boomknoop op te slaan
  3. CEen stack te implementeren
  4. DDe kanten van een graaf op te slaan

Antwoordenblad

  1. 1. A · Een graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand
  2. 2. B · Elke knoop heeft hoogstens twee kinderen
  3. 3. C · Een pad dat begint en eindigt in dezelfde knoop
  4. 4. B · De meest linkse knoop van zijn rechtersubboom
  5. 5. A · O(log n)
  6. 6. B · O(1)
  7. 7. D · Een queue (of een willekeurige verzameling) van knopen met ingraad 0
  8. 8. A · Bereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden

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