Örebro universitet
Institutionen för teknik
Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se)




Tentamen i

Programmeringsmetodik

för D2, SDU2 m fl

torsdag 6 november 2008 kl 8:00 - 12:00

Gäller som tentamen för:
DT2010 Datateknik B, Programmeringsmetodik, provkod 0100
DT2006 Datateknik B, Tillämpad datavetenskap B, provkod 0110





Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 40.
För godkänt betyg (3 respektive G) krävs 20 poäng.
Resultat: Meddelas på kursens hemsida eller via e-post senast måndag 24 november 2008.
Visning och frågestund: Tisdag 25 november 2008 kl 15:00-15:30 i mitt rum (T2220).
Efter visningen kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-73 47 013.



LYCKA TILL!

Prioritet och associativitet hos operatorerna i C

Den fullständiga tabellen, med alla operatorer som finns i C:

Prioritet Kategori Operator Associativitet
Högsta Unära postfixoperatorer (), [], ->, ., ++, -- vänster
  Unära prefixoperatorer !, ~, ++, --, +, -, *, &, sizeof, (typ) höger
  Multiplikation mm *, /, % vänster
  Addition mm +, - vänster
  Bitvis skift <<, >> vänster
  Jämförelser <, <=, >=, > vänster
  Likhetsjämförelser ==, != vänster
  Bitvis OCH & vänster
  Bitvis XOR ^ vänster
  Bitvis ELLER | vänster
  Logiskt OCH && vänster
  Logiskt ELLER || vänster
  Villkorsoperatorn ?: höger
  Tilldelning =, +=, -=, *=, /=, %=, >>=, <<=, &=, ^=, |= höger
Lägsta Komma-operatorn , vänster

Uppgift 1 (1 p)

Talen 1, 3, 2, 6, 4, 10, 9, 8, 7 och 5 läggs in i ett binärt träd, i den ordningen. Rita upp hur trädet ser ut när talen är inlagda.

Uppgift 2 (1 p)

Talen 1, 2, 3, 4, 5, 6, 7, 8, 9 och 10 läggs in i ett binärt träd, i den ordningen. Rita upp hur trädet ser ut när talen är inlagda.

Uppgift 3 (1 p)

Man brukar ange tidskomplexiteten för olika algoritmer, till exempel att sökning i ett binärt träd är O(log n). Antag att variabeln a är en array med N element:
    double a[N];

a) Vi vill summera talen i arrayen a med de här programraderna:

    summa = 0;
    for (int i = 0; i < N; ++i)
        summa += a[i];
Vilken tidskomplexitet har den summeringen?

b) Vi provkör programmet med N = 1000, och ser att summeringen av arrayen a tar 1 sekund. Hur lång tid kan vi räkna med att summeringen tar om N är tio gånger större, dvs 10000?

c) Jämför datorn som vi använde i b-uppgiften med en vanlig, modern skrivbordsdator. Är datorn från b-uppgiften snabbare, ungefär lika snabb, eller långsammare?

Uppgift 4 (1 p)

Antag att variabeln m är en tredimensionell matris med NxNxN element:
    double m[N][N][N];

a) Vi vill summera talen i matrisen m, med de här programraderna:

    summa = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < N; ++k)
                summa += m[i][j][k];
Vilken tidskomplexitet har den summeringen?

b) Vi provkör programmet (på en annan dator) med N = 200, och ser att summeringen av matrisen m tar 1 sekund. Hur lång tid kan vi räkna med att den summeringen tar om N = 2000?

Uppgift 5 (1 p)

Vi skapar tre char-variabler:
    char c1 = 7, c2 = 3, c3 = 5;
Vilka värden har c1, c2 och c3 när följande satser körts?
    c1 = c2;
    c2 = c2 & 6;
    c3 |= 8;

Scenario till uppgift 6-8

Det finns ett spel som går ut på att man ger kommandon till en robot, som rör sig på en spelplan. Man kan beordra roboten att åka till en punkt på spelplanen. Punkter anges med en x- och en y-koordinat, i form av heltal. Roboten startar i origo, dvs punkten med x=0 och y=0. Med flera kommandon kan man få roboten att köra en bana:

Ett diagram över rörelserna

Vi ska hantera den här typen av banor i ett C-program.

Uppgift 6 (12 p)

Vi ska skapa den abstrakta datatypen MapPoint, som används för att representera punkter på en spelplan enligt scenariot.

Datatypen ska bestå av en posttyp ("struct") som innehåller x- och y-koordinaterna, och det ska finnas flera funktioner som arbetar med sådana kartpunkter:

a) (4p) Skriv (hela) include-filen MapPoint.h.

b) (6p) Skriv (hela) implementationsfilen MapPoint.c.

c) (2p) För att prova MapPoint-paketet skapar vi en main-funktion, i filen test_points.c, som gör följande:

Skriv (hela) filen test_points.c.

Uppgift 7 (15 p)

En bana eller rutt består av en lista med kartpunkter, som roboten har besökt. Vi ska nu skapa den abstrakta datatypen Route, som används för att representera robotens bana.

Datatypen ska lagra alla punkter (ett antal MapPoint) som roboten besökt i en länkad lista. Eftersom MapPoint-posterna själva inte innehåller några pekare, så kan det vara lämpligt att göra en ny datatyp, LinkPoint, som innehåller en MapPoint och en pekare till nästa LinkPoint.

Följande funktioner ska finnas:

a) (5p) Skriv (hela) include-filen Route.h.

b) (10p) Skriv (hela) implementationsfilen Route.c.

Uppgift 8 (8 p)

Ju längre robotens kört, desto långsammare går den. Det visar sig att det är funktionen has_visited som är problemet. När banan som roboten kört innehåller många punkter, måste funktionen has_visited söka igenom hela den länkade listan med punkter, och det blev alltså för långsamt. Därför behöver vi skapa en alternativ datastruktur, där det går snabbt att kolla om roboten besökt en viss punkt, även när rutten innehåller många tusen punkter.

Skapa därför den abstrakta datatypen PointSet, eller "mängd av kartpunkter", där det går snabbt att kolla om en viss punkt finns med i punktmängden. Förslagsvis används antingen ett binärt träd eller en hashtabell.

Följande funktioner ska finnas:

(Vi struntar i att göra någon cleanup_pointset, som skulle göra anrop till free.)

Några tips:

a) (3p) Skriv (hela) include-filen PointSet.h.

b) (5p) Skriv (hela) implementationsfilen PointSet.c.