 # Data Structure and Algo Questions

This Test will cover basic concepts of data Structure and related algorithm.

Q. Which of the following tree is height balance binary search tree?
 A. Red black tree B. Complete binary tree C. Extended binary tree D. M-way search tree
Q. For the given in-order and pre-order traversal of binary tree, calculate post-order traversal:
In-Order: 4 2 5 1 6 3 7
Pre-Order: 1 2 4 5 3 6 7
 A. 4 5 2 6 7 3 1 B. 5 4 2 7 6 3 1 C. 5 4 2 6 7 3 1 D. 4 5 6 7 2 3 1
Q. Which of the following is a sub problem of travelling salesman problem?
 A. Simple walk B. Hamiltonian cycle C. Euler's cycle D. Closed circuit

Q. Which of the following is a valid declaration of three dimensional array?
 A. Int arr [ ] [5 ] [6 ]; B. Int arr [ 5] [ ] [6 ]; C. Int arr [ 6] [5 ] [ ]; D. Int arr [ ] [ ] [6 ];
Q. Boolean satisfiability problem with 2 and 3 literals respectively are:
 A. NP –complete and P B. both P C. both NP D. NP- Complete and NP-hard
Q. Suppose a person has four friends. He wants to visit to all of his friends using the shortest route possible. Moreover he is also restricted to visit every friend house exactly once. This problem can solved optimally using which of the following algorithm?
 A. Huffman's Encoding B. Travelling salesman problem C. Prim's algorithm D. Floyd warshall's algorithm
Q. What can be the possible time complexity to search an element in a Binary search tree?
\
 A. O(n log n) B. O(n) C. O(n2) D. O(n2logn)
Q. Which of the following algorithm may lead to forest in intermediate stages when applied on a weighted graph?
 A. Prim's Algorithm B. kruskal's algorithm C. Both (A) & (B) D. none of the above

Q. Ram wants to evaluate the post fix notation equation in his data structure exam. Which of the following data structure will be sufficient enough?
 A. One Queue B. One Priority list C. Two Linked list D. One Stack
Q. There is a group of 100 people. Every person in the group is having some relation with every other person. We want to represent this relationships among people using graph. Which of the following will be best suited choice for this operation?
 A. Adjacency list B. Adjacency matrix C. Any of (A) or (B) D. None of the above
Q. We have to implement balanced parenthesis problem using a stack. But stack is not directly available to us. We are only provided with a set of queues. What is the minimum number of queues required for implementing this problem?
 A. Atleast 1 B. Atleast 2 C. Atleast 3 D. Atleast 4
Q.Which of the following algorithm is best suited for finding all pair of shortest path in a graph?
 A. Dijkastra's algorithm B. Bellman ford algorithm C. Floyd warshall's algorithm D. Ford Fulkerson's algorithm

Q. What is the time complexity of bubble sort in the best possible case?
 A. O(n) B. O(n2) C. O(n1.5) D. O(n0.5)
Q. What is the maximum depth of the stack required to process below graph using DFS? A. 5 B. 4 C. 3 D. 2
Q. What is the amortized time complexity required to apply Breadth first traversal on a graph having `n` nodes, `e` edges and `k` components ?
 A. O(e + n) B. O(e + nlog k) C. O(elog k + n) D. O(elogn)