1. In a depth-first search of an undirected graph G, every edge of G is:

(a) Either a tree edge or a back edge
(b) Either a forward edge or a cross edge
(c) Either a left edge or a right edge
(d) Either a front edge or a parallel edge

Answer: (a)

2. The time required to perform a sequence of data structure operations is averaged over all the operations performed is called:

(a) Average case analysis
(b) Amortized analysis
(c) Performance analysis
(d) Best case analysis

Answer: (b)

3. Which algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative?

(a) Dijkstra algorithm
(b) Bellman-Ford algorithm
(c) Ford-Fulkerson algorithm
(d) Prim algorithm

Answer: (b)

4. Which of the following statements are correct regarding asymptotic notation?

1. 𝑂-notation provides an asymptotic upper bound on a function
2. Ω- notation provides an asymptotic lower bound on a function
3. 𝜃- notation provides an asymptotic lower bound on a function

(a) 1 and 2 only
(b) 1 and 3 only
(c) 2 and 3 only
(d) 1, 2 and 3

Answer: (a)

5. What is the asymptotic bound for the following recurrence using master theorem method?



Answer: (b)

6. The primary determinant in selecting activities in each iteration of the spiral model of software development is:

(a) Cost
(b) Iteration size
(c) Constraints
(d) Risk

Answer: (d)

7. Which one of the following testing is essentially a set of path test performed to examine the many different paths through the modules?

(a) Integration testing
(b) Unit testing
(c) Function testing
(d) System testing

Answer: (b)

8. An approach which is very simple in its philosophy where basically all the modules are constructed and tested independently of each other and when they are finished, they are all put together at same time is:

(a) Top-Down strategy
(b) Bottom-Up strategy
(c) Big-Bang strategy
(d) Breadth-First strategy

Answer: (c)

9. Capability maturity model in software engineering is a technique which is used to improve the:

(a) Testing
(b) Understanding of the software
(c) Software process
(d) Prototype model

Answer: (c)

10. A model which enables the developer to apply the prototyping at any stage in evolution of the product and which addresses the risks associated with software development is:

(a) Spiral model
(b) Prototype model
(c) Water fall model
(d) V-shape model

Answer: (a)