IN2010 oblig 1

Du må laste opp et dokument for å få tilgang til dette dokumentet.

Medlemskap gir deg full tilgang til en omfattende samling av dokumenter.

Emne

in2010 algoritmer og datastrukturer

Type

Oblig

Karakter

Godkjent

Nedlastinger

2

Ord

228

Sider

3

Opplastet

19. september 2022

Nyttig?

0

Du må være registrert og logget inn for å stemme.

Det anbefales sterkt å kun bruke dokumentene som en supplementær kilde til hjelp. Det er viktig å huske at den virkelige læringen kommer fra å gjøre oppgavene selv, og at kopiering kan føre til alvorlige konsekvenser i form av plagiat. Derfor bør man alltid sørge for å forstå og anvende kunnskapen på egen hånd, i stedet for å avhenge utelukkende av dokumentene.

Utdrag

Oppg. 1

a)

method push_front(tall):

arraylist.add(indeks0, tall)

method push_back(tall):

arraylist.add(tall)

method push_middle(tall):

initialize variable midten

midten <- Math.round(arraylist.lengde()/2)

arraylist.add(midten, tall)

method get(indeks):

print(indeks)

b) vedlagt kode

c)

Push_front: O(n)

Push_middle: O(n)

Push_back: O(n)

Get(): O(1)

d) Hvis vi vet at N er begrenset vil det generelt sett bli mindre kompleks O-notasjon.

2 Estimatet blir O(n*log(n))

I dette tilfellet blir kjøretiden lengre ettersom .get(i) er O(n) i forhold til for eksempel Arrays der

Array[indeks] er konstant.

3

For node in nodeListe do:

If kattPosisjon = node.verdi then

Return node

While node is not null do:

Node = node.forelder

4a)

Procedure konstruer (A[] , start, slutt):

If start>slutt then

Return null

Midten <- (start+slutt)/2

Data <- A[midten]

Node <- new Node(data)

Node.left <- konstruer(A[], start, slutt)

Node.right <- k

...