INF2220 Ukeoppgaver (17.9 - 21.9) ================================= OPPGAVE 1 --------- Du skal foresl? en datastruktur for en kompilatorrutine som leser inn en programkode. Koden inneholder variabelnavn og metodenavn. For hvert navn som leses, skal navnet lagres sammen med annen informasjon knyttet til det. Hver gang et navn leses, m? det unders?kes om navnet finnes fra f?r. Hvis det finnes, vil programmet trenge informasjonen som er lagret om det. Hvis det ikke finnes, m? det settes inn. N?r skopet endres (f.eks. ved at en metode avsluttes), vil man m?tte slette navn. Du har f?lgende valgmuligheter for datastruktur: array, lenket liste, B-tre og hashtabell. Lag en tabell som gir gjennomsnittelig tidsestimat for innsetting, sletting og oppslag. OPPGAVE 2 --------- Anta at vi har et tomt B-tre med M=4 og L=4. Bruk innsettingsstrategien illustrert i MAW figur 4.59-4.61. Sett inn f?lgende verdier i angitt rekkef?lge: 1, 10, 20, 30, 11, 29, 28, 27, 25, 26, 23 og 23. Tegn treet etterhvert som det forandrer seg. OPPGAVE 3 --------- Mot slutten av MAW 4.7 (s. 150) beskrives en annen innsettingsprosedyre. Gj?r oppgave 2 om igjen med denne strategien. Hvordan vil denne strategien fungere med et veldig stort tre? OPPGAVE 4 --------- Returner til treet i oppgave 2 og ta ut f?lgende verdier: 1, 10, 20. OPPGAVE 5 --------- Anta at vi benytter B-tr?r med M=128, og at vi som et grovt gjennomsnitt har 100 barn under hver node. Hvordan ser da et tre ut som oppbevarer pekere til 1 millon data-recorder i en database. Vi kan videre anta at hver record i databasen er p? 100 byte, at hver peker og verdi i de mellomliggende nodene er p? 4 byte hver og at en node i tillegg har 10 byte. Hvor stor plass tar et slikt B-tre i databasen med de 1 million recordene ? OPPGAVE 6 --------- Anta at vi har arbeidet en stund med ? sette inn og ta ut data i et B-tre. Vi f?r s? vite at det ikke blir noe mer forandring p? dataene, og at det vil bli kritisk med plassen fremover. Vi ?nsker derfor ? legge dataene inn i et nytt B-tre, der nodene er s? fulle (og dermed s? f?) som mulig. De gamle nodene skal kastes. Skisser hvordan dette kan gj?res. Merk: Det viktigste er her ? f? s? f? noder som mulig, s? om man noen f? steder bryter kravet til fyllingsgrad s? er ikke det s? farlig.