1. a) Falskt. Jämförelseoperatorn "== kontrollerar om det är samma objekt medans equals är en överskuggningsbar metod som i regel kontrollerar att objekten är exakt likadana. b) Falskt. Om trädet är mycket glest tar enn arrayrepresentation upp onödigt mycket extra minne, jämfört med en representation med länkade noder. c) Sant, detta är definitionen av Theta d) Falskt, det största talet befinner sig alltid längst till höger i trädet (detta kan ibland vara roten, dock). e) Falskt. En stabil sorteringsalgoritm garanterar att element med samma värde ej byter plats innebördes. f) Sant. Interfaces fungerar som abstrakta klasser med endast abstrakta metoder. 2. a) 78 / \ / \ 19 89 / \ 18 61 / 27 / \ 22 42 b) * Inte fullständigt eftersom trädet saknar noder på flera nivåer * Inte heapsorterat eftesrom till exempel varken det minsta eller största värdet ligger i roten * Inte fullt eftersom nod 65 endast hat ett barn 3. Denna uppgift har flera accepterbara svar. Poäng ges efter hur väl svaret är motiverat. a) Datastrukturen som behövs behöver ha följande metoder: addMovie och removeOldest. En priorieteskö eller kö kan vara lämplig. Om man tar med i beräkningen att ett elements nyckel kan komma att ändras (då Erik ser på en film) följer dock ett problem i både prioritetskön och kön, vilket försvårar valet. Klassiskt går det med ovanstående datatrukturer endast att ta ut element med hjälp av upprepade anrop till dequeue respektive removeMin, vilket gör proceduren besvärande omständig. Om kön är representerad som en lista är det dock möjligt att implementera en ytterligare metod remove(key), vilket dock gör kön mer lik en ADT Lista. ADT ----------- | addMovie | removeOldest | changeKey..| Prioritetskö | 1* | logn | nlogn | Kö | 1 | 1 | n | Sorterad lista | 1 | 1 | n | *antagande: filmen är nyligen sedd, så ingen bubbling sker Om man inte gör antagandet att filmen alltid är just sedd när den läggs in i kollektionen är Kö olämplig. Om man dessutom gör antagandet att värdenas nyckel inte ändras blir Prioritetskö det bästa valet. b) Se extern bild c) Misstag 1. Kravet radixsort har på sin sorteringsalgoritm är att den är stabil, vilket inte quicksort uppfyller. Misstag 2. Filmerna ligger inte i en array eller en osorterad lista, utan i en heap. Det kan vi dra nytta av genom att använda heapsort. Algoritmen blir som följer: 1. använd removeOldestAccess() upprepade gånger för att få fram en lista sorterad på när filmen sågs senast (dvs heapsort). 2 Sortera denna lista med någon stabil sorteringsalgoritm, till exempel insertionsort. 4. I bästafallet finns bara högerbarn i trädet, det vill säga minsta värdet är i roten. Algoritmen blir som följer: 1 Hitta noden att ta bort: O(1) (finns i roten) 2 Hitta en ersättare och ersätt: O(1) (ersätt med dess högra barn eftersom vänsterbarn inte finns) 3 Lägg in i en lista: O(1) Detta upprepas en gång för varje element, så komplexiteten blir (O(1) + O(1) +O(1))*O(n) = O(n) I värstafallet finns bara vänsterbarn i trädet, det vill säga det minsta värdet är längst ned i trädet. Algoritmen blir som följer: 1 Hitta noden att ta bort; O(n) (måste söka igenom n noder) 2 Hitta en ersättare och ersätt: O(1) (inga barn, så ersättningen skippas) 3 Lägg in i en lista: O(1) Detta upprepas en gång för varje element, så komplexiteten blir (O(n) + O(1) + O(1))*O(n) = O(n^2) Sammafattat: Bästafall: O(n), Värstafall: O(n^2)