4.P Prøver til del 4: Trær: søketrær, balanserte trær og heap
Fire prøver som dekker del 4 (trær: søketrær, balanserte trær og heap) på eksamensnivå, med fulle løsningsforslag.
dekker hele Del 4 — binære søketrær, tre-algoritmene i pseudokode, balanserte trær
og heap. Alle oppgaver er nyskrevne og satt i eksamens sjangre, og
løsningsforslagene viser formen sensor forventer, med margnotater om hva som gir
uttelling.
- Prøve 4.A (25 min): Binære søketrær — innsetting, in-order, søk og sletting,
pluss skillet mellom heap-egenskapen og søketre-egenskapen. Dekker
kap. 4.1.
- Prøve 4.B (30 min): Håndkjøring av min-heap — Insert og RemoveMin med
indeks fra 0. Dekker kap. 4.4 og
kap. 4.5.
- Prøve 4.C (30 min): Tre-algoritmene i pseudokode — beskåret in-order,
diameter og gyldighetssjekk, der lavest kjøretid gir mest uttelling. Dekker
kap. 4.2.
- Prøve 4.D (30 min): AVL-rotasjoner, pluss fakta om rød-svart-trær og heap
(med fire flervalg inline i prøven). Dekker
kap. 4.3 og kap. 4.4.
Slik bruker du dem: ta én prøve på tid, uten fasit og uten oppslag. Eksamen er
en firetimers digital skoleeksamen i Inspera — UiOs digitale eksamenssystem —
uten hjelpemidler. Du skriver alt, også pseudokoden, rett inn i Inspera, og du
får aldri se en heap eller et rotasjonsskjema underveis. Å håndkjøre på papir og
skrive RemoveMin fra hukommelsen er ferdigheter som bare øves på én måte.
Prøvene kan trygt deles over flere kvelder — én prøve per økt. De fire
flervalgsspørsmålene står inline i prøve 4.D, med bokstavsvar i fasiten; den
interaktive quizen til kapitlene 4.1 til 4.5 er den store flervalgsbanken, og den
tas separat.
Åpne fasiten først når du er ferdig, og bruk selvdiagnose-lista nederst i hver
prøve. Husk at C er en god og vanlig karakter — målet er ikke plettfrie tabeller,
men å levere alle delmomentene.
Forkunnskaper
Prøvene forutsetter hele Del 4: kap. 4.1 om binære søketrær,
innsetting og in-order; kap. 4.2 om tre-algoritmene i
pseudokode — beskåret in-order, diameter, gyldighetssjekk;
kap. 4.3 om AVL-rotasjoner og rød-svart-trær;
kap. 4.4 om min-heap, Insert og RemoveMin; og drillen i
kap. 4.5.
Fra tidligere deler trengs -notasjonen (kap. 1.1),
løkketellingen (kap. 1.2) og sammenligningen med
sorteringsalgoritmene i kap. 2.2.
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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.