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 cykel in een graaf?

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

Wat wordt in een representatie als adjacency list (buurlijst) van een graaf per knoop opgeslagen?

  1. AHet kortste pad naar elke andere knoop
  2. BEen lijst van de buurknopen
  3. CEen rij van V Booleaanse waarden
  4. DHet totale aantal kanten in de graaf
3.Makkelijk

Wat is een botsing (collision) in een hashtabel?

  1. ADe tabel heeft geen geheugen meer
  2. BEen sleutel kan helemaal niet worden gehasht
  3. CTwee verschillende sleutels worden op dezelfde index afgebeeld
  4. DTwee gelijke sleutels worden twee keer opgeslagen
4.Gemiddeld

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

  1. AEen enkelvoudig gekoppelde lijst
  2. BEen dubbel gekoppelde lijst
  3. CEen gesorteerde array
  4. DEen dynamische array
5.Gemiddeld

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

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

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

  1. AArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  2. BGekoppelde lijsten slaan elementen altijd op schijf op
  3. CArrays gebruiken minder instructies om waarden te vergelijken
  4. DEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
7.Moeilijk

Wat is het belangrijkste voordeel van een skiplist ten opzichte van een gesorteerde gekoppelde lijst?

  1. AHij slaat sleutels ongeordend op
  2. BGegarandeerd zoeken in O(1), omdat elke knoop een pointer naar elke andere knoop bewaart
  3. CVerwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers
  4. DHij gebruikt geen extra geheugen
8.Moeilijk

Waarom zou een server zijn hashfunctie willekeurig kiezen uit een universele familie?

  1. AOm het vergroten van de tabel overbodig te maken
  2. BOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt
  3. COm het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
  4. DOm de hashtabel gesorteerd te maken

Antwoordenblad

  1. 1. A · Een pad dat begint en eindigt in dezelfde knoop
  2. 2. B · Een lijst van de buurknopen
  3. 3. C · Twee verschillende sleutels worden op dezelfde index afgebeeld
  4. 4. B · Een dubbel gekoppelde lijst
  5. 5. C · De hoogten van de linker- en rechtersubboom verschillen hoogstens 1
  6. 6. A · Array-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
  7. 7. C · Verwacht zoeken in O(log n) door meerdere niveaus van voorwaartse pointers
  8. 8. C · Om het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen

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