Data Structure and Algorithm Analysis
Questions 271 to 280
271.

The suitable data structure to represent the data of
rainfall of week days in ten cities of three states is __________
(a) Stack (b) Queue (c) Array
(d) Multi
way tree (e) Connected
graph.

The data structure which allows the insertion at both the
ends, but allows the deletion at only one end is ________
(a) Output restricted Deque
(b) Input restricted Deque
(c) Circular queue
(d) Linear queue
(e) Priority queue.


Searching the linked list requires linked list be created
in _________
(a) Ascending
order (b) Descending order
(c) With underflow condition (d) Any order (e)
Without underflow condition.


The time complexity of binary search in best, worst cases
for an array of size N is
(a) N, N^{2} (b) N,
N (c) Log
N, N^{2} (d) 1,
N log N (e) 1,
log N.


How many minimum number of spanning trees, one can have
from a given connected graph with N nodes is having different weights for the
edges.
(a) N1 (b) One (c) 1/(N+1) 2N_{CN}
(d) 2N_{CN} (e) N.


How many children do an external node of a binary tree of
order N contains.
(a) N at least (b) 2 exactly (c) More than two (d) 0 (e) N
at most.


Inorder traversal of binary search tree implies visiting
the nodes in __________
(a) Postorder
(b) The order of
increasing magnitude of their key
(c) Preorder
(d) The order of
decreasing magnitude of their key N
(e) Arbitrary order.


For a binary tree the Inorder traversal was found to be
as HIGCEFD. Once the postorder traversal was conducted the output is
IHGFEDC. What is the perorder for the given tree?
(a) CGDHEIF (b) GHICDEF (c)
CGHIDEF
(d) CDEFGHI (e) Data
insufficient and hence can’t be answered.


Breadth first search uses __________ as an auxiliary
structure to hold nodes for future processing.
(a) Stack (b) Linked list (c) Graph (d) BTree (e) Queue.


Folding is a method of generating ________
(a) A hash function
(b) Index function
for a triangular matrix
(c) Header node for
a circular linked list
(d) Linear probing
(e) Chaining.

Answers:
271.

Answer : (c)
Reason: As the array
can keep the data for multiple dimension values which is not possible by
using any other data structure given in the question.

Answer : (a)
Reason: Because in
Deque insertion and deletion can take place at any end, but in the question
it is given as deletion is allowed only at one end. Hence it is Output restricted Deque


Answer : (d)
Reason: Because the
reference of the next node is stored in the node itself with which one can go
to next node, and hence a particular order is not required.


Answer : (e)
Reason: Because if
the list is either small or the element is present at the mid position for
the first call to the function or for the first iteration then it takes one
unit of time. In worst case it takes log
n time,


Answer : (b)
Reason: Because one
can have at most one tree which is minimum, also the weights are different.


Answer : (d)
Reason: Because
external node is a leaf node, that can’t have the children


Answer : (b)
Reason: Because if
we traverse a BST in inorder, then it
is nothing but traversing in the
order of increasing magnitude of their key.


Answer : (c)
Reason: Draw the
tree according to the asked inorder and postorder and traverse the tree in
preorder.


Answer : (e)
Reason: As this
requires the traversing of nodes on the same level before traversing the
nodes at next level of the tree, it requires queue.


Answer : (a)
Reason: Because
folding is one of the method of hashing function to locate the key.

No comments :
Post a Comment