• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Lös bara en uppgift per blad. Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
• Skriv gärna förklaringar om hur du tänkt! Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Uppgift 1 (10 p)

1
Olle Karlsson
Strutsvägen 7, 640 50 Garphammar
42
4
Svea Svensson
Granvägen 319, 702 21 Örebro
39
3
Lisa Karlsson
Strutsvägen 7, 640 50 Garphammar
41

och så vidare

Som vi kan se står varje uppgift på en egen rad, så varje person upptar fyra rader i filen. Numret och skonumret är heltal. Såväl namnet som adressen kan innehålla högst 40 tecken.

Skriv ett C-program som läser filen, och lagrar alla personernas data i en länkad lista av poster (eller "structar", som man också kan säga). Programmet ska fråga användaren efter ett skonummer, och sen ska det skriva alla personer med det skonumret på en ny fil, som ska heta utvalda.txt. Den nya filen ska ha samma format som den ursprungliga.

Uppgift 2 (10 p)

• En posttyp ("struct") som heter Bok. och som innehåller bokens titel, författare och ISBN-nummer.
• En funktion som heter las_bok, och som läser in data om en bok till en sådan post. Inläsningen sker från standardinmatningen, som normalt är kopplad till tangentbordet.
• En funktion som heter skriv_bok, och som skriver ut en bokpost. Utskriften sker på standardutmatningen, som normalt hamnar i ett fönster på skärmen.

a) Skriv (hela) header-filen bok.h, som innehåller en definition av posttypen, och deklarationer av funktionerna.

b) Skriv (hela) filen bok.c, som innehåller funktionernas definitioner, dvs "funktionskropparna" med programkod.

c) Skriv (hela) filen bokmain.c, som innehåller en enkel main-funktion som använder sig av bokpaketet ovan. Den main-funktionen ska ha en variabel av typen Bok, den ska läsa in data till den med hjälp av las_bok, och den ska skriva ut den med hjälp av skriv_bok.

Uppgift 3 (20 p)

SCB lagrar alla årsinkomsterna i en binärfil med heltal av typen int. Det finns drygt sex miljarder människor på jorden, så filen kommer att innehålla mer än sex miljarder heltal, ett för varje människa på jorden. Filen heter inkomster.bin. Inkomsterna anges i kronor.

Nu vill vi veta typvärdet för årsinkomsten, alltså vilken av årsinkomsterna som förekommer flest gånger i filen. Skriv ett C-program som ska räkna ut det!

Gör hur du vill!

Tips: Du behöver någon form av datastruktur som kan hålla reda på inkomsterna, och för varje inkomst även antalet förekomster. Det kommer att finnas sammanlagt mer än sex miljarder förekomster, men bara några miljoner olika inkomster.

Men!

För full poäng på uppgiften krävs att programmet har acceptabla prestanda. Ett program som lagrar inkomsterna i poster, med antal kronor och antal förekomster i varje post, och sen placerar de posterna i en osorterad länkad lista, kommer att behöva flera år på sig för att köra klart, även på en modern och snabb dator. För varje inkomst som programmet läser från filen, måste det nämligen söka igenom den länkade listan, och efter ett tag blir den listan flera miljoner steg lång. Moderna datorer är snabba, och kan faktiskt stega igenom en länkad lista med flera miljoner steg utan att användaren ens hinner märka det, men här ska den göra det sex miljarder gånger. Då tar det lång tid.

En bra lösning kräver därför en snabbare datastruktur, till exempel ett binärt träd eller en hashtabell.