CS301- Data Structures final term current papers July 2011

[Vuhelper]

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 )
Convert 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