Get 2 days of unlimited access
Study Guides (350,000)
CA (140,000)
SFU (4,000)
CMPT (100)
Midterm

CMPT 225 Study Guide - Midterm Guide: Avl Tree, Boarding Pass, Linked ListExam


Department
Computing Science
Course Code
CMPT 225
Professor
Anne Lavergne
Study Guide
Midterm

This preview shows pages 1-3. to view the full 11 pages of the document.
Simon Fraser University
Computing Science 225
Spring 2019
Midterm Examination
SOLUTION
Time: 45 minutes
Last/Family Name (please, print):
First Name (please, print):
Student Number:
Signature:
Instructor: Anne Lavergne
This examination has 6 pages.
No books, cheat sheets, calculators, computers,
cell phones, or other materials may be used.
Read each question carefully before answering it.
List any assumptions you make when answering a
question.
ADT means Abstract Data Type.
Always comment your code.
The marks for each question are given in [ ].
Use this to manage your time:
1 mark corresponds to 1 minute of work.
Do not spend more time on a question
than the number of marks assigned to it.
Good luck!
#
Marks
Part 1
Q. 1 to 10
/ 20
Part 2
Q. 1
/ 5
Part 2
Q. 2
/ 10
Part 2
Q. 3
/ 10
Total
/ 45

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Name Student Number
Page 2 of 6
Part 1 [2 marks each no part marks] Answer each question either in its right column or below.
1. Express, using the Big O notation, the space efficiency
of the worst case scenario of the insertion operation of a
binary search tree ADT class implemented recursively.
O(n)
2. Assuming a linked list of n nodes, the following C++
code fragment
Node *current = head;
while (current != NULL) {
cout << current->data << endl;
current = current->next;
} // end while
requires _____________ comparison(s).
A. 1
B. n 1
C. n
D. n + 1
E. None of the above.
D. n + 1
3. Imagine a List ADT class implemented as follows:
class List {
private:
static const int SIZE = 1024;
Patient elements[SIZE];
public:
/* Public method declarations here. */
/* There are no public attributes. */
}
Express, using the Big O notation, the time efficiency of
determining the number of elements stored into an object
of this List ADT class.
Since there is no
elementCount attribute
to keep track of the
number of elements, the
time efficiency of
determining the number
of elements stored into
an object of this List
ADT class -> O(n)
where the public method
(perhaps called
getElementCount( ))
would have to iterate
through the array in
order to count the
number of elements.
We also know that the
size of the array is SIZE

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Name Student Number
Page 3 of 6
(1024) and since the
array elements is
statically allocated, its
size would not change.
Therefore, we could also
argue that the maximum
number of elements we
can store in an object of
this List ADT class is
constant at SIZE (1024),
therefore the time
efficiency of determining
the number of elements
stored into an object of
this List ADT class
(worst case scenario, i.e.,
maximum possible
number of elements) ->
O(n) where n = 1024 ->
O(1024) = 1024 O(1) =
O(1)
4. Fill in the blanks with the most appropriate words (1 word per blank):
During the testing step of the software development process,
we implement a test driver for each of our classes. Such
program must call each of a class’ public methods at least
once.
5. Write an array of elements (integers) that would represent simultaneously the worst case
scenario of selection sort as well as the best case scenario of insertion sort. Note that we are
sorting our elements in decreasing sort order.
7 6 5 4 3 2 1 0
Selection sort -> worst case scenario = average case scenario = best
You're Reading a Preview

Unlock to view full version