Data Structures Interview
Questions
1. If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :
1. less than 1. 2. less than n. 3. less than m. 4. less than n/2.
2. The time required to delete a node x from a doubly linked list having n nodes is
1. O (n) 2. O (log n) 3. O (1) 4. O (n log n)
3. Which of the following sorting methods would be most suitable for sorting a list which is almost sorted
1. Bubble Sort 2. Insertion Sort 3. Selection Sort 4. Quick Sort
4. A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are
1. greater than n–1 2. less than n(n–1) 3. greater than n(n–1)/2 4. less than n2/2
5. An ADT is defined to be a mathematical model of a user-defined type along with the collection of all ____________ operations on that model.
1. Cardinality 2. Assignment 3. Primitive 4. Structured
6. Which of the following sorting algorithm is stable
1. insertion sort. 2. bubble sort. 3. quick sort. 4. heap sort.
7. Which of the following is not the required condition for binary search algorithm?
1. The list must be sorted 2. there should be the direct access to the middle element in any sublist
3. none of above 4. There must be mechanism to delete and/or insert elements in list
8. When new data are to be inserted into a data structure, but there is no available space; this situation is usually called
1. underflow 2. overflow 3. houseful 4. saturated
9. Which of the following is two way list?
1. grounded header list 2. circular header list
3. linked list with header and trailer nodes 4. none of above
10. The complexity of the average case of an algorithm is
1. Much more complicated to analyze than that of worst case
2. Much more simpler to analyze than that of worst case
3. Sometimes more complicated and some other times simpler than that of worst case
4. None or above
11. Which of the following is not a limitation of binary search algorithm?
1. must use a sorted array
2. requirement of sorted array is expensive when a lot of insertion and deletions are needed
3. there must be a mechanism to access middle element directly
4. binary search algorithm is not efficient when the data elements are more than 1000.
12. B Trees are generally
1. very deep and narrow 2. very wide and shallow 3. very deep and very wide 4. cannot say
13. A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as
1. full binary tree. 2. AVL tree. 3. threaded tree. 4. complete binary tree.
14. One can convert a binary tree into its mirror image by traversing it in
1. inorder 2. preorder 3. postorder 4. any order
15. The number of leaf nodes in a complete binary tree of depth d is
1. 2d 2. 2d–1+1 3. 2d+1+1 4. 2d+1
