TDT4120 Algoritmer og datastrukturerTilbake

3.P Prøver til del 3: Datastrukturer: hauger, søketrær og hashing

Alle fag for Høyskole

3.P Prøver til del 3: Datastrukturer: hauger, søketrær og hashing

Fire prøver som dekker del 3 (datastrukturer: hauger, søketrær og hashing) på eksamensnivå, med fulle løsningsforslag.

120 min

0 oppgaver

Prøver til del 3Datastrukturerhaugersøketrærhashing

Din fremgang i kapitlet

0 / 0 oppgaver

Kapitlets plass i kurset

Bygger på

3.5Køer, stakker, amortisert analyse og disjunkte mengder

Fire prøver à ~25–30 min: prøve 3.A (30 min), 3.B (30 min), 3.C (25 min) og 3.D (30 min) — 115 minutter til sammen. 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. Prøvene dekker hele Del 3. BST og hauger er telt i 16 av de 17 settene i grunnlaget (94 %) og er den sikreste håndkjøringskandidaten faget har — derfor får de to hele prøver (3.A og 3.B). Hashing er telt i 7 av de 17 settene (41 %), og i alle tre settene fra 2022–23. Køer, stakker, amortisert analyse og disjunkte mengder er telt i 5 av de 17 settene (29 %). Prøve 3.C er kontrastprøven mellom de to strukturene som forveksles oftest, og 3.D samler de øvrige strukturene.

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 sluttilstanden, 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.
- 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 3, ikke her. Bruk prøvene til å skrive svar for hånd; bruk quizen til å pugge fakta.

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 3, og på ingenting annet:

- kap. 3.1 — hauger og Heapsort
- kap. 3.2 — binære søketrær
- kap. 3.3 — drillen på håndkjøring av hauger og BST
- kap. 3.4 — hashing
- kap. 3.5 — køer, stakker, amortisert analyse og disjunkte mengder

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

- Haugene er array A[1..n] med indeks fra 1. Forelderen til A[i] står på $\lfloor i/2\rfloor$ , barna på $2i$ og $2i+1$ . Det er NTNU- og CLRS-konvensjonen, og alle prøvene under bruker den.
- Haugegenskapen (maks-haug): forelderen er større enn eller lik begge barna. Det finnes ingen orden mellom venstre og høyre barn.
- BST-egenskapen: alt i venstre deltre er $\le$ roten, som er $\le$ alt i høyre deltre. Derfor gir Inorder-Tree-Walk nøklene sortert.
- Build-Max-Heap er $\Theta(n)$ , ikke $\Theta(n\lg n)$ .
- Lastfaktoren i en hashtabell er $\alpha = n/m$ : $n$ nøkler fordelt på $m$ bøtter.
- En FIFO-kø i array leveres med hele tabellen, inkludert de døde cellene, pluss head og tail.

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

Prøve 3.A — Håndkjøring av hauger (30 min)

Prøve 3.B — Håndkjøring av binære søketrær (30 min)

Prøve 3.C — BST mot haug, og kjøretidene (25 min)

Prøve 3.D — Hashing, kø med wraparound og Union-Find (30 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.