Sist endret: 23.09.2016  
 

Teorioppgave - Rotfaste trestrukturer

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 02.10.2017 15:00

NB! Du er ikke innlogget. Logg inn for å få frem det du har skrevet tidligere.
Dersom du har levert øvingen fra før, vil det du har levert bli slettet dersom du klikker på 'Vis alternativer'

NB! Det du skriver i tekstfeltene blir ikke vurdert som en del av besvarelsen. De er kun til eget bruk, før du velger 'Vis alternativer'.

Oppgave 1

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 %)


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


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


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


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 %)


f) Er heapsort en stabil sorteringsalgoritme? (11.1 %)


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


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 %)


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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Stikkord til forelesning

Du får mer utbytte av en forelesning dersom du på forhånd vet helt overfladisk hva den handler om. Du bør ane hva stikkordene for neste forelesning betyr.
Skriv gjerne ned kommentarer til stikkordene for neste forelesning og se over dem på neste teoriøving.

Kommentarer til stikkordene er kun til eget bruk og blir ikke vurdert av andre.

Det er ikke lagt inn noen stikkord for neste forelesning.


Eventuelt tidligere innlevering vil bli OVERSKREVET om du klikker på 'Vis alternativer'.