TDT4120 Algoritmer og datastrukturerTilbake

2.P Prøver til del 2: Sortering og utvelgelse

Alle fag for Høyskole

2.P Prøver til del 2: Sortering og utvelgelse

Fire prøver som dekker del 2 (sortering og utvelgelse) på eksamensnivå, med fulle løsningsforslag.

120 min

0 oppgaver

Prøver til del 2Sorteringutvelgelse

Din fremgang i kapitlet

0 / 0 oppgaver

Kapitlets plass i kurset

Bygger på

2.4DRILL — Sortering: håndkjøring, kjøretid og kombinasjon

Fire prøver à ~25–35 min: prøve 2.A (25 min), 2.B (30 min), 2.C (30 min) og 2.D (35 min) — 120 minutter i alt. Prøvene kan trygt deles over flere kvelder; én prøve per økt er den rytmen som fungerer best, fordi hver prøve trener én ferdighet ferdig.

Dekning. Sortering er telt i 17 av de 17 settene i grunnlaget (100 %) — sammen med asymptotisk notasjon og NP-stoffet er det ett av tre temaer som kommer hver eneste gang. Det er høyeste prioritet: dette må sitte. Kjøretidene, stabiliteten og kravene til de lineære sorteringene forventes direkte, uten hjelpemidler, og de får prøve 2.A og 2.C. Håndkjøring av en navngitt algoritme får prøve 2.B. Utvelgelse — Partition, Randomized-Select og Select — er telt i 8 av de 17 settene (47 %) og hører til stoffet du bør kjenne til; det får prøve 2.D sammen med den nedre grensen for sammenligningsbasert sortering.

Sjangrene du møter her, skrevet ut i klarspråk:

- sjanger C — håndkjøring: du utfører algoritmen steg for steg og oppgir bare det som blir etterspurt, i det formatet oppgaven ber om.
- sjanger D — definisjon med egne ord: én presis setning, med hovedpoenget først.
- sjanger E — kjøretid: ett uttrykk, med $\Theta$ der garantien er tett og $O$ der bare den øvre grensen er vist. Si «forventet» der tallet er en forventning over tilfeldige valg.
- sjanger F — «stemmer dette?»: ja eller nei først, deretter én setning som begrunner.

Hvor flervalget bor. De statiske flervalgsoppgavene står inline i prøveteksten under, med alternativer merket a)–d) og fasitbokstaven i løsningsforslaget. De interaktive flervalgsspørsmålene — dem du klikker deg gjennom og får rettet automatisk — ligger i quizen til kapitlene i Del 2, ikke her. Bruk prøvene til å skrive svar for hånd; bruk quizen til å pugge fakta.

Én ting om formen. Eksamen i TDT4120 er en firetimers skoleeksamen uten hjelpemidler — NTNU kaller det hjelpemiddelkode E — med rundt 20 korte frisvarsoppgaver som teller likt. Kjøretidstabellen for de sju sorteringene i denne delen er derfor ren puggeflate. Løsningsforslagene viser hva som gir uttelling, og delpoeng-notatene under sier hvor poengene faller når svaret er halvveis.

Tidsbudsjett. Minuttallene er arbeidstid med penn og papir. Legger du til lesing av oppgaveteksten og gjennomlesing av eget svar, bruker du i praksis litt mer — det er normalt, og det er nettopp tempoferdigheten eksamen også måler.

Forkunnskaper

Prøvene her hviler på hele Del 2, og på asymptotisk notasjon fra Del 1:

- kap. 2.1 — Insertion-Sort, Merge-Sort, Quicksort og Randomized-Quicksort
- kap. 2.2 — Counting-Sort, Radix-Sort, Bucket-Sort og stabilitet
- kap. 2.3 — Partition, Randomized-Select og Select
- kap. 2.4 — drillen på håndkjøring, kjøretid og kombinasjon
- kap. 1.1 — de asymptotiske symbolene, som alle kjøretidssvar bruker
- kap. 1.4 — masterteoremet, som gir Merge-Sort sin $\Theta(n\lg n)$

Dette er det du trenger å ha friskt før du setter deg ned:

- Arrayene er A[1..n] med indeks fra 1. Det er konvensjonen i hele boka, og alle håndkjøringene under bruker den.
- Partition bruker siste element som pivot, altså A[r], og returnerer den endelige plassen til pivoten.
- Counting-Sort har tre løkker: telling, prefikssum og plassering. Plasseringsløkka går baklengs gjennom A, og det er nettopp det som gjør sorteringen stabil.
- Stabil sortering betyr at to elementer med lik nøkkel beholder den innbyrdes rekkefølgen de hadde i inputen.
- Skillet garantert mot forventet: $\Theta$ der grensen holder for enhver input, «forventet» der tallet er et snitt over algoritmens egne tilfeldige valg.
- Den nedre grensen $\Omega(n\lg n)$ gjelder bare sammenligningsbaserte sorteringer. Counting-Sort og Radix-Sort bryter den ikke — de sammenligner ikke nøkler mot hverandre i det hele tatt.

Har du ikke lest kapitlene ennå, er prøvene fortsatt lesbare — men da leser du dem som fasitskriver, ikke som kandidat.

Prøve 2.A — Kjøretider og stabilitet (25 min)

Prøve 2.B — Håndkjøring av Counting-Sort og Partition (30 min)

Prøve 2.C — Kombinasjon og lineær sortering (30 min)

Prøve 2.D — Utvelgelse, nedre grense og definisjoner (35 min)

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.