Kurssiviikko 7¶

Itseopiskelu¶

Viikon aiheet: (i) Puut ja puiden tietorakenteet, (ii) Puiden läpikäynti ja (iii) Mitätöityminen

Puu-tietorakenteet video

Puiden toteuttaminen video

Puiden läpikäynti video

Säiliönviittausten mitätöityminen video

Puut kalvot

Säiliönviittausten mitätöityminen kalvot

Puut¶

Kysymys 1

Mitkä seuraavista juurellisia puita koskevista väitteistä ovat totta? (Videossa puu on sama kuin juurellinen puu.)

Solmulla saa olla enintään 2 vanhempaa.

Solmua, jolla ei ole lapsia, kutsutaan lehdeksi.

Solmua, jolla ei ole vanhempaa, kutsutaan juureksi.

Jos solmulla on enemmän kuin yksi lapsi, yksikään lapsista ei voi olla lehti.

Solmua, jonka vanhemmalla ei ole muita lapsia, kutsutaan yksinäiseksi solmuksi.

Kysymys 2

Oletetaan, että juurellisessa puussa olevalla solmulla \(x\) on useita lapsia. Mikä seuraavista väitteistä solmun \(x\) alipuista pitää paikkansa? (Videossa puu on sama kuin juurellinen puu.)

Jokaisen \(x\) alipuun juuri on \(x\).

Solmun \(x\) alipuiden lukumäärä on yksi enemmän kuin solmun \(x\) lasten lukumäärä.

Solmun \(x\) vanhempi ei kuulu mihinkään solmun \(x\) alipuuhun.

Jokainen solmun \(x\) lapsi kuuluu täsmälleen kahteen solmun alipuuhun.

Kysymys 3

Tarkastellaan juurellista puuta, jonka korkeus on neljä. Mikä seuraavista väitteistä on aina totta? (Videossa puu on sama kuin juurellinen puu.)

Juurella on ainakin neljä lasta.

Puulla on enintään neljä lehteä.

Juuresta alkaen on käytettävä vähintään viisi kaarta, jotta pääsee lehteen, joka on kauimpana juuresta.

Puussa on vähintään viisi solmua.

Kysymys 4

Olkoon \(x\) solmu juurellisessa puussa. Solmun \(x\) jälkeläinen on mikä tahansa solmu missä tahansa solmun \(x\) alipuissa. Mikä seuraavista väitteistä on aina totta? (Videossa puu on sama kuin juurellinen puu.)

Solmun \(x\) lapsen jälkeläisten lukumäärä on pienempi kuin solmun \(x\) jälkeläisten lukumäärä.

Puun juuren jälkeläisten lukumäärä on täsmälleen sama kuin puun solmujen lukumäärä.

Jos solmu ei ole lehti, niin jokainen lehti on sen jälkeläinen.

Jos on 2 solmua, joista kumpikaan ei ole lehti, niillä ei voi olla samaa määrää jälkeläisiä.

Puu-tietorakenteet ja puiden läpikäynti¶

Kysymys 1

On olemassa binääripuu, jossa jokainen solmu tallennetaan kahdella lasten osoittimella nimeltä left_child ja right_child. Jos koko binääripuussa on neljä solmua, kuinka monta näistä osoittimista lapsille on yhtä suuri kuin nullptr?

on mahdotonta tietää kuinka monta

Kysymys 2

Mikä seuraavista kuvaa parhaiten eroa sen välillä, miten solmu tallennetaan yleiseen juurelliseen puuhun ja miten solmu tallennetaan binääripuuhun? (Videossa puu on sama kuin juurellinen puu.)

Binääripuussa osoitinta solmun vanhemmalle ei koskaan tarvita, kun taas yleisessä puussa tällaista osoitinta tarvitaan joskus.

Binääripuussa on kaksi erillistä osoitinta solmun lapsille, kun taas yleisessä puussa tarvitaan säiliö (esim. vektori), johon tallennetaan osoittimet solmun lapsiin.

Binääripuussa solmun avaimen (tai id-numeron) on oltava parillinen, kun taas yleisellä puulla avain voi olla mikä tahansa positiivinen kokonaisluku.

