Sist endret: 23.09.2016  
 

Teorioppgave - Datastrukturer

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 11.09.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

Anta du har en kø Q = <4,7,32,72,3> hvor det bakerste elementet representerer hodet til køen. Alle deloppgavene refererer til denne køen.

a) Hvordan vil køen se ut etter å ha kjørt ENQUEUE(Q,3)? (5 %)


b) Hvordan vil køen se ut etter å ha kjørt DEQUEUE(Q)? (5 %)


c) Hva er det minste antallet ENQUEUE/DEQUEUE-operasjoner du trenger for at køen skal endres til <3,4,7,32,72,3>? (5 %)


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

Oppgave 2

Anta du har en stakk S = <4,7,32,72,3> hvor det bakerste elementet representerer toppen av stakken.

a) Hvordan vil stakken se ut etter å ha kjørt PUSH(S,3)? (5 %)


b) Hvordan vil stakken se ut etter å ha kjørt POP(S)? (5 %)


c) Hva er det minste antallet PUSH/POP-operasjoner du trenger for at stakken skal endres til <3,4,7,32,72,3>? (5 %)


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

Oppgave 3

Anta at du har en sirkulær dobbel lenket liste L = <4,7,32,72,3> hvor HEAD peker på 4-tallet.

a) Hvordan vil listen se ut etter LIST-SEARCH(L,4)? (5 %)


b) Hvordan vil listen se ut etter LIST-INSERT(L,3)? (5 %)


c) Hvordan vil listen se ut etter LIST-DELETE(L,x) for noden x der x.key = 4? (5 %)


d) Vi ønsker å implementere L som et flerarray av objekter tilsvarende som i Cormen (figur 10.5 s.242). Hvilket av alternativene under for startvariabel L og arrayene N = next, K = key og P = prev er korrekt implementert? (5 %)


e) Vi ønsker å implementere L som et array av objekter tilsvarende som i Cormen (figur 10.6 s.243). Hvilket av alternativene under for startvariabel L og array A er korrekt implementert? (5 %)


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

Oppgave 4

a) En god hash-funksjon vil, for en tabell av lengde n, kunne garantere for at k < n innsettinger ikke vil gi kollisjon? (5 %)


b) Du får oppgitt at x.key = m og h(m) = j der h er en hash-funksjon. Da er... (5 %)


c) Er h(k) = (k * randint(0,k)) mod m hvor k er nøkkelen og m er størrelsen på hashtabellen en god hashfunksjon? (5 %)


d) Hva betyr kollisjon (collision) i forbindelse med hash-tabeller? (5 %)


e) Hvis vi har en funksjon DELETE(T,x) der T er en kjedet hash-tabell og x er et listenode, så er worst case kjøretide... (Legg merke til at x her er en faktisk listenode - ikke en nøkkel) (5 %)


f) Hva er worst-case-kjøretiden for innsetting i en hash-tabell om man bruker kjeding ved kollisjoner? Anta at innsettingen også må sjekke om elementet allerede finnes i tabellen. (5 %)


g) For å unngå at vi lager for stor initiell hashtabell ønsker vi å doble størrelsen på hashtabellen hver gang lastfaktoren blir ¼ (lastfaktor beregnes N/M hvor N er antall elementer i hashtabellen og M er størrelsen på hashtabellen). Hvis vi benytter amorisert analyse får vi at kjøretiden for innsetting er ... (5 %)


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

Oppgave 5

a) Anta du har binærtre G og legger til en ny kant i treet. Du vil nå ha... (5 %)


b) Hvorfor er amortisert analyse bedre enn vanlig worst-case-beregning i mange tilfeller? (5 %)


Ø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'.