School

Simon Fraser UniversityDepartment

Computing ScienceCourse Code

CMPT 225Professor

Anne LavergneStudy Guide

MidtermThis

**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