PROMOTE MY BLOG: JUST CLICK BELOW BUTTON

Search Any Paper On This Blog

Friday, December 24, 2010

CS301- Data Structures complete Finalterm Past paper 2010

FINALTERM  EXAMINATION
Spring 2010
CS301- Data Structures
Time: 90 min
Marks: 58
Question No: 1      ( Marks: 1 ) - Please choose one



Here is a small function definition:

void f(int i, int &k)
{
i = 1;
k = 2;
}
Suppose that a main program has two integer variables x and y, which are given the value 0. Then the main program calls f(x,y); What are the values of x and y after the function f finishes?


       Both x and y are still 0.

       x is now 1, but y is still 0.

       x is still 0, but y is now 2.

       x is now 1, and y is now 2.



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



A binary tree with N internal nodes has _____ links, _______ links to internal nodes and ________ links to external nodes


       N+1, 2N, N-1

       N+1, N-1, 2N

       2N, N-1, N+1

       N-1, 2N, N+1

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


Each node in doubly link list has,


       1 pointer


       2 pointers






       3 pointers


       4 pointers




Question No: 4      ( Marks: 1 ) - Please choose one
 If you know the size of the data structure in advance, i.e., at compile time, which one of the following is a good data structure to use.


       Array


       List


       Both of these 


       None of these




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


If a complete binary tree has height h then its no. of nodes will be,


       Log (h)


       2h+1- 1


       Log (h) - 1


       2h - 1




Question No: 7      ( 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[1]

  data[n-1]

       data[n]

       data[2*n+1]



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

Which one is a self-referential data type?                                                                    

       Stack

       Queue


       Link list


       All of these





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


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


       1

       3

       2

       4




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


Which of the following can be the inclusion criteria for pixels in image segmentation. 

       Pixel intensity 

       Texture 

       Threshold of intensity 

       All of the given options



Question No: 11      ( 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
15    5  12  23  10  7  40
Name the algorithm used


       Heap sort

       Selection sort

       Insertion sort

       Bubble sort



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


In a perfectly balanced tree the insertion of a node needs  ________ .

       One rotation 

       Two rotations


       Rotations equal to number of levels 

       No rotation at all 



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


If there are N elements in an array then the number of maximum steps needed to find an element using Binary Search is _______ .

       N

       N2

       Nlog2N

       log2N



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

Which of the following is NOT a correct statement about Table ADT.

       In a table, the type of information in columns may be different.

       A table consists of several columns, known as entities. 

       The row of a table is called a record. 

       A major use of table is in databases where we build and use tables for keeping information. 




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


If both pointers of the node in a binary tree are NULL then it will be a/an _______ .


       Inner node

       Leaf node

       Root node

       None of the given options


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


Suppose we are sorting an array of eight integers using quick sort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10
Which statement is correct?



       The pivot could be either the 7 or the 9.

       The pivot could be the 7, but it is not the 9.

       The pivot is not the 7, but it could be the 9.

       Neither the 7 nor the 9 is the pivot.


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


What is the best definition of a collision in a hash table?


       Two entries are identical except for their keys.


                   Two entries with different data have the exact same key

       Two entries with different keys have the same exact hash value.


                   Two entries with the exact same key have different hash values.



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

For a perfect binary tree of height h, having N nodes, the sum of heights of nodes is 


       N – (h – 1) 

       N – (h + 1) 

       N – 1 

       N – 1 + h 




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


A binary tree with 33 internal nodes has _______ links to internal nodes.


       31

       32

       33

       66



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


Suppose you implement a Min heap (with the smallest element on top) in an array. Consider the different arrays below; determine the one that cannot possibly be a heap:                

       16, 18, 20, 22, 24, 28, 30  

       16, 20, 18, 24, 22, 30, 28

       16, 24, 18, 28, 30, 20, 22

       16, 24, 20, 30, 28, 18, 22



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


Which of the following is not true regarding the maze generation?

       Randomly remove walls until the entrance and exit cells are in the same set. 

       Removing a wall is the same as doing a union operation. 

       Remove a randomly chosen wall if the cells it separates are already in the same set. 

        Do not remove a randomly chosen wall if the cells it separates are already in the same set. 



Question No: 22      ( Marks: 1 ) - Please choose one
 Which formula is the best approximation for the depth of a heap with n nodes?


       log (base 2) of n

       The number of digits in n (base 10), e.g., 145 has three digits

       The square root of n

       n




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



The _______ method of list will position the currentNode and lastCurrentNode at the start of the list.

       Remove


       Next


       Start


       Back




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


Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?


       Elements in the first half of the array are less than or equal to elements in the second half of the array.

       None of the given options.

       The array elements form a heap.

       Elements in the second half of the array are less than or equal to elements in the first half of the array.


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

Suppose we had a hash table whose hash function is “n % 12”, if the number 35 is already in the hash table, which of the following numbers would cause a collision?


       144

       145

       143

       148



Question No: 27      ( Marks: 2 )
onvert this tree representation of a heap into the corresponding array representation




Question No: 28      ( Marks: 2 )


What are different applications of Hashing?



Question No: 29      ( Marks: 2 )


Give the operation names that we can perform on Table abstract data type.




Question No: 30      ( Marks: 2 )


Give your comments on the statement:
"Efficiently developed data structures decrease programming effort"




Question No: 31      ( Marks: 3 )

When Hashing is NOT suitable?


Question No: 32      ( Marks: 3 )


Give any three characteristics of Union by Weight method.





Question No: 33      ( Marks: 3 )


Consider the following Max Heap add node 24 in it and show the resultant Heap,

Question No: 34      ( Marks: 5 )



Heapify the elements of the following array (reading from left to right ) into a Min Heap and show that Min Heap contents in the form of array as shown below,


original array
6
5
3
9
1
2
10
8
-



Heapified  array















Question No: 35      ( Marks: 5 )


Here is an array of ten integers:

5 3 8 9 1 7 0 2 6 4

Show the first three merging steps for Merge sort on this array.




Question No: 36      ( Marks: 5 )

Consider the following sequence of union commands on the set of elements
{1,2,3,4, 5}:
union(4,2)
union(3,1)
union(5,4)
union(5,3)
Show the result when the unions are performed


No comments:

Post a Comment

PLEASE COMMENT ABOUT YOUR VISIT AND MY SITE

Note: Only a member of this blog may post a comment.