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 2L Nodes at level L.
(ii)	A complete binary tree of depth d is a binary tree that contains 2L Nodes at each level L between 0 and d, both inclusive.
(iii)	The total number of nodes (Tn ) 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 2 (Tn+1)-1 where Tn 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 

MIDTERM  EXAMINATION 
Spring 2010
CS301- Data Structures 
Time: 60 min
Marks: 38 

Question No: 1      ( Marks: 1 ) - Please choose one
 A queue where the de-queue operation depends not on FIFO, is called a priority queue  

       ► False 

       ► True 

Question No: 2      ( Marks: 1 ) - Please choose one
 The data of the problem is of 2GB and the hard disk is of 1GB capacity, to solve this problem we should  

       ►  Use better data structures 

       ► Increase the hard disk space  

       ► Use the better algorithm  
       ►  Use as much data as we can store on the hard disk  

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

Consider the function X as under
 int X (int& Value)
{
 return Value; 
}
Now a and b are integers in a calling function. Which one of the following is a valid call to the above function X.  

       ► a = X (b) ;  

       ► a = X (&b) ; 

       ► a = X (*b) ;  

       ► None of the given options

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

In the call by value methodology, a copy of the object is passed to the called function.  

       ► False

       ► True

Question No: 5      ( Marks: 1 ) - Please choose one
 
The tree data structure is a  

       ► Linear data structure 

       ► Non-linear data structure 

       ► Graphical data structure 

       ► Data structure like queue 

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

When should you use a const reference parameter?

       ► Whenever the parameter has huge size.

       ► Whenever the parameter has huge size, the function changes the parameter within its body, and you do NOT want these changes to alter the actual argument.

       ► Whenever the parameter has huge size, the function changes the parameter within its body, and you DO want these changes to alter the actual argument.
       ► Whenever the parameter has huge size, and the function does not change the parameter within its body.

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

Here is the start of a C++ 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 alter the PRIVATE member variables of the foo object that activates the function? 

       ► Only x can alter the private member variables of the object that activates the function. 

       ► Only y can alter the private member variables of the object that activates the function. 

       ► Only z can alter the private member variables of the object that activates the function. 

       ► Two of the functions can alter the private member variables of the object that activates the function. 

Question No: 8      ( Marks: 1 ) - Please choose one
 What is the maximum depth of recursive calls a function may make? 

       ► 1

       ► 2

       ► n (where n is the argument) 

       ► There is no fixed maximum

Question No: 9      ( 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

       ► Log2 (n+1) 

       ► Log2 (n) – 1

       ► Log2 (n) 

Question No: 10      ( Marks: 1 ) - Please choose one
 
In the linked list implementation of the stack class, where does the push member function places the new entry on the linked list?

       ► At the head

       ► At the tail

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

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

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

Suppose we have a circular array implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42, i.e., the array has been declared to be of size 42. Where does the push member function place the new entry in the array?

       ► data[1]

       ► data[2]

       ► data[11]

       ► data[12]

Question No: 12      ( Marks: 1 ) - Please choose one
 
The expression AB+C*  is called ?

       ► Prefix expression 

       ► Postfix expression 

       ► Infix expression 

       ► None of these

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

_________ is a binary tree where every node has a value, every node's left subtree contains only values less than or equal to the node's value, and every node's right subtree contains only values that are greater then or equal ?                                                                    

       ► Strictly Binary Tree

       ► Binary Search tree 

       ► AVL tree

       ► All of these

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

Consider the following binary search tree (BST):

If node A in the BST is deleted, which two nodes are the candidates to take its place?

       ► J and I

       ► H and E

       ► D and E

       ► L and M

Question No: 15      ( Marks: 1 ) - Please choose one
 
Let’s call the node as a that requires re-balancing. Consider the two cases given below:
 1) An insertion into left subtree of the left child of a
 2) An insertion into right subtree of the right child of a.

Which of the following statement is correct about these two cases.  
 
1) The insertion occurs outside (i.e., left-left or right-right) in cases 1 and 2. single rotation can fix the balance in these two cases.  
2) The insertion occurs inside ((i.e., left-left or right-right) in cases 1 and 2. single rotation cannot fix the balance in these two cases  

Question No: 16      ( 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: 17      ( Marks: 2 )
 
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: 18      ( Marks: 2 )

How we can delete a node with two Childs in a binary search tree using its right sub tree.

Question No: 19      ( Marks: 2 )
 What is Function Call Stack Give short answer.

Question No: 20      ( Marks: 3 )

xplain the two cases in which we apply double rotation in an AVL tree.

Question No: 21      ( Marks: 3 )

Here is a small binary tree.

Write the order of the nodes visited in
a)	A Post-order traversal 
b)	A level-order traversal 

Question No: 22      ( Marks: 5 )
 
Please consider the following AVL tree.  
1.	Insert new node 87 in this tree and make tree balance.
2.	Write balance factor of each node after and before inserting node 87.

Question No: 23      ( Marks: 5 )
 
Consider the following binary tree

Show the state of the tree after deleting 24.

MIDTERM  EXAMINATION 
Fall 2009
CS301- Data Structures (Session - 5) 
Ref No: 885482 
Time: 60 min 
Marks: 38

Question No: 1    ( Marks: 1 )    - Please choose one
 Which one of the following is a valid postfix expression? 

       ► ab+c*d-
       ► abc*+d-
       ► abc+*d-
       ► (abc*)+d-
    
Question No: 2    ( Marks: 1 )    - Please choose one
 The tree data structure is a  

       ► Linear data structure 
       ► Non-linear data structure 
       ► Graphical data structure 
       ► Data structure like queue 
    
Question No: 3    ( Marks: 1 )    - Please choose one
 A Compound Data Structure is the data structure which can have multiple data items of same type or of different types. Which of the following can be considered compound data structure?

       ► Arrays 

       ► LinkLists

       ► Binary Search Trees

       ► All of the given options

Question No: 4    ( Marks: 1 )    - Please choose one
 Suppose a pointer has been declared in main but has not assigned any variable address then

►That pointer points to First byte in main function

►That pointer contains a NULL value 

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

►That pointer points to any memory address

Question No: 5    ( Marks: 1 )    - Please choose one
 Here is the start of a C++ 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 alter the PRIVATE member variables of the foo object that activates the function? 

►Only x can alter the private member variables of the object that activates the function. 
►Only y can alter the private member variables of the object that activates the function. 

►Only z can alter the private member variables of the object that activates the function. 
►Two of the functions can alter the private member variables of the object that activates the function. 

Question No: 6    ( Marks: 1 )    - Please choose one
 The operation for removing an entry from a stack is traditionally called:                            
       ► delete 
       ► peek 
       ► pop 
       ► remove 
    
Question No: 7    ( Marks: 1 )    - Please choose one
 Which statement of the following statements is incorrect? 
       ► Lists can be implemented by using arrays or linked lists 

       ► A list is a sequence of one or more data items 
       ► Stack is a special kind of list in which all insertions and deletions take place at one end 
       ► Stacks are easier to implement than lists 

Question No: 8    ( Marks: 1 )    - Please choose one
 Parameters in function call are passed using,

       ► Stack 

       ► Queue 

       ► Binary Search Tree 

       ► AVL Tree

