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] .
|
Answer
: (a)
Reason: To represent the sparse matrices, we have
Singly Linked List where each node contains non- zero elements of the matrix
|
|
Answer
: (e)
Reason: Linear Probing has a desired key is searched,
starting itself from hash address, sequentially in a table.
|
|
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
|
|
Answer
: (c)
Reason: Stack is used in conversion of an infix
expression to a postfix expression.
|
|
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.
|
|
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.
|
|
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.
|
|
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
|
|
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.
|
No comments :
Post a Comment