Search Papers On This Blog. Just Write The Name Of The Course

Monday 27 December 2010

Complete Solved CS301- Data Structures Final term Past Paper Of VU

FINALTERM  EXAMINATION
Fall 2009
CS301- Data Structures (Session - 1)
Time: 120 min
Marks: 75
    
Question No: 1    ( 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: 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 is a valid postfix expression?

       ab+c*d-
       abc*+d-
       abc+*d-
       (abc*)+d-
   
Question No: 4    ( Marks: 1 )    - Please choose one
 In sequential access data structure, accessing any element in the data structure takes different amount of time. Tell which one of the following is sequential access data structure, Linked list

       Arrays

       Lists

       Both of these

       None of these

   
Question No: 5    ( Marks: 1 )    - Please choose one
 I have implemented the queue with a circular array. If data is a circular array of CAPACITY elements, and last is an index into that array, what is the formula for the index after last?
       (last % 1) + CAPACITY
       last % (1 + CAPACITY)
       (last + 1) % CAPACITY
       last + (1 % CAPACITY)
   
Question No: 6    ( Marks: 1 )    - Please choose one
 Which one of the following is TRUE about recursion?

       Recursion extensively uses stack memory.

       Threaded Binary Trees use the concept of recursion.

       Recursive function calls consume a lot of memory.

       Iteration is more efficient than iteration.


Question No: 7    ( Marks: 1 )    - Please choose one
 Compiler uses which one of the following to evaluate a mathematical equation,

Binary Tree

Binary Search Tree

Parse Tree

AVL Tree

   
Question No: 8    ( Marks: 1 )    - Please choose one
 Which one of the following is TRUE about iteration?

Iteration extensively uses stack memory.

Threaded Binary Trees use the concept of iteration.

Iterative function calls consumes a lot of memory.

Recursion is more efficient than iteration.

   
Question No: 9    ( Marks: 1 )    - Please choose one
 If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value? Data[0]

       data[1]
       data[n-1]
       data[n]
       data[2*n+1]
   
Question No: 10    ( Marks: 1 )    - Please choose one
 If there are 56 internal nodes in a binary tree then how many external nodes this binary tree will have?

       54
       55
       56
       57
   
Question No: 11    ( Marks: 1 )    - Please choose one
 Which of the following heap method increase the value of key at position ‘p’ by the amount ‘delta’?

       increaseKey(p,delta)
       decreaseKey(p,delta)
       preculateDown(p,delta)
       remove(p,delta)

Question No: 12    ( Marks: 1 )    - Please choose one
 If we have 1000 sets each containing a single different person. Which of the following relation will be true on each set:
       Reflexive 
         Symmetric 
         Transitive
          Associative
   
Question No: 13    ( Marks: 1 )    - Please choose one
 Which one of the following is not an example of equivalence relation: 

       Electrical connectivity 
       Set of people
       <= relation 
       Set of pixels 
   
Question No: 14    ( Marks: 1 )    - Please choose one
 A binary tree of N nodes has  _______.

       Log10 N levels 
       Log2 N levels 
       N / 2 levels 
       N x 2 levels 

Question No: 15    ( Marks: 1 )    - Please choose one
 Binary Search is an algorithm of searching, used with the ______ data.
       Sorted
       Unsorted
       Heterogeneous
       Random
   
Question No: 16    ( Marks: 1 )    - Please choose one
 Consider te following array
  23  15  5  12  40  10  7
After the first pass of a particular algorithm, the array looks like
1.      5  12  23  10  7  40
Name the algorithm used

       Heap sort
       Selection sort
       Insertion sort
       Bubble sort
   
Question No: 17    ( Marks: 1 )    - Please choose one
 Which of the following statements is correct property of binary trees? 
       A binary tree with N internal nodes has N+1 internal links. 
       A binary tree with N external nodes has 2N internal nodes. 
       A binary tree with N internal nodes has N+1 external nodes. 
       None of above statement is a property of the binary tree. 
   
Question No: 18    ( Marks: 1 )    - Please choose one
 Which of the following is a property of binary tree?
       A binary tree of N external nodes has N internal node.
       A binary tree of N internal nodes has N+ 1 external node.
       A binary tree of N external nodes has N+ 1 internal node.
       A binary tree of N internal nodes has N- 1 external node.
 
Question No: 19    ( Marks: 1 )    - Please choose one
 Which of the following statement is true about dummy node of threaded binary tree?
       The left pointer of dummy node points to the itself while the right pointer points to the root of tree.
       The left pointer of dummy node points to the root node of the tree while the right pointer points itself i.e. to dummy node
       The left pointer of dummy node points to the root node of the tree while the right pointer is always NULL.
       The right pointer of dummy node points to the itself while the left pointer is always NULL.
   
Question No: 20    ( Marks: 1 )    - Please choose one
 If the bottom level of a binary tree is NOT completely filled, depicts that the tree is NOT a

       Expression tree
       Threaded binary tree
       complete Binary tree
       Perfectly complete Binary tree
   
Question No: 21    ( Marks: 1 )    - Please choose one
 In a selection sort of n elements, how many times the swap function is called to complete the execution of the algorithm?

       n-1
       n log n
       n2
       1
   
Question No: 22    ( Marks: 1 )    - Please choose one
 Which of the following statement is correct about find(x) operation: 

       A find(x) on element x is performed by returning exactly the same node that is found. 
        A find(x) on element x is performed by returning the root of the tree containing x. 
        A find(x) on element x is performed by returning the whole tree itself containing x.
       A find(x) on element x is performed by returning TRUE. 
   
Question No: 23    ( Marks: 1 )    - Please choose one
 Which of the following statement is NOT correct about find operation: 

           It is not a requirement that a find operation returns any specific name, just that finds on two elements return the same answer if and only if they are in the same set. 
       One idea might be to use a tree to represent each set, since each element in a tree has the same root, thus the root can be used to name the set. 

         Initially each set contains one element. 
         Initially each set contains one element and it does not make sense to make a tree of one node only. 
   
Question No: 24    ( Marks: 1 )    - Please choose one
 Consider the following postfix expression S and the initial values of the variables.

S = A B - C + D E F - + ^
Assume that A=3, B=2, C=1, D=1, E=2, F=3

What would be the final output of the stack?

       1
       2
       0
       -1
   
Question No: 25    ( Marks: 1 )    - Please choose one
 The maximum number of external nodes (leaves) for a binary tree of height H is _________
       2H       
       2H +1
       2H -1
       2H +2
 
Question No: 26    ( Marks: 1 )    - Please choose one
 In threaded binary tree the NULL pointers are replaced by ,

       preorder successor or predecessor
       inorder successor or predecessor
       postorder successor or predecessor
       NULL pointers are not replaced
   
Question No: 27    ( Marks: 1 )    - Please choose one
 In a min heap ,  preculateDown procedure will move smaller value______ and bigger value______.
       left,right
       right,left
       up,down
       down,up

Question No: 28    ( Marks: 1 )    - Please choose one
 Which of the following statement is correct about union: 
       To perform Union of two sets, we merge the two trees by making the root of one tree point to the root of the other. 
         To perform Union of two sets, we merge the two trees by making the leaf node of one tree point to the root of the other. 
        To perform Union of two sets, merging operation of trees in not required at all. 
       None of the given options.
   
Question No: 29    ( Marks: 1 )    - Please choose one
 Suppose A is an array containing numbers in increasing order, but some numbers occur more than once when using a binary search for a value, the binary search always finds ____________

       the first occurrence of a value.
       the second occurrence of a value.
       may find first or second occurrence of a value.
       None of the given options.

Question No: 30    ( Marks: 1 )    - Please choose one
 Let heap stored in an array as H = [50, 40, 37, 32, 28, 22, 36, 13].  In other words, the root of the heap contains the maximum element. What is the result of deleting 40 from this heap
       [50,32, 37,13, 28, 22, 36]
       [37, 28, 32, 22, 36, 13]
       [37, 36, 32, 28, 13, 22]
       [37, 32, 36, 13, 28, 22]
   
Question No: 31    ( Marks: 1 )
 Describe the conditions for second case of deletion in AVL Trees.

Answer:
The node to be deleted has either left child (subtree) or right child (subtree). In this case we bypass the node in such a way that we find the inorder successor of this node and then link the parent of the node to be deleted to this successor node.Thus the node was deleted.

   
Question No: 32    ( Marks: 1 )
 What is Table abstract data type.
Answer:
An abstract data structure is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics.


Question No: 33    ( Marks: 2 )
 How we can generate a maze .Give an algorithm.

Answer:

A maze can be generated by starting with a predetermined arrangement of cells (most commonly a rectangular grid but other arrangements are possible) with wall sites between them. This predetermined arrangement can be considered as a connected graph with the edges representing possible wall sites and the nodes representing cells.
The algorithm is as follows:
Randomly remove walls until the entrance and exit cells are in the same set.
Removal of the wall is the same as doing a union operation.
Do not remove a randomly chosen wall if the cells it separates are already in
the same set.
   
Question No: 34    ( Marks: 2 )
 Represent the following Binary tree using array representation.





A
B
C
D


E

 0         1       2       3       4       5        6       7
   
Question No: 35    ( Marks: 3 )
 What is an Equivalent relation? Give any two examples.

A binary relation R over a set S is called an equivalence relation if it has following
Properties
1.Reflexivity: for all element x S, x R x
2. Symmetry: for all elements x and y, x R y if and only if y R x
3. Transitivity: for all elements x, y and z, if x R y and y R z then x R z
   
Question No: 36    ( Marks: 3 )
 "For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply." Justify why?
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
Full example of quicksort on a random set of numbers. The boxed element is the pivot. It is always chosen as the last element of the partition.The steps are:

1.Pick an element, called a pivot, from the list.
2.Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3.Recursively sort the sub-list of lesser elements and the sub-list of greater elements
  
Question No: 37    ( Marks: 3 )
 How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7 ?
We know that the total number of nodes (leaf and non-leaf) of a complete binary tree
of depth d is equal to 2d+1 – 1.
It can be calculated as
27=14 nodes

   
Question No: 38    ( Marks: 5 )
 Remove the smallest element from the following array which represents a min-heap.


original min-heap
1
3
2
5
4
8
9
10
7


and show the resultant heap in the form of array as shown below,


after removal
2
3
8
5
4

9
10
7



Question No: 39    ( Marks: 5 )
 Here is an array with exactly 15 elements:
                        1   2   3   4   5   6   7   8   9   10   11   12   13   14   15.
Suppose that we are doing a binary search for an element. Indicate any elements that will be found by examining two or fewer numbers from the array.
   
Question No: 40    ( Marks: 10 )
 a) Write C++ algorithm for Binary Search

