Werkblad Algoritmen & complexiteit met antwoorden

Gratis printbaar werkblad Algoritmen & complexiteit: 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 beschrijft de average-case looptijd?

  1. ADe tijd voor een invoer van gemiddelde lengte
  2. BDe verwachte tijd over een gegeven verdeling van invoeren van grootte n
  3. CDe tijd op de meest gebruikte computer
  4. DDe middelste waarde tussen de looptijden in het beste en het slechtste geval
2.Makkelijk

Hoe heet groei van O(2ⁿ)?

  1. APolynomiaal
  2. BLineair
  3. CLogaritmisch
  4. DExponentieel
3.Makkelijk

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

Breedte-eerst zoeken (BFS) op een ongewogen graaf vindt:

  1. AEen topologische volgorde in alle grafen
  2. BKortste paden in grafen met negatieve kantgewichten
  3. CDe minimaal opspannende boom
  4. DKortste paden in aantal kanten vanaf de startknoop
5.Gemiddeld

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

  1. AMergesort is al O(n)
  2. BMergesort heeft geen recursieve structuur
  3. CDynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
  4. DDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
6.Gemiddeld

Een functie voert één lus van n iteraties uit en daarna, los daarvan, nog een lus van n iteraties. Wat is de tijdcomplexiteit?

  1. AO(2ⁿ)
  2. BO(n²)
  3. CO(n)
  4. DO(log n)
7.Moeilijk

Waarom heeft elke zoekmethode op basis van vergelijkingen in een gesorteerde array in het slechtste geval Ω(log n) vergelijkingen nodig?

  1. AElke vergelijking kost logaritmische tijd
  2. BEen beslisboom met n mogelijke uitkomsten moet een diepte van minstens log₂ n hebben
  3. CElk element moet minstens één keer worden vergeleken
  4. DBinair zoeken is het enige mogelijke algoritme en heeft log₂ n vergelijkingen nodig
8.Moeilijk

Kortste enkelvoudige paden kunnen in polynomiale tijd worden gevonden. Wat is bekend over het vinden van het langste enkelvoudige pad tussen twee knopen in een algemene graaf?

  1. AHet is altijd oplosbaar in O(V + E)
  2. BHet is onbeslisbaar
  3. CHet is NP-moeilijk
  4. DHet kan worden opgelost met het algoritme van Dijkstra met negatieve gewichten

Antwoordenblad

  1. 1. B · De verwachte tijd over een gegeven verdeling van invoeren van grootte n
  2. 2. D · Exponentieel
  3. 3. A · O(n)
  4. 4. D · Kortste paden in aantal kanten vanaf de startknoop
  5. 5. D · De deelproblemen overlappen niet, dus er valt niets te hergebruiken
  6. 6. C · O(n)
  7. 7. B · Een beslisboom met n mogelijke uitkomsten moet een diepte van minstens log₂ n hebben
  8. 8. C · Het is NP-moeilijk

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