Simon Fraser University
Computing Science 225
Fall 2019
Midterm Examination 2
Time: 50 minutes
Circle the campus you attend most often: Burnaby Surrey Vancouver
Last/Family Name (please, print):
First Name (please, print):
Student Number:
Signature:
Instructor: Anne Lavergne
# Marks
This examination has 7 pages.
No books, cheat sheets, calculators, computers, Part 1
cell phones, or other materials may be used.
/ 24
Q. 1 to 12
Read each question carefully before answering it.
Part 2
/ 4
List any assumptions you make when answering a Q. 1
question.
Part 2
ADT means Abstract Data Type. / 8
Q. 2
BST means Binary Search Tree.
Part 2
Always comment your code. / 8
Q. 3
The marks for each question are given in [ ].
Use this to manage your time: Part 2
1 mark corresponds to 1 minute of work. / 6
Q. 4
Do not spend more time on a question
than the number of marks assigned to it.
Total / 50
Good luck!
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:12:35 GMT -05:00
https://www.coursehero.com/file/58846898/Cmpt225-MidTerm-2-Fall-2019-SOLUTIONpdf/
, Name Student Number
Part 1 – [2 marks each – No part marks!] Answer each question in its box.
1. In our Assignment 3, we were introduced to the exception throwing mechanism of C++.
List all the files used in this assignment in which we would be expecting to find
try/catch block statements?
BankSimApp.cpp
PriorityQueue.h
(Queue/BinaryHeap/PriorityQueue Test Drivers – but these files are not officially part of
Assignment 3 – Bank Simulation as they as testing tools)
2. Imagine a List ADT class implemented as follows:
class List {
private:
unsigned int arraySize;
Patient * elements;
public:
/* Public method declarations here. */
/* There are no public attributes. */
}
Using the Big O notation, express the time efficiency of determining the number of
elements stored into an object of this List ADT class.
O(n)
Since there is no “elementCount” data member, in order to determining the number of
elements stored into an object of this List ADT class, one would have to traverse the List
object, counting each element.
3. Consider a Binary Search Tree ADT class. Using the Big O notation, express the space
efficiency of the worst case scenario of its insertion if this operation is implemented
recursively.
O(n)
The worst case scenario of a BST is a degenerate BST (long linked list).
Therefore, the worst case scenario of its insertion operation is O(n) in which one would have
to go all the way down to the leaf level in order to insert an element.
If this insertion is recursively implemented (called at each level of the BST), there will be a
stack frame (stack memory) associated with each call made to this recursive insertion
method (given to each execution of this method) -> O(n) stack frames.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:12:35 GMT -05:00 Page 2 of 7
https://www.coursehero.com/file/58846898/Cmpt225-MidTerm-2-Fall-2019-SOLUTIONpdf/
Computing Science 225
Fall 2019
Midterm Examination 2
Time: 50 minutes
Circle the campus you attend most often: Burnaby Surrey Vancouver
Last/Family Name (please, print):
First Name (please, print):
Student Number:
Signature:
Instructor: Anne Lavergne
# Marks
This examination has 7 pages.
No books, cheat sheets, calculators, computers, Part 1
cell phones, or other materials may be used.
/ 24
Q. 1 to 12
Read each question carefully before answering it.
Part 2
/ 4
List any assumptions you make when answering a Q. 1
question.
Part 2
ADT means Abstract Data Type. / 8
Q. 2
BST means Binary Search Tree.
Part 2
Always comment your code. / 8
Q. 3
The marks for each question are given in [ ].
Use this to manage your time: Part 2
1 mark corresponds to 1 minute of work. / 6
Q. 4
Do not spend more time on a question
than the number of marks assigned to it.
Total / 50
Good luck!
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:12:35 GMT -05:00
https://www.coursehero.com/file/58846898/Cmpt225-MidTerm-2-Fall-2019-SOLUTIONpdf/
, Name Student Number
Part 1 – [2 marks each – No part marks!] Answer each question in its box.
1. In our Assignment 3, we were introduced to the exception throwing mechanism of C++.
List all the files used in this assignment in which we would be expecting to find
try/catch block statements?
BankSimApp.cpp
PriorityQueue.h
(Queue/BinaryHeap/PriorityQueue Test Drivers – but these files are not officially part of
Assignment 3 – Bank Simulation as they as testing tools)
2. Imagine a List ADT class implemented as follows:
class List {
private:
unsigned int arraySize;
Patient * elements;
public:
/* Public method declarations here. */
/* There are no public attributes. */
}
Using the Big O notation, express the time efficiency of determining the number of
elements stored into an object of this List ADT class.
O(n)
Since there is no “elementCount” data member, in order to determining the number of
elements stored into an object of this List ADT class, one would have to traverse the List
object, counting each element.
3. Consider a Binary Search Tree ADT class. Using the Big O notation, express the space
efficiency of the worst case scenario of its insertion if this operation is implemented
recursively.
O(n)
The worst case scenario of a BST is a degenerate BST (long linked list).
Therefore, the worst case scenario of its insertion operation is O(n) in which one would have
to go all the way down to the leaf level in order to insert an element.
If this insertion is recursively implemented (called at each level of the BST), there will be a
stack frame (stack memory) associated with each call made to this recursive insertion
method (given to each execution of this method) -> O(n) stack frames.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:12:35 GMT -05:00 Page 2 of 7
https://www.coursehero.com/file/58846898/Cmpt225-MidTerm-2-Fall-2019-SOLUTIONpdf/
