CS301 Midterm Past Solved Paper (1)

MIDTERM  EXAMINATION

Spring 2010

CS301- Data Structures

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   next to it 

       ► In an array the elements are contiguous 

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

 

Each operator in a postfix expression refers to the previous ________ operand(s).

       ► One

       ► Two

       ► Three

       ► Four

p67

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

 

Which one of the following calling methods does not change the original value of the argument in the calling function? 

       ► None of the given options

       ► Call by passing the value of the argument

       ► Call by passing reference of the argument

       ► Call by passing the address of the argument

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 statement changes currentNode so that it refers to the next node?

       ► currentNode ++;

       ► currentNode = nextNode;

       ► currentNode += nextNode;

       ► currentNode = currentNode->nextNode;

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

 

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

       ► False

       ► True

p101

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

 

Which one is a self- referential data type?                                                                    

       ► Stack

       ► Queue

       ► Link list

       ► All of these

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

 

Each node in doubly link list has,

       ► 1 pointer

       ► 2 pointers

       ► 3 pointers

       ► 4 pointers

p39

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

 

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?

       ► Neither changes

       ► Only front pointer changes.

       ► Only rear pointer changes.

       ► Both change.

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

 

Consider the following tree.

How many of the nodes have at least one sibling?

       ► 8

       ► 7

       ► 5

       ► 6

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

 

The nodes with no successor are called _________

       ► Root Nodes

       ► Leaf Nodes  

       ► Both of these

       ► None of these

Question No: 12      ( 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: 13      ( Marks: 1 ) - Please choose one

 

We access elements in AVL Tree in,

       ► Linear way only

       ► Non Linear way only

       ► Both linear and non linear ways

       ► None of the given options.

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

 

A binary search tree should have minimum of one ________ node/s at each level,

       ► One  ( not sure )

       ► Two

       ► Three

       ► Four

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

 

Consider the following statements.

(i)       A binary tree can contain at least 2^L Nodes at level L.

(ii)     A complete binary tree of depth d is a binary tree that contains 2^L Nodes at each level L between 0 and d, both inclusive.

(iii)   The total number of nodes (T_n ) in a complete binary tree of depth d is 2 ^d+1 - 1 .

(iv)   The height of the complete binary tree can be written as h = log ₂ (T_n+1)-1 where T_n is Total number of Nodes.

Which one of the following is correct in respect of the above statements regarding the Binary trees?

       ► (i) and (iii) only

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

       ► (ii) and (iii) only

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

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

 

“+” is a _________operator.

       ► Unary

       ► Binary

       ► Ternary

       ► None of the above

Question No: 17      ( Marks: 2 )

 

What would the state of a stack be after the following operations?

create stack

push A onto stack

push F onto stack

push X onto stack

pop item from stack

push B onto stack

pop item from stack

pop item from stack

                  A Remening On The Stack          

Question No: 18      ( Marks: 2 )

 

What are the applications of Binary Tree.

Question No: 19      ( Marks: 2 )

 

 What is difference between call by reference and call by value?

One application is to find duplicates in a list of numbers.

Let a given list be" 12 34 56 89 33 11 89
the first number in the list is placed in a node that is established as the root of a binary tree. Each number is compared with the node in the root, if the number is larger, we search the right sub-tree else we search the left sub-tree. If the sub-tree is empty, the number is not a duplicate and this will be added as a new node.
2. Binary trees can be used for sorting a given list such that, if we take the first number as root, the numbers less than that number will be transfered to left sub-tree and the greater numbers to right sub-tree.
3. Binary trees are also used for developing the huffman codes.

Question No: 20      ( Marks: 3 )

 

What is the functionality of the following method of BST class

TreeNode<int>* function(TreeNode<int>* tree)

{

    if( tree == NULL )

        return NULL;

    if( tree->getLeft() == NULL )

        return tree; // this is it.

    return function( tree->getLeft() );

}

Question No: 21      ( Marks: 3 )

 

a) Write a C++  statement that declares a valid reference of int i;

b) What is the benefit of reference and where can we use it?

In the last lecture we were discussing about reference variables, we saw three examples; call by value, call by reference and call by pointer. We saw the use of stack when a function is called by value, by reference or by pointer. The arguments passed to the function and local variables are pushed on to the stack. There is one important point to note that in this course, we are using C/C++ but the usage of stack is similar in most of the computer languages like FORTRAN and Java . The syntax we are using here is C++ specific, like we are sending a parameter by pointer using & sign. In Java, the native data types like int, float are passed by value and the objects are passed by reference. In FORTRAN, every parameter is passed by reference. In PASCAL, you can pass a parameter by value or by reference like C++. You might have heard of ALGOL, this language had provided another way of passing parameter ca

lled call by name. These kinds of topics are covered in subjects like

Question No: 22      ( Marks: 5 )

 

Determine what the following recursive “mystery” function computes when given a pointer to the root node of a binary tree.

struct bt_s { int key; struct bt_s *left, *right; } bt_t;

int MFunc (bt_t *T) {

int N1, N2;

if (T == NULL) return -1;

N1 = MFunc(T->left);

N2 = MFunc(T->right);

return (N1 > N2 ? N1 : N2) + 1;

}

Question No: 23      ( Marks: 5 )

 

Is the given tree is an AVL tree? If Not then redraw is so that it becomes AVL