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.
- A binary tree can contain at least 2LNodes at level L.
- A complete binary tree of depth d is a binary tree that contains 2LNodes at each level L between 0 and d, both inclusive.
- The total number of nodes (Tn) in a complete binary tree of depth d is 2 d+1- 1 .
- The height of the complete binary tree can be written as h = log 2(Tn+1)-1 where Tnis 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