Binääripuussa juurella on oltava täsmälleen kaksi lasta, kun taas yleisessä puussa juuren lasten lukumäärä voi olla jopa negatiivinen.

Kysymys 3

Oletetaan, että suoritetaan sekä preorder-läpikäynti (esijärjestys) että postorder-läpikäynti (jälkijärjestys) koko juurelliselle puulle, jossa on vähintään kaksi solmua. Mikä seuraavista on totta? (Videossa puu on sama kuin juurellinen puu.)

Läpikäytyjen solmujen lukumäärät eivät ole yhtä suuria eri läpikäyntitekniikoilla.

Järjestys, jossa solmut käydään läpi poikkeaa eri läpikäyntitekniikoilla.

Ensimmäinen solmu, jossa käydään molemmissa läpikäynneissä, on lehti.

Kummankaan läpikäynnin ei tarvitse tietää läpikäytävän solmun lapsia.

Kysymys 4

Esitellyt läpikäyntitekniikat ovat preorder, postorder ja inorder (esijärjestys, jälkijärjestys ja välijärjestys). Millä tavalla inorder eroaa kahdesta muusta läpikäynnistä?

Inorder-läpikäynti toimii vain puilla, joilla ei ole lehtiä. Kahta muuta läpikäyntiä voidaan käyttää millä tahansa puulla.

Binääripuulla voidaan käyttää vain inorder-läpikäyntiä. Binääripuulla ei voida käyttää postorder- tai preorder-läpikäyntiä.

Inorder-läpikäyntiä voidaan käyttää vain puilla, joilla on seuraava ominaisuus: jokaisella solmulla on täsmälleen kaksi lasta.

Inorder-läpikäyntiä voidaan käyttää vain binääripuulla. Preorder- ja postorder-läpikäyntiä voidaan käyttää millä tahansa puulla.

Mitätöityminen¶

Kysymys 1

Seuraavassa annetaan väitteitä mitätöinnistä ja erilaisista STL-säiliöista. Mitkä niistä ovat totta?

Kaikilla säiliöillä mitätöidyn iteraattorin käyttö ei aiheuta ongelmia, koska STL-kirjasto tarkistaa aina mitätöidyt iteraattorit.

Joillakin säiliöillä on olemassa operaatioita, jotka voivat aiheuttaa kaikkien iteraattoreiden mitätöinnin.

Jokaiselle säiliölle on olemassa hyvin määritellyt operaatiot, jotka aiheuttavat mitätöityjä iteraattoreita.

On olemassa säiliöitä, joille iteraattorin mitätöintiä ei voi koskaan tapahtua.

Kysymys 2

Mitä voidaan sanoa yleisesti mitätöinnistä ja iteraattoreista, osoittimista ja indekseistä?

Mitätöinti on ongelma vain iteraattoreilla ja osoittimilla. Vektorin tai taulukon indeksin mitätöintiä ei voi tapahtua.

Vain iteraattorin mitätöinti aiheuttaa ohjelman kaatumisen. Mitätöidyt osoittimet tai indeksit aiheuttavat pelkästään ohjelman hidastumisen.

Iteraattorin, osoittimen tai indeksin mitätöinti voi tapahtua vain käytettäessä STL-algoritmia.

On mahdollista kirjoittaa ohjelmia, joissa mitätöintiä ei tapahdu ja ohjelmassa käytetään iteraattoreita ja osoittimia ja indeksejä.

Kysymys 3

Mitä mitätöinti aiheuttaa STL:n säiliötä käytettäessä?

STL-säilön lähdekoodi vioittuu.

Epäsuorat viittaukset joihinkin alkioihin (esim. osoittimet, iteraattorit) muuttuvat käyttökelvottomiksi.

Kaikki säiliön alkiot poistetaan.

Käyttäjän on vaihdettava käyttämänsä C++-kääntäjä.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

Puut

Puu-tietorakenteet

Puiden läpikäynti

Mitätöinti

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Lisäinformaatiota aiheesta:

Viikko07 - Sanasto

Viikkoharjoitusten palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät