# Data Structures Sample Questions and Answers

The Free download links of **Data Structures Sample Questions and Answers** Papers enclosed below. Candidates who are going to start their preparation for the Data Structures Sample papers can use these links. Download the Data Structures Sample Papers PDF along with the Answers. Data Structures Sample Papers are updated here. A vast number of applicants are browsing on the Internet for the Data Structures Sample Question Papers & Syllabus. For those candidates, here we are providing the links for Data Structures Sample Papers. Improve your knowledge by referring the Data Structures Sample Question papers.

## Sample Questions and Answers on Data Structures

1. The number of possible commutative binary operations that can be defined on a set of n elements (for a given n) is.

(a) 2

(b) 2n

(c) n

(d) n^{2}

2. Number of rooted binary trees with n nodes is equal to

(a) the number of ways of multiplying (n+1) matrices.

(b) the number of ways of arranging n out of 2n distinct elements.

(c) 2n/n(n+1)

(d) <n

3. The complexity of comparison based sorting algorithms is

(a) θ (n log n)

(b) θ (n 2)

(c) θ (n)

(d) θ (n A n)

4. Consider the number given by the decimal expression

16³ * 9+16² * 7+16*5+3

The number of I’s in the unsigned binary representation of the number is 9

(a) 6

(b) 9

(c) 16

(d) 12

5. The minimum number of comparison required to sort 5 element is

(a) 6

(b) 15

(c) 10

(d) none of the above

6. The following sequence of operations is performed on a stack.

PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSHEW, POP

The sequence of values popped out is

(a) 20, 10, 20, 10, 20

(b) 10, 20, 20, 10, 20

(c) 20, 20, 10, 10, 20

(d) 20, 20, 10, 20, 10

7. Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is

(a) O (m)

(b) O (m+n)

(c) O (n)

(d) none of the above

8. Maximum number of edges in a planer graph with n vartices is 3 n-6

(a) n

(b) 3n

(c) 3n-2

(d) 3n-6

9. A-2-3 tree is a tree such that

1. all internal nodes have either 2 or 3 children.

2. all paths from root to the leaves have the same length.

The number of internal nodes of a 2-3 tree having 9 leaves could be

(a) 4

(b) 5

(c) 6

(d) 7

10. A non planer graph with minimum number of vertices has

(a) 10 edges, 5 vertices

(b) 6 edges, 4 vertices

(c) 9 edges, 6 vertices

(d) 9 edges, 5 vertices

11. Which of the following algorithm(s) can be used to sort n integers in the range [1 n3] in O(n) time?

(a) Heap Sort

(b) Quick Sort

(c) Merge Sort

(d) Radix Sort

12. The number of distinct simple graphs with upto three nodes is

(a) 15

(b) 7

(c) 10

(d) 9

13. The recurrence relation that arises in relation with the complexity of binary search is

(a) T (n)= T (n/2) + K

(b) T(n)= T (n/2) + log n

(c) T (n)=2T (n/2) + K

(d) T (n)= T (n/2) + n

Where K is a constant

14. Which on the following permutations can be obtained in the output (in the same order), using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?

(a) 3, 4, 5, 1, 2

(b) 3, 4, 5, 2, 1

(c) 1, 5, 2, 3, 4

(d) 5, 4, 3, 2, 1

15. The number of distinct simple graphs with up to three nodes

(a) 15

(b) 10

(c) 9

(d) 7

16. Linked lists are not suitable data structure for which one of the following problems?

(a) Insertion Sort

(b) Binary Search

(c) Radix

(d) Polynomial Manipulation

17. Which of the following algorithm design techniques is used in the quick sort algorithm?

(a) Dynamic Programming

(b) Divide and Conquer

(c) Back tracking

(d) Greedy Method

18. Merge sort uses

(a) Divide and conquer strategy

(b) Heuristic

(c) Back tracking approach

(d) Greedy approach

19. For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of

(a) 0 (m)

(b) 0 (n)

(c) 0 (m+n)

(d) 0 (log m+ log n)

20. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is

(a) \log _{2}n

(b) n

(c) n-1

(d) 2^{n}

21. Minimum number of edges in a connected cyclic graph of n vertices is

(a) n-1

(b) n

(c) n+1

(d) none of the above

22. The post fix expression for the infix expression A+B* (C+D)/F+D *E, is

(a) ABCD+* F/DE* ++

(b) A+ * BCD/F* DE ++

(c) AB+CD+*F/D + E*

(d) A*B+CD/F* DE ++

23. An advantage of chained hash table over the open addressing scheme is

(a) worst case complexity of search operation is less

(b) space used is less

(c) deletion is easier

(d) none of the above

24. Which of the following sequences denotes the post order traversal sequence of the tree of question (27) ?

(a) feg cd ba

(b) g c d b f e a

(c) g c b dafe

(d) f ed g c b a

25. The minimum number of inter changes needed to convert the array 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70 into a heap with maximum element at the root is

