# Data Structure placement model papers

## Data Structure placement model papers

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 :

a. less than 1.
b. less than n.
c. less than m.
d. less than n/2.

2. The time required to delete a node x from a doubly linked list having n nodes is

a. O (n)
b. O (log n)
c. O (1)
d. O (n log n)

3. Which of the following sorting methods would be most suitable for sorting a list which is almost sorted

a. Bubble Sort
b. Insertion Sort
c. Selection Sort
d. Quick Sort

4. A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are

a. greater than n–1
b. less than n(n–1)
c. greater than n(n–1)/2
d. 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.

a. Cardinality
b. Assignment
c. Primitive
d. Structured

6. Which of the following sorting algorithm is stable

a. insertion sort.
b. bubble sort.
c. quick sort.
d. heap sort.

7. Which of the following is not the required condition for binary search algorithm?

a. The list must be sorted
b. there should be the direct access to the middle element in any sublist
c. There must be mechanism to delete and/or insert elements in list
d. none of above

ANSWER: c. 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

a. underflow
b. overflow
c. houseful
d. saturated

9. Which of the following is two way list?

d. none of above

10. The complexity of the average case of an algorithm is

a. Much more complicated to analyze than that of worst case
b. Much more simpler to analyze than that of worst case
c. Sometimes more complicated and some other times simpler than that of worst case
d. None or above

ANSWER: a. Much more complicated to analyze than that of worst case

11. Which of the following is not a limitation of binary search algorithm?

a. must use a sorted array
b. requirement of sorted array is expensive when a lot of insertion and deletions are needed
c. there must be a mechanism to access middle element directly
d. binary search algorithm is not efficient when the data elements are more than 1000.

ANSWER: d. binary search algorithm is not efficient when the data elements are more than 1000.

12. B Trees are generally

a. very deep and narrow
b. very wide and shallow
c. very deep and very wide
d. 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

a. full binary tree.
b. AVL tree.
d. complete binary tree.

14. One can convert a binary tree into its mirror image by traversing it in

a. inorder
b. preorder
c. postorder
d. any order

15. The number of leaf nodes in a complete binary tree of depth d is

a. 2d
b. 2d–1+1
c. 2d+1+1
d. 2d+1

16. A B-tree of minimum degree t can maximum _____ pointers in a node.

a. t–1
b. 2t–1
c. 2t
d. t

17. One of the major drawback of B-Tree is the difficulty of traversing the keys sequentially.

a. True
b. False

18. The best average behavior is shown by

a. Quick Sort
b. Merge Sort
c. Insertion Sort
d. Heap Sort

19. The extra key inserted at the end of the array is called a,

a. End key.
b. Stop key.
c. Sentinel.
d. Transposition.

20. The elements of an array are stored successively in memory cells because

a. by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated
b. the architecture of computer memory does not allow arrays to store other than serially
c. both of above
d. none of above

ANSWER: a. by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated

21. You have to sort a list L consisting of a sorted list followed by a few “random” elements. Which of the following sorting methods would be especially suitable for such a task?

a. Bubble sort
b. Selection sort
c. Quick sort
d. Insertion sort

22. A full binary tree with 2n+1 nodes contain

a. n leaf nodes
b. n non-leaf nodes
c. n-1 leaf nodes
d. n-1 non-leaf nodes

23. A full binary tree with n leaves contains

a. n nodes.
b. log n 2 nodes.
c. 2n –1 nodes.
d. n 2 nodes.

24. A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are

a. more than n
b. more than n+1
c. more than (n+1)/2
d. more than n(n-1)/2

25. The quick sort algorithm exploit _________ design technique

a. Greedy
b. Dynamic programming
c. Divide and Conquer
d. Backtracking

26. The total number of companions required to merge 4 sorted files containing 15, 3, 9 and 8 records into a single sorted file is

a. 66
b. 39
c. 15
d. 33

27. An adjacency matrix representation of a graph cannot contain information of :

a. nodes
b. edges
c. direction of edges
d. parallel edges

28. When inorder traversing a tree resulted E A C K F H D B G; the preorder traversal would return

a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG

29. The in order traversal of tree will yield a sorted listing of elements of tree in

a. Binary trees
b. Binary search trees
c. Heaps
d. None of above