Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________
OPGAVE 1 Bekijk onderstaand algoritme recAlg.
5 punten 5 punten 5 punten 5 punten
a
Bepaal recAlg(5) en laat zien hoe u het antwoord hebt verkregen.
b
Wat berekent recAlg in het algemeen? Verklaar uw antwoord.
c
Bepaal de complexiteit van recAlg. Licht uw antwoord toe.
d
Breng een kleine verandering aan in recAlg zodanig dat deze efficiënter wordt. Bepaal de complexiteit van de veranderde recAlg. Licht uw antwoord toe. Algorithm recAlg(n): Input: Integer n Output: Integer result Å 1 if n > 1 then result Å 1 + recAlg(n - 1) + recAlg(n - 1) { end if } return result
OPGAVE 2
10 punten
a
Geef een snel recursief algoritme in pseudo-code of Java voor het omkeren van een enkelvoudige geschakelde lijst L, zodat de volgorde van de schakels in de lijst omgekeerd wordt. Hint: Gebruik een hulpmethode waarin de eerste n schakels van de lijst worden omgekeerd. De terugkeerwaarde van de hulpmethode is een verwijzing naar de n‐de schakel. U mag er vanuit gaan dat de klasse SLinkedList uit codefragment 3.13 van het tekstboek methoden addFirst en getFirst heeft.
b
Wat is de complexiteit van uw algoritme? Geef ook een verklaring van de complexiteit. OPGAVE 3
5 punten
10 punten
Waar kan in een heap het element met de grootste sleutel staan? Licht uw antwoord toe. OPGAVE 4 Gegeven is de rij S 5 16 22 45 2 10 18 30 50 12 1
5 punten
a 10 punten
1
Voeg de getallen van S in de gegeven volgorde (eerst 5, dan 16, …) toe aan een lege binaire zoekboom en teken het eindresultaat.
Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________
b
Voeg de getallen van S in de gegeven volgorde toe aan een lege AVLboom en teken het tussenresultaat direct voor en na elke rotatie en teken het eindresultaat.
OPGAVE 5
10 punten
Op blz 408 van het tekstboek staat dat een hash-tabel niet geschikt is om een geordende dictionary te realiseren. De uitleg hiervan is summier. Licht dit nader toe. OPGAVE 6 5 punten
a
Op blz. 612 van het tekstboek wordt gesproken over BFS voor gerichte grafen. Geef een implementatie van directedBFS in pseudocode.
b
We passen directedBFS toe op de gerichte graaf van figuur 13.10 (a) op blz. 614 van het tekstboek. Kies een knooppunt van waaruit de gehele graaf wordt doorlopen en geef een volgorde van de knooppunten waarin deze bezocht kunnen worden door directedBFS.
c
Geef de verschillende soorten kanten (zowel tree edges als nontree edges) die door directedBFS worden benoemd. OPGAVE 7 We bekijken de string X = ‘dogs do not spot hot pots or cats’.
a
Geef een frequentietabel en een Huffman‐boom voor (de karakters van) X en geef de bijbehorende code van de karakters ‘d’, ‘o’, ‘g’ en ‘ ’.
b
Zijn er andere Huffman‐bomen voor X mogelijk? Zo ja, geef er één en geef de bijbehorende code van de karakters ‘d’, ‘o’, ‘g’ en ‘ ’.; zo nee, waarom niet?
5 punten
5 punten
8 punten
7 punten
2
Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________
UITWERKINGEN
a
b
OPGAVE 1 Het eenvoudigste is om achteraan te beginnen. recAlg(1) = 1 recAlg(2) = 1 + 2*1 = 3 recAlg(3) = 1 + 2*3 = 7 recAlg(4) = 1 + 2*7 = 15 recAlg(5) = 1 + 2*15 = 31 recAlg(n) = 2n ‐ 1 Dit is in te zien door de uitwerking van a te herschrijven: recAlg(1) = 1 = 20 recAlg(2) = 20 + 2*20 = 20 + 21 recAlg(3) = 20 + 2*(20 + 21) = 20 + 21 + 22 recAlg(4) = 20 + 2*(20 + 21 + 22) = 20 + 21 + 22 + 23 … (eigenlijk met volledige inductie te bewijzen) recAlg(n) = 20 + … + 2n‐1 = 2n ‐ 1
c
Het aantal recursieve aanroepen verdubbelt steeds en is bij recAlg(n) gelijk aan 2n‐1. Per aanroep hebben we 1 toekenning of 1 toekenning en 2 optellingen, dus altijd O(1), en dus is het totaal aantal primitieve bewerkingen evenredig met 2n‐1. De complexiteit is dus O(2n) en zelfs Θ(2n) omdat er geen sprake is van een verschil tussen een slechtste en beste geval.
d
Vervang result Å 1 + recAlg(n ‐ 1) + recAlg(n ‐ 1) door result Å 1 + 2 * recAlg(n ‐ 1). Nu is de complexiteit Θ(n) want het aantal recursieve aanroepen bij recAlg(n) is gelijk aan n ‐ 1. OPGAVE 2
a
private static Node reverse(SLinkedList list, int n){ if (n == 1){ return list.getFirst(); } else { Node end = reverse(list, n-1); if (end != null){ Node newfirst = end.getNext(); end.setNext(newfirst.getNext()); // newfirst verwijderen list.addFirst(newfirst); } return end; }
} Deze recursieve methode roepen we als volgt aan in methode reverse. : public static void reverse(SLinkedList list){ reverse(list, list.size()); }
3
Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________
b
In totaal zijn er n recursieve aanroepen waarbij n het aantal elementen in de geschakelde lijst is. Binnen een recursieve aanroep zijn alle methode aanroepen O(1), de complexiteit van het gehele algoritme is dus Θ(n). OPGAVE 3 In een heap geldt de eis dat elk knooppunt m.u.v. de wortel een grotere of dezelfde sleutel bevat als zijn ouder. Dus bij allemaal verschillende sleutels zal de grootste alleen in de één‐na onderste of twee‐na onderste laag voorkomen. (Nota bene, de bladeren van een heap bevatten geen elementen.) Als de grootste sleutel echter meermaals voorkomt, kan deze ook op een hoger niveau staan mits er onder alleen maar duplicaten voorkomen. Alleen als alle sleutels gelijk zijn, kan de ‘grootste’ in de wortel staan. OPGAVE 4
a 5 2
16
1
10
22
12
18
45 30
b Na toevoeging van de eerste drie is het hoogteverschil 2: 3 5 2 0
16 1 22
Enkele rotatie:
4
50
Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________
16 5
22
Verder geen rotaties meer nodig, dus meteen het eindresultaat: 16 5 2 1
a
b
5
22 10
18 12
45 30
50
OPGAVE 5 Een hash-tabel is geschikt voor de realisatie van een ongeordende dictionary (zie blz. 393 ev). We hoeven dus alleen te laten zien dat een hash‐tabel niet geschikt is voor realisatie van de methoden die specifiek zijn voor geordende dictionaries, te weten first, last en successors, predecessors. Uiteraard gaan we er van uit dat de sleutels geordend kunnen worden, anders gezegd dat ze een lineair geordend verzameling vormen. In een hash‐tabel wordt een item opgeslagen door op de sleutel de hash‐ functie toe te passen die de hash‐code als functiewaarde geeft. Ook al zijn de sleutels geordend, hun hash‐codes zijn dat in het algemeen niet, dus een hash‐tabel is een ongeordende tabel. Als nu een methode first of last gerealiseerd moet worden, betekent dat dat de gehele hash‐tabel doorzocht moet worden en dat is zeer inefficiënt. Hetzelfde geldt voor successors en predecessors. OPGAVE 6 In het algoritme op blz 605 van het tekstboek moeten we alleen kanten e bekijken die vanuit punt v vertrekken. Methode endVerticeces(e) geeft een Array A zodanig dat A[0] het begin punt en A[1] het eindpunt is van de kant e. (zie blz 608 van het tesktboek). Vervang daarom in het algoritme op blz 605 van het tekstboek de regel ‘for all edges e in G.incidentEdges (v) do’ door ‘for all edges e in G. incidentEdges(v) do if G.endVertices(e)[0] = v De knooppunten worden in geval van BFS niveau voor niveau nagelopen. Als we beginnen met knooppunt BOS, dan is dat het 0e niveau.
Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________
c
a
In het 1e niveau vinden we dan JFK en MIA Het 2e niveau levert SFO , DFW en LAX op In het 3e niveau is er nog ORD . Een mogelijke volgorde is BOS, JFK, MIA, SFO, DFW, LAX, ORD. Opmerking Als er verschillende kanten van het ene niveau naar het volgende niveau lopen dan worden ze in willekeurige volgorde bezocht en dus zijn er ook andere mogelijkheden voor deze volgorde. JFK en MIA zouden bijvoorbeeld omgekeerd kunnen staan, ook de drie knooppunten in niveau twee kunnen onderling in een andere volgorde staan. DirectedBFS verdeelt de edges in tree edges (discovery edges) en nontree edges. De tree edges zijn kanten die leiden naar een nog niet bezocht knooppunt, en die samen met de knooppunten een boom vormen met als wortel het beginknooppunt. In de voorbeeldgraaf zijn dat voor de gekozen volgorde: BOS Æ JFK , BOS Æ MIA , JFK Æ SFO , JFK Æ DFW , MIA Æ LAX en DFW Æ ORD. Bij de BFS (ongerichte variant) waren nontree edges altijd cross edges, dat wil zeggen kanten die een knooppunt verbinden met een knooppunt dat noch zijn voorouder noch zijn nakomeling is in de BFS boom. In de DirectedBFS vinden we twee soorten nontree edges, de genoemde cross edges: JFK Æ MIA, MIA Æ DFW, DFW Æ LAX, DFW Æ SFO en LAX Æ ORD, en back edges, die een knooppunt met een voorouder in de BFS boom verbinden: JFK Æ BOS en ORD Æ DFW. OPGAVE 7 De frequentietabel van de string X = ‘dogs do not spot hot pots or cats’ is:
‘‘
A
c
d
g
h
n
o
p
r
s
t
7
1
1
2
1
1
1
7
2
1
4
5
Na verwerking met het Huffman‐coderingsalgoritme ontstaat de volgende boom:
6
Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________ 33
14 19
‘‘
o
7
7
8
s
4
p
2
11
t
4
6
5 2
4
2 a
g
1
1
c
r
1
1
2 h
n
1
1
b
7
d
2
De codes worden dan: d = 11111 o = 01 g = 10001 ‘ ‘ = 00 Er zijn andere Huffman-bomen mogelijk. Het hangt af van de volgorde in de frequentietabel (of liever gezegd de volgorde waarin de elementen in eerste instantie in Q worden gezet) en ook van de implementatie van de priorityqueue-methoden: nl. om de heaporde te herstellen bij insertie en removal wordt een ouder die groter is dan zijn kind(eren) met het kleinste kind omgewisseld. Echter als beide kinderen even groot zijn geeft het boek geen duidelijke richtlijnen en kun je blijkbaar kiezen tussen het linker en rechterkind waarmee de ouder verwisseld wordt. Dus zowel verschillen in de volgorde van de karakters als verschillen in de manier van ‘heapen’ kunnen tot een andere boom leiden. Onderstaande boom ontstaat door de spatie als laatste karakter toe te voegen aan Q in plaats van als eerste karakter.
Voorbeeldtentamen 1
Tentamen Datastructuren en algoritmen (T26241 en T26741) ________________________________________________________________________________________ 33
14
19
o
‘‘ 8
7
11
7 4
t
4
6
5 p
2
2
2
2 a 1
c 1
De codes worden dan: d = 1110 o = 00 g = 10110 ‘ ‘ = 01
8
h
n
g
1
1
1
d
s
2
4
r 1
