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



Tentamen i

Programmeringsmetodik

för D2, SDU2 m fl

torsdag 19 augusti 2010

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 torsdag 9 september 2010.
Återlämning av tentor: Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning i L1506, måndag till torsdag kl 10-14.
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, 100, 10, 1000 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 2 (3 p)

a) (1p) Vad innebär kollisioner i samband med hashtabeller?

b) (1p) Beskriv något sätt att hantera kollisioner.

c) (1p) En hashtabell har storleken 10 och hashfunktionen h(k) = k mod 10. (C-programmerare kanske hellre skulle skriva den som h(k) = k % 10.) För att hantera kollisioner används metoden från deluppgift b. Talen 1, 100, 10, 1000 och -10 läggs in i hashtabellen, i den ordningen. Rita upp hur hashtabellen ser ut när talen är inlagda.

Uppgift 3 (5 p)

Man brukar ange tidskomplexiteten för olika algoritmer. Till exempel har sökning i ett binärt träd tidskomplexiteten O(log n), där n är antalet noder i trädet. Antag att variabeln m är en matris med N gånger N element:
    int m[N][N];

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

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

b) Vi provkör matrissummeringen i deluppgift a med N = 1000000 (en miljon), och ser att summeringen av matrisen m tar 1 sekund. Hur lång tid kan vi räkna med att summeringen tar om N är tre gånger så stor, dvs 3000000 (tre miljoner)?

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?

d) Nu vill vi i stället summera talen i diagonalen i matrisen m:

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

e) Vi provkör diagonal-summeringen i deluppgift d med N = 1000000 (en miljon), på en annan dator än den i b-uppgiften, och ser att summeringen av matrisen m tar 1 sekund. Hur lång tid kan vi räkna med att summeringen tar om N är tre gånger så stor, dvs 3000000 (tre miljoner)?

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

g) Får matrisen m plats i minnet på en vanlig, modern skrivbordsdator, när N = 1000000 (en miljon)? (Motivera svaret.)

Uppgift 4 (4 p)

De åtta minst signifikanta bitarna i heltalsvariabeln g används för att styra åtta julgransljus i en julgran. En bit som är satt till ett betyder ett tänt ljus, och en bit som är satt till noll betyder ett släckt ljus. Julgransljusen numreras från 1 (styrs av minst signifikanta biten) och uppåt.

Vi kan tända alla åtta ljusen så här:

    g = 255; // 255 har bitmönstret 1111 1111
Vi kan släcka alla åtta ljusen så här:
    g = 0; // 0 har förstås bitmönstret 0000 0000
Vi kan tända enbart ljus nummer 1 och 3 så här:
    g = 5; // 5 har bitmönstret 0000 0101

Skriv C-kod för följande:

a) Tänd alla ljus utom nummer 1, som ska vara släckt.

b) Tänd ljus nummer 2, utan att påverka de andra ljusen.

c) Släck ljus nummer 3, utan att påverka de andra ljusen.

d) Heltalsvariabeln ljusnummer innehåller numret på ett ljus (1 till 8). Tänd det ljuset, utan att påverka de andra ljusen.

Scenario till uppgift 5-7

Rymdpolisen har till uppgift att patrullera rymden. Då och då får de ett larm från någon planet i galaxen, och rycker ut med sina rymdskepp.

Ett polisrymdskepp under utryckning

Rymdpolisen skriver upp sina utryckningar i en fil, utryckningar.txt. Varje rad i filen bekriver en utryckning, och består av ett datum, ett klockslag, namnet på den planet som utryckningen gällde, samt vad det handlade om. Exempel:

2210-08-12 18:04 Saturnus Fortkörning
2210-08-12 18:07 Glorbatron Inbrott
2210-08-13 01:33 Saturnus Bråkiga rymdmonster
2210-08-13 02:19 Zoflomork Fortkörning

För att spara bensin till rymdskeppen vill rymdpolisen upprätta en lokal polisstation på den mest brottsbelastade planeten. Vi ska därför skriva ett program som läser filen utryckningar.txt, räknar antalet utryckningar till varje planet, och till sist talar om vilken planet som hade flest utryckningar.

I exemplet ovan har vi haft två utryckningar till planeten Saturnus, och en var till planeterna Glorbatron och Zoflomork. Det är alltså Saturnus som är den mest brottsbelastade planeten.

Planetnamn består av ett enda ord. Planeternas namn är unika. Det finns flera miljoner planeter. Filen innehåller flera miljarder utryckningar.

Uppgift 5 (10 p)

Först ska vi lagra planeterna i en osorterad länkad lista. Varje länk i listan består av en planet-post (en "struct") med ett planetnamn och ett tal som anger antalet utryckningar.

Så här kan man göra:

Skriv programmet, antingen i C eller C++.

Programkoden ska vara tydligt och lättbegriplig, men du behöver inte dela upp programmet i filer och abstrakta datatyper. Ett tips är dock att strukturera programmet så att delar av det enkelt kan återanvändas i uppgiften nedan.

Uppgift 6 (13 p)

Rymdpatrullen har inte råd med nya datorer, så deras program körs på en riktigt gammal maskin, från år 2010. Programmet med den länkade listan i uppgiften ovan kommer att ta månader att köra. Så länge har rymdpatrullen inte tid att vänta!

Skriv ett nytt program (i C eller C++) som gör samma sak, men välj nu datastrukturer som gör att programkörningen går rimligt fort.

Programkoden ska vara tydligt och lättbegriplig, men du behöver inte dela upp programmet i filer och abstrakta datatyper. Du får återanvända delar av programmet från uppgiften ovan, utan att skriva samma programkod igen.

Uppgift 7 (4 p)

Vi antar att det ursprungligen fanns 3 miljarder utryckningar på filen utryckningar.txt, fördelade på 4 miljoner planeter. Då tar ditt program från uppgift 5 (det med länkade listor) tiden T5 att köra, och ditt program från uppgift 6 (det med bättre datastrukturer) tar tiden T6 att köra.

a) Hur lång tid tar ditt program från uppgift 5 (det med länkade listor) att köra, om antalet utryckningar fördubblas från 3 miljarder till 6 miljarder, men antalet planeter är oförändrat 4 miljoner?

b) Hur lång tid tar ditt program från uppgift 5 (det med länkade listor) att köra, om i stället antalet planeter fördubblas från 4 miljoner till 8 miljoner, men antalet utryckningar är oförändrat 3 miljarder?

c) Hur lång tid tar ditt program från uppgift 6 (det med bättre datastrukturer) att köra, om antalet utryckningar fördubblas från 3 miljarder till 6 miljarder, men antalet planeter är oförändrat 4 miljoner?

d) Hur lång tid tar ditt program från uppgift 6 (det med bättre datastrukturer) att köra, om antalet planeter fördubblas från 4 miljoner till 8 miljoner, men antalet utryckningar är oförändrat 3 miljarder?

Förklara kort hur du räknat eller resonerat.