Tietorakenteet ja algoritmit, syksy 2014, 2. välikoe

Tehtävä 1 (5p)

Selitä lyhyesti, millainen tietorakenne on keko. Missä suhteessa se on parempi kuin tasapainoinen binäärihakupuu (esim. AVL-puu) ja missä suhteessa se on huonompi?

Tehtävä 2 (5p)

Ilmoita jokaisesta seuraavasta väitteestä, onko se tosi vai epätosi. Joka kohdasta saat 1p, jos vastaus on oikein, ja -1p, jos vastaus on väärin. Jos et ilmoita mitään, saat 0p kohdasta.

1. Floyd-Warshallin algoritmin aikavaativuus on O(n³), missä n on solmujen määrä.
2. Pikajärjestäminen vaatii, että taulukon alkiot ovat kokonaislukuja.
3. Seuraava on hajautusfunktio:

   int h(String x) {
       int a = x.length();
       return a*a;
   }
   

4. Jos verkko on puu, jokaisen solmun aste on enintään 3.
5. Bellman-Fordin algoritmi on tehokkaampi kuin Dijkstran algoritmi.

Tehtävä 3 (5p)

Näytä, miten Kruskalin algoritmi käsittelee seuraavan verkon:

Tehtävä 4 (5p)

Annettuna on labyrintti, joka muodostuu seuraavista ruuduista:

• # – seinä
• . – lattia
• U – Uolevin sijainti
• M – Maijan sijainti
• H – hirviön sijainti

Ruutuja U, M ja H on tasan yksi ja kaikki reunaruudut ovat seinää.

Joka sekunti Uolevi ja hirviö voivat liikkua yhden askeleen (vasemmalle, oikealle, ylöspäin tai alaspäin) tai pysyä paikallaan. Maija taas pysyy koko ajan paikallaan. Suunnittele algoritmi, joka tarkistaa, onko Uolevilla turvallinen reitti Maijan luokse. Reitti on turvallinen, jos Uolevi sitä seuraamalla ei joudu samaan ruutuun hirviön kanssa, vaikka hirviö liikkuisi miten tahansa.

Esimerkiksi ruudukossa

#############
#.#U#H#.#.#.#
#...........#
#.#########.#
#......M....#
#############

Uolevi pääsee Maijan luokse turvallisesti, mutta ruudukossa

#############
#.#U#.#.#.#H#
#...........#
#.#########.#
#......M....#
#############

tämä ei ole mahdollista.