Cmpt225_MidTerm_2_Fall_2019_SOLUTION Simon Fraser University CMPT 225
82 views 0 purchase
Course
CMPT 225
Institution
CMPT 225
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
This examina...
cmpt225midterm2fall2019solution simon fraser university cmpt 225
simon fraser university computing science 225 fall 2019 midterm examination 2 time 50 minutes circle the campus you atte
Written for
CMPT 225
All documents for this subject (9)
Seller
Follow
beckyfawcet
Reviews received
Content preview
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
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
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller beckyfawcet. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.49. You're not tied to anything after your purchase.
