CS301 Midterm Past Paper Fall 2003 Session 2

MIDTERM EXAMINATION · SEMESTER FALL 2003 · CS301-DATA STRUCTURE · Instructions

1. The duration of this examination is 60 Mins.
2. This examination is closed book, closed notes, closed neighbors; any one found cheating will get no grade.
3. Unless stated otherwise, all questions carry a single mark.
4. Most, but not all, of the examination consists of multiple-choice questions. Choose only one choice as your

Answer: a. If you believe that two (or more) of the choices are the correct ones for a particular question, choose the best one. b. On the other hand, if you believe that all of the choices provided for a particular question are the wrong ones, select the one that appears to you as being the least wrong.

7. You are allowed to use any development environment like Dev C++ etc.

Q1. Marks: 2

Here is the start of a class declaration: · class Foo · public: · void x(Foo f); · void y(const Foo f); · void z(Foo f) const;

Which of the three member functions can change the PRIVATE member variables of the Foo

object that activates the function?

1. Only x and y
2. Only x and z
3. Only y and z
4. None of three the functions.

e. All three functions.

Q2. Marks: 2

What is the common pattern of writing class definitions?

1. Member functions and member variables are both private.
2. Member functions are private, and member variables are public.
3. Member functions are public, and member variables are private.
4. Member functions and member variables are both public.

Q3. Marks: 2

The Bag ADT is like the List ADT. The Bag ADT does not store items in any particular

order and it allows duplicates. Suppose that the Bag class is efficiently implemented with a fixed array with a capacity of 4000. Insert appends the new item at the end of the array. Choose the best description of b’s member variables size (count of items in the bag) and data (the array that holds the actual items) after we execute these statements:

Bag b; · b.insert(5); · b.insert(4); · b.insert(6);

What will be the values of b.size and b.data after the statements?

1. b.size is 3, b.data[0] is 4, b.data[1] is 5, b.data[2] is 6
2. b.size is 3, b.data[0] is 5, b.data[1] is 4, b.data[2] is 6
3. b.size is 3, b.data[0] is 6, b.data[1] is 4, b.data[2] is 5
4. b.size is 3, b.data[0] is 6, b.data[1] is 5, b.data[2] is 4

Q4. Marks: 2

The operation for adding an entry to a stack is traditionally called:

a. add · b. append · c. insert · d. push

Q5. Marks: 5

Consider the following pseudo code: · declare a stack of characters · while ( there are more characters in · the word to read ) { · read a character · push the character on the stack · while ( the stack is not empty ) { · pop a character off the stack · write the character to the screen

What is written to the screen for the input “carpets”?

1. serc
2. carpets
3. steprac
4. ccaarrppeettss

Q6. Marks: 2

In the linked list implementation of the stack class, where does the push member function

place the new entry on the linked list?

1. At the head
2. At the tail
3. After all other entries that are greater than the new entry.
4. After all other entries that are smaller than the new entry.

Q7. Marks: 2

One difference between a queue and a stack is:

a. Queues require dynamic memory, but stacks do not. b. Stacks require dynamic memory, but queues do not. c. Queues use two ends of the structure; stacks use only one. d. Stacks use two ends of the structure, queues use only one.