Seuraavassa on varsinaisten tulosten jälkeen lisäksi arviointiohjeet, jotka kannattaa lukea ennen välikokeen tutustumistilaisuuteen saapumista.
Terveisin
Ari Korhonen, Jussi Nikander ja Lauri Malmi
Arvosteluun voi tulla tutustumaan 8.4. klo 13-15 neuvotteluhuoneeseen B219. Tutustumistilaisuuteen on ilmoittauduttava Webtopilla.
Review of the first mid-term exam will be held on friday 8th of April at 13-15 (1-3 pm) in room B219 of the CS-building. Register for the review session through Webtopi.
Arvosanarajat varmistuvat toisen välikokeen jälkeen.
Grading will be published after the second mid-term exam.
| Pisteet / Points | Arvosana / Grade |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |
Kohta et tarkoittaa esitentin tekemisestä saatuja pisteitä.
opnro et #1 #2 #3 #4 #5 #yht stuNro pe #1 #2 #3 #4 #5 #tot ------------------------------------------------------------ 45372a 0 4 1 0 0 5 10 49302u 3 5 6 3 10 6 33 49507p 3 5 6 8 8 8 38 49531v 3 7 6 6 8 9 39 51131c 3 5 4 3 8 4 27 51723f 0 4 6 0 9 9 28 52472r 0 3 6 0 4 4 17 53512k 0 0 5 0 6 4 15 53668p 3 4 4 0 9 5 25 53749v 3 8 6 10 8 9 44 53881u 3 5 6 2 7 10 33 53910j 3 5 5 2 8 4 27 53916r 3 4 6 2 10 10 35 53960a 3 5 6 0 6 7 27 54827p 0 6 6 10 9 9 40 55209s 3 5 6 6 9 10 39 55460w 3 6 6 1 5 4 25 56375c 3 6 4 1 5 10 29 56748s 3 4 6 0 7 10 30 57190a 3 2 6 0 9 4 24 57718t 0 2 6 0 6 9 23 57722a 3 0 6 0 7 4 20 58040s 0 3 5 0 0 4 12 58151n 3 5 6 4 9 9 36 58165h 3 5 5 2 6 6 27 58181d 0 3 0 5 9 8 25 58189n 3 7 6 0 6 6 28 58317h 0 2 5 0 7 4 18 58455n 3 2 0 1 5 6 17 59784m 3 1 6 3 3 8 24 59827t 0 4 6 2 7 8 27 60092s 3 4 5 2 8 9 31 60464h 3 6 5 2 10 9 35 60581l 3 7 6 0 8 10 34 60727d 0 0 0 0 0 0 0 60735n 3 6 6 8 10 9 42 60966s 3 7 5 4 6 8 33 60992c 0 3 0 0 7 8 18 61026v 3 5 6 3 9 6 32 61117r 0 5 6 7 9 10 37 61406v 3 5 6 1 9 1 25 61584f 3 7 5 7 9 9 40 61611r 0 4 6 0 9 10 29 62480k 0 4 2 0 6 9 21 62692n 3 7 6 2 10 8 36 62696t 3 3 6 5 9 2 28 62727k 3 3 2 0 0 4 12 62736v 3 3 6 2 4 6 24 62739b 3 7 5 0 8 10 33 62758b 0 5 6 0 8 9 28 62810t 3 4 5 3 5 5 25 62820h 3 3 6 6 9 10 37 62833a 3 6 6 1 7 10 33 62844n 3 5 6 3 10 9 36 62855d 3 3 6 0 9 5 26 62903r 3 5 6 5 10 10 39 62937l 3 7 4 0 6 7 27 62960r 3 8 6 2 6 10 35 63013l 3 5 5 1 7 5 26 63014m 3 5 6 2 9 4 29 63058u 3 5 5 2 8 10 33 63060w 3 5 6 0 4 10 28 63064d 3 5 5 0 7 9 29 63070l 0 7 5 0 7 10 29 63177c 3 6 5 5 10 10 39 63246s 0 1 6 0 4 10 21 63266t 3 2 6 0 6 9 26 63285t 3 1 0 0 0 0 4 63306v 3 7 6 6 9 10 41 63402w 3 3 6 0 9 4 25 63416r 0 7 6 8 8 10 39 63442b 3 7 5 3 9 8 35 63493s 3 6 4 2 5 9 29 63527m 3 5 4 0 5 9 26 63589t 3 2 5 0 4 4 18 63591v 3 8 6 2 10 10 39 63634d 3 3 4 0 7 10 27 63672d 3 3 6 3 7 4 26 63725w 3 3 6 2 10 4 28 63737n 3 5 5 6 10 10 39 63768e 3 5 6 2 4 4 24 63826f 3 8 5 2 10 9 37 63827h 3 5 5 4 9 9 35 63860b 0 4 2 2 0 7 15 64156p 3 6 6 5 9 10 39 64401m 3 3 3 0 5 5 19 64425t 3 6 6 5 8 10 38 64450c 0 3 5 3 8 8 27 64475k 0 7 6 2 8 10 33 64527d 3 3 6 7 9 10 38 64587h 0 4 5 6 9 9 33 64611n 3 5 5 2 7 9 31 64631p 3 7 5 8 9 9 41 64647l 3 5 2 7 7 10 34 64683j 3 1 5 1 3 8 21 64756e 3 4 6 0 0 5 18 64843t 3 6 6 1 10 6 32 64844u 3 6 6 2 10 10 37 64860r 3 1 1 1 0 4 10 65037a 0 6 5 1 8 9 29 65025j 3 6 5 5 9 10 38 65095b 0 5 5 2 9 10 31 65108s 0 5 5 0 6 4 20 65194f 0 6 6 9 9 10 40 65230d 0 3 4 0 10 8 25 76516d 3 8 4 6 10 7 38 76906r 3 7 6 5 9 9 39 lkm: paperin lukumäärä kumul: kumulatiivinen lukumäärä %-osuus: kumulatiivinen osuus kaikista papereista # lkm kumul %-osuus ----------------------------------- 0 1 1 0.9 : * 1 0 1 0.9 : 2 0 1 0.9 : 3 0 1 0.9 : 4 1 2 1.9 : * 5 0 2 1.9 : 6 0 2 1.9 : 7 0 2 1.9 : 8 0 2 1.9 : 9 0 2 1.9 : 10 2 4 3.7 : ** 11 0 4 3.7 : 12 2 6 5.6 : ** 13 0 6 5.6 : 14 0 6 5.6 : 15 2 8 7.5 : ** 16 0 8 7.5 : 17 2 10 9.3 : ** 18 4 14 13.1 : **** 19 1 15 14.0 : * 20 2 17 15.9 : ** 21 3 20 18.7 : *** 22 0 20 18.7 : 23 1 21 19.6 : * 24 4 25 23.4 : **** 25 7 32 29.9 : ******* 26 5 37 34.6 : ***** 27 8 45 42.1 : ******** 28 6 51 47.7 : ****** 29 7 58 54.2 : ******* 30 1 59 55.1 : * 31 3 62 57.9 : *** 32 2 64 59.8 : ** 33 8 72 67.3 : ******** 34 3 75 70.1 : *** 35 5 80 74.8 : ***** 36 3 83 77.6 : *** 37 4 87 81.3 : **** 38 4 91 85.0 : **** 39 9 100 93.5 : ********* 40 3 103 96.3 : *** 41 2 105 98.1 : ** 42 1 106 99.1 : * 43 0 106 99.1 : 44 1 107 100.0 : *
opnro et #1 #2 #3 #4 #5 #yht stuNro pe #1 #2 #3 #4 #5 #tot ------------------------------------------------------------ 27416w 3 1 0 0 0 6 10 36152s 0 8 8 0 6 4 26 45421n 3 5 5 0 1 4 18 45626j 0 3 7 0 5 4 19 47610t 3 5 0 0 10 5 23 50353d 3 7 5 0 8 6 29 51207c 0 7 7 0 9 9 32 51223w 0 6 8 2 8 10 34 51224a 3 3 4 0 7 7 24 51233l 3 5 8 3 8 10 37 51397c 3 3 1 0 4 7 18 51457f 0 5 8 0 7 5 25 51659v 0 4 8 0 5 9 26 52262p 3 6 8 4 10 10 41 52983n 0 6 4 1 6 7 24 52299n 3 3 6 4 5 4 25 53013d 3 5 4 0 6 6 24 53606j 0 4 7 0 6 10 27 53969l 0 3 0 0 6 8 17 54232h 3 4 8 0 5 9 29 54250f 3 5 1 1 5 9 24 54295p 0 5 6 0 6 6 23 54366j 3 7 5 0 8 6 29 54538k 3 4 6 1 5 8 27 54570c 3 4 8 1 7 7 30 54635m 0 8 8 5 10 8 39 54649f 3 5 8 2 9 9 36 54724e 3 2 1 0 7 4 17 54750n 0 6 7 2 9 10 34 54823k 0 3 0 0 4 6 13 54911b 0 6 8 0 8 9 31 54950c 0 8 6 2 7 7 30 54975k 0 6 1 2 9 10 28 55170r 3 4 5 1 9 8 30 55310b 3 8 8 2 6 4 31 55340p 0 4 6 1 6 4 21 55344u 3 5 5 2 9 4 28 56378f 0 2 6 1 1 4 14 55445d 0 3 5 0 5 4 17 55448h 3 7 8 4 8 9 39 55484e 3 6 1 2 6 7 25 55503e 3 8 8 0 8 4 31 55514t 3 6 8 4 9 6 36 55561f 3 5 8 2 7 6 31 55698l 0 3 8 0 5 9 25 55746a 3 8 7 2 10 9 39 57213e 3 4 5 0 8 4 24 57297p 0 5 2 0 9 4 20 57508s 3 4 8 5 10 4 34 57534c 3 4 6 2 6 10 31 57355r 3 6 7 0 7 10 33 57590b 0 6 8 3 10 10 37 57665a 3 3 0 0 5 4 15 57676n 3 5 6 1 6 7 28 57747h 0 8 8 6 10 8 40 57750l 0 4 6 0 7 5 22 57759w 0 4 4 0 6 2 16 57766h 3 6 7 1 8 6 31 57806k 3 7 8 3 8 5 34 57811r 0 4 7 0 4 7 22 57830r 3 6 7 6 8 10 40 57897e 3 5 6 1 7 8 30 57902l 3 7 8 2 8 10 38 57905p 3 8 5 2 9 5 32 57922m 3 7 6 2 4 8 30 57931a 0 8 6 2 10 4 30 57954e 3 5 6 1 8 10 33 57965t 3 8 7 2 8 8 36 57971c 3 8 8 5 9 10 43 57997l 3 5 5 0 6 8 27 58000p 3 4 6 1 7 8 29 58037n 0 8 6 1 9 8 32 58039r 0 0 0 0 0 4 4 58058r 3 6 7 4 9 9 38 58099u 3 7 8 5 7 10 40 58107f 3 1 6 0 7 9 26 58131m 3 5 8 3 9 9 37 58133p 3 4 7 3 5 10 32 58146h 3 3 3 0 8 6 23 58188m 3 7 8 0 7 7 32 58221f 3 3 5 0 7 4 22 58282l 3 7 8 5 10 10 43 58298h 3 7 8 2 7 8 35 58299j 3 4 8 4 10 9 38 58321m 3 4 4 1 7 4 23 58349a 3 7 8 4 10 10 42 58364t 3 6 4 1 5 9 28 58393h 3 6 8 6 10 9 42 58400r 3 6 6 3 8 6 32 58418p 3 8 8 5 10 9 43 58432j 3 6 8 4 8 10 39 58467e 3 7 7 2 5 8 32 58478t 3 4 6 0 8 9 30 58480v 0 7 8 5 9 9 38 58490k 0 6 8 5 9 8 36 58493n 3 8 7 1 9 10 38 58498u 0 4 8 0 6 9 27 58533r 3 6 8 6 9 9 41 58538w 3 6 5 2 10 6 32 58647r 3 7 5 5 8 9 37 58654b 3 8 7 5 9 10 42 58655c 0 6 8 4 7 8 33 58668t 3 5 6 2 8 10 34 59932h 0 4 5 0 9 7 25 60059a 3 6 4 0 10 8 31 60066j 0 6 6 1 8 9 30 60067k 3 2 6 1 5 10 27 60116a 3 3 0 2 5 9 22 60251c 0 6 8 3 7 9 33 60278m 3 4 8 4 8 8 35 60289c 3 1 5 0 5 4 18 60316m 3 4 7 3 8 7 32 60328d 3 4 6 3 8 9 33 60342v 0 7 5 1 7 5 25 60368f 3 3 7 0 5 6 24 60402b 0 4 6 0 5 10 25 60405e 3 6 8 2 8 9 36 60424e 3 3 0 0 8 1 15 60438w 3 7 8 3 5 7 33 60444f 3 5 6 0 8 7 29 60458a 0 4 8 0 8 10 30 60521h 3 4 0 0 5 9 21 60582m 3 6 6 0 6 8 29 60584p 3 6 6 0 6 9 30 60636j 3 5 7 5 7 10 37 60640n 3 5 6 3 7 6 30 60649b 0 7 5 0 6 4 22 60666w 3 8 8 3 8 8 38 60678n 3 8 8 6 9 9 43 60721u 0 6 8 5 8 10 37 60730h 3 7 8 6 10 9 43 60738s 3 6 7 2 8 9 35 60745c 3 7 2 2 6 8 28 60759u 3 3 0 0 6 5 17 60762a 3 8 7 2 9 7 36 60806h 3 6 8 2 10 8 37 60828l 0 5 5 4 7 9 30 60854u 3 4 6 1 8 5 27 60874v 0 6 5 1 9 4 25 60890s 3 5 4 2 9 7 30 60893v 3 3 6 4 9 8 33 60909s 3 5 6 0 9 9 32 60945p 3 5 7 0 5 8 28 60973c 0 7 6 0 6 2 21 60985s 3 6 4 0 7 2 22 60989w 3 7 8 5 8 8 39 61008w 3 5 6 3 6 8 31 61035j 3 6 1 1 8 6 25 61039n 3 5 5 3 9 9 34 61075l 3 4 4 0 7 5 23 61084w 3 4 6 1 6 6 26 61085a 3 4 0 0 7 4 18 61092j 3 4 8 1 10 9 35 61108e 3 5 8 2 7 10 35 61114m 3 8 8 6 10 10 45 61126d 3 2 4 0 8 0 17 61127e 0 6 5 0 5 9 25 61223f 3 3 5 0 8 2 21 61227l 3 5 6 1 7 7 29 61244j 0 5 6 3 5 7 26 61252t 3 6 8 3 7 9 36 61275a 3 7 6 2 6 7 31 61297d 3 8 6 2 7 10 36 61328t 3 7 6 0 6 7 29 61352b 3 4 8 5 10 9 39 61360l 3 4 6 0 8 8 29 61368v 3 5 6 3 10 5 32 61383r 0 6 8 5 8 10 37 61393e 3 2 6 0 5 7 23 61395h 0 4 3 0 2 1 10 61415j 3 4 6 0 9 10 32 61430d 3 6 7 0 7 9 32 61547h 3 6 6 0 8 4 27 61603f 3 1 5 0 9 7 25 62426n 0 1 7 1 1 7 17 62581s 0 5 8 2 8 5 28 62708k 3 7 5 0 7 8 30 62725h 3 6 6 2 5 9 31 62785l 3 2 6 0 2 4 17 62790s 0 8 5 1 7 10 31 62893d 3 3 6 0 6 2 20 62944u 3 8 7 0 6 9 33 62953h 3 6 6 3 9 9 36 63020u 3 6 4 1 7 8 29 63082c 3 4 8 5 10 10 40 63094s 0 5 4 2 5 8 24 63100b 3 3 5 0 8 4 23 63223m 3 4 7 2 8 9 33 63254d 3 3 7 0 8 5 26 63276h 3 6 0 4 6 8 27 63277j 3 8 4 0 9 10 34 63290b 0 2 4 0 0 4 10 63301p 3 6 6 2 5 8 30 63321r 0 7 8 3 5 10 33 63333h 3 2 0 0 3 8 16 63340r 0 5 7 2 6 6 26 63501d 3 8 8 3 8 8 38 63511r 3 7 5 1 7 2 25 63522f 3 4 4 1 9 6 27 63528n 3 3 6 1 6 10 29 63738p 3 2 5 0 3 4 17 63764a 3 5 5 5 9 9 36 63828j 3 6 7 2 4 8 30 63897a 3 7 8 2 9 10 39 63908n 3 4 6 1 10 4 28 64363m 3 3 4 0 3 5 18 64897p 3 2 6 0 0 4 15 65136e 3 5 8 4 7 6 33 65146s 3 7 7 4 7 9 37 65147t 3 6 8 5 7 9 38 65214h 3 5 7 0 9 10 34 71741u 0 3 0 1 6 4 14 76494a 3 7 5 3 9 4 31 76520j 3 2 1 2 4 7 19 76753p 0 8 8 2 10 8 36 76982r 3 4 6 1 7 5 26 lkm: paperin lukumäärä kumul: kumulatiivinen lukumäärä %-osuus: kumulatiivinen osuus kaikista papereista # lkm kumul %-osuus ----------------------------------- 0 0 0.0 : 1 0 0.0 : 2 0 0.0 : 3 0 0.0 : 4 1 1 0.5 : * 5 0 1 0.5 : 6 0 1 0.5 : 7 0 1 0.5 : 8 0 1 0.5 : 9 0 1 0.5 : 10 3 4 1.9 : *** 11 0 4 1.9 : 12 0 4 1.9 : 13 1 5 2.3 : * 14 2 7 3.2 : ** 15 3 10 4.6 : *** 16 2 12 5.6 : ** 17 8 20 9.3 : ******** 18 5 25 11.6 : ***** 19 3 28 13.0 : *** 20 1 29 13.4 : * 21 4 33 15.3 : **** 22 6 39 18.1 : ****** 23 7 46 21.3 : ******* 24 7 53 24.5 : ******* 25 12 65 30.1 : ************ 26 8 73 33.8 : ******** 27 9 82 38.0 : ********* 28 8 90 41.7 : ******** 29 11 101 46.8 : *********** 30 16 117 54.2 : **************** 31 12 129 59.7 : ************ 32 13 142 65.7 : ************* 33 11 153 70.8 : *********** 34 8 161 74.5 : ******** 35 5 166 76.9 : ***** 36 11 177 81.9 : *********** 37 9 186 86.1 : ********* 38 8 194 89.8 : ******** 39 7 201 93.1 : ******* 40 4 205 94.9 : **** 41 2 207 95.8 : ** 42 3 210 97.2 : *** 43 5 215 99.5 : ***** 44 0 215 99.5 : 45 1 216 100.0 : *
Tehtävä 1: [T-kurssi] (2p + 2p + 4p): Algoritmianalyysi.
a) Jos algoritmin pahimman tapauksen aikavaatimus on Ω(2N), sen toiminnasta erilaisilla syötteillä ei tiedetä paljoakaan. Parhaassa ja keskimääräisessä tapauksessa algoritmi saattaa toimia polynomisessa ajassa, mutta siitä ei tietenkään ole mitään takeita (1p). Toisaalta algoritmilla on jokin syöte (pahin tapaus), jolla se ei ainakaan toimi polynomisessa ajassa (1p).
b) Matemaattisen algoritmianalyysin perustelluista hyvistä ja huonoista puolista saa tässä molemmista yhden pisteen. Luentokalvoissa on annettu esimerkkeinä (perustelu suluissa) mm. "+ riippumaton syöteaineiston laadusta (etsitään esim. pahinta tapausta, jolloin voidaan analysoida vertailukelpoinen aikakompleksisuuden yläraja mille tahansa syötteelle)", "+ riippumaton toteutuksesta (toteutus vaikuttaa suoritukseen vain kertoimen verran)", "- tulokset voivat olla epäkäytännöllisiä (pahin tapaus voi esiintyä harvoin/esim. "parhaan" ylärajan löytäminen voi olla hankalaa)" ja "- voi johtaa analyyttisesti vaikeisiin ongelmiin (kaikkia algoritmeja ei ole kyetty analysoimaan analyyttisesti (ns. tiukka yläraja on tuntematon))".
c) Valintajärjestämisalgoritmi: vertailuja (N-1) + (N-2) + (N-3) + ... + 1 = Σk=1..N-1(k) = (N-1)*N/2 kpl (1p); vaihtoja N-1 kpl (1p); parhaan tapauksen (parhaassakin tapauksessa tehdään O(N2) vertailua) aikavaatimus O(N2) (1p); pahimman tapauksen aikavaatimus O(N2) (1p).
Tehtävä 1: [Y-kurssi] (2p + 2p + 2p + 2p): Käsitteistöä. Tehtävänannossa pyydettiin määrittelemään käsite sekä antamaan esimerkki. Oikeasta määrittelystä sai 1p ja esimerkistä 1p. Tehtävässä oli 4 kohtaa, joista jokaisesta sai max. 2p, yhteensä siis max. 8p.
Tehtävä 2: Binäärikeko (3p + 3p + [2p]). Tehtävässä piti a) lisätä annetut alkiot binäärikekoon ja b) poistaa sen jälkeen keosta kolme alkiota piirtämällä välivaiheet. Pisteytys: a) 3p edellytettiin virheetön suoritus. Virheistä (esim. väärä kekoehto tai yksittäiset huolimattomuusvirheet kuten jonkin alkion lisäämättä jättäminen) vähennettiin jokaisesta 0.5p (pyöristys lopullisissa pisteissä ylöspäin);
b) jokaisesta oikein menneestä poistosta 1p.
c) [Y-kurssi] Analyysin lopputulos O(log N) 1p; perustelusta (jokainen lisäys tekee korkeintaan täydellisen binääripuun korkeuden h = O(log(N)) verran vaihtoja, kun alkiolle etsitään paikkaa keosta, jonka koko on N) 1p
Tehtävä 3: Valikointi ja mediaanin etsintä (2p + 4p + [4p]).
a) Oikea määritelmä (etsitään k:nneksi pienintä/suurinta alkiota) 1p; esimerkki (esim. jos k=N/2 on kyseessä mediaanin etsintä) 1p
b) Mediaani voidaan löytää lukuisilla eri menetelmillä (luennoilla on käsitelty useita menetelmiä, joissa käytetään prioriteettijonoa sekä quickselect-menetelmä), joiden ymmärrettävästä selityksestä (= selitys, jonka perusteella menetelmä voidaan analysoida) sai 2p. Oikeasta, mutta hieman puutteellisesta selityksestä (esim. oppikirjassa mainitun menetelmän pelkkä nimeäminen) sai 1p. Tehtävässä pyydettiin erityisesti menetelmiä, jotka eivät perustu aineiston järjestämiseen, joten esim. valintajärjestämisestä (järjestetään puoleen väliin) sai vain yhden pisteen.
c) [T-kurssi] Analysoitavana oli 3 menetelmää, joista järjestäminen vie O(Nlog(N)) ajan, jos käytössä on jokin tehokas menetelmä tai O(N2), jos käytössä on jokin perusmenetelmä. Prioriteettijonon avulla rakenne voidaan alustaa lineaarisessa ajassa (binäärikeko), jonka jälkeen mediaani voidaan löytää poistamalla puolet keon alkioista ajassa (N/2)*log(N) eli päästään aikavaatimukseen N + Nlog(N)/2 = O(Nlog(N)). Quickselect-algoritmi toimii keskimäärin (tai parhaassa tapauksessa) lineaarisessa ajassa, koska sen tarvitsee jokaisella rekursiokutsulla partitioida vain puolet käsiteltävästä alueesta. Em. analyyttisistä tuloksista (tai vastaavasti muiden menetelmien analyyseistä) sai jokaisesta 1p. Tehtävässä pyydettiin myös vertailemaan menetelmiä keskenään, josta sai 1p jos päätyi suosittelemaan esim. quickselect-algoritmia, koska se on tehokkain.
Tehtävä 4: Järjestäminen (3*3p + 1p). Seuraavassa taulukossa on tiivistelmä oikeasta vastauksesta (3*3 = 9 kohtaa á 1p, yhteensä 9p).
| Kriteeri | Lisäysjärjestäminen | Kekojärjestäminen | Lomitusjärjestäminen |
| Stabiili | Kyllä | Ei | Kyllä |
| Rekursiivinen | Ei | Ei | Kyllä |
| Ylimääräinen muistitila | Ei | Ei | Kyllä (O(N)) |
Johtopäätös: näistä menetelmistä vain lisäysjärjestäminen täyttää kaikki kolme kriteeriä (stabiili, ei-rekursiivinen, eikä tarvitse ylimääräistä muistitilaa). 1p
Tehtävä 5: Puiden läpikäynti; 4p + 6p.
a) Piste jokaisesta oikeasta yhdistelystä.
b) Alla esimerkki oikeasta ratkaisusta
0 Preorder(root) 1 S.push(root) 2 while (S.notEmpty()) do 3 next = S.pop() 4 visit(next) 5 if (next->right != NULL) S.push(next->right) 6 if (next->left != NULL) S.push(next->left)
Pisteytys: algoritmi saa syötteenään puun juuren 1p; lähtösolmu laitetaan pinoon 1p; käydään läpi silmukassa (ei rekursiivisesti) solmuja, kunnes pino on tyhjä 1p; poistetaan aina pinon päällimmäinen solmu ja vieraillaan/tulostetaan solmu 1p; alipuiden käsittely (työnnetään pinoon lapset järjestyksessä oikea, vasen) 1p. Huolehditaan myös tyhjien alipuiden käsittelystä 1p. Rekursiivisesta toteutuksesta (joka kutsuu itseään ensin vasemmalle ja sen jälkeen oikealle alipuulle) voi saada max. 4p.