Data Structure and Algorithm Analysis
Questions 41 to 50
41.
|
Let f, t:
N→R ³ 0, and
t (n) ÎO (f
(n)) iff t(n) ≤ c.f (n) where c is positive real constant
and
n ≥ no, then no is ___________
(a) Upper bound (b)
Lower bound
(c) Duality value (d) Threshold value (e) Maximum value.
|
42.
|
In a circular
queue, we can disambiguate empty from full queue by
(a) Using a gap in the array
(b) Incrementing queue positions by 2 instead
of 1
(c) Keeping a count of the number of elements
(d) (a) and (c) above
(e) (a), (b), and (c) above.
|
43.
|
In a
graph, a vertex with degree one is known as ___________
(a) Pendant vertex (b) Leaf
(c) Root (d)
End vertex (e)
Internal.
|
44.
|
Consider
the usual algorithm for determining whether a sequence of parentheses is
balanced. What is the maximum number of parentheses that will appear on the
stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5 or more.
|
45.
|
If a
graph G = (N, E), where E= {f}, then the corresponding adjacency
matrix is _____
(a) Unit Matrix
(b) Identity Matrix
(c) Having Diagonal elements Zero
(d) Matrix with all 1’s
(e) Zero Matrix.
|
46.
|
Suppose
we have an array implementation of the stack class, with ten items in the
stack stored at data[0] through data[9]. The SIZE is 42. Where does the push
method place the new entry in the array?
(a) data[0] (b) data[1] (c)
data[9] (d) data[10] (e) data[11].
|
47.
|
Breadth
first search __________
(a) Scans each incident node along with its
children.
(b) Scans all incident edges before moving to
other node.
(c) Is same as backtracking
(d) Scans all the nodes in random order.
(e) Scans all the nodes in pre-order manner.
|
48.
|
Provided
the space is available, then to insert an element in the queue, we can use
for the following structure
struct queue
{
int Q[20];
int f, r;
}Q;
(a) ++Q.Q[Q.r] = x; (b) Q.Q[++Q.r] = x; (c) Q.Q[Q.r]++ = x;
(d) Syntax error (e) Q.Q[Q.r++] = x;
|
49.
|
Which
method of traversal does not use stack to hold nodes that are waiting to be
processed?
(a) Dept First (b) D-search (c)
Breadth first
(d) Back-tracking (e) Bounding.
|
50.
|
If the
characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then
removed one at a time, in what order will they be removed?
(a) ABCD (b)
ABDC (c) DCAB (d) DCBA (e) ACDB.
|
Answers
41.
|
Answer : (d)
Reason : According to the mathematical definition of
the big Oh notation, this is the Threshold value defines the upper limit on
the size of the instance.
|
42.
|
Answer : (d)
Reason : The option B is not the suitable one and not
correct also, while the other two(a, c ) can be used
|
43.
|
Answer : (a)
Reason : According to the definition of the graph, and
the degrees of the vertex.
|
44.
|
Answer : (c)
Reason : Use stack and increment counter by one if
opening bracket is encountered, and decrement it by one if a closing bracket
is encountered.
|
45.
|
Answer : (e)
Reason : As E = empty set, means there is no any edge
between any two set of vertices. And hence it is zero matrix.
|
46.
|
Answer : (d)
Reason : As it is Stack always the items are pushed at
the top of the stack if there is any space. Also data[10] is the next space
as data[0] to data[9] are already filled.
|
47.
|
Answer : (b)
Reason : As BFS always make use of the Queue.
|
48.
|
Answer : (b)
Reason : Because first we have to increment the rear
pointer and at that place we can insert an element.
|
49.
|
Answer : (c)
Reason : As D search, DFS uses stack, so BFS only uses
queue and not the stack.
|
50.
|
Answer : (d)
Reason : As Queue follows FIFO structure.
|
No comments :
Post a Comment