Question No: 9    ( 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: 10    ( Marks: 1 )    - Please choose one
 What is the maximum depth of recursive calls a function may make? 

       ► 1
       ► 2
       ► n (where n is the argument) 
       ► There is no fixed maximum
    
Question No: 11    ( Marks: 1 )    - Please choose one
 Consider the following function:

void test_a(int n)
{
cout << n << " ";
if (n>0)
test_a(n-2);
}

What is printed by the call test_a(4)?

       ► 4 2
       ► 0 2 4
       ► 0 2

       ► 2 4

Question No: 12    ( Marks: 1 )    - Please choose one
 Queue follows, 

       ► Last in First out

       ► First in Last out

       ► First in First out

       ► None of these

Question No: 13    ( Marks: 1 )    - Please choose one
 _________ is a binary tree where every node has a value, every node's left subtree contains only values less than or equal to the node's value, and every node's right subtree contains only values that are greater then or equal ?                                                                    
►Strictly Binary Tree
►Binary Search tree 

►AVL tree

►All of these
    
Question No: 14    ( Marks: 1 )    - Please choose one
 Four statements about trees are below. Three of them are correct. Which one is INCORRECT? 
►Trees are recursively defined multi-dimensional data structures 
►The order of a tree indicates a maximum number of childen allowed at each node of the tree 
►A search tree is a special type of tree where all values (i.e. keys) are ordered 

►If Tree1's size is greater than Tree2's size, then the height of Tree1 must also be greater than Tree2's height. 
    
Question No: 15    ( Marks: 1 )    - Please choose one
 Below is a binary search tree. If we delete the value 50 using the algorithm we discussed, what value will be in the root of the remaining tree?

       ► 50
       ► 60
       ► 70
       ► 80
    
Question No: 16    ( Marks: 1 )    - Please choose one
 _________ is a data structure that can grow easily dynamically at run time without having to copy existing elements.

       ► Array

       ► List

       ► Both of these  

       ► None of these

Question No: 17    ( Marks: 1 ) 
 Give the names of basic Queue Operations
Ans:
Definition: A collection of items in which only the earliest added item may be accessed. Basic operations are add (to the tail) or enqueue and delete (from the head) or dequeue. Delete returns the item removed. Also known as "first-in, first-out" or FIFO.
    
Question No: 18    ( Marks: 1 ) 
 Give one benefit of using Stack.
In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. the data structure itself enforces the proper order of calls.
    
Question No: 19    ( Marks: 2 ) 
 Let’s call the node as a that requires re-balancing. Consider the two cases given below:
 1) An insertion into left subtree of the left child of a
 2) An insertion into right subtree of the right child of a.

Which of the following statement is correct about these two cases.  
 
