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.
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:
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:
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:
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!
| 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:
Exempel!
| 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!
| 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. |