Sist endret: 23.09.2016

Løsningsforslag - Datastrukturer

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

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

<3,4,7,32,72,3>

<4,7,32,72,3,3>

<4,7,32,72,3>

<4,7,32,72>

Din kommentar:
LF-forklaring:

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

<3,4,7,32,72,3>

<4,7,32,72,3,3>

<4,7,32,72,3>

<4,7,32,72>

<7,32,72,3>

Din kommentar:
LF-forklaring:

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

0

1

2

5

6

11

Din kommentar:
LF-forklaring:

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

<3,4,7,32,72,3>

<4,7,32,72,3,3>

<4,7,32,72,3>

<4,7,32,72>

<7,32,72,3>

Din kommentar:
LF-forklaring:

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

<3,4,7,32,72,3>

<4,7,32,72,3,3>

<4,7,32,72,3>

<4,7,32,72>

<7,32,72,3>

Din kommentar:
LF-forklaring:

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

0

1

2

5

6

11

Din kommentar:
LF-forklaring:

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

<3,4,7,32,72,3>

<4,7,32,72,3,3>

<4,7,32,72,3>

<4,7,32,72>

<7,32,72,3>

Din kommentar:
LF-forklaring:

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

<3,4,7,32,72,3>

<4,7,32,72,3,3>

<4,7,32,72,3>

<4,7,32,72>

<7,32,72,3>

Din kommentar:
LF-forklaring:

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

<3,4,7,32,72,3>

<4,7,32,72,3,3>

<4,7,32,72,3>

<4,7,32,72>

<7,32,72,3>

Din kommentar:
LF-forklaring:

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

L = 2, N = < /,6,1,3,0,4>, K = <3,4,72,32,0,7>, P = <3,/,4,1,0,2>

L = 4, N = <8,6,/,1,0,0,0,2>, K = <7,32,72,4,0,0,0,3>, P = <4,8,2,/,0,0,0,1>

L = 1, N = <2,3,4,5,/>, K = <4,7,32,72,3>, P = <1,2,3,4,/>

L = 7, N = <3,0,4,/,0,1,6,0>, K = <32,0,72,3,0,7,4,0>, P = <6,0,1,3,0,7,/,0>

Din kommentar:
LF-forklaring:

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

L = 19 A = <32,7,13,0,0,0,72,16,1,0,0,0, 7,1,19,3,/,9,4,13,/,0,0,0>

L = 13 A = <0,0,0,7,1,13,32,4,22,0,0,0,4,13,/,3,/,4,0,0,0,72,16,1>

L = 4 A = <72,13,10,4,7,/,7,10,4,32,1,7,3,/,1>

L = 4 A = <72,16,13,4,10,/,32,13,10,7,7,4,0,0,0,3,/,1>

Din kommentar:
LF-forklaring:

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

Nei

Din kommentar:
LF-forklaring:

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

x elementet, m nøkkelen og j hashen.

x elementet, j nøkkelen og m hashen.

j elementet, m nøkkelen og x hashen.

Ingen av delene

Din kommentar:
LF-forklaring:

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

Nei

Din kommentar:
LF-forklaring:

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

Flere ulike hash-verdier gir samme faktiske verdi.

Flere ulike faktiske nøkler gir samme hash-verdi.

Begge alternativene.

Ingen av alternativene.

Din kommentar:
LF-forklaring:

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

O(1) både for enkel og dobbel lenket liste.

O(n) både for enkel og dobbel lenket liste.

O(n) for enkel lenket liste og O(1) for dobbel lenket liste.

O(1) for enkel lenket liste og O(n) for dobbel lenket liste.

Din kommentar:
LF-forklaring:

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

O(1)

O(lg(n))

O(n)

O(nlg(n))

Din kommentar:
LF-forklaring:

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

O(1)

O(lg(n))

O(n)

O(nlg(n))

Din kommentar:
LF-forklaring:

Oppgave 5

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

Et binærtre med en kant mer.

Et tre med høyere grad.

En syklisk graf.

Ingen av delene.

Din kommentar:
LF-forklaring:

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

Worst case kan gi ugyldig svar.

Worst case kan være altfor pessimistisk.

Amortisert analyse er raskere å beregne.

Amortisert analyse gir også en nedre grense.

Din kommentar:
LF-forklaring: