CS301 Mid term paper Solved 2010 - 1

MIDTERM  EXAMINATION

Spring 2010

CS301- Data Structures

Question No: 1      ( M a r k s: 1 ) http://vuzs.net

 

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      ( M a r k s: 1 ) http://vuzs.net

 

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

       ► One

       ► Two

       ► Three

       ► Four

p67

Question No: 3      ( M a r k s: 1 ) http://vuzs.net

 

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      ( M a r k s: 1 ) - Please choose vuzs 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      ( M a r k s: 1 ) http://vuzs.net

 

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      ( M a r k s: 1 ) http://vuzs.net

 

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

       ► False

       ► True

p101

Question No: 7      ( M a r k s: 1 ) http://vuzs.net

 

Which one is a self-referential data type?                                                                    

       ► Stack

       ► Queue

       ► Link list

       ► All of these

 

Question No: 8      ( M a r k s: 1 ) http://vuzs.net

 

Each node in doubly link list has,

       ► 1 pointer

       ► 2 pointers

 

       ► 3 pointers

       ► 4 pointers

p39

Question No: 9      ( M a r k s: 1 ) http://vuzs.net

 

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      ( M a r k s: 1 ) http://vuzs.net

 

Consider the following tree.

How many of the nodes have at least one sibling?

       ► 8

       ► 7

       ► 5

       ► 6

Question No: 11      ( M a r k s: 1 ) http://vuzs.net

 

The nodes with no successor are called _________

       ► Root Nodes

       ► Leaf Nodes  

       ► Both of these

       ► None of these

 

Question No: 12      ( M a r k s: 1 ) http://vuzs.net

 

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      ( M a r k s: 1 ) http://vuzs.net

 

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      ( M a r k s: 1 ) http://vuzs.net

 

A binary search tree should have minimum ofone________ node/s at each level,

       ► One  ( not sure )

       ► Two

       ► Three

       ► Four

 

Question No: 15      ( M a r k s: 1 ) http://vuzs.net

 

Consider the following statements.

1. A binary tree can contain at least 2^LNodes at level L.
2. A complete binary tree of depth d is a binary tree that contains 2^LNodes at each level L between 0 and d, both inclusive.
3. The total number of nodes (T_n) in a complete binary tree of depth d is 2 ^d+1- 1 .
4. The height of the complete binary tree can be written as h = log ₂(T_n+1)-1 where T_nis 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      ( M a r k s: 1 ) http://vuzs.net

 

“+” is a _________operator.

       ► Unary

       ► Binary

       ► Ternary

       ► None of the above

 

Question No: 17      ( M a r k s: 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      ( M a r k s: 2 )

 

What are the applications of Binary Tree.

Question No: 19      ( M a r k s: 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      ( M a r k s: 3 )

 

What is the functionality of the following method of BST class

TreeNode* function(TreeNode* tree)

{

    if( tree == NULL )

        return NULL;

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

        return tree; // this is it.

    return function( tree->getLeft() );

}

Question No: 21      ( M a r k s: 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      ( M a r k s: 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      ( M a r k s: 5 )

 

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