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 op de meest gebruikte computer
  2. BDe verwachte tijd over een gegeven verdeling van invoeren van grootte n
  3. CDe middelste waarde tussen de looptijden in het beste en het slechtste geval
  4. DDe tijd voor een invoer van gemiddelde lengte
2.Makkelijk

Wat is de tijdcomplexiteit van het vinden van de grootste waarde in een ongesorteerde array van n getallen?

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

Een lus begint met i = 1 en verdubbelt i bij elke iteratie totdat i > n. Hoeveel iteraties voert hij uit?

  1. AOngeveer n / 2
  2. BOngeveer n
  3. COngeveer n²
  4. DOngeveer log₂ n
4.Gemiddeld

Wat berekent het algoritme van Floyd-Warshall, en hoe snel?

  1. AEen minimale opspannende boom in O(E log V)
  2. BKortste paden tussen alle paren knopen in O(V³)
  3. CKortste paden vanuit één bronknoop naar alle andere in O(V + E)
  4. DEen topologische ordening in O(V²)
5.Gemiddeld

Wat meet geamortiseerde analyse?

  1. ADe verwachte kosten over willekeurige invoer
  2. BDe gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen
  3. CDe kosten van de ene duurste bewerking ergens in de reeks
  4. DDe kosten van een algoritme bij de beste invoer
6.Gemiddeld

Welke uitspraak over een recursieve functie zonder bereikbaar basisgeval is juist?

  1. ADe compiler maakt er altijd een lus van die veilig eindigt
  2. BZe blijft zichzelf aanroepen totdat de call stack overloopt
  3. CZe loopt in O(1) tijd
  4. DZe geeft automatisch 0 terug
7.Moeilijk

Wat moet je doen om aan te tonen dat een nieuw probleem X NP-moeilijk is?

  1. AAantonen dat X in polynomiale tijd kan worden geverifieerd
  2. BX in polynomiale tijd reduceren tot een bekend NP-moeilijk probleem
  3. CEen bekend NP-moeilijk probleem in polynomiale tijd reduceren tot X
  4. DAantonen dat X geen polynomiaal algoritme heeft voor kleine invoer
8.Moeilijk

Hoe wordt het handelsreizigersprobleem geclassificeerd?

  1. ADe beslissingsversie zit in P, maar de optimalisatieversie is NP-volledig
  2. BDe beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk
  3. CHet is onbeslisbaar
  4. DHet zit in P, omdat het algoritme van Dijkstra het oplost door elke stad één keer te bezoeken

Antwoordenblad

  1. 1. B · De verwachte tijd over een gegeven verdeling van invoeren van grootte n
  2. 2. B · O(n)
  3. 3. D · Ongeveer log₂ n
  4. 4. B · Kortste paden tussen alle paren knopen in O(V³)
  5. 5. B · De gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen
  6. 6. B · Ze blijft zichzelf aanroepen totdat de call stack overloopt
  7. 7. C · Een bekend NP-moeilijk probleem in polynomiale tijd reduceren tot X
  8. 8. B · De beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk

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