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.
Alla äkta matkuponger har ett unikt nummer, som består av upp til tio siffror eller bokstäver. Det kan till exempel vara 251392 som på bilden. Andra exempel på kupongnummer är ABC123456R och KGX193.
På en fil finns numren på alla inlämnade matkuponger. Varje rad består av numret på en kupong, numret på den restaurang där den lämnades in, ett datum och ett klockslag. Exempel:
25132 2 2012-12-12 11:22:03 KGX193 1 2012-12-12 12:10:19 25132 1 2012-12-14 11:27:24 |
Det vi är intresserade av är att hitta om samma kupongnummer förekommer flera gånger. I exemplet ovan har två olika kuponger med numret 25132 lämnats in. Minst en av dem måste vara förfalskad!
Vi behöver ett program som läser filen med inlämnade kuponger, och som talar om vilka kupongnummer som förekommer mer än en gång. I exemplet ovan vill vi få en utmatning bestående av numret 25132.
Om flera olika kupongnummer förekommer flera gånger spelar ordningen mellan dem i utskriften ingen roll, men varje kupongnummer ska bara skrivas ut en gång.
| 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. |
Skriv ett program som först tar emot namnet på en textfil, antingen som ett kommandoradsargument eller genom att läsa in det. Textfilen ska innehålla rader enligt scenariot ovan. Därefter ska programmet läsa den angivna textfilen, och lista de kupongnummer som observerats mer än en gång.
Använd länkade listor eller arrayer. 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 en miljon olika kupongnummer,
och minst en miljon rader på filen.
Det finns inga krav på 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 alla observerade kupongnummer, och söker igenom den länkade listan eller den osorterade arrayen för varje ny kupongrad från filen, kan programmet bli mycket långsamt för stora filer (som testfil-1M.txt).
Gör en ny version av programmet i uppgift 1, där alla de observerade kupongnumren lagras i en hashtabell eller ett binärt träd. Vi vill ha en enorm förbättring av prestanda.
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 signaler och rader,
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. |