Session activities¶

Aktiviteetit¶

Tehtävässä 1 käytetään alla olevaa puuta. Jokaisen solmun avain on näkyvissä ja puun juuri on 8.

Tehtävä 1a¶

Jokaisesta puun solmusta on olemassa uniikki reitti juureen. Esimerkiksi reitti solmusta, jonka avain on 4 on seuraavan näköinen: { 4, 7, 6, 8 }.

Kirjoita kaikki reitit jokaisesta solmusta juurisolmuun. (9 reittiä)

Tehtävä 1b¶

Tehtävänä on koota joukko, joka sisältää kaikki harjoituksessa 1a annetut polut. Sinulla on pääsy juurisolmuun, ja sinun tulee käyttää kaikkia solmuja lehtiin asti, aloittaen juurisolmusta. Kootut polut tulee kuitenkin alkaa jokaisesta solmusta ja ulottua juurisolmuun asti, kuten harjoituksessa 1a.

Kirjoita pseudokoodi tai C++-koodi, joka kokoaa polut jokaisesta solmusta juureen. (Huom: koska kokoat joukon, polkujen järjestys joukossa ei ole tärkeä.)

Pseudokoodi¶

Voidaan olettaa, että jokaisella puun solmulla on datatyyppi Node, jolla on seuraavat attribuutit:

Node.key = solmun avain
Node.parent = pointteri Node:n vanhempaan tai NIL, jos juuri
Node.children = Node:n kaikki lapset

Voidaan tehdä seuraavat oletukset:

Node.children on joku säiliö, joka sisältää kaikki Node:n lapset.
Node.children.length() Noden:n lapsien lukumäärä.
Root on Node, joka sisältää puun juurisolmun.

C++¶

Vastaavasti kuin pseudokoodissa, voit käyttää seuraavaa C++ structia ja vakioita tehtävässäsi, joka kokoaa polut annetussa tehtävässä 1a.

Kaikki solmut käyttävät seuraavan näköistä structia:

struct Node {
  int key=NO_KEY;
  Node* parent = NO_NODE;
  std::unordered_set<Node*> children = {};
}

Jossa vakiot ovat seuraavat:

int NO_KEY = -1;
Node* NO_NODE = nullptr;

Voit käyttää C++-pohjakoodia, joka on saatavilla: zip-pakkauksena. Koodi sisältää jo Node-rakenteen ja yllä esitetyt vakiot. Se myös luo yllä esitetyn esimerkkipuun. Sinun tarvitsee kirjoittaa vain funktio, joka kokoaa polut.

Tehtävä 2a¶

Tehtävässä 2 harjoitellaan kekorakenteiden käyttöä tietojen ylläpidossa, ja erityisesti sitä, kuinka voidaan ylläpitää tietoa syötesekvenssin mediaanista käyttämällä kahta kekoa. Aloita pohtimalla alkioiden lisäämistä syötesekvenssistä ja seuraa, kuinka mediaani muuttuu jokaisen lisäyksen jälkeen.

Anna seuraavat tiedot jokaisen alkion lisäyksen jälkeen syötesekvenssistä: 5, 6, 7, 4, 2, 1, 11, 12, 13, 14, 15:

Lisätyn alkion arvo.
Onko lisätty arvo pienempi vai suurempi kuin vanha mediaaniarvo.
Uusi mediaaniarvo lisäyksen jälkeen.

Tehtävä 2b¶

Kirjoita pseudokoodi tai C++-koodi, joka ylläpitää tietoa syötesekvenssin mediaanista käyttämällä kahta kekoa. Ratkaisun tulisi toimia tehokkaasti tilanteessa, jossa mediaania pyydetään usein, ja uutta tietoa lisätään mediaanipyyntöjen välissä.

Voit käyttää C++-pohjakoodia, joka on saatavilla: zip .

Seuraavat funktiot saattavat olla hyödyllisiä:

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.