Nada

Lösning till övningstentamen i Datalogi, 2D1343

1 Vetenskap (5p)

Skonummer och betyg i första klass (båda ökar med åldern). När bridgespelaren ser sina tretton kort kan han alltid konstatera att det är ytterst osannolikt att få just den kombinationen.

2 Vattengissning (5p)

Putta in dom i en trappa (heap) sorterad efter avvikelsen mellan gissningen och verkligheten. Hämta sedan ut tusen poster ur trappan - det är vinnarna!

3 Förbjudna personnummer (10p)

Ingen lyckas. Elon får 8180990818. Elof får 4201190818.

4 Längre vårdag (10p)

Problemträdet består av ordposter med faderspekare. Det tomma ordet är stamfar. Man gör breddenförstsökning med hjälp av en kö ända tills kön tömts. Det sista ordet ger då lösningen via faderspekarkedjan. Söner skapas genom att en bokstav läggs till först eller sist. Klassuppdelning som i salighetslabben.

5 Abstrakta personnummer (5p)

En int får inte vara hur stor som helst, tiosiffriga pnr kan bli för stora. En char[] tar mycket minnesutrymme (tjugo byte). En String är det bökigt att plocka ut t ex årtal ur. Väljer man en abstrakt datatyp kan man sedan välja den bästa implementationen genom att bara ändra i klassen Pnr. Här är ett utkast till klass.
class Pnr{
   private ... //implementeringen är privat
   public Pnr(String word) throws WrongCheckdigit{...} //konstruktor
   public boolean male(){...}
   public boolean female(){...}
   public int year(){...}
   public int month(){...}
   public int day(){...}
   public int last4(){...}
   public boolean equals(Pnr pnr){...}
   public String toString(){...}
}

6 Hashmissbruk (5p)

Ett balanserat binärträd med SAOLs 120259 ordlistord har sjutton nivåer. Lyckad sökning kräver i genomsnitt sexton jämförelser. En hashvektor med 180000 platser kräver i genomsnitt kanske 1.6 jämförelser och är alltså tio gånger snabbare.

Stavaprogrammet finns att studera i föreläsningsanteckningarna nr 16.

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

Två träd är lika om
  1. dom båda rotpersonnumren är lika,
  2. dom båda vänsterträden är lika
  3. dom båda högerträden är lika
...men om båda träden är tomma är dom också lika
...men om bara det ena är tomt är dom inte lika.

8 På djupet (5p)

Preorder ger just djupet-först. Avbrott kan göras med ett särfall

throw new Found(personen);


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