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,
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
