TESTING AREA for teachers - real service at plus.tuni.fi

  1. TIE-99001
  2. 1. Kurssin viikon 8 kotitehtävät ja viikolla 9 harjoituksissa tehtävät
  3. 1.2 Kurssiviikolla 9 harjoituksissa tehtävät

Kurssiviikolla 9 harjoituksissa tehtävät

Tehtävä 1

Tässä tehtävässä käytetään esimerkkimnä alla olevaa puuta, jonka juuri on solmu 8.

../_images/puu-lasnavh.png

Jokaisen solmun avain on annettu.

  1. Puussa jokaisella solmulla on uniikki polku juurelle. Esimerkiksi solmun 4 polku juurelle on [ 4, 7, 6, 8 ].

  2. Kaikista kohdan 1. poluista halutaan koota joukko. Voidaan olettaa, että jokaiselle puun solmulle on olemassa datatyyppi Node, jolla on seuraavat ominaisuudet:

    • Node.key = solmun avain (ts. numero, aina positiivinen)

    • Node.parent = solmun vanhemman avain

    • Node.children = säiliö, jossa on solmun lapsien avaimet

    • Node.children.length() on lapsien lukumäärä

    • Juurisolmun tunnistaa siitä, että sen parent = -1

    Kaikki puun Nodet ovat tallessa tietorakenteessa, jonka voi käydä läpi yksi kerrallaan, ja josta löytää helposti avaimen avulla Noden. Kirjoita pseudokoodi, joka kerää yhteen joukkoon polut jokaisesta solmusta juureen. (Huom. Koska kootaan joukkoa, polkujen välisellä järjestyksellä ei ole väliä.)

Tehtävä 2

Missä kohdin alla olevassa koodissa tapahtuu iteraattoreiden mitätöitymisiä? Millä eri tavoin mitätöitymisen voisi estää koodin toivottua toiminnallisuutta muuttamatta?

 1int main()
 2{
 3    std::vector<int> v1;
 4    auto beg1 = v1.begin();
 5    auto end1 = v1.end();
 6
 7    for (int i = 0; i < 10; ++i)
 8    { v1.insert(beg1, i); }
 9
10    std::vector<int>::iterator beg2;
11    std::vector<int>::iterator end2;
12    if (v1.size() > 0)
13    {
14        std::vector<int> v2(beg1, end1);
15        beg2 = v2.begin();
16        end2 = v2.end();
17
18        for (auto i = beg2; i < end1; i = i+2)
19        { v2.erase(i); }
20    }
21
22    std::copy(beg2, end2, beg1);
23}
Posting submission...