Education In Pakistan

Papers, Notes, Books & Help For Students

UPDATED EDUCATIONAL NEWS INTERVIEW HELP FOR ALL JOBS ONLINE BOOKS SCHOLARSHIPS AVAILABLE INTERNSHIP JOBS

Tag: VU .CS301-.DATA. STRUCTURE.MIDTERM .EXAMINATION .SEMESTER. FALL. 2003

VU CS301-DATA STRUCTURE MIDTERM EXAMINATION SEMESTER FALL 2003

.

MIDTERM EXAMINATION

Total Marks:86

SEMESTER FALL 2003

CS301-DATA STRUCTURE Duration: 60min

Instructions

Please read the following instructions carefully before attempting any question:

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. Do not ask any questions about the contents of this examination from anyone.

a. If you think that there is something wrong w ith any of the questions, attempt it to the best of your

understanding.

b. If you believe that some essential piece of information is missing, make an appropriate assumption

and use it to solve the problem.

5. Most, but not all, of the examination consists of multiple-choice questions. Choose only one choice as your

answ er.

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.

.

Question No: 1 Marks: 2

Given the class declaration

class MyClass

{

public:

void Func();

private:

int n;

};

what notation does the body of Func use to assign the value 3 to n?

(a) n = 3;

(b) MyClass.n = 3;

(c) MyClass::n = 3;

(d) someObject.n = 3;

(d) It can’t be done–n is private.

Question No: 2 Marks: 2

Suppose that the class declaration of SomeClass includes the following function prototype.

bool LessThan( SomeClass anotherObject );

Which of the following tests in the client code correctly compares two class objects alpha and beta ?

(a) if (alpha < beta)

(b) if (alpha.LessThan(beta))

(c) if (LessThan(alpha, beta))

(d) if (alpha.LessThan.beta)

(e) if (LessThan(alpha).beta)

Question No: 3 Marks: 2

When should you use a const reference parameter?

(a) Whenever the data type might be many bytes.

(b) Whenever the data type might be many bytes, the function changes the parameter within its body, and

you do NOT want these changes to alter the actual argument.

(c) Whenever the data type might be many bytes, the function changes the parameter within its body, and you

DO want these changes to alter the actual argument.

( d) Whenever the data type might be many bytes, and the function does not change the

parameter within its body.

Question No: 4 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?

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

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

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

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

Question No: 5 Marks: 2

The operation for removing an entry from a stack is traditionally called:

(a) delete

(b) peek

(c) pop

(d) remove

Question No: 6 Marks: 2

Which of the following stack operations could result in stack underflow?

(a) is empty

(b) pop

(c) push

(d) Two or more of the above answers

Question No: 7 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 ”?

(a) serc

(b) carpets

(c) steprac

(d) ccaarrppeettss

Question No: 8 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?

(a) At the head

(b) At the tail

(c) After all other entries that are greater than the new entry.

(d) After all other entries that are smaller than the new entry.

Question No: 9 Marks: 2

Given a stack of n items, how many POP and PUSH operations need to be performed to

remove the item at its bottom?

(a) 0 POP operation and 0 PUSH operation

(b) 1 POP operation and 1 PUSH operation

(c) n POP operations and n PUSH operations

(d) n POP operations and n-1 PUSH operations

(e) Unknown

Question No: 10 Marks: 2

In the linked list implementation of the queue class, where does the insert member

function place the new entry on the linked list?

(a) At the head

(b) At the tail

(c) After all other entries that are greater than the new entry.

(d) After all other entries that are smaller than the new entry.

Question No: 11 Marks: 2

.

I have implemented the queue with a linked list, keeping track of a front pointer and a rear

pointer. Which of these pointers will change during an insertion into a NONEMPTY queue?

(a) Neither changes

(b) Only front pointer changes.

(c) Only rear pointer changes.

(d) Both change.

Question No: 12 Marks: 2

I have implemented the queue with a linked list, keeping track of a front pointer and a rear

pointer. Which of these pointers will change during an insertion into an EMPTY queue?

(a) Neither changes

(b) Only front pointer changes.

