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



Tentamen i

Programmeringsmetodik

för D2, SDU2 m fl

lördag 13 december 2008 kl 14:00 - 18: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 lördag 3 januari 2009.
Återlämning av tentor: Efter att resultatet meddelats 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)

Följande namn läggs in i ett binärt sökträd, i den här ordningen:
Nixon, Ford, Carter, Reagan, Clinton, Bush, Obama
Den jämförelsefunktion som används är vanlig bokstavsordning.
Rita upp hur trädet ser ut när namnen är inlagda.

Uppgift 2 (1 p)

Samma namn som i uppgiften ovan, i samma ordning, läggs in i en osorterad enkellänkad länkad lista, där nya element läggs till i slutet. Rita upp hur listan ser ut när namnen är inlagda.

Uppgift 3 (1 p)

Följande tal läggs in i en hashtabell, i den här ordningen:
664, 116, 780, 1000, 850, 566, 64, 492, 249, 31
Hashtabellen har 10 positioner. Som hashfunktion använder vi h(x) = x mod 10. (C-programmerare kanske hellre skulle skriva den som h(x) = x % 10.) Kollisioner hanteras med länkade listor.
Rita upp hur hashtabellen ser ut när talen är inlagda.

Uppgift 4 (2 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 m är en tredimensionell matris med NxNx7 flyttal:
    float m[N][N][7];

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 < 7; ++k)
                summa += m[i][j][k];
Vilken tidskomplexitet har den summeringen?

b) Vi provkör programmet med N = 1000. och ser att summeringen av matrisen m tar 5 sekunder. Hur lång tid kan vi räkna med att den summeringen tar om N = 2000?

c) Hur lång tid kan vi räkna med att summeringen tar om N = 1 miljon?

Uppgift 5 (1 p)

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

Scenario till uppgift 6 och 7

Det finns ett spel som går ut på att man placerar ut robotar på en spelplan. Här har vi till exempel placerat ut roboten C3PO i punkten med koordinaterna (x=1, y=2), roboten R2-D2 i punkten (x=2, y=4), och så vidare. Koordinaterna är heltal.

Ett diagram över robotar och deras positioner

Vi ska hantera robotar och spelplaner i ett C-program.

Uppgift 6 (15 p)

Vi ska skapa den abstrakta datatypen Robot, som används för att representera robotar enligt scenariot.

Datatypen ska bestå av en posttyp ("struct") som innehåller x- och y-koordinaterna, och dessutom ett namn på roboten. Namn är textsträngar som kan vara högst 10 tecken långa.

(Beroende på hur man väljer att göra funktionerna, kan man behöva skicka med fler parametrar än de angivna.)

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

b) (8p) Skriv (hela) implementationsfilen Robot.c.

c) (3p) För att provköra Robot-paketet skapar vi ett program, på filen test_robots.c, som gör följande:

Skriv (hela) filen test_robots.c.

Uppgift 7 (19 p)

En spelplan är helt enkelt en samling robotar, med olika (eller, om de krockat, samma) koordinater. Vi ska nu skapa den abstrakta datatypen Board, som används för att representera en spelplan.

Välj själv hur spelplanen ska lagras. Det ska gå att skriva följande funktioner, som ska finnas med:

Några krav på implementationen:

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

b) (8p) Skriv (hela) implementationsfilen Board.c.

c) (4p) För att provköra Board-paketet skapar vi ett program, på filen test_board.c, som först skapar en tom spelplan, och sen läser in hundra robotar från filen robots.txt med hjälp av funktionen fetch_robot, och också placerar ut var och en av dem på spelplanen med funktionen put_robot. Som avslutning ska funktionen walk_robots anropas en gång.

d) (3p) Vilken tidskomplexitet har de tre funktionerna find_robot, put_robot och walk_robots? Vad händer om vi vill placera ut flera miljoner robotar? Skulle din lösning behöva ändras, och i så fall hur?