# Education In Pakistan

## VU CS301- Data Structures 2009 MIDTERM EXAMINATION

.

MIDTERM EXAMINATION

CS301- Data Structures 2009

Question No: 1 ( Marks: 1 ) – Please choose one

A subscript of an array may be an integer or an integer expression.

► True

► False

Question No: 2 ( Marks: 1 ) – Please choose one

Doubly Linked List always has one NULL pointer.

► True

► False

Question No: 3 ( Marks: 1 ) – Please choose one

In which of the traversal method, the recursive calls can be used to traverse a binary tree ?

► In preorder traversal only

► In inorder traversal only

► In postorder traversal only

► All of the given options

Question No: 4 ( Marks: 1 ) – Please choose one

A tree is an AVL tree if

► Any one node fulfills the AVL condition

► At least half of the nodes fulfill the AVL condition

► All the nodes fulfill the AVL condition

► None of the given options

Question No: 5 ( Marks: 1 ) – Please choose one

Suppose currentNode refers to a node in a linked list (using the Node class with member

variables called data and nextNode). What boolean expression will be true when cursor refers to

the tail node of the list?

► (currentNode == null)

► (currentNode->nextNode == null)

► (nextNode.data == null)

► (currentNode.data == 0.0)

Question No: 6 ( Marks: 1 ) – Please choose one

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?

► if (alpha < beta)

.

► if (alpha.LessThan(beta))

► if (LessThan(alpha, beta))

► if (LessThan(alpha).beta)

Question No: 7 ( Marks: 1 ) – Please choose one

In C what is the operation that you can not do with primitive types?

► Assign a value to primitive type using a literal

► Declare primitive types to be constant using the Const keyword

► Create a new instance of primitive type with New keyword

► None of these

Question No: 8 ( Marks: 1 ) – Please choose one

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

► append

► insert

► push

Question No: 9 ( Marks: 1 ) – Please choose one

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

► delete

► peek

► pop

► remove

Question No: 10 ( Marks: 1 ) – Please choose one

Consider the following sequence of push operations in a stack:

stack.push(’7’);

stack.push(’8’);

stack.push(’9’);

stack.push(’10’);

stack.push(’11’);

stack.push(’12’);

► 7 8 9 10 11 12

► 9 8 11 10 7 12

► 9 10 8 11 12 7

► 9 10 8 12 7 11

Question No: 11 ( Marks: 1 ) – Please choose one

________ is the maximum number of nodes that you can have on a stack-linked list ?

► Zero

► 2n (where n is the number of nodes in linked list)

► Any Number

► None of these

Question No: 12 ( Marks: 1 ) – Please choose one

Which of the following can be used to reverse a string value,

► Stack

► Queue

.

► Both of these

► None of these

Question No: 13 ( Marks: 1 ) – Please choose one

Consider the following tree,

How many leaves does it have?

► 2

► 4

► 6

► 9

Question No: 14 ( Marks: 1 ) – Please choose one

AVL Tree is,

► Non Linear data structure

► Linear data structure

► Hybrid data structure (Mixture of Linear and Non Linear)

► None of the given options.

Question No: 15 ( Marks: 1 ) – Please choose one

The following are statements related to queues.

(i) The last item to be added to a queue is the first item to be removed

.

(ii) A queue is a structure in which both ends are not used

(iii) The last element hasn’t to wait until all elements preceding it on the queue are removed

(iv)A queue is said to be a last-in-first-out list or LIFO data structure.

Which of the above is/are related to normal queues?

► (iii) and (ii) only

► (i), (ii) and (iv) only

► (ii) and (iv) only

► None of the given options

Question No: 16 ( Marks: 1 ) – Please choose one

An array is a group of consecutive related memory locations.

► True

► False

Question No: 17 ( Marks: 1 )

In which of traversal method, recursion can not be applied.?

Question No: 18 ( Marks: 1 )

What is meant by an empty stack?

Question No: 19 ( Marks: 2 )

Is the following statement correct? If your answer is No, then correct it.

“A tree is an AVL tree if at least half of the nodes fulfill the AVL condition”

Question No: 20 ( Marks: 3 )

The following function is performing some operation on the elements of a singly link list please

tell what this functions is doing,

int result = 0;

while( temp->getNext() != NULL ){

temp = temp->getNext();

int value = temp->get();

if(value % 2 == 0)

{ value ++;

temp->set(value);

}

}

}

.

Question No: 21 ( Marks: 5 )

See the code below , give comments against each line and identify which line will result in error?

1. void main(void)

2. {

3. int actual = 123;

4. int &other = actual;

5.

6. int natural = 456;

7. other = &natural;

8. }

Question No: 22 ( Marks: 10 )

Draw AVL Tree by following digits 78, 21, 25, 28, 38, 36, 75 and also perform necessary

rotation, while showing all the intermediate trees being created in the process. In each

stage, the AVL transformation should be conducted at a discrepancy that is farthest from

the root.

