Exempel!

Programmeringsmetodik: Tentamen 2010-11-04

Det här är datortentan som går torsdag 4 november 2010 i kursen Programmeringsmetodik, kl 8:15-12:15. (Nej, det är det egentligen inte. Det är bara ett exempel!) Lokal: T120, och vid behov T124 och T117.

Ni ska inte anmäla er till tentan via den vanliga tentaanmälan, utan kom bara till datorsalarna. Tentatiden börjar klockan 08:15, men kom dit 08:00, så alla hinner få sina platser innan tentan börjar!

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

Ansvarig lärare är Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), telefon 070-73 47 013.

Instruktioner

  1. Normalt används Visual Studio på era vanliga datorkonton, men man kan också använda en egen bärbar dator, om man har nätuppkoppling på den.
  2. Skicka in lösningarna till mig (thomas.padron-mccarthy@oru.se) senast klockan 12:15. Spara också själv en kopia, ifall det blir något fel med posten!
  3. Använd C eller C++.
  4. Packa ihop hela katalogen med applikationen i en Zip-fil, och skicka den som en bilaga. Men döp först om Zip-filen från nånting.zip till exempelvis nånting.info för att överlista överambitiösa virusfilter.
    Spara också själv en kopia, ifall det blir något fel med posten!
  5. För att en lösning på en uppgift ska bli godkänd krävs att den fungerar (utom möjligen för vissa konstiga specialfall) och att den inte strider mot specifikationen.
  6. För betyget 3 respektive G krävs godkänt på uppgift 1. För betyget 4 respektive VG krävs godkänt på både uppgift 1 och 2. För betyget 5 krävs godkänt på uppgift 1, 2 och 3.
  7. Godkänt resultat på denna tentamen ger betyget 3, 4 eller 5 (respektive G eller VG) på teoridelen av kursen. Tillsammans med godkända inlämningsuppgifter ger godkänt resultat på den här tentan ett godkänt betyg på hela kursen. Betyget på hela kursen blir samma som på tentan.

Hjälpmedel vid tentamen

  1. Uppgiften ska lösas enskilt, dvs inga grupper av två eller flera studenter.
  2. Du får använda datorn, böcker och vilka andra hjälpmedel som helst, men du får inte samarbeta eller fråga någon (utom mig). Det är alltså tillåtet att söka med Google, eller på frågeforum som Stack Overflow, men det är inte tillåtet att posta egna frågor.
  3. Om du behöver fråga något, så kontakta läraren. Jag finns på plats i datorsalarna, och man kan också ringa mig (se mobilnumret ovan).

Scenario

(Jag har stulit det här scenariot från tentan 2009-08-20, med vissa ändringar. Till den riktiga tentan ska jag försöka hitta på ett nytt.)

Stålmannen har förklarat krig mot myggen, och nu flyger han världen runt och slår ihjäl mygg. Med hjälp av sin dator håller han reda på hur många myggor han slagit ihjäl, och var.

Stålmannen har en textfil som heter platser.txt, och som innehåller data om platser. Varje plats anges med en rad, bestående av tre tal: först ett (unikt) heltal som är platsens nummer, och sen platsens latitud och longitud:

17 59.2466 15.2448
3 59.2549 15.2463
421609 59.3326 18.0651
25 37.421987 -122.084067

och så vidare

Filen innehåller flera miljoner platser. Platsnumren är alltså unika, men det är inte säkert att de kommer i nummerordning i filen, eller att det inte finns luckor i numreringen. (Om det finns tre platser, kan de alltså ha numren 4711, 3000000000 och 17.)

Stålmannen har också en hel massa andra textfiler, där han skrivit upp data om de myggor han slagit ihjäl. Så här kan en sådan textfil se ut:

17 3
25 1
17 1
421609 47
17 2

och så vidare

Varje rad i en sådan textfil innehåller två heltal: ett platsnummer och ett myggantal. Enligt filen ovan har han först varit på plats 17 och slagit ihjäl 3 myggor. Sen flög han till plats 25 och slog ihjäl en ensam mygga. Därefter flög han tillbaka till plats 17, och dödade ännu en ensam mygga. Sen flög han till plats 421609 och slog ihjäl inte mindre än 47 myggor, innan han igen flög tillbaka till plats 17 och dödade 2 myggor.

