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
(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[0] .
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.



1 comment :