CS301 Final term Paper 2010 - 2

 FINALTERM  EXAMINATION
Spring 2010
CS301- Data Structures
 
Time: 90 min
M - 58
CS301 - Data Structures - Q.No. 1      ( M - 1 )
 
 
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.

CS301 - Data Structures - Q.No. 2      ( M - 1 )
 
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
CS301 - Data Structures - Q.No. 3      ( M - 1 )
 
Each node in doubly link list has,
       ► 1 pointer
       ► 2 pointers
       ► 3 pointers
       ► 4 pointers

CS301 - Data Structures - Q.No. 4      ( M - 1 )
 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
CS301 - Data Structures - Q.No. 5      ( M - 1 )
 
Which one of the following is not an example of equivalence relation: 
       ► Electrical connectivity 
       ► Set of people
       ► <= relation 
       ► Set of pixels 

CS301 - Data Structures - Q.No. 6      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 7      ( M - 1 )
 
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]

CS301 - Data Structures - Q.No. 8      ( M - 1 )
 
Which one is a self-referential data type?                                                                    
       ► Stack
       ► Queue
       ► Link list
       ► All of these


CS301 - Data Structures - Q.No. 9      ( M - 1 )
 
There is/are ________ case/s for rotation in an AVL tree,
       ► 1
       ► 3
       ► 2
       ► 4

CS301 - Data Structures - Q.No. 10      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 11      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 12      ( M - 1 )
 
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 

CS301 - Data Structures - Q.No. 13      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 14      ( M - 1 )
 
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. 

CS301 - Data Structures - Q.No. 15      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 16      ( M - 1 )
 
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.
CS301 - Data Structures - Q.No. 17      ( M - 1 )
 
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.

CS301 - Data Structures - Q.No. 18      ( M - 1 )
 
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 


CS301 - Data Structures - Q.No. 19      ( M - 1 )
 
A binary tree with 33 internal nodes has _______ links to internal nodes.
       ► 31
       ► 32
       ► 33
       ► 66
CS301 - Data Structures - Q.No. 20      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 21      ( M - 1 )
 
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. 

CS301 - Data Structures - Q.No. 22      ( M - 1 )
 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


CS301 - Data Structures - Q.No. 23      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 24      ( M - 1 )
 
The _______ method of list will position the currentNode and lastCurrentNode at the start of the list.
       ► Remove
       ► Next
       ► Start
       ► Back

CS301 - Data Structures - Q.No. 25      ( M - 1 )
 
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.


CS301 - Data Structures - Q.No. 26      ( M - 1 )
 
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

CS301 - Data Structures - Q.No. 27      ( M - 2 )
 Convert this tree representation of a heap into the corresponding array representation
 
 
CS301 - Data Structures - Q.No. 28      ( M - 2 )
 
What are different applications of Hashing?
CS301 - Data Structures - Q.No. 29      ( M - 2 )
 
Give the operation names that we can perform on Table abstract data type.

CS301 - Data Structures - Q.No. 30      ( M - 2 )
 
Give your comments on the statement:
"Efficiently developed data structures decrease programming effort"
CS301 - Data Structures - Q.No. 31      ( M - 3 )
 
When Hashing is NOT suitable?
CS301 - Data Structures - Q.No. 32      ( M - 3 )
 
Give any three characteristics of Union by Weight method.

CS301 - Data Structures - Q.No. 33      ( M - 3 )
 
Consider the following Max Heap add node 24 in it and show the resultant Heap,
 
CS301 - Data Structures - Q.No. 34      ( M - 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
 
 
 
 
 
 
 
 
 


CS301 - Data Structures - Q.No. 35      ( M - 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.

CS301 - Data Structures - Q.No. 36      ( M - 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

Leave a Reply

Related Posts Plugin for WordPress, Blogger...