Nada

Fiktiv tentamen 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 sex bonuspoäng.

1 Vetenskap (5p)

Koppla ihop nedanstående personer med var sitt nyckelord.
Personer: Alan Turing, Hannes Alfvén, Kurt Gödel, James Randi, Arkimedes.
Nyckelord: Hypotenusa, meditation, badkar, blod, plasma, skepsis, obevisbarhet, pappersremsa, pyramid.

2 Sortera kö (5p)

I en abstrakt kö ligger personposter slumpmässigt ordnade. Beskriv i ord eller med programkod hur man från huvudprogrammet kan ordna kön efter fältet pnr. Sist i kön ligger en fiktiv post med pnr=999999999 (tionde personnummersiffran används inte).

3 Samkörning (5p)

Kommunen vill samköra två personregister, ett med daghemsföräldrar och ett med sjukförsäkrade, för att kontrollera att inkomstuppgifterna stämmer överens. (Det är ju frestande att anmäla låg inkomst till dagis och hög till sjukkassan.) Båda filerna är sorterade i personnummerordning, men många personer finns bara med i den ena filen. Föreslå en algoritm för samkörningen!

4 Nya personnummerlagen (10p)

Nya regler för personnummeranvändning gör det nödvändigt att ta bort dom fyra sista siffrorna ur personnummerfältet i många register. Som sorterings- och söknyckel kommer man att i första hand välja födelsedatum och vid samma datum sortera i bokstavsordning på namnet. Register som nu är sorterade efter personnummer måste alltså sorteras om, så att t ex 6705091152 ERIKSSON,KIMMO kommer före 6705091053 ERIKSSON,LABAN.

Föreslå lämplig sorteringsmetod om registret är en array med cirka tiotusen poster på cirka hundra byte var.

Föreslå lämplig metod om registret är ett binärträd (sorterat på det gamla sättet efter pnr) och ett nytt binärträd ska tillverkas med den nya ordningen.

5 Abstrakta pengar (5p)

Den som programmerar ekonomiska tillämpningar stöter snart på ett problem: Vilken datatyp är pengar? Det går inte med int när man ska räkna med 7.15 (vad en skollunch får kosta) och inte med double när man har sextonsiffriga tal som 11267503824199.50 (USAs statsskuld). Det är bäst att använda en abstrakt datatyp, kronor . Definiera en sådan genom att ange några viktiga metoder. Föreslå också en implementering.

6 Syntetisering (10p)

I en processkemisk databas finns poster av ungefär följande utseende:
C6H10O5 -> HNOC17H32O16(COOH)2  0.93   ..processbeskrivning..
Processen framställer den andra substansen av den första och utbytet är 93%. Uppfinn en algoritm som letar fram den effektivaste processkedjan för att framställa en given substans av en annan given substans! Ange också datastrukturer och lämplig modulindelning.

7 Hashning av substanser (5p)

För blixtsnabb sökning i den nämnda databasen med cirka tiotusen poster vill man använda hashning med den första formeln som nyckel (alltså C6H10O5 i exemplet ovan). Föreslå en hashfunktion och storlek på hashvektorn.

8 Snabbsortering (5p)

Tilda och Totte skrev var sin sorteringsprocedur. Tilda valde en utsökt quicksort medan Totte tog en standard selection sort. När dom provkörde med tusen poster gick ändå Tottes program lika fort, eftersom han har superdator. Men med tiotusen poster vann Tilda. Hur många gånger snabbare var hon?

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


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