5.P Prøver til del 5: Grafer: representasjon, traversering og komponenter
Fire prøver som dekker del 5 (grafer: representasjon, traversering og komponenter) på eksamensnivå, med fulle løsningsforslag.
dekker hele Del 5 — grafegenskaper og representasjonskjøretider, bredde-først og
dybde-først i pseudokode, tofarging og komponenttelling, og de store
komponentoppgavene der startmengden og kjøretidsvalget avgjør. Alle oppgaver er
nyskrevne og satt i eksamens sjangre, og løsningsforslagene viser formen sensor
forventer, med poengfordeling per delmoment.
- Prøve 5.A (25 min): Grafegenskaper og kjøretidene for naboliste og
nabomatrise — sjanger F, altså matrise- og tabellavkryssing der du kobler
egenskap til graf eller algoritme. Med fem flervalg inline i prøven. Dekker
kap. 5.1 og kap. 5.3.
- Prøve 5.B (30 min): Bredde-først og dybde-først i pseudokode, og skillet
mellom kjøretiden fra én node og for et fullt søk — sjanger H og F. Dekker
kap. 5.2.
- Prøve 5.C (30 min): Tofarging og komponenttelling i pseudokode — sjanger H.
Dekker kap. 5.3.
- Prøve 5.D (35 min): Sterkt sammenhengende komponenter — rundturer,
startmengde og valget av lavest kjøretid, sjanger H. Dekker
kap. 5.4 og drillen i kap. 5.5.
Slik bruker du dem: ta én prøve på tid, uten fasit og uten oppslag. Eksamen er
en firetimers digital skoleeksamen i Inspera — UiOs eksamenssystem — uten
hjelpemidler, og du skriver alt, også pseudokoden, rett inn i systemet. Å skrive
et bredde-først-søk fra hukommelsen og håndkjøre det på papir 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 5.A, med bokstavsvar i fasiten; den
interaktive quizen til kapitlene 5.1 til 5.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 5: kap. 5.1 om grafer som
, naboliste mot nabomatrise og grunnbegrepene sti, sykel og grad;
kap. 5.2 om bredde-først- og dybde-først-traversering og
det faste skillet mellom kjøretiden fra én node og for et fullt søk;
kap. 5.3 om komponenter, tofarging og sykeldeteksjon;
kap. 5.4 om sterkt sammenhengende komponenter og
komponentgrafen; og drillen i kap. 5.5, som binder
mønstrene sammen.
Fra tidligere deler trengs -notasjonen fra kap. 1.1 og
løkketellingen fra kap. 1.2, som er det du bruker når du
skal begrunne en kjøretid.
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.