Nada

Övningstentamen i Datalogi, 2D1343

Hjälpmedel: Weiss eller annan algoritmbok. Betygsgränser: 25-34 => trea, 35-44 => fyra, 45-55 => femma. Totalt finns femtio tentapoäng och sju bonuspoäng.

1 Vetenskap (5p)

2 Vattengissning (5p)

Det pågår en gissningstävling om hur många millimeter som kommer att hamna i vattenfestivalens regnmätare 1999. Gissningen och gissarens namn och adress skrivs in i en jättefil. När det rätta svaret blir känt gäller det att gå igenom dom hundratusentals gissningarna och leta fram dom tusen bästa gissarna - dom vinner nämligen var sitt häftigt festivalparaply. Beskriv den bästa algoritmen och ange vilka datastrukturer som kommer till användning.

3 Förbjudna personnummer (10p)

Databasen över alla elektrospexare strider mot datalagen eftersom varje personpost innehåller variabeln char[] pnr med plats för tio siffror. Kanske kan man gå runt lagen genom att skriva personnumret baklänges?

4 Längre vårdag (10p)

Ordet vårdag har den speciella egenskapen att man kan stryka en bokstav i taget, den första eller den sista, och hela tiden få riktiga ord, nämligen

VÅRDAG -> VÅRDA -> VÅRD -> VÅR -> ÅR -> Å

Du ska nu skissera ett datorprogram som letar fram det längsta ordet i Svenska Akademiens Ordlista med denna egenskap! Du behöver inte skriva någon programkod, men du ska förklara algoritmen utförligt och beskriva datastrukturer, metoder och klassuppdelning. Klassen Stava, som du fått av Viggo, innehåller en metod public static boolean SAOL(String word) för att avgöra om ett ord finns i ordlistan. Programmet ska använda metoden, inte själva ordlistfilen.

5 Abstrakta personnummer (5p)

Den som programmerar personregister stöter snart på ett problem: Vilken datatyp är personnummer? Förklara några nackdelar med dom konkreta typerna int och String och char[]. Förklara vad som menas med en abstrakt datatyp Pnr och motivera att den kan vara bättre. Föreslå några viktiga metoder i klassen Pnr.

6 Hashmissbruk (5p)

Sorterings- och salighetslabben använde binärträd för snabb sökning i ordlista. Ännu snabbare hade sökningen blivit med en hashtabell. Hur många gånger snabbare skulle den bli om alla SAOLs 120259 ordlistord ska lagras? Du kan anta att det är antalet jämförelser som bestämmer tiden. Ange vilken storlek på hashvektorn du tänker dej.

I din hashvektor finns alla ord lagrade. Egentligen är det hashmissbruk eftersom Viggos program Stava klarar uppgiften utan ordlista. I stället beräknar det fjorton hashindex och tittar i en boolesk vektor om det står true på dessa fjorton ställen. Vektorn har längden size=3999971. Förklara hur det fungerar!

7 Är träden lika? (5p)

I ett program finns två binärträd med poster, varje post med ett heltalsfält pnr. Man vill programmera en metod boolean lika(Node root1, Node root2) som avgör om träden är identiska (samma personnummer och samma struktur). Formulera en korrekt rekursiv tanke som omedelbart kan omsättas i fungerande programkod!

8 På djupet (5p)

Man vill söka igenom ett binärträd djupet-först för att hitta ett visst personnummer. Kan någon av ordningarna preorder, inorder och postorder användas? Förklara i ett litet exempel, nämligen ett balanserat träd med sju poster. Föreslå också ett sätt att avbryta sökningen omedelbart när sökt person hittas.

Tentamensresultatet kommer upp på måndag på Nadas stora anslagstavla

Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 12 maj 1999
Tekniskt stöd: <webmaster@nada.kth.se>