# 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
(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
(c) Doubly Linked List
(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?

(a) Quadratic probing
(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
(e) Radix sort.

#### Answers

 121 Answer : (a) Reason:  if  a heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), then the entry with the greatest value is  data . 122 Answer : (a) Reason:  To represent the sparse matrices, we have Singly Linked List where each node contains non- zero elements of the matrix 123 Answer : (e) Reason:  Linear Probing has a desired key is searched, starting itself from hash address, sequentially in a table. 124 Answer : (b) Reason:  If 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 the address of A[i, j] is  K + (i-1) * n + j – 1 125 Answer : (c) Reason:  Stack is used in conversion of an infix expression to a postfix expression. 126 Answer : (b) Reason:  if the  following function  is called. void disp( node *first )               if( first->next ) {               {                      printf("%4d", first->data);                disp( first->next );               } }             then  it Display the data of all nodes of the list. 127 Answer : (d) Reason:  With the ``wrap around'' implementation of a queue, front = (front ++) % max_queue_size  should be used to work out the next location of deletion. 128 Answer : (c) Reason:  if the order of a tree is represented by M. Then , Every non-leaf node can have at most M subtrees is true. 129 Answer : (b) Reason:  1, Log N are the time complexities of binary search for an array of size N in best and worst cases respectively 130 Answer : (d) Reason:  Bubble sort is the algorithm, which scans the list by swapping the entries whenever pair of adjacent keys is out of desired order.

<< PrevNext >>

#### 1 comment :

1. 