Gäller som tentamen för:
DT2020 Datateknik B, Programmeringsmetodik, provkod 0100
DT2022 Datateknik B, Tillämpad datavetenskap, provkod 0110
DT2011 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.
| Bilar | |||
|---|---|---|---|
| Bilnummer | Märke | Årsmodell | |
| RFN540 | Renault | 1999 | |
| PXT158 | Citroen | 2010 | |
| JHR109 | Citroen | 2008 | |
| Svampar | |||
|---|---|---|---|
| Svampnummer | Art | Vikt | Bil |
| 1 | kantarell | 0.79 | PXT158 |
| 2 | fotsvamp | 1.03 | JHR109 |
| 3 | kantarell | 1.03 | PXT158 |
Bilnummer och svampnummer är unika. För varje svamp anges vilken bil den finns i. Alla bilnummer, bilmärken och svamparter består av ett enda ord utan mellanslag.
Nu har vi tyvärr ingen databas med tabeller, utan vi får nöja oss med textfiler. Vi har en textfil som innehåller data om alla bilar, med en bil på varje rad:
RFN540 Renault 1999 PXT158 Citroen 2010 JHR109 Citroen 2008 |
Vi har också en textfil som innehåller data om alla svampar, med en svamp på varje rad:
1 kantarell 0.79 PXT158 2 fotsvamp 1.03 JHR109 3 kantarell 1.03 PXT158 |
| 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. |
Vilken bil innehåller den största sammanlagda vikten av svamp? I exemplet från scenariot är det PXT158, som innehåller 1.82 kilo svamp. Skriv ett program som räknar ut detta, och skriver ut registreringsnumret på bilen. Om det är flera bilar som har den högsta vikten, spelar det ingen roll vilken av dem som skrivs ut.
Använd länkade listor eller arrayer för de data som behöver lagras i programmet. Det ska vara datastrukturer gjorda specifikt för detta ändamål, så använd inte någon generell datatyp som till exempel std::list. Man får, men behöver inte, dela upp programmet i flera filer.
Övriga krav på lösningen:
Programmet måste kunna hantera minst tusen bilar och tusen svampar.
Det finns inga särskilda krav på prestanda eller felhantering.
| 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. |
Om man använder en länkad lista eller en osorterad array för att lagra data, kan programmet bli mycket långsamt för stora datamängder.
Gör en ny version av programmet i uppgift 1, men med datastrukturer som valts för att ge bättre prestanda. Även med miljoner bilar och miljoner svampar ska programmet ge svaret på sekunder, eller i värsta fall kanske någon minut.
Datastrukturerna som används ska vara skapade specifikt för detta ändamål, så använd inte någon generell datatyp. Man får, men behöver inte, dela upp programmet i flera filer.
Övriga krav på lösningen:
Programmet måste kunna hantera godtyckligt många bilar och svampar,
bara med de begränsningar som följer av minnesstorleken.
Det finns inga krav på felhantering.
| 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! |
Gör om uppgift 2 med hjälp av en generell datatyp.
Skapa först den generella datatypen (till exempel trädtypen GenericTree). Välj själv metod för att skapa en generell datatyp. Dela upp på lämpliga filer. Det är inte förbjudet att inspireras av existerande lösningar, men du ska lämna in en som du gjort själv.
Använd den därefter i programmet.
| 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. |