CMPT225-Midterm2-V1 Simon Fraser University CMPT 225

CMPT​ ​225​ ​-​ ​Midterm​ ​2
November​ ​17,​ ​2017
Time:​ ​45​ ​minutes



DO​ ​NOT​ ​begin​ ​until​ ​told​ ​to​ ​do​ ​so.
Fill​ ​in​ ​your​ ​name​ ​and​ ​student​ ​ID​ ​below.
Turn​ ​off​ ​your​ ​phone​ ​and​ ​put​ ​it​ ​in​ ​your​ ​bag.
Keep​ ​your​ ​student​ ​ID​ ​card​ ​on​ ​your​ ​desk​ ​at​ ​all​ ​times.
You​ ​can't​ ​have​ ​anything​ ​other​ ​than​ ​a​ ​pen/pencil​ ​and​ ​your​ ​student​ ​ID​ ​card​ ​on​ ​you​ ​during​ ​the​ ​test.
Before you begin, please check that your exam consists of ​7 ​consecutively numbered questions
and​ ​2​ ​pages​ ​of​ ​appendix.

Read​ ​the​ ​questions​ ​carefully​ ​and​ ​more​ ​than​ ​once.
Good​ ​luck!



NAME:​ ​ ​…………………………………………………………………............

STUDENT​ ​ID: ​ ​ ​ ​…………………………………………………………………



SCORE:



Question Marks


Question​ ​1​ ​(5​ ​marks)

Question​ ​2​ ​(5​ ​marks)

Question​ ​3​ ​(5​ ​marks)

Question​ ​4​ ​(10​ ​marks)

Question​ ​5​ ​(5​ ​marks)

Question​ ​6​ ​(10​ ​marks)

Question​ ​7​ ​(10​ ​marks)

, 1.​ ​Give​ ​the​ ​in-order​ ​traversal​ ​of​ ​the​ ​following​ ​tree​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​(5​ ​marks)




in-order​ ​traversal:
1,​ ​2,​ ​4,​ ​6,​ ​5,​ ​8,​ ​3,​ ​10,​ ​9,​ ​11,​ ​13,​ ​14,​ ​16


2.​ ​True/False?​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​(5​ ​marks)
a.​ ​the​ ​above​ ​tree​ ​is​ ​a​ ​min-heap​ ​ ​F
b.​ ​the​ ​above​ ​tree​ ​is​ ​complete​ ​ ​F
c.​ ​the​ ​above​ ​tree​ ​is​ ​proper​ ​ ​T
d.​ ​the​ ​above​ ​tree​ ​is​ ​a​ ​binary​ ​search​ ​tree​ ​ ​F
e.​ ​the​ ​height​ ​of​ ​the​ ​above​ ​tree​ ​is​ ​5​ ​ ​ ​F

3.​ ​What​ ​will​ ​the​ ​following​ ​heap​​ ​look​ ​like​ ​after​ ​you​ ​insert​ ​17​ ​into​ ​it?​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​(5​ ​marks)