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

Hoeveel kanten heeft een boom met n knopen?

  1. A2n
  2. Bn − 1
  3. Cn + 1
  4. Dn
2.Makkelijk

Wat is een gerichte graaf?

  1. AEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  2. BEen graaf waarin elk paar verschillende knopen door een kant verbonden is
  3. CEen graaf waarvan alle kanten een gewicht hebben
  4. DEen graaf zonder cykels
3.Makkelijk

Wat zijn broer- of zusknopen (siblings) in een boom?

  1. AKnopen zonder kinderen
  2. BEen knoop en zijn ouder
  3. CKnopen die dezelfde ouder hebben
  4. DKnopen op dezelfde diepte in verschillende subbomen
4.Gemiddeld

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

  1. AHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
  2. BArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
  3. CHeaps bevatten nooit meer dan 100 elementen
  4. DAlle sleutels in een heap zijn gelijk
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(n)
  2. BO(1)
  3. CO(log n)
  4. DO(n²)
6.Gemiddeld

Wat is in het slechtste geval de hoogte van een binaire zoekboom met n knopen als de sleutels in gesorteerde volgorde worden ingevoegd?

  1. An (hij wordt een gekoppelde lijst)
  2. Blog₂ n
  3. C√n
  4. D1
7.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 deque met indices in afnemende volgorde van waarde
  3. CEen enkelvoudig gekoppelde lijst van de elementen in het venster
  4. DEen min-heap die voor elk venster opnieuw wordt opgebouwd
8.Moeilijk

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

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

Antwoordenblad

  1. 1. B · n − 1
  2. 2. A · Een graaf waarvan de kanten een richting hebben van de ene knoop naar de andere
  3. 3. C · Knopen die dezelfde ouder hebben
  4. 4. A · Het is een complete binaire boom, dus posities volgen eenvoudige indexformules
  5. 5. B · O(1)
  6. 6. A · n (hij wordt een gekoppelde lijst)
  7. 7. B · Een deque met indices in afnemende volgorde van waarde
  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.