# Data Structures and Algorithm Analysis Set 13

## Data Structures and Algorithm Analysis

### Questions 121 to 130

121. Consider that a 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?

(a) data[0]
(b) data[n-1]
(c) data[n]
(d) data[2*n + 1]
(e) data[2*n + 2].

122. Which of the following are used to represent the sparse matrices?

(a) Singly Linked List where each node contains non- zero elements of the matrix
(b) Circular Linked List for each row, column with each node corresponding to non-zero element
(d) Can’t be represented using Linked List, but with arrays only
(e) Can be represented only by queues.

123. Which of the following has a desired key is searched, starting itself from hash address, sequentially in a table?

(b) Random probing
(c) Reverse probing
(d) Chaining
(e) Linear probing.

124. Consider A is an array of order m*n stored in a Row Major order. If the address of the first element in the array is K which is there at A[0, 0], then What is the address of A[i, j]?

(a) K + (i-1) * m + j – 1
(b) K + (i-1) * n + j – 1
(c) K + i * m + j
(d) K + (j-1) * m + j – 1
(e) K + j * n +  i.

125. Which of the following is used in conversion of an infix expression to a postfix expression?

(a) Circular list
(b) Array
(c) Stack
(d) Queue
(e) Dequeue.

126. What is the output of the following function when it is called?
void disp( node *first )
if( first->next )
{
{
printf("%4d", first->data);
disp( first->next );
}
}

(a) Display the data of next node always in the list
(b) Display the data of all nodes of the list
(c) Does not execute
(d) Display the data of the first node only
(e) Display the data of the last node only.

127. With the “wrap around” implementation of a queue, which of the following code should be used to work out the next location of deletion?

(a) front++
(b) front--
(c) front = (front % max_queue_size) + 1
(d) front = (front ++) % max_queue_size
(e) front = 0.

128. Consider the order of a tree is represented by M. Then, which of the following is true?

(a) Every non-leaf node must have M subtrees
(b) Every non-leaf node must have M keys
(c) Every non-leaf node can have atmost M subtrees
(d) Every non-leaf node can have atmost M keys
(e) The Height of the tree is M.

129. What are the time complexities of binary search for an array of size N in best and worst cases respectively?

(a) N, N2
(b) 1, Log N
(c) Log N, N2
(d) 1, N Log N
(e) N, N.

130. What is the algorithm, which scans the list by swapping the entries whenever pair of adjacent keys is out of desired order?

(a) Insertion sort
(b) Quick sort
(c) Shell sort
(d) Bubble sort