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 op het patroon in de tekst te herkennen.

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