Sist endret: 23.09.2016  
 

Løsningsforslag - Rotfaste trestrukturer

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 02.10.2017 15:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på Piazza.

Oppgave 1

[ riktig ]a) Dersom man allerede har laget en heap av tallene som skal sorteres, kan man sortere med Heapsort i $O(n)$ kjøretid. (11.1 %)

Sant
Usant

Din kommentar:
LF-forklaring: Heap-konstruksjon er $O(n)$. Det er selve sorteringen som tar $O(n lg n)$ tid.

[ riktig ]b) I en heap har du en node med indeks 6. Hva er indeksen til foreldrenoden? (11.1 %)

2
3
5
8
12

Din kommentar:
LF-forklaring: Foreldrenoden til en node har indeks floor(i/2).

[ riktig ]c) I en heap har du en node med indeks 4. Hva er indeksen til de to barnenodene? (11.1 %)

2 og 3
4 og 6
5 og 6
7 og 8
8 og 9

Din kommentar:
LF-forklaring: Barnenodene har index 2i og 2i+1.

[ riktig ]d) Hvilke av disse tilfredsstiller kravene til en max-heap? (11.1 %)

A og B
A og C
A og D
B og C
B og D
C og D
Alle
Ingen

Din kommentar:
LF-forklaring: A og C er ikke max-heaper siden 8 < 9.

[ riktig ]e) Hvis vi har en heap som ser slik ut, hvordan ser da listen som representerer heapen ut etter at vi har kjørt fire iterasjoner av heapsort? (11.1 %)

21, 14, 12, 11, 9, 8, 4
11, 8, 9, 4, 12, 14, 21
11, 9, 4, 8, 12, 14, 21
9, 8, 4, 11, 12, 14, 21

Din kommentar:
LF-forklaring:

[ riktig ]f) Er heapsort en stabil sorteringsalgoritme? (11.1 %)

Ja
Nei

Din kommentar:
LF-forklaring: Hvis vi har heapen [2a, 2b, 1] og kjører Heapsort vil vi få returnert [1, 2b, 2a] (tegn opp og se!)

[ riktig ]g) Hva er den såkalte heap-egenskapen ved en max-heap? (11.1 %)

Verdien til en node er alltid størreenn eller lik enn verdiene til barnenodene
Verdien til en node er alltid mindre enn eller lik enn verdiene til barnenodene
Verdien til en barnenode er større hvis den er til venstre for barnenoden
Verdien til en barnenode er mindre hvis den er til venstre for barnenoden

Din kommentar:
LF-forklaring:

[ feil ]h) Hvis du setter verdiene 1, 2, 9, 5, 10, 7, 6, 4, 8 og 3 inn i et tomt binærsøketre (e?n etter e?n, i oppgitt rekkefølge), hva blir høyden til treet (antall kanter i den lengste stien fra rota til en løvnode)? (11.1 %)

5
6
7
8

Din kommentar:
LF-forklaring:

[ feil ]i) Hvis du setter verdiene 1, 2, 9, 5, 10, 7, 6, 4, 8 og 3 inn i en tom binær min-heap (e?n etter e?n, oppgitte rekkefølge), hva blir høyden til heapen (antall kanter i den lengste stien fra rota til en løvnode)? (11.1 %)

2
3
4
5

Din kommentar:
LF-forklaring: Høyden i en binær min-heap er bare avhengig av antallet verdier, og er floor(lg n) = floor(lg 10) = 3.