int isPresent(int *arr, int val, int N)
{
int low = 0;
int high = N - 1;
int mid;
while ( low <= high )
{
mid = ( low + high )/2;
if (arr[mid] == val)
return 1; // found!
else if (arr[mid] < val)
low = mid + 1;
else
high = mid - 1;
}
return 0; // not found
Example

int binarySearch(int sortedArray[], int first, int last, int key) {
   // function:
   //   Searches sortedArray[first]..sortedArray[last] for key. 
   // returns: index of the matching element if it finds key,
   //         otherwise  -(index where it could be inserted)-1.
   // parameters:
   //   sortedArray in  array of sorted (ascending) values.
   //   first, last in  lower and upper subscript bounds
   //   key         in  value to search for.
   // returns:
   //   index of key, or -insertion_position -1 if key is not
   //                 in the array. This value can easily be
   //                 transformed into the position to insert it.
  
   while (first <= last) {
       int mid = (first + last) / 2;  // compute mid point.
       if (key > sortedArray[mid])
           first = mid + 1;  // repeat search in top half.
       else if (key < sortedArray[mid])
           last = mid - 1; // repeat search in bottom half.
       else
           return mid;     // found it. return position /////
   }
   return -(first + 1);    // failed to find key
}

b) Consider the following array of values; show how the binary search algorithm would find the value -5. Clearly show/explain your work; that is, show the values of start, end, etc. for each step of the algorithm.


   
Question No: 41    ( Marks: 10 )
 Show the result of following sequence of instructions

Union(1,2)
Union(3,4)
Union(3,5)
Union(1,7)
Union(3,6)
Union(8,9)
Union(1,8)
Union(3,10)
Union(3,11)
Union(3,12)
Union(3,13)
Union(14,15)
Union(16,17)
Union(14,16)
Union(1,3)
Union(1,14)

When the unions are performed by height

Note: You have to show only Final tree, No need to show all steps.

No comments:

Post a Comment