Gäller som tentamen för:
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.
Olle Olsson Grums Bengt Larsson Säffle Olle Olsson Säffle Bengt Larsson Säffle Bengt Larsson Säffle Olle Olsson Grums |
Varje personuppgift består av två rader: först namnet på personen, och sedan personens hemort.
Filen ovan innehåller tolv rader, med sex personuppgifter om tre olika personer. Bengt Larsson i Säffle förekommer tre gånger, Olle Olsson i Grums förekommer två gånger, och Olle Olsson i Säffle en gång.
Ett visst namn på en viss ort identifierar en person unikt. Däremot kan det finnas flera personer med samma namn men som har olika hemorter.
Inget person- eller ortnamn är längre än 100 tecken.
| 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 personuppgifter enligt scenariot ovan. Därefter ska programmet läsa den angivna textfilen, och tala om vilken person som förekom flest gånger, och även hur många gånger det var.
Med exempelfilen ovan, testfil-6.txt, ska programmet alltså svara att Bengt Larsson i Säffle förekom oftast, nämligen 3 gånger.
Programmet måste kunna hantera godtyckligt många personer och personuppgifter, bara med de begränsningar som följer av minnesstorleken. Det finns inga krav på felhantering.
Programmet behöver lagra de unika personerna. Använd en länkad lista eller kanske en dynamisk array. (En fast array är olämplig, eftersom den har en begränsad storlek.) 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.
Några exempelfiler som man kan provköra med (filerna är textfiler i Windows-format):
| 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. |
Med stora filer, som exempelfilen testfil-1M.txt, blir lösningen med länkade listor (eller en osorterad dynamisk array) mycket långsam.
Gör en ny version av programmet i uppgift 1, men med snabbare datastrukturer. 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.
| 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 hashtabellen GenericHashTable). 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. |