This section contains more frequently asked Data Structure Fundamentals Multiple Choice Questions Answers in the various University level and competitive examinations.
1. When we say an algorithm has a time complexity of O (n), what does it mean?
- The algorithm has ‘n’ nested loops
- The computation time taken by the algorithm is proportional to n
- The algorithm is ‘n’ times slower than a standard algorithm
- There are ‘n’ number of statements in the algorithm
2. Can we read a data item at any location of a list within a constant time (i.e. O(1))?
- Yes
- Yes, only if the list is implemented by pointers (i.e. linked-list)
- Yes, only if the list is implemented by an array
- No, we need O(n) computation steps no matter what kind of implementation is used
3. Sequential search has a time complexity of O(n), and binary search has a time complexity of O(log(n)). What difference will it make when the size n is 1000?
- You would not notice much difference because computers run very fast anyway
- As n is 1000, binary search is twice as fast as sequential search
- As n is 1000, binary search is 10 times as fast as sequential search
- As n is 1000, binary search is 100 times as fast as sequential search.
4. Readthe following statements carefully, and choose the correct answer. I. The Ω notation is Anti Symmetric. II. The big Oh notation is Semi Equivalence.
- (I) is FALSE but (II) is TRUE
- Both (I), (II) are TRUE
- (I) is TRUE but(II) is FALSE
- Both (I), (II) are FALSE
5. Find the odd one out.
- Merge Sort
- TVSP Problem
- KnapSack Problem
- OBST Problem
6. 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.
- N-1
- One
- 1/(N+1) 2NCN
- 2NCN
7. The mathematical definition for Omega can be defined as, provided f,g:NR+ and c is a positive constant and n > n0,
- f(n)≥ c. g(n) n
- f(n) £ c. g(n) n
- f(n) ≥ c + g(n) n
- f(n) £ c + g(n) n
- f(n) £ g(n) n.
8. The OBST algorithm in worst case takes _______ time if all c(i, j )’s and r(i, j)’s are calculated.
- O(log n)
- O(n^4)
- O(n^3)
- O(n log n)
9. The notation is __________ I. Symmetric. II. Reflexive. III. Transitive.
- Only (I) above
- Only (II) above
- Only (III) above
- All (I), (II) and (III) above.
10. Breadth first search uses __________ as an auxiliary structure to hold nodes for future processing.
- Stack
- Linked list
- Graph
- Queue