Det finns flera tusen såna här filer, och varje fil kan innehålla flera miljoner rader med data om mosade myggor.

Dessutom fins en tredje fil, med namnet filer.txt, som innehåller namnen på alla textfilerna med data om dödade myggor. Varje rad innehåller ett filnamn:

mosade.txt
meramosade.txt
meramosade2.txt
meramosade2b.txt
onsdagsmosningar.txt
torsdagsmosningar.txt
extramos.txt

och så vidare

Det fanns ju flera tusen filer, och eftersom filen filer.txt innehåller en rad för varje fil, så innehåller den flera tusen rader.

Exempel!

1. Uppgift för betyget 3 respektive G

Lös denna uppgift först, och skicka in den. Spara också själv en kopia, ifall det blir något fel med posten! Börja inte med de andra uppgifterna innan du är klar med denna, och har skickat in den.

Skapa en abstrakt datatyp FileQueue, som är en kö av filnamn. Varje filnamn är en sträng. Kön ska vara implementerad som en länkad lista, och det ska inte finnas några onödiga begränsningar i kölängden. Det ska vara en länkad lista specifikt för detta ändamål, så använd inte någon generell datatyp (som std::list). Denna abstrakta datatyp ska implementeras som en modul med en .c- och en .h-fil. Följande funktioner ska finnas:

Skriv sedan en funktion som heter find_files, som läser filen filer.txt, och placerar alla filnamnen i den filen på en kö av typen FileQueue.

Skriv också en funktion som heter read_files, som går igenom kön, och som använder fopen och fclose för att först öppna och sen direkt stänga var och en av filerna på kön. Om den misslyckas med att öppna någon fil, ska ett felmeddelande skrivas ut, och programmet avslutas.

Skriv till sist ett huvudprogram, som:

  1. anropar find_files för att läsa filnamnen från filer.txt
  2. skriver ut hur många filnamn det var
  3. anropar read_files

Exempel!

2. Uppgift för betyget 4 respektive VG

Lös först uppgift 1, och skicka in den. Därefter kan du lösa, och skicka in, den här uppgiften. Spara också själv en kopia, ifall det blir något fel med posten! Börja inte med uppgift 3 innan du är klar med denna, och har skickat in den.

Nu ska vi göra ett program som talar om vilken plats som Stålmannen sammanlagt slagit ihjäl flest myggor på. Programmet ska skriva ut den platsens nummer, latitud och longitud. Man måste alltså på något sätt summera ihop antalet dödade myggor för varje plats, och sen välja ut den plats som har högst summa. Om det är flera platser som delar på förstaplatsen, dvs har samma summa av dödade myggor, spelar det ingen roll vilken av dem man skriver ut.

Utgå från programmet i uppgift 1, som skapar en kö med alla filerna med mosningsdata, och sen betar av den kön.

Om man väljer olämpliga datastrukturer, till exempel osorterade länkade listor, kan det ta mycket lång tid att köra programmet med de stora datamängder som det handlar om. Välj därför datastrukturer så att programmet går att köra på en normal, modern dator utan att ta orimligt lång tid, och utan att krascha på grund av minnesbrist.

Datstrukturerna som används ska bara skapade specifikt för detta ändamål, så använd inte någon generell datatyp.

Exempel!

3. Uppgift för betyget 5

Lös först uppgift 1 och 2, och skicka in dem. Därefter kan du lösa, och skicka in, den här uppgiften. Spara också själv en kopia, ifall det blir något fel med posten!

I uppgift 1 skapade vi en kö av filnamn. Nu ska vi göra om den med hjälp av en generell datatyp.

Skapa först den generella länkade listan GenericQueue, som är en kötyp som kan användas för olika datatyper. Välj själv metod för att skapa en generell datatyp. Kön ska även nu lagras som en länkad lista.

Använd därefter GenericQueue för att skapa kön av filnamn.

Den här sista-uppgiften för betyget 5 kanske kan ta lite längre tid att lösa. Om den inte är helt klar när tentatiden tar slut, är det därför tillåtet att skicka in en preliminär lösning, som man sedan kan komplettera. Ange tydligt att det är en preliminär lösning. Kompletteringen ska skickas in senast en vecka efter tentan.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 19 oktober 2010