INF1020 ukeoppgaver uke 4 (19/9-23/9) ===================================== OPPGAVE 1: ---------- Tegn det r?d-svarte treet som blir resultatet av f?lgende innsettingsekvens: 3, 1, 4, 6, 9, 2, 5, 7 OPPGAVE 2: ---------- P? forelesningen 29/8 brukte vi et bin?rt s?ketre for ? lagre alle ordene i Ibsens skuespill Vildanden. S?ketreet ble imidlertid veldig skjevt. Implementer innsetting i r?d-svarte tr?r som skissert p? forelesningen 12/9, og bruk denne til ? lage et r?d-svart tre med ordene i Vildanden. Hvordan blir det med balansen n?? OPPGAVE 3 --------- 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 4 --------- MAW figur 4.62 - 4.63 beskriver en annen innsettingsprosedyre. Gj?r oppgave 2 om igjen med denne strategien. Hvordan vil denne strategien fungere med et veldig stort tre? OPPGAVE 5 --------- Returner til treet i oppgave 3 og ta ut f?lgende verdier: 1, 10, 20. OPPGAVE 6 --------- 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 7 --------- 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. OPPGAVE 8 --------- Vi skal skrive et program som sjekker visse aspekter ved Java-programmer, nemlig: - at {}-par kommer riktig - at vanlige parentes-par kommer riktig - at det ikke kommer semikolon eller {} inne i parenteser Vi skal ikke bry oss med detaljene i lesingen av programmet, men kan f.eks. anta at vi har en metode String nesteSymb() som leverer neste interessante symbol i programmet, og hvor "EOF" angir programslutt. Man kan bruke en (String) stakk for ? sjekke dette. Beskriv et sett av stakk-operasjoner som er tilstrekkelig for denne sjekkingen, og skriv hovedprogrammet ut fra dette. OPPGAVE 9 --------- Regnestykket 1.23 + ( (4.56 * 7.89) / (3.3 + 4.44) ) kan skrives p? postfiks form uten bruk av parenteser slik: 1.23 4.56 7.89 * 3.33 4.44 + / + N?r uttrykk p? postfiks form skal beregnes er det naturlig ? bruke en stakk av tall. M?let er da at svaret st?r alene igjen p? stakken n?r beregningen er ferdig. a) Forklar f?rst med ord hva slags stakk-operasjoner som m? gj?res n?r man leser inn et postfiks uttrykk sekvensielt, og f?r inn henholdsvis et tall eller en av de fire operasjonene. Tenk deg ogs? en operasjon som henter ut svaret til slutt, slik at det blir i alt seks operasjoner. b) Anta at man har en standard-pakke for stakker av reelle tall, og bruk denne til ? implementere de seks operasjonene. c) Lag en direkte implementasjon av de seks operasjonene som bruker en array. Legg ogs? inn i denne modulen mekanismer som tester om uttrykket er et korrekt uttrykk.