(c) Only rear pointer changes.

(d) Both change.

Question No: 13 Marks: 6

For public part of the Throttle declaration below, mark each function member header as

follows:

• Mark C for any constructor;

• mark X for any function that is forbidden from changing the throttles data fields.

class Throttle

{

public:

Throttle( );

Throttle(int size);

void shut_off( );

void shift(int amount);

double flow( ) const;

bool is_on( ) const;

Answer/Solution

class Throttle

{

public:

Throttle( ); C

Throttle(int size); C

void shut_off( );

void shift(int amount);

double flow( ) const; X

bool is_on( ) const; X

Question No: 14 Marks: 5

.

I am going to execute this code with THREE pushes and ONE pop:

Stack s;

s.push(1);

s.push(2);

s.push(3);

cout << s.pop( );

Suppose that the stack s is represented by a singly linked list . Draw the linked list after the above

operations and show where the top element is in the list.

head –>

Answer/Solution

head 2 1

Question No: 15 Marks: 10

Complete the body of this function. Use a Queue of characters to store the input line as

it is being read.

int counter( )

// Precondition:

// There is a line of input waiting to be read from cin.

// Postcondition:

// A line of input has been read from cin, up to but not

// including the newline character. The return value of

// the function is the number of times that the LAST

// character of the line appeared somewhere in this line.

// EXAMPLE

// Input: PQQYDYYTY

// The value returned by the function counter would

// be 4 for this input since there are 4 Y’s in

// the input line.

{

int answer = 0;

Queue q;

Answer/Solution

int counter()

{

char a[100];

int i=0;

int answer=0;

Queue q;

cin.getline(a,98,’\n’);

for(i=0;i<strlen(a);i++)

{

q.enqueue(a[i]);

}

i–;

while(!q.isEmpty())

.

{i

f(a[i]==q.dequeue())

{

answer++;

}}

return answer;

}

Question No: 16 Marks: 5

. I am going to execute this code with THREE inserts (enqueue) and ONE remove ( dequeue ):

Queue s;

s.insert(1);

s.insert(2);

s.insert(3);

cout << s.remove( );

Suppose that queue s is represented by a circular array. Draw the state of the private member

variables “ data ” and “front ” of s after the above code:

Answer/Solution

0 1 2 3 4 5 6 7 8 9

2 3 Front 1

Question No: 17 Marks: 10

.

Consider CList and Node classes defined as follows:

class Node

{

public:

Node *next;

Node *prev;

int data;

};

class CList

{

public:

void insertHead(int);

void insertTail(int);

void removeHead();

void removeTail();

bool isEmpty();

bool find(int);

private:

Node *head;

Node *tail;

};

A. write the body of the member function insertHead which inserts a new element at the head

of the list.

void Clist::insertHead( int x )

{

B. write the body of the member function removeTail which removes the element at the tail of

the list.

void Clist::removeTail( int x )

{

Answer/Solution

(a) Solution for Question 17 option (a)

void CList::insertHead( int x)

{

Node *newNode= newNode();

newNode->data=x;

newNode->next=NULL;

newNode->prev=NULL;

if (isEmpty())

head=tail=newNode;

else

{ newNode->next=head;

newNode->prev=NULL;

head->prev=newNode;

head=newNode;

}}

(b) Solution for Question 17 option (b)

void CList::removeTail( int &x)

{

if (isEmpty())

.

return ;

else

{

Node *p=tail;

if (head==tail)

head=tail=NULL;

else

{ tail=tail->prev;

tail->next=NULL;

}

x=p->data;

delete p;

return ;

}}

Question No: 18 Marks: 10

Trace the running of the infix to postfix conversion algorithm on the infix expression

A * (B – C)/D

A * ( B – C ) / D

Symbol Postfix Stack

A A

* A *

( A *(

B AB *(

– AB *(-

C ABC *(-

) ABC- *(

ABC- *

.

/ ABC-* /

D ABC-*D

ABC-*D/

Question No: 19 Marks: 13

Here is a small binary tree:

A. What are all the leaves? (2pts)

C. What are the ancestors of the node 30?(2pts)

D. What are the descendants of the node 11? (2pts)

E. Is the tree a binary search tree (BST) (true/false)? (2pts)

F. Print the tree when visited in in-order manner? (5pts)

Answer/Solution

A) Leaves of the Tree = 1,3,7,40

B) Ancestors of the node 30 = 11,14

C) Descendants of the node 11= 10,30,7,40

D) Is the three a binary search tree (BST) (True/False) False

E) In-order Traversal = 1,2,3,14,7,10,11,30,40

VU CS301-DATA STRUCTURE MIDTERM EXAMINATION SEMESTER FALL 2003

.

MIDTERM EXAMINATION

Total Marks:86

SEMESTER FALL 2003

CS301-DATA STRUCTURE Duration: 60min

Instructions

Please read the following instructions carefully before attempting any question:

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. Do not ask any questions about the contents of this examination from anyone.

a. If you think that there is something wrong w ith any of the questions, attempt it to the best of your

understanding.

b. If you believe that some essential piece of information is missing, make an appropriate assumption

and use it to solve the problem.

5. Most, but not all, of the examination consists of multiple-choice questions. Choose only one choice as your

answ er.

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.

.

Question No: 1 Marks: 2

Is it possible for a member function of a class to activate another member function of the same class?

a. No.

b. Yes, but only public member functions.

c. Yes, but only private member functions.

d. Yes, both public and private member functions can be activated within another member function.

Question No: 2 Marks: 2

Consider this class definition:

class quiz

{

public:

quiz( );

int f( );

int g( ) const;

private:

double score;

};

Which functions can carry out an assignment score=1.0; to the private ember variable score?

a. Both f and g can carry out the assignment.

b. f can carry out the assignment, but not g.

c. g can carry out the assignment, but not f.

d. Neither f nor g can carry out the assignment

Question No: 3 Marks: 2

In C++, when allocating an array of objects, what constructor is used to initialize all of the objects in the

array?

a. The automatic copy constructor.

b. The constructor specified at the declaration.

c. The default constructor.

d. None of the above.

Question No: 4 Marks: 2

The list abstract data type (ADT) is used to work with ordered or unordered sequence of items such as

numbers or strings. What of the following implementation of list ADT is best to answer questions such as

“What is the item at position n?”

a. Lists implemented with an array.

b. Doubly-linked lists.

c. Singly-linked lists.

d. Doubly-linked or singly-linked lists are equally best

Question No: 5 Marks: 5

.

Consider this function declaration:

void quiz(int i)

{ if (

i

1)

{

quiz(i / 2);

quiz(i / 2);

}

cout << “*”;

}

How many asterisks are printed by the function call quiz(5)?

a. 3

b. 4

c. 7

d. 8

e. Some other number

Question No: 6 Marks: 2

Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?

a. 0

b. 3

c. 4

d. 5

Question No: 7 Marks: 2

“Entries in a stack are Ordered”. What is the meaning of this statement?

a. A collection of stacks can be sorted.

b. Stack entries may be compared with the < operation.

c. The entries must be stored in a linked list.

d. There is a first entry, a second entry, and so on.

Question No: 8 Marks: 2

Which of the following applications may use a stack?

a. A parentheses balancing program.

b. Keeping track of local variables at run time.

c. In-order traversal of a binary tree.

d. All of the above.

Question No: 9 Marks: 2

.

When the compiler compiles your program, how is a recursive call treated differently than a non-recursive

function call?

a. Parameters are all treated as reference arguments

b. Parameters are all treated as value arguments

c. There is no duplication of local variables

d. None of the above

Question No: 10 Marks: 2

What is the maximum depth of recursive calls a function may make?

a. 1

b. 2

c. n (where n is the argument)

d. There is no fixed maximum

Question No: 11 Marks: 2

In which location do dynamic variables reside?

a. The code segment.

b. The data segment.

c. The heap.

d. The run-time stack.

Question No: 12 Marks: 2

Select the one FALSE statement about binary trees:

a. Every binary tree has at least one node.

b. Every non-empty tree has exactly one root node.

c. Every node has at most two children.

d. Every non-root node has exactly one parent.

Question No: 13 Marks: 6

he nodes of a binary tree have data 1, 2, 3, 4. The in-order traversal of the tree T yields 2,1,4,3. The

postorder traversal is 2, 4, 3, 1. The root of the tree is at level 0.

Q1: In this binary tree, which value is at the root? (1 Pt)

(A) 1(B) 2 (C) 3 (D) 4 (E) none

Q2: Which value is in the left child of the root? (1 Pt)

(A) 1 (B) 2 (C) 3 (D) 4 (E) none

Q3: Which value is in the right child of the root? (1 Pt)

.

(A) 1 (B) 2 (C) 3 (D) 4 (E) none

Q4: Which value is in a node at level 2 and is the left child of a node at level 1? (1.5 Pt)

(A) 1 (B) 2 (C) 3 (D) 4(E) none

Q5: Which value is in a node at level 2 and is the right child of a node at level 1? (1.5 Pt)

(A) 1 (B) 2 (C) 3 (D) 4(E) none

Question No: 14 Marks: 5

I am going to execute this code with THREE pushes and ONE pop:

Stack s;

s.push(1);

s.push(2);

s.push(3);

cout << s.pop( );

Suppose that the stack s is represented by a fixed-sized array . Draw the state of the private

member variables “ data ” and “top ” of “s ” after the above code:

Answer/Solution

0 1 2 3 4 5 6 7 8 9

1 2 Top1

Question No: 15 Marks: 10

Complete the body of this function. Use a Queue of characters to store the input line as

it is being read.

int counter( )

// Precondition:

// There is a line of input waiting to be read from cin.

// Postcondition:

// A line of input has been read from cin, up to but not

// including the newline character. The return value of

// the function is the number of times that the LAST

// character of the line appeared somewhere in this line.

// EXAMPLE

// Input: ABBXDXXZX The value returned by counter would

// be 4 for this input since there are 4 X’s in

// the input line.

{ int answer =

0;

Queue q;

Answer/Solution

.

int counter()

{c

har a[100];

int i=0;

int answer=0;

Queue q;

cin.getline(a,98,’\n’);

for(i=0;i<strlen(a);i++)

{

q.enqueue(a[i]);

}

i–;

while(!q.isEmpty())

{ if(a[i]==q.dequeue())

{a

nswer++;

}} return answer;

}

Question No: 16 Marks: 5

I am going to execute this code with THREE insert s and ONE remove :

Queue s;

s.insert(1);

s.insert(2);

s.insert(3);

cout << s.remove();

Suppose that s is represented by a singly linked linked list. Draw the linked list and the state of the

private member variables of s after the above code:

front_ptr

rear_ptr

Answer/Solution

2 3

rear_prt

Front_prt

Question No: 17 Marks: 10

.

A list is said to be sortedif the elements are in (say) increasing order, so {1, 2, 3, 3, 4, 4} is sorted whereas

{1, 2, 3, 4, 3, 1} is not. A partial declaration for a singly-linked integer list class that keeps data in sorted

order is as follows:

class Node {

public:

int data;

Node* next;

Node(int d, Node *n)

{

data = d; next = n;

}}

;

class intList

{

public:

// …

// Remove any duplicate elements from the sorted list

void removeDuplicates();

private:

Node* head; // points to the first Node in the list

// …

}; Give an implementation of the function which removes any duplicate removeDuplicates elements from the

sorted list, so, for example {1, 2, 3, 3, 4, 4} would be reduced to {1, 2, 3, 4}.

Answer/Solution

// there a number of ways of doing this. Here is one.

void intList::removeDuplicates()

{

Node* cur = head;

Node *temp;

Node* next = head != NULL? head->next : NULL;

while( next != NULL )

{ // delete next node if it has the same data as current node

if( cur->data == next->data )

{ temp=next;

next = next->next; // cur stays where it is

cur->next=next;

delete temp;;

}e

lse

{c

ur = next; // move to next pair

next = cur->next;

}}}Q

uestion No: 18 Marks: 10

.

Trace the running of the infix to postfix conversion algorithm on the infix expression

A – ( B + C ) / D

Answer/Solution

Symbol Postfix Stack

A A

– A –

( A – (

B AB – (

+ AB – ( +

C ABC – ( +

) ABC+ – (

ABC+ –

/ ABC+ – /

D ABC+D – /

ABC+D/-

Question No: 19 Marks: 13

Here is a small binary tree:

A. What are all the leaves? (2pts)

C. What are the ancestors of the node 10? (2pts)

D. What are the descendants of the node 30? (2pts)

E. Is the tree a binary search tree (BST) (true/false)? (2pts)

F. Print the tree when visited in post-order manner? (5pts)

Answer/Solution

A) Leaves of the tree = 1,3,7,40

B) Ancestors of the node 10 = 11,14

C) Descendants of the node 30 = 40

D) Is the tree a binary search tree (BST) (true/false) False

E) Post Order Traversal = 1,3,2,7,10,40,30,11,14

.

VU CS301-DATA STRUCTURE MIDTERM EXAMINATION SEMESTER FALL 2003

VU CS301-DATA STRUCTURE MIDTERM EXAMINATION SEMESTER FALL 2003

.

MIDTERM EXAMINATION

Total Marks:86

SEMESTER FALL 2003

CS301-DATA STRUCTURE Duration: 60min

Instructions

Please read the following instructions carefully before attempting any question:

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. Do not ask any questions about the contents of this examination from anyone.

a. If you think that there is something wrong w ith any of the questions, attempt it to the best of your

understanding.

b. If you believe that some essential piece of information is missing, make an appropriate assumption

and use it to solve the problem.

5. Most, but not all, of the examination consists of multiple-choice questions. Choose only one choice as your

answ er.

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.

.

Question No: 1 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?

a. Only x and y

b. Only x and z

c. Only y and z

d. None of three the functions.

e. All three functions.

Question No: 2 Marks: 2

What is the common pattern of writing class definitions?

a. Member functions and member variables are both private.

b. Member functions are private, and member variables are public.

c. Member functions are public, and member variables are private.

d. Member functions and member variables are both public.

Question No: 3 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?

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

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

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

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

Question No: 4 Marks: 2

.

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

a. add

b. append

c. insert

d. push

Question No: 5 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 ”?

a. serc

b. carpets

c. steprac

d. ccaarrppeettss

Question No: 6 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?

a. At the head

b. At the tail

c. After all other entries that are greater than the new entry.

d. After all other entries that are smaller than the new entry.

Question No: 7 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.

Question No: 8 Marks: 2

.

I have implemented the queue with a linked list, keeping track of a front pointer and a rear

pointer. Which of these pointers will change during an insertion into a NONEMPTY queue?

a. Neither changes

b. Only front pointer changes.

c. Only rear pointer changes.

d. Both change.

Question No: 9 Marks: 2

I have implemented the queue with a linked list, keeping track of a front pointer and a rear

pointer. Which of these pointers will change during an insertion into an EMPTY queue?

a. Neither changes

b. Only front pointer changes.

c. Only rear pointer changes.

d. Both change.

Question No: 10 Marks: 2

In a single function declaration, what is the maximum number of statements that may be

recursive calls?

a. 1

b. 2

c. n (where n is the argument)

d. There is no fixed maximum

Question No: 11 Marks: 2

What is the maximum depth of recursive calls a function may make?

a. 1

b. 2

c. n (where n is the argument)

d. There is no fixed maximum

Question No: 12 Marks: 2

In which location do dynamic variables reside?

a. The code segment.

b. The data segment.

c. The heap.

d. The run-time stack

Question No: 13 Marks: 6

.

For public part of the Throttle declaration below, mark each function member header as

follows:

• Mark C for any constructor;

• mark X for any function that is forbidden from changing the throttles data fields.

class Throttle

{

public:

Throttle( );

Throttle(int size);

void shut_off( );

void shift(int amount);

double flow( ) const;

bool is_on( ) const;

Answer/Solution

class Throttle

{

public:

Throttle( ); C

Throttle(int size); C

void shut_off( );

void shift(int amount);

double flow( ) const; X

bool is_on( ) const; X

Question No: 14 Marks: 5

I am going to execute this code with THREE pushes and ONE pop:

Stack s;

s.push(1);

s.push(2);

s.push(3);

cout << s.pop( );

Suppose that the stack s is represented by a fixed-sized array . Draw the state of the private

member variables “ data ” and “top ” of “s ” after the above code:

Answer/Solution

0 1 2 3 4 5 6 7 8 9

1 2 Top1

Question No: 15 Marks: 10

.

Complete the body of this function. Use a Queue of characters to store the input line as

it is being read.

int counter( )

// Precondition:

// There is a line of input waiting to be read from cin.

// Postcondition:

// A line of input has been read from cin, up to but not

// including the newline character. The return value of

// the function is the number of times that the LAST

// character of the line appeared somewhere in this line.

// EXAMPLE

// Input: ABBXDXXZX The value returned by counter would

// be 4 for this input since there are 4 X’s in

// the input line.

{

int answer = 0;

Queue q;

Answer/Solution

int counter()

{

char a[100];

int i=0;

int answer=0;

Queue q;

cin.getline(a,98,’\n’);

for(i=0;i<strlen(a);i++)

{

q.enqueue(a[i]);

}

i–;

while(!q.isEmpty())

{i

f(a[i]==q.dequeue())

{

answer++;

}}

return answer;

}

Question No: 16 Marks: 5

.

I am going to execute this code with THREE insert s and ONE remove :

Queue s;

s.insert(1);

s.insert(2);

s.insert(3);

cout << s.remove();

Suppose that s is represented by a singly linked linked list. Draw the linked list and the state of the

private member variables of s after the above code:

front_ptr

rear_ptr

Answer/Solution 2 3

rear_prt

Front_prt

Question No: 17 Marks: 10

Consider CList and Node classes defined as follows:

class Node

{

public:

Node *next;

Node *prev;

int data;

};

class CList

{

public:

void insertHead(int);

void insertTail(int);

void removeHead();

void removeTail();

bool isEmpty();

bool find(int);

private:

Node *head;

Node *tail;

};

A. write the body of the member function insertHead which inserts a new element at the head

of the list.

void Clist::insertHead( int x )

{

B. write the body of the member function removeTail which removes the element at the tail of

the list.

void Clist::removeTail( int x )

{

.

Answer/Solution

(a) Solution for Question 17 option (a)

void CList::insertHead( int x)

{

Node *newNode= new Node();

newNode->data=x;

newNode->next=NULL;

newNode->prev=NULL;

if (isEmpty())

head=tail=newNode;

else

{

newNode->next=head;

newNode->prev=NULL;

head->prev=newNode;

head=newNode;

}

}

(b) Solution for Question 17 option (b)

void CList::removeTail( int &x)

{

if (isEmpty())

return ;

else

{

Node *p=tail;

if (head==tail)

head=tail=NULL;

else

{ tail=tail->prev;

tail->next=NULL;

}

x=p->data;

delete p;

return ;

}

}

Question No: 18 Marks: 10

.

Trace the running of the infix to postfix conversion algorithm on the infix expression

(A – B) + C/D

Answer/Solution

Symbol Postfix Stack

( (

A A (

– A (-

B AB (-

) AB- (

AB-

+ AB- +

C AB-C +

/ AB-C +/

Question No: 19 Marks: 13

Here is a small binary tree:

A. What are all the leaves? (2pts)

C. What are the ancestors of the node 10? (2pts)

D. What are the descendants of the node 30? (2pts)

E. Is the tree a binary search tree (BST) (true/false)? (2pts)

F. Print the tree when visited in post-order manner? (5pts)

Answer/Solution

A) Leaves of the tree = 1,3,7,40

B) Ancestors of the node 10 = 11,14

C) Descendants of the node 30 = 40

D) Is the tree a binary search tree (BST) (true/false) False

E) Post Order Traversal = 1,3,2,7,10,40,30,11,14

Education In Pakistan © 2016