Fiktiv tentamen i Tillämpad datalogi, 2D1320

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

1 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).

2 Vattengissning (6p)

Det pågår en gissningstävling om hur många millimeter som kommer att hamna i vattenfestivalens regnmätare 1996. Gissningen (ett flyttal) 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 Nya personnummerlagen (8p)

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.

4 Fikonspråket (9p)

En BNF-grammatik för begreppet <ord> innehåller syntaxregeln <ord>::=<fördel><efterdel>. Din uppgift är att skriva syntaxreglerna för <fördel> och <efterdel> . Avsikten är att fördelen ska sträcka sej fram till och med första vokalen i ordet. Du får anta att begreppen <vokal>, <konsonant> och <bokstav> är definierade.

Beskriv sedan i ord hur grammatiken kan användas för att skriva en kompilator som översätter vanlig text som Talar du detta språk till Filartakon fidukon fittadekon fikspråkon?

5 Abstrakta pengar (6p)

Den som programmerar ekonomiska tillämpningar stöter snart på ett problem: Vilken datatyp är pengar? Det går inte med INTEGER när man ska räkna med 7.15 (vad en skollunch får kosta) och inte med REAL när man har tolvsiffriga tal som 67503824199 (Nordbankens kreditförluster). Det är bäst att använda en abstrakt datatyp, kronor . Definiera en sådan genom att ange några viktiga procedurer. Föreslå också en implementering och beskriv moduluppdelningen.

6 Syntetisering (9p)

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 (7p)

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.

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


Senast ändrad 17 dec. 1996 <henrik@nada.kth.se>