Gegevensstructuren en Algoritmen

Uit Wina Examenwiki
Naar navigatie springen Naar zoeken springen
Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Nuttige links


Examenvragen

2006-2007

ma 29/01 8 uur

  1. Beschrijf hoe men (binaire en niet-binaire) bomen kan voorstellen.

  1. Leg aan de hand van de stack operaties PUSH, POP en MULTIPOP de technieken van geamortizeerde analyse uit:
    1. geaggregeerde analyse
    2. boekhoudmethode
    3. potentiaal methode
  1. Leg het Rabin Kap algoritme uit voor het matchen van een string in een tekst. Wat is de complexiteit? In het slechtste geval? Gemiddeld? Pas dit algoritme toe op
    1. alfabet = {0,1,2,3,4,5,6,7,8,9}
    2. tekst 52312121221
    3. patroon 121
    4. priemgetal q=11

ma 15/01 14 uur

  1. geef alle sorteeralgoritmes en vergelijk ze qua complexiteit(moest alleen vergelijkende sorteeralgoritmes) bijvragen zoals: en wat in worst case, hoeveel plaats heb je daarvoor nodig,..
  2. red-black trees
    1. wat is dat?
    2. je kreeg de code voor INSERT en FIXUP (zelfde als boek) en je moest dat uitleggen
    3. bewijs correctheid
    4. complexiteit?
    5. bouw een boom op door in volgorde 10,20,30,40,50 en 60 toe te voegen
  3. dynamisch programmeren, en demonstreren adhv dat voorbeeld van matrixvermenigvuldiging

(ik wist niets van die matrixvermenigvuldiging meer, maar ze was daar mild voor, je moet enkel de basis weten, niet tot in detail)

ma 15/01 8 uur

    1. a) wat is een heap
    2. b) hoe kan je een heap representeren met een array
    3. c) leg in detail uit (woorden of pseudocode) hoe heapsort werkt
    4. d) Toon aan dat het algoritme correct is
    5. e) bepaal de complexiteit van heapsort
    6. f) Vergelijk de complexiteit met de complexiteit van de andere sorteer algoritmes
    7. g) pas heapsort toe op A[3 7 2 5 8 1 9 4)
  2. Hashtabel van lengte m = 11
 Gebruik dubbel hashing met primaire functie h1(k)= k mod m
 en secundaire hashfunctie h2(k)=1+(kmod(m-1)) om achtereenvolgens de 
 sleutels 4,10,15,22,5 en 49 in te voegen, vertrekkende van een lege tabel.
  1. leg kort alle algoritmes uit voor String matching en vergelijk ze op gebied van complexiteit

2005-2006

dit jaar werkte nog met een ander boek, daarmee dat de vragen misschien wat raar kunnen overkomen.

oude examenvragen gegeven door de prof via Toledo:

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. Pas het algoritme toe op enkele gegeven getallen.

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

ma 30/01 8u00

  1. De ADT Queue
    1. bespreek de verschillende implementaties van een Queue
    2. Geef de efficientie van deze implementaties
  2. Beschrijf mergesort & selection sort. Wat is de tijdscomplexiteit en pas het algoritme toe op een gegeven rij.
  3. Geef de definitie van een AVL boom, wat zijn de voordelen ervan ten opzichte van een binaire zoek boom. Voeg de elementen(1-8) toe in een lege AVL boom. Verwijder 4 & 7 uit de bekome boom.
  4. Beschrijf het Knuth-Morris-Pratt matching algoritme. 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.

Willem 30 jan 2006 11:38 (CET)

wo 23/08

  1. De ADT Stack
    1. Bespreek de verschillende implementaties van de Stack
    2. Geef een algoritme gebaseerd op de ADT stack dat formules in infix omzet in formules in prefix
    3. Pas het algoritme toe op een voorbeeldje
  2. Heap-Sort
    1. Geef het algoritme van heapsort
    2. Bespreek de complexiteit van dit algoritme
    3. Pas het toe op een voorbeeldje
  3. Hashing
    1. Leg uit
    2. Geef de verschillende manieren om "botsingen" op te lossen en bespreek hun efficentie
  4. String-matching
    1. Bespreek het Rabin-Karb algoritme
    2. Wat is de complexiteit van dit algoritme
    3. Pas het toe op een voorbeeldje
Overgenomen van "http://examens.wina.be/index.php?title=Gegevensstructuren_en_Algoritmen&oldid=6451"