Gegevensstructuren en Algoritmen

Nuttige links

• Slides hooofdstuk 14: Deze slides staan niet op Toledo van G&A-Leuven, maar wel op die van G&A-Kulak
  • Ch14.odp (OpenOffice2) In deze versie heb ik de achtergrondkleur verwijderd
  • Ch14.ppt (Microsoft Powerpoint) Dit is de originele versie van KULAK

Examenvragen

2005-2006

ma 23/01 8u00

1. De ADT Heap
   1. Beschrijf de ADT Heap
   2. Beschrijf een array-implementatie van de ADT Heap
   3. Voeg een bepaald getal in in een gegeven heap
   4. Verwijder een getal uit de dan bekomen heap
   5. Geef de algoritmes die je voor het invoegen en verwijderen hierboven hebt gebruikt (in pseudocode)
2. Beschrijf het Heapsort-algoritme en pas dit toe op een gegeven rij. Wat is de tijdscomplexiteit van dit algoritme?
3. Wat is 'hashing'? Geef de verschillende manieren die je hebt gezien om botsingen op te lossen. Wat is de efficiëntie?
4. Geef het string-match algoritme dat gebruik maakt van eindige automaten. Je moet de gedachte zelf opbouwen, zonder echter de gedetailleerde bewijzen te geven van de gebruikte eigenschappen. Wat is de tijdscomplexiteit ervan? Gegeven een tekst en een patroon, gebruik het algoritme om het patroon in de tekst te herkennen.

--Stevel 23 jan 2006 14:34 (CET) aangevuld door --Thomas 23 jan 2006 16:39 (CET)

di 24/01 8u00

1. De ADT Priority Queue
   1. Beschrijf de priority queue.
   2. Geef een implementatie ervan.
   3. Voeg elementen 1-6 toe en verwijder dan een element.
2. Beschrijf quicksort, en implementeer het (pseudo-code). Wat is de tijdscomplexiteit en pas het algoritme toe op een gegeven rij.
3. Geef de definitie van een 2-3-4 boom, wat zijn de voordelen ervan ten opzichte van een 2-3 boom. Geef ook een aantal toevoegingen en verwijderingen (goed kiezen)
4. Beschrijf het algoritme dat breekpunten verwijdert met zo minimaal mogelijk flippings om een permutatie in een identieke permutatie te veranderen. Wat is de efficientie van dat algoritme.

--Dwight 24 jan 2006 15:18 (CET)