## VU CS301- Data Structures 2009 MIDTERM EXAMINATION

.

MIDTERM EXAMINATION CS301- Data Structures 2009

Time: 60 min

Marks: 38

Question No: 1 ( Marks: 1 ) – Please choose one

Which one of the following statement is NOT correct .

► In linked list the elements are necessarily to be contiguous

► In linked list the elements may locate at far positions in the memory

► In linked list each element also has the address of the element next to it

► In an array the elements are contiguous

Question No: 2 ( Marks: 1 ) – Please choose one

In a program a reference variable, say x, can be declared as

► int &x ;

► int *x ;

► int x ;

► None of the given options

Question No: 3 ( Marks: 1 ) – Please choose one

Linked lists are collections of data items “lined up in a row” , insertions and deletions can

be made only at the front and the back of a linked list.

► True

► False

Question No: 4 ( Marks: 1 ) – Please choose one

A Linear Data Structure is the data structure in which data elements are arranged in a

sequence or a linear list. Which of the following is Non Linear Data Structure?

► Arrays

► Binary Search Trees

► None of these

Question No: 5 ( Marks: 1 ) – Please choose one

A queue where the de-queue operation depends not on FIFO, is called a priority queue

►

►True

Question No: 6 ( Marks: 1 ) – Please choose one

Which one of the following statements is correct?

►Array size is fixed once it is created.

Link List size is fixed► once it is created.

Binary Search Tree size is► fixed once it is created

AVL Tree size is fixed► once it is created

Question No: 7 ( Marks: 1 ) – Please choose one

Which one of the following is correct about pointers?

They always point to► different memory locations

They may point to a single► memory location

.

►The address of two pointer variables is same

None of these►

Question No: 8 ( Marks: 1 ) – Please choose one

Which of the following abstract data types are NOT used by Integer Abstract Data type group?

►short

int►

float►

long►

Question No: 9 ( Marks: 1 ) – Please choose one

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

append►

insert►

►push

Question No: 10 ( Marks: 1 ) – Please choose one

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

delete►

peek►

►pop

remove►

Question No: 11 ( Marks: 1 ) – Please choose one

We can add elements in QUEUE From _________

Front►

►Rear

From Both Rare and Front►

None of these►

Question No: 12 ( Marks: 1 ) – Please choose one

The difference between a binary tree and a binary search tree is that ,

a binary search tree has► two children per node whereas a binary tree can have none, one,

or two children per node

►in binary search tree nodes are inserted based on the values they contain

in binary tree nodes are► inserted based on the values they contain

none of these►

Question No: 13 ( Marks: 1 ) – Please choose one

Suppose n is the number of nodes in a complete Binary Tree then maximum steps required for a

search operation are,

►Log2 (n+1) -1

Log►2 (n+1)

Log►2 (n) – 1

Log►2 (n)

Question No: 14 ( Marks: 1 ) – Please choose one

The following is a segment of a C program.

int pqr(BinaryNode t)

{ if (t == null )

return -1;

.

else

return 1+max(pqr(t.left),pqr(t.right)) }

Identify, what the above program intend(s) to do?

Compute the height of a► binary tree using an in-order traversal

Compute the height of a► binary tree using a pre-order traversal

►Compute the depth of a binary tree using a pre-order traversal

Compute the depth of a► binary tree using a post-order traversal

Question No: 15 ( Marks: 1 ) – Please choose one

Consider the following infix expression:

3 + 5 * 6 – 7 * (8 + 5)

Which of the following is a correct equivalent expression(s) for the above?

► 3 6 5 + * 7 5 8 + – *

► 3 6 5 7 5 8 + * + – *

► 3 5 6 + * 7 8 5 + – *

► 3 5 6 * + 7 8 5 + * –

Question No: 16 ( Marks: 1 ) – Please choose one

An array is a group of consecutive related memory locations.

► True

► False

Question No: 17 ( Marks: 1 )

Is this a correct statement? Give answer in Yes or No.

A node cannot be deleted, when the node to be deleted has both left and right subtrees.

No, it can be deleted.

Question No: 18 ( Marks: 1 )

Deleting a leaf node in binary search tree involves setting ______ pointer/s of that nodes parent

as null.

1

2

3

4

Question No: 19 ( Marks: 2 )

Describe any two uses of priority queues?

Question No: 20 ( Marks: 3 )

How we evaluate postfix expressions?

Question No: 21 ( Marks: 5 )

Following is the while loop used in level-order traversal:

while( !q.empty() )

{

treeNode = q.dequeue();

cout << *(treeNode->getInfo()) << ” “;

if(treeNode->getLeft() != NULL )

q.enqueue( treeNode->getLeft());

if(treeNode->getRight() != NULL )

?

}

What should be the statement to replace the question mark in the loop above:

.

Question No: 22 ( Marks: 10 )

Write a friend function for a Linked List class called mergeLists that takes two non-empty lists,

merge these two lists and return the merged list.

Use the following function prototype:

List mergeLists(List x,List y)