Övning 1: Pythonuppgifter, abstrakta datatyper
- Pythons dokumentation: string och list
- Abstrakt datatyp för temperatur
- Stack implementerad med länkad lista
- Tentafrågor på olika betygsnivå
Pythons dokumentation: string och list
Mål: Pythons inbyggda datastrukturer - öva på att läsa dokumentationen.
Slå upp string Links to an external site. i Pythons dokumentation, och svara på följande frågor:
- Vad har capitalize för parametrar och returvärden?
- Vad har count för parametrar och returvärden?
- Vad gör metoden split? Vilken datatyp returneras? Visa med ett eget exempel.
- Vad gör metoden strip?
- Finns det någon metod här som inte har returvärde?
Slå upp list Links to an external site. i Pythons dokumentation, och svara på följande frågor:
- Vad har append för parametrar och returvärden?
- Vad är skillnaden mellan append, extend och insert?
- Vad är skillnaden mellan remove och pop?
- Läs om copy. Vad menas med "shallow copy"?
- Finns det någon metod här som inte har returvärde? Jämför med strängmetoderna och förklara skillnaden.
Länkad lista
Mål: Förstå hur en länkad lista fungerar i detalj.
Med en nodklass kan vi skapa datastrukturen länkad lista.class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
För varje uppgift nedan, rita en bild som visar hur det ser ut när man...
- ...lägger in en ny nod i en tom lista.
- ...lägger in en ny nod sist i en lista med en nod.
- ...lägger in en ny nod först i en lista med en nod.
- ...tar bort den första noden från en lista med två noder.
- ...tar bort den sista noden från en lista med två noder.
Skriv också upp vilka satser (pekartilldelningar) som ska utföras i vart och ett av fallen.
Jämför med din bänkkompis, och kontrollera att satserna stämmer med era bilder.
Linus lösning, s 1 (Länkar till en externa sida.)
Knepiga listor, uppgift 5 tenta 2005-12-05 (Länkar till en externa sida.) från kursen DD1321 tilpro
Beta försöker lära sig hantera länkade listor under lovet. Det är inte lätt. Givet följande listor
p -> A -> B -> C -> D
q -> E -> F -> G
a) Hur ser listan/listorna ut efter följande rader kod?
z = p.next
p.next = q.next
z.next.next = p
q = p = z
b) Hur skulle det ha sett ut om man istället skrivit följande rader kod?
p.next.next.next = q.next.next
q.next = p
p = q
En kö implementerad med länkad lista
Metoden enqueue ska lägga in ett nytt element i listan.
- Var ska det nya elementet in?
- Vilka pekare ska ändras?
- Spelar det roll i vilken ordning man gör saker?
Metoden dequeue ska plocka ut ett element från listan.
- Vilket element ska tas ut?
- Vilka pekare ska ändras?
- Spelar det roll i vilken ordning man gör saker?
Abstrakt datatyp för temperatur (diskutera först vilka attribut och metoder som behövs, skriv sedan koden)
Mål: Öva på abstraktion, repetera klasser.
I kursen ska ni själva implementera datastrukturer, oftast genom att skriva egna klasser i Python. Här är ett exempel.
Temperatur kan anges i olika skalor. En abstrakt datatyp minskar risken för missförstånd. Konstruera en klass Temp som representerar en temperatur.
Testa klassen i ett program som läser in utomhustemperaturen (Celsius) och skriver ut temperaturen så att en amerikan förstår (Fahrenheit).
Svara sedan på följande frågor:
- Vad är relationen mellan en klass och ett objekt?
- Om du skulle skriva dokumentation för klassen - vad är viktigt att ta med?
Tentauppgifter
Mål: Veta hur tentans E-, C-, och A-uppgifter skiljer sig åt. Kunna lösa uppgifter på olika betygsnivå.
Betygskriterier - sammanfattning
- För betyg E ska man kunna avgöra vilken algoritm som löser ett givet problem, kunna beskriva algoritmen och demonstrera den steg för steg med givna data, samt implementera den. Motsvarande gäller för datastrukturer.
- För betyg C ska kraven för betyg E vara uppfyllda, och dessutom ska man kunna jämföra algoritmer och datastrukturer och bedöma dessas lämplighet för ett givet problem. Här ställs också krav på tidsplanering. Se tidsgränser för aktuell kursomgång under Laborationer.
- För betyg A ska kraven för betyg C vara uppfyllda, och man ska dessutom kunna modifiera/kombinera algoritmer och datastrukturer för att lösa nya problem. Här ställs också höga krav på tydlighet i algoritmbeskrivningar.
- Cykeltentan 2014-10-24, uppgift 4 (betyg E)
Cyklisterna köar vid övergångsstället nere vid Valhallavägen. Först i kön står Linda, sen Alexander, sen Robert och sist Marko.
Kön är implementerad med en länkad lista. Rita bilder som visar hur det ser ut i detalj (varje steg) när man sätter in respektive plockar ut ett element ur kön.
- Alien-tentan 2015-03-20, uppgift 6 (betyg E/C)
En norrskensentusiast vill lagra bilder på norrsken. Vad finns det för fördelar respektive nackdelar med en vektor respektive en länkad lista när det gäller
- åtkomst
- insättning
- borttagning
Svara med en tabell med tre rader.
- Japantentan 2007-10-24, uppgift 5 (betyg A)
Våra datorer läser texter radvis, från vänster till höger. Men japansk text står i kolumner uppifrån och ner, som läses från höger till vänster.
Ge en algoritm för att med hjälp av en abstrakt kö eller stack ordna om en japansk text om m kolumner och n rader.Exempel:
7 4 1
8 5 2
9 6 3
läses in som 7 4 1 8 5 2 9 6 3, men vi vill ha ordningen 1 2 3 4 5 6 7 8 9.Du kan förutsätta att alla kolumner och rader är helt fyllda, men antalet kolumner, m, behöver inte vara detsamma som antal rader, n. Till exempel kan det finnas fem rader men bara tre kolumner. Visa sedan hur din algoritm fungerar för exemplet ovan. Utred till sist vilken komplexitet din algoritm har!