1) The insertion occurs outside (i.e., left-left or right-right) in cases 1 and 2. single rotation can fix the balance in these two cases.  
2) The insertion occurs inside ((i.e., left-left or right-right) in cases 1 and 2. single rotation cannot fix the balance in these two cases  

Question No: 20    ( Marks: 3 ) 
 Consider the following sequence of push operations in a stack:                  

stack.push(’1’);
stack.push(’2’);
stack.push(’3’);
stack.push(’4’);
stack.push(’5’);
stack.push(’6’);

You can insert as many stack.pop()’s as you like in the above sequence of stack.push’s to get a desired output. Which of the following cannot be an output?
A. 123456
B. 325416
C. 342561
D. 342615
E. 342165

Question No: 21    ( Marks: 5 ) 
 Give short answers of the following questions:

1.	Why List wastes less memory as compared to Arrays.

Ans: 
1.  Linked lists do not need contiguous blocks of memory; extremely large data sets stored in an array might not be able to fit in memory.
   2. Linked list storage does not need to be preallocated (again, due to arrays needing contiguous memory blocks).
   3. Inserting or removing an element into a linked list requires one data update, inserting or removing an element into an array requires n (all elements after the modified index need to be shifted).

Array is a collection of same data type. In linked list there are two field one is address and other is pointer. In array elements are arranged in a specific order

2.	Why we can change the size of list after its creation when we can not do that in simple arrays.
   Some how the answer will be same as part 1 because Inserting or removing an element into a linked list requires one data update, inserting or removing an element into an array requires n (all elements after the modified index need to be shifted).

Array is a collection of same data type. The size of array is mentioned with its declaration. in arrays the elements are in contiguous position. one must after another. while in linked list we gave the address of next element in the next part of node.

Question No: 22    ( Marks: 10 ) 
 Convert the following infix expression into postfix expressions using stack (Show complete steps)

1-2 ­3­3-(4+5*6)*7
Step 1	Post fix	stack	
1	1		
-		-	
2	2		
	12	-	

			

			

			

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
► LinkLists
► 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 : 
add►
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)

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 :       
► add
► 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,
void LinkList::mystery(){
Node * temp = headNode;
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. 

MIDTERM  EXAMINATION 
Spring 2010
CS301- Data Structures 
Ref No: 1349576
Time: 60 min
Marks: 38

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

In an array we can store data elements of different types.  

       ► True

       ► False 

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

 In an array list the current element is  

       ► The first element  

       ► The middle element 

       ►  The last element  

       ► The element where the current pointer points to  

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

Which one of the following statements is NOT correct?

       ► Array size can be changed after its creation.

       ► Link List size can be changed after its creation

       ► Binary Search Tree size can be changed after its creation 

       ► AVL Tree size can be changed after its creation 

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

A queue is a ________data structure, whereas a stack is a ________data structure. 

       ► FIFO, LIFO	

       ► LIFO,FIFO

       ► none of these

       ► both of these

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

Which one of the following operators has higher priority than all of others ?

       ► Multiplication operator

       ► Minus operator

       ► Plus operator

       ► Exponentiation operator

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

Each node in Binary Search Tree has

       ► 1 pointer

       ► 2 pointers

       ► 3 pointers

       ► 4 pointers

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

Four statements about trees are below. Three of them are correct. Which one is INCORRECT? 

       ► Trees are recursively defined multi-dimensional data structures 

       ► The order of a tree indicates a maximum number of childen allowed at each node of the tree 

       ► A search tree is a special type of tree where all values (i.e. keys) are ordered 

       ► If Tree1's size is greater than Tree2's size, then the height of Tree1 must also be greater than Tree2's height. 

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

Which of the following is "TRUE" about arrays,

       ► We can increase the size of arrays after their creation.

       ► We can decrease the size of arrays after their creation.

       ► We can increase but can't decrease the size of arrays after their creation.

       ► We can neither increase nor decrease the array size after their creation.

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

Searching an element in an AVL tree take maximum _______ time (where n is no. of nodes in AVL tree),

       ► Log2(n+1)

       ► Log2(n+1) -1

       ► 1.44 Log2n

       ► 1.66 Log2n

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

There is/are ________ case/s for rotation in an AVL tree,

       ► 1

       ► 3

       ► 2

       ► 4

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

Consider the following statements.

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

Consider the following infix expression.
5 + 6/2 
If one converts the above expression into postfix, what would be the resultant expression?

       ► 56/ + 2

       ► 5 6 2 / +

       ► 5 6 / 2 + 

       ► /62 + 5 

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

Which of the following is a non linear data structure? 

       ► Linked List

       ► Stack

       ► Queue 

       ► Tree 

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

“+” is a _________operator.

       ► Unary

       ► Binary

       ► Ternary

       ► None of the above

Question No: 17      ( Marks: 2 )
 
Which process places data at the back of the queue?

Question No: 18      ( Marks: 2 )

How we can delete a node with two Childs in a binary search tree using its right sub tree.

Question No: 19      ( Marks: 2 )

Why we use Reference Variables. Give one example.

Question No: 20      ( Marks: 3 )

The nodes of a binary tree have data 1, 2, 3, 4. The in-order traversal of the tree yields 2,1,4,3. The postorder traversal is 2, 4, 3, 1. The root of the tree is at level 0. 	
Q3: Which value is in the right child of the root? (1 Pt)
(A) 1   (B) 2   (C) 3   (D) 4   (E) none

Question No: 21      ( Marks: 3 )

What normally is the sequence of operations while constructing an AVL tree?

Question No: 22      ( Marks: 5 )

Here is a small binary tree:

                 14
                 / \
                2   11
               / \  / \
              1  3 10 30
                  /  /
                 7  40
Write the order of the nodes visited in:

A. An in-order traversal:

B. A pre-order traversal:

Question No: 23      ( Marks: 5 )

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