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

Een hashtabel slaat data op als:

  1. AUitsluitend een gesorteerde lijst
  2. BSleutel-waardeparen die via een hashfunctie worden gevonden
  3. CEen string met vaste lengte
  4. DEen boom met geordende sleutels
2.Makkelijk

Wat is een botsing (collision) in een hashtabel?

  1. ATwee verschillende sleutels worden op dezelfde index afgebeeld
  2. BDe tabel heeft geen geheugen meer
  3. CTwee gelijke sleutels worden twee keer opgeslagen
  4. DEen sleutel kan helemaal niet worden gehasht
3.Makkelijk

Wat is de max-heap-eigenschap?

  1. AAlle bladeren bevatten de maximale sleutel
  2. BDe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  3. CDe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer
  4. DDe sleutels zijn van links naar rechts gesorteerd
4.Gemiddeld

Een wegennet heeft 100,000 kruispunten, die elk met ongeveer 4 andere verbonden zijn. Welke representatie is het meest geschikt?

  1. AAdjacency list
  2. BAdjacency matrix
  3. CEén gesorteerde array van knopen
  4. DEen binaire heap van kanten
5.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 preorder-doorloop?

  1. A1 2 3 4 5
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D4 2 5 1 3
6.Gemiddeld

Wat is het doel van een sentinelknoop (dummyknoop) in een gekoppelde lijst?

  1. ADe code vereenvoudigen door speciale gevallen aan kop of staart weg te nemen
  2. BDe lijst gesorteerd maken
  3. CHet aantal elementen opslaan
  4. DVoorkomen dat de lijst groeit voorbij een vast maximumaantal knopen
7.Moeilijk

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

  1. AO(n) tijd en O(1) extra geheugen
  2. BO(n) tijd en O(n) extra geheugen
  3. CO(n log n) tijd en O(1) extra geheugen
  4. DO(1) tijd en O(1) 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 het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
  3. COm de hashtabel gesorteerd te maken
  4. DOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt

Antwoordenblad

  1. 1. B · Sleutel-waardeparen die via een hashfunctie worden gevonden
  2. 2. A · Twee verschillende sleutels worden op dezelfde index afgebeeld
  3. 3. B · De sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
  4. 4. A · Adjacency list
  5. 5. C · 1 2 4 5 3
  6. 6. A · De code vereenvoudigen door speciale gevallen aan kop of staart weg te nemen
  7. 7. A · O(n) tijd en O(1) extra geheugen
  8. 8. B · 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.