Datastructuren en algoritmen: oefenopgaven en tentamenvragen

Big-O-notatie, de looptijd van veelgebruikte algoritmen en de afwegingen tussen arrays, gelinkte lijsten, bomen, hashtabellen en grafen.

Oefen dit vak gratisDit vak oefenenMaak een proeftentamenElke dag 5 gratis opgaven. Geen creditcard nodig.

Samenvattingspakket (pdf)Formuleoverzichten, methodestappen en oefenopgaven met volledige oplossingen, klaar om af te drukken.

Onderwerpen in dit vak

  1. Algoritmen & complexiteitkernbegrippen en feiten · begrippen toepassen · casussen en analysemeerkeuze
  2. Datastructurenkernbegrippen en feiten · begrippen toepassen · casussen en analysemeerkeuze
  3. Grafentheoriegraden en kanten · Eulerpaden en bomen · kortste paden en opspannende bomenrekenopgaven

Tentamentips voor Datastructuren en algoritmen

  • Vermenigvuldig bij geneste lussen het aantal iteraties; houd bij lussen na elkaar de grootste term.
  • Ken de kosten van zoeken, invoegen en verwijderen voor elke datastructuur.
  • De invoer bij elke stap halveren geeft logaritmische tijd.

Uitgewerkte voorbeelden

Algoritmen & complexiteitMakkelijk

Welke notatie beschrijft een bovengrens voor de groei?

  1. AGrote Omega (Big Omega)
  2. BKleine omega (little omega)
  3. CGrote O (Big O)
  4. DGrote Theta (Big Theta)
Hints tonen
  1. "Hoogstens".
  2. Twee foute antwoorden zijn nu doorgestreept. Een van de twee overgebleven antwoorden is goed.
Toon het antwoord en de uitleg

Waarom dit het antwoord is

O geeft een bovengrens, Ω een ondergrens en Θ een strakke grens.

Antwoord

C · Grote O (Big O)
DatastructurenGemiddeld

Hoe werkt extract-min in een binaire min-heap?

  1. AVerwijder het laatste element van de array
  2. BVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
  3. CVerwijder de wortel en schuif alle elementen één plaats naar links
  4. DZoek in alle bladeren naar het nieuwe minimum
Hints tonen
  1. Houd de boom compleet en herstel dan de ordening.
  2. Twee foute antwoorden zijn nu doorgestreept. Een van de twee overgebleven antwoorden is goed.
Toon het antwoord en de uitleg

Waarom dit het antwoord is

Het laatste element vult het gat in de wortel en wordt verwisseld met zijn kleinste kind tot de heap-eigenschap geldt, wat O(log n) kost.

Antwoord

B · Verplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)

Zo werkt het oefenen

  • “Dit vak oefenen” mengt opgaven uit al zijn onderwerpen, net als een echt tentamen.
  • Elke opgave heeft nieuwe waarden, zodat je de methode leert in plaats van een antwoord.
  • Kom je vast te zitten? Open eerst een kleine hint en de volledige uitleg pas als je die nodig hebt.
  • Proeftentamens zijn getimed en hebben geen hints, en aan het eind krijg je je score en een volledige bespreking.

Gerelateerde vakken

Basis informaticaDiscrete wiskundeComputernetwerken
Oefen dit vak gratisDit vak oefenenMaak een proeftentamenElke dag 5 gratis opgaven. Geen creditcard nodig.