# Data Structure and Algorithm Analysis Set 5

## 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 through data. The SIZE is 42. Where does the push method place the new entry in the array? (a) data               (b) data               (c) data               (d) data             (e) data. 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;               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 is the next space as data to data 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.

<< PrevNext >>

#### No comments :

What you think about these Questions and Answers ? Let me know in comments.