Uke 35

Question 1

Hva er en algoritme?

Answer 1

Oppskrift. Presis beskrivelse hvordan løse problem.
Små, entydige skritt.
Algoritme må:
-terminere etter endelig steg
-hvert steg presist def
-ta 0+ input
-lager output som matcher input
-bør være effektiv

Question 2

Hva er en datastruktur?

Answer 2

*Samling av verdier som følger en fast struktur utgjør en datastruktur

*måter å ordne data på

Question 3

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n.
Etter i iterasjoner av den ytre loopen i Bubble sort, er de i første elementene sortert.

Answer 3

Usant, se på
5 4 3 2 1
og 3 ytre iterasjoner

Er sann hvis n-1 ≤ i

Question 4

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n.
Etter i iterasjoner av den ytre loopen i Bubble sort, er de i siste elementene sortert.

Answer 4

Sant
se på
54321 som etter 3 iterasjoner blir til

21 3 4 5

Question 5

Sant/Usant: Bubble sort bytter kun elementer som står direkte ved siden av hverandre

Answer 5

Sant

Question 6

Sant / Usant: Bubble sort garanterer et minimalt antall bytter

Answer 6

Usant
Se på 321
Bubble sort bruker 2 iterasjoner, mens man kan bytte 3 med 1 med 1 iterasjon ved selection sort

Question 7

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n. Etter i iterasjoner av den ytre loopen i Selection sort, er de i første elementene sortert.

Answer 7

Sant
tre iterasjoner på

53214
1 3254
1 2 354

1 2 3 54

Question 8

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n. Etter i iterasjoner av den ytre loopen i Selection sort, er de i siste elementene sortert.

Answer 8

Usant
tre iterasjoner på

53214
1 3254
1 2 354

1 2 3 54 (ser at 3 54 IKKE er sortert)

Question 9

Sant/Usant
Selection sort bytter kun elementer som står direkte ved siden av hverandre

Answer 9

Usant

Question 10

Sant / Usant
Selection sort garanterer et minimalt antall bytter

Answer 10

Usant

Question 11

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n. Etter i iterasjoner av den ytre loopen i Insertion sort, er de i første elementene sor‐
tert

Answer 11

Sant
se på
4213
2 413
2

Question 12

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n. Etter i iterasjoner av den ytre loopen i Insertion sort, er de i siste elementene sortert

Answer 12

Usant
se på
312 med 1 iterasjon av ytre loop
1 32

Question 13

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n. Insertion sort bytter kun elementer som står direkte ved siden av hverandre.

Answer 13

Sant

Question 14

Sant / Usant:
Du kan anta at A er et array med n elementer, og at i er et heltall 0 ≤ i < n. Insertion sort garanterer et minimalt antall bytter

Answer 14

Usant