3.P Prøver til del 3: Hashing og søk
Fire prøver som dekker del 3 (hashing og søk) på eksamensnivå, med fulle løsningsforslag.
dekker hele Del 3 — håndkjøring av linear probing, load-faktor og rehashing,
Insert-prosedyren i pseudokode, og Del 2-søkeoppgavene der poengtrappen avgjør.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 3.A (25 min): Linear-probing håndkjøring — oppgi hele tabellen
(sjanger E). Dekker kap. 3.1 og
kap. 3.3.
- Prøve 3.B (25 min): Load-faktor, rehashing og hashmap-fakta (sjanger C, med
fem flervalg inline i prøven). Dekker kap. 3.2.
- Prøve 3.C (30 min): Skriv Insert og Contains i pseudokode, med kjøretid
(sjanger I). Dekker kap. 3.1 og
kap. 3.3.
- Prøve 3.D (30 min): Finn duplikat og finn par — velg lavest kjøretid,
sortert mot usortert (sjanger I). Dekker
kap. 3.4.
Slik bruker du dem: ta én prøve på tid, uten fasit og uten oppslag. Eksamen er
en firetimers digital skoleeksamen i Inspera uten hjelpemidler — du skriver
alt, også pseudokode, rett inn i Inspera, og du får aldri se en tabell underveis.
Å håndkjøre en hashtabell på papir og skrive Insert 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 fem
flervalgsspørsmålene står inline i prøve 3.B, med bokstavsvar i fasiten; den
interaktive quizen til kapitlene 3.1 til 3.4 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 3: kap. 3.1 om hashtabellen,
, lineær probing og wraparound; kap. 3.2
om load-faktor, rehashing og hashmap/hash-set; drillen i
kap. 3.3; og kap. 3.4 om binærsøk,
duplikatsøk og parsøk.
Fra tidligere deler trengs -notasjonen og skillet mellom forventet og verste
tilfelle (kap. 1.1), løkketellingen
(kap. 1.2) og sortér-og-skann-strategien
(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.