Sist endret: 17.08.2010

Løsningsforslag - Grafer og hashing

Innleveringsfrist: 23.09.2011 10:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på algdats nyhetsgruppe. Denne nyhetsgruppen har også et webgrensesnitt.

Oppgave 1

a) Hvis du vet at en graf G inneholder sykler, da kan du si at G er: (2.5 %)

Rettet
Urettet
Ingen av alternativene er riktige

Din kommentar:
LF-forklaring:	Både rettede og urettede grafer kan ha sykler

b) Hvis du vet at en rettet graf G ikke inneholder sykler, da kan du si at G er: (2.5 %)

Et tre
En DAG
Umulig å si uten å vite strukturen til G

Din kommentar:
LF-forklaring:	DAG står for Directed Asyclic Graph (Rettet graf uten sykler)

c) Hvordan ville du representert en graf med få kanter? (2.5 %)

Nabomatrise
Nabolister
Lenket liste
Heap

Din kommentar:
LF-forklaring:

d) Hvordan ville du representert en graf med mange kanter? (2.5 %)

Nabomatrise
Nabolister
Lenket liste
Heap

Din kommentar:
LF-forklaring:

e) Hvilken påstand er ikke sann? (5 %)

BFS kan brukes til å finne én-til-alle korteste vei
DFS kan brukes til trefarging av en graf
All traversering kan brukes til to-farging av en graf
Både BFS og DFS finner alle noder i en sammenhengende graf

Din kommentar:
LF-forklaring:	Trefarging av en graf er et vanskelig problem som ingen har funnet en effektiv måte for å løse. Mer om dette senere i kurset.

Oppgave 2

I figuren ovenfor er det vist en urettet graf med kostnader på kantene,
og fire mulige måter å traversere grafen på.

1. - Q,H,P,D,G,F,C,L,E,K,O,B,A,J,N,M,I
2. - Q,H,P,D,G,C,B,A,E,F,K,N,J,M,I,O,L
3. - Q,H,D,G,C,B,A,E,F,K,N,J,M,I,O,P,L
4. - Q,H,P,D,G,F,L,C,E,K,O,B,A,J,N,M,I

a) Hvilket tilfelle er traverseringen et Bredde-Først-Søk? (10 %)

1 2 3 4

Din kommentar:
LF-forklaring:

b) Hvilket tilfelle er traverseringen et Dybde-Først-Søk? (10 %)

1 2 3 4

Din kommentar:
LF-forklaring:

c) Hva vil køen til et bredde-først-søk inneholde rett etter at node L har blitt behandlet hvis vi starter i node Q? (Vi forutsetter at nabonoder legges inn i køen i omvendt alfabetisk rekkefølge.) (12.5 %)

C, E, K, O C, F, K F, G, D K, O, P, I

Din kommentar:
LF-forklaring:	med "køen" sikter vi her til datastrukturen som holder rede på hvilken node algoritmen har igjen å besøke, og rekkefølgen på disse. Dette er den samme konsept som bredde først køen dere brukte i den praktiske øvingen

d) Hva vil stacken til et dybde-først-søk være rett etter at node L har blitt behandlet hvis vi starter i node Q? (Vi forutsetter at nabonoder besøkes i alfabetisk rekkefølge.) MERK: Oppgavteksten har blitt endret fra oppdaget til behandlet. Ingen alternativ var riktig med den tidligere ordlyden. (12.5 %)

Q, H, D, G, L Q, H, G, L Q, H, G, C, B, A, E, F, P, L Q, P, F, O, N, J, A, B, C, G, L

Din kommentar:
LF-forklaring:

Oppgave 3

I figuren ovenfor er det vist en urettet graf med navngitte noder.

Dybde først søk (DFS) skal kjøres på grafen, og følgende ekstraopplysning er gitt: Nabolister er sortert alfabetisk, dvs. hvis noden C har en kant til A, H og F er nabolisten [A, F, H].

Hva vil tidsmerkene (timestamps) på node C være dersom DFS kjøres på grafen med utgangpunkt i node G?

(5 %)

6/7 5/14 8/9 8/13

Din kommentar:
LF-forklaring:	DFS traverserer grafen i følgende rekkefølge: (1) Oppdag G, (2) Oppdag B, (3) Oppdag D, (4) Avslutt D, (5) Avslutt B, (6) Oppdag E, (7) Oppdag H, (8) Oppdag C, (9) Oppdag A, (10) Avslutt A, (11) Oppdag F, (12) Avslutt F, (13) Avslutt C, (14) Oppdag I, (15) Avslutt I, (16) Avslutt H, (17) Avslutt E, (18) Avslutt G

Hvilken farge har node H i det øyeblikk node A blir fargelagt svart?

(5 %)

Hvit (uoppdaget) Grå (besøkt) Svart (ferdig)

Din kommentar:
LF-forklaring:	Node H har timestamp 7/16 og node A har 9/10

Oppgave 4

a) En god hash-funksjon vil, for en tabell av lengde n, kunne garantere for at k < n innsettinger ikke vil gi kollisjon? (2.5 %)

Ja.
Nei.

Din kommentar:
LF-forklaring:	Nei, for en god hash-funksjon skal det være like sannsynlig for en nøkkel å sendes til hver av plassene i hash-tabellen.

b) Du får oppgitt at x.key = m og h(m) = j der h er en hash-funksjon. Da er (2.5 %)

x elementet, m nøkkelen og j hashen.
x elementet, j nøkkelen og m hashen.
j elementet, m nøkkelen og x hashen.
Ingen av delene.

Din kommentar:
LF-forklaring:

c) Er h(k) = k*r%m,hvor k er nøkkelen, m er et gitt positivt heltall og r er et tilfeldig positivt heltall, en god hash-funksjon? (2.5 %)

Ja.
Nei.

Din kommentar:
LF-forklaring:	Nei, da har man jo ingen mulighet til å slå opp i tabellen.

d) Hvilken operasjon er ikke typisk for på en hash-tabell? (2.5 %)

sort(Tabell, Kolonne)
delete(Tabell, Nøkkel)
search(Tabell, Nøkkel)
insert(Tabell, Nøkkel)

Din kommentar:
LF-forklaring:

e) Hva betyr kollisjon (collision) i forbindelse med hash-tabeller? (2.5 %)

flere ulike hash-verdier gir samme faktiske verdi
begge alternativer
ingen av alternativene
flere ulike faktiske nøkler gir samme hash-verdi

Din kommentar:
LF-forklaring:

f) Hvordan kan man løse kollisjons-problematikken fra forrige deloppgave? (5 %)

dividering (division)
kjeding (chaining)
multiplisering (multiplication)
randomisering (randomization)
ingen av alternativene

Din kommentar:
LF-forklaring:

g) Hvis vi har en funksjon SLETT(T,x) der T er en kjedet hash-tabell og x er et listeelement, så er worst case kjøretiden? (7.5 %)

O(n) både for lenket og dobbelt-lenket liste
O(1) både for lenket og dobbelt-lenket liste
Ingen av delene

Din kommentar:
LF-forklaring:	Merk at vi tar inn elementet x og ikke dens nøkkel k. Derfor trenger vi bare å endre pekerverdiene til den foran og den etter. For lenket liste er vi nødt til å søke frem elementet foran, mens for dobbelt-lenket vet vi både den foran og bak. Dermed blir kjøretiden O(1) for dobbelt-lenket og O(n) for lenket.

h) Hva betyr åpen addressering (open adressing/closed hashing) i forbindelse med hash-tabeller? (5 %)

elementene lagres direkte i hash-tabellen
nøklene indekseres på flere måter for lettere aksess til elementene
man oppretter et ekstra sett pekere som peker til både elementet og tilhørende nøkkel for å få bedre kjøretid ved operasjonene på hash-tabellen

Din kommentar:
LF-forklaring: