Exam text content

JÄ AEL...
Y

TIE-20100 Tietorakenteet ja algoritmit Tentti 7.9.2015

TIE-20100 Tietorakenteet ja
algoritmit

Tentti 7.9.2015

Terhi Kilamo

Tentissä ei saa käyttää ylimääräistä kirjallista materiaalia, laskimia, tietokoneita tai muita lunttausvälineitä.
Muista vastata kaikkiin tehtäviin.

Kirjoita vastauksesi siistillä käsialalla lyhyesti -
Vääristä vastauksista ei yleisesti vähennetä pisteitä,
itsellään mahdollisuuden antaa miinuspisteitä täysin järjettömistä tai sisäisesti

sista vastauksista (siis selvistä arvauksista).

vastauksia ei arvostella viivoittimella.
mutta tentin tarkastaja pidättää
ristiriitai-

1. a) Selitä lyhyesti käsiteett asymptoottinen analyysi ja amortisoitu ajoaika sekä miten

ne liittyvät toisiinsa. (3p)
b) Kurssilla käytiin läpi algoritmien suunnitteluperiaatteita. Yksi näistä oli hajoita

ja hallitse. Kuvaile suunnitteluperiaate. Selitä lisäksi seuraavaa taulukkoa apunasi

käyttäen, miten joku hajoita ja hallitse -periaatteeseen perustuva algoritmi

järjestää taulukon.

 

11]5 [41]31] 42] 9 [10] 32]

 

 

 

 

 

 

(3P)

(6 p)

binäärihakupuu ja tasapainotettu binäärihakupuu.

2. a) Määrittele binääripuu,
anna esimerkki, miten se voidaan

Perustele, mitä etua tasapainoituksesta on ja
saavuttaan. (3 p)
b) Millainen tietorakenne on hajautustaulu? (3 Pp)

 
 

TIE-20100 Tietorakenteet ja algoritmit Tentti 7.9.2015

3. a) Kelju K. Kojootti on kasaamassa uutta maantiekiitäjäansaansa, kun Kelju
tipauttaa ansassa tarvitut pultit ja mutterit sikin sokin maahan. Miten epäonnen
riivaama kojoottiparka saa pultit ja mutterit löytämään parinsa mahdollisimman
vikkelästi. Kelju voi kokeilla, sopiiko pultti ja mutteri yhteen eli onko mutteri
suurempi kuin pultti, pienempi vaiko sopiva. Kahta pulttia ja kahta mutteria ei
voi vertailla keskenään. Mikä on ratkaisusi tehokkuus kertaluokkamerkinnöillä
esitettynä? (3 p)

Yksi tiedonpakkauksen menetelmä on ns. Huffmanin koodaus, jossa merkkeille
luodaan puumallilla bittiesitykset. Mihin suunnitteluperiaatteeseen oheinen
algoritmi näyttäisi perustuvan?

HUFFMAN ALGORITMI
Askel 1 Alusta jokaiselle merkistön merkille oma yhden solmun puunsa ja

merkitse kyseisen merkin esiintymistiheys merkin puun juureen. Se kertoo

S=

puun painon.

Askel 2 Toista seuraavaa kunnes yksi eheä puu on saatu rakennettua. Etsi kaksi
puuta, joiden painot ovat pienimmät. Tee valitsemistasi puista uuden puun
oikea ja vasen alipuu ja merkitse niiden painojen sunna uuden puun juureen
sen painoksi.

Rakenna Huffmanin koodaus alla olevalle datalle:

merkki = 80 D <
todennäköisyys | 0.4 0.1 0.2 0.15 0.15
ja koodaa merkkijono ABACABAD sen perusteella. (3 p)

(6 p)

4. Pitävätkö seuraavat väittämät paikkansa? (0.5 p/kohta)

irjestyksessä tietorakenteessa.

 

a) Syötteen alkiot kannattaa aina pi
b) Alkioiden järjestäminen on mahdollista tehdä O(n) ajassa.

c) Rengaspuskuri on tapa toteuttaa jono tehokkaasti.

d) Algoritmin muistinkäyttöä voi analysoida asymptoottisesti.

e) Jos algoritmin suoritusaika on kertaluokassa O(n), se on varmasti myös kertaluokassa

O(n?).

f) Jos algoritmin suoritusaika on kertaluokassa 0(n?), se on varmasti myös kertaluokassa
An).

g) Jos algoritmin suoritusaika on kertaluokassa O(nl/ogn), se on varmasti myös kertaluokassa
(log).

h) Jos algoritmin suoritusaika on kertaluokassa O(n), se on varmasti myös kertaluokassa
O(nlogn).

i) Jos algoritmin suoritusaika on kertaluokassa O(n?), se on varmasti myös kertaluokassa
O(n?).

j) Jos algoritmin suoritusaika on kertaluokassa O(n), se on varmasti myös kertaluokassa
An).

k) Jos algoritmin suoritusaika on kertaluokassa 9(logn), se on varmasti myös kertaluokassa
O(logn).

1) Jos algoritmin suoritusaika on kertaluokassa O(nlogn), se on varmasti myös kertaluokassa
O(nlogn). (6 p)

=
5
€
S
S
z

 

A ra 10
 

TIE-20100 Tietorakenteet ja algoritmit Tentti 7.9.2015

5. 4) Olet toteuttamassa uutta labyrintin suunnittelujärjestelmää, jonka avulla voidaan
testata haastelabyrinttien vaikeustasoa. Suunnittele tietorakenne, jolla voisit
esittää labyrintteja. Voit käyttää apunasi C++:n standardikirjastoa. Kuva olisi
kiva. (3 p)

b) Kuvaile hakualgoritmi, joka löytää lyhimmän reitin ulos labyrintista. Kuvaile
myös, miten tilanne muuttuu, kun labyrintin vaikeustasoa kasvatetaan lisäämällä
matkalle kulkua hidastavia haasteita kuten örkkejä ja taikoja. (3 p)

(6 p)