• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Prioritet och associativitet hos operatorerna i C

Uppgift 1 (1 p)

Uppgift 2 (1 p)

Uppgift 3 (1 p)

    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];

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)

    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];

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)

    char c1 = 7, c2 = 3, c3 = 5;

    c1 = c2;
    c2 = c2 & 6;
    c3 |= 8;

Scenario till uppgift 6-8

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

Uppgift 6 (12 p)

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:

• init_point, som initierar en MapPoint-post. Man skickar med x- och y-värdet till funktionen.
• save_point, som sparar MapPoint-post på en öppen textfil. Man skickar med en FILE*, och en post.
• fetch_point, som läser in en MapPoint-post från en öppen textfil. Man skickar med en FILE*.
• same_point, som jämför två MapPoint-poster och returnerar ett sant värde om de är lika.

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:

• Skapar de två kartpunkterna (x=3, y=1) och (x=4, y=7), med hjälp av funktionen init_point.
• Anropar same_point för att se om de är lika, och kontrollerar att den faktiskt returnerar ett falskt värde som den ska.

Uppgift 7 (15 p)

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:

• init_route, som initierar en Route-post så den innehåller en tom lista med punkter.
• append_point, som lägger till en kartpunkt i slutet av rutten.
• save_route, som sparar en komplett rutt på en öppen textfil. Anropa gärna funktionen save_point.
• fetch_route som läser in en komplett rutt från en öppen textfil. Anropa gärna funktionen fetch_point.
• has_visited, som tar två argument, en rutt och en kartpunkt, och som kollar om den kartpunkten redan finns med i den rutten. Anropa gärna funktionen same_point.
• cleanup_route, som avallokerar hela den länkade listan som representerar rutten genom att göra de anrop till free som behövs.

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

Uppgift 8 (8 p)

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:

• init_pointset, som initierar ett PointSet så det innehåller en tom mängd
• add_point, som lägger till en ny punkt till en punktmängd
• is_member, som ersätter den gamla has_visited

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

Några tips:

• Om man använder ett binärt träd, behöver man kunna jämföra två punkter för att se vilken som är "minst". Annars kan man inte sortera in punkterna i trädet. Ett enkelt sätt är att först jämföra x-koordinaterna, och om de är lika så jämför man y-koordinaterna. Punkten (x=3, y=100) är alltså mindre än punkten (x=4, y=7), och punkten (x=3, y=100) är mindre än punkten (x=3, y=101).
• Om man använder en hashtabell, behöver man en hashfunktion för punkterna. En enkel hashfunktion är att addera x-värdet och y-värdet, och sen ta den summan modulo hashtabellens storlek.

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

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