(a) 1

(b) 2

(c) 3

(d) None of above

26. The recurrence relation.

T (1)=2

T(n)=3T (n/4)+n, has the solution T(n) equal to

(a) 0 (n)

(b) 0 (n³/4)

(c) 0 (log n)

(d) None of above

27. The average number of key comparisons done on a successful sequential search in list of length in is

(a) log n

(b) (n-1)/2

(c) n/2

(d) (n+1)/2

28. A binary tree is generated by inserting in order the following integers

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

the number of nodes in the left subtree of the root respectively is

(a) (4, 7)

(b) (8, 3)

(c) (7, 4)

(d) (3, 8)

29. Quick sort is run on two inputs shown below to sort in ascending order

1. 1, 2, 3, … n

2. n, n-1, n-2, … 2, 1

Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then

(a) C₁ <C₂

(b) C₁ > C₂

(c) C₁=C₂

(d) we cannot say anything for arbitrary n

30. The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

(a) singly linked list

(b) circular doubly linked list

(c) doubly linked list.

(d) array implementation of list

31. Which of the following is essential for converting an infix expression to the post fix form efficiently?

(a) An operator stack

(b) An operand stack

(c) An operand stack and an operator stack

(d) A parse tree

32. Heap allocation is required for languages

(a) that support recursion

(b) that support dynamic data structure

(c) that use dynamic scope rules

(d) none of the above

33. A polynomial p (x) is such that p (0) = 5, p(1) = 4, p(2) = 9 and p(3) = 20 the minimum degree it can have is

(a) 1

(b) 2

(c) 3

(d) 4

34. A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre order and the values are printed out. Which of the following sequences is a valid output

(a) 53124786

(b) 53126487

(c) 53241678

(d) 53124768

35. A priority queue is used to implement a stack S that stores characters PUSH (C) is implemented as INSERT (Q. C, K) where K is an appropriate integer key closed by the implementation. POP is implemented as DELETEMIN (Q). For a sequence of operations, the key chosen are in

(a) non-increasing order

(b) strictly increasing order

(c) non-decreasing order

(d) strictly decreasing order

36. The number of functions from an m element set to an n element set is

(a) m+n

(b) mn

(c) nm

(d) m-n

37. Suppose A is a finite set with n elements. The number of elements in the largest equivalence relation of A is

(a) n

(b) n^{2}

(c) 1

(d) n+1

38. Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

(a) Dynamic programming

(b) Greedy

(c) Back tracking

(d) Divide and Conquer

39. How may substrings of different lengths (non zero) can be formed from a character string of length n?

(a) n

(b) 2n

(c) n²

(d) n(n+1)/2

40. Which of the following statement is false?

(a) A tree with n nodes has (n-1) edges

(b) A labled rooted binary tree can be uniquely constructed given its post order and preorder traversal results.

(c) A complete binary tree with internal nodes has (n + 1) leaves.

(d) The maximum number of nodes in a binary tree of height h is (2″+1-1).

41. The number of binary relations on a set with n elements is

(a) n²

(b) 2^{n}

(c) 2^{n^{2}}

(d) None of the above

42. The number of binary strings of n zeroes and K ones such that no two ones are adjacent

(a) n H C_{k}

(b) nC_{KH}

(c) n C_{k}

(d) none of above

43. If one uses straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17

then the order of these elements after the 2nd pass of the algorithm is

(a) 8, 9, 15, 20, 47, 4, 12, 17, 13, 40

(b) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17

(c) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17

(d) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40

44. If n is a power of 2, then the minimum number of multiplication needed to compute an is

(a) \log _{2}n

(b) √n

(c) N

(d) n-1

45. The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit numbers is

(a) 0 (n²)

(b) 0 (n)

(c) 0 (1)

(d) 0 (n log n)

46. Which of the following is correct?

(a) B-trees are for storing data on disk and B trees are for main memory.

(b) Range quenes are faster on B+ trees.

(c) B-trees are for primary indexes and B’ trees are for secondary indexes.

(d) The height of B trees is independent of number of records.

47. Consider the following nested representation of binary trees (xyz) indicates y and z are the left right subtrees, respectively, of node x. Note that y and may be NULL or further nested. Which of the following represents a valid binary tree?

(a) (1 2 (4 5 6 7))

(b) (1 ((2 3 4) 5 6) 7)

(c) (1 (234) (567))

(d) (1 (23 NULL) (45))

48. B+ trees are preferred to binary trees in data bases because

(a) disk capacities are greater than memory capacities.

(b) disk access is much slower than memory Access.

(c) disk data transfer rates are much less than memory data transfer rates.

(d) disks are more reliable than memory.

49. The most widely used method for interpreting bit setting as non negative integers is the

(a) Octal number system

(b) ASCII

(c) ANSI

(d) Binary number system

50. The method used by computers to represent real number is

(a) floating point notation

(b) base

(c) mantissa

(d) exponent