# Data Structures Important Questions and Answers

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

## Important Questions and Answers on Data Structures

1. The variables which can be accessed by all modules in a program, are known as

(a) local variables

(b) external variables

(c) internal variables

(d) global variables

2. In what kind of storage structure for strings, one can easily insert, delete, concatenate and rearrange substrings?

(a) fixed length storage structure

(b) linked list storage

(c) variable length storage with fixed maximum

(d) array type storage

3. What is the time complexity of linear search algorithm over an array of n elements?

(a) O (\log _{2}n)

(b) O (n \log _{2}n)

(c) O (n)

(d) O (n²)

4. What is the time taken by binary search algorithm to search a key in a sorted array of n elements?

(a) O (\log _{2}n)

(b) O (n \log _{2}n)

(c) O(n)

(d) O(n²)

5. What is the time required to search an element in a linked list of length n?

(a) O(\log _{2}n)

(b) O(1)

(c) O(n)

(d) O(n²)

6. What is the worst case time required to search a given element in a sorted linked list of length n?

(a) O(1)

(b) O(log₂ n)

(c) O(n log₂ n)

(d) O(n)

7. Consider a linked list of n element which is pointed by an external pointer. What is the time taken to delete the element which is successor of the element pointed to by a given pointer?

(a) O(1)

(b) O(log₂ n)

(c) O(n)

(d) O(n log₂ n)

8. Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer?

(a) O(1)

(b) O(n)

(c) O(log₂ n)

(d) O(n \log _{2}n)

9. Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?

(a) deleting a node whose location is given

(b) searching an unsorted list for a given item

(c) inserting a node after the node with a given location

(d) traversing the list to process each node.

10. Which data structure is needed to convert infix notations to postfix notations?

(a) Queue

(b) Stack

(c) linear list

(d) tree

11. Recursive procedures are implemented by

(a) Queues

(b) linked lists

(c) stacks

(d) strings

12. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as

(a) Queues

(b) Tree

(c) Stacks

(d) queue

13. Consider a linked list implementation of a queue with two pointers: front and rear. What is the time needed to insert element in a queue of length n?

(a) O(1)

(b) O(n)

(c) O(log₂ n)

(d) O(n log₂ n)

14. A linear list in which elements can be added or removed at either end but not in the middle is known as

(a) Queue

(b) Stack

(c) Deque

(d) tree

15. What is the time required to insert an element in a stack with linked implementation?

(a) O(1)

(b) O(n)

(c) O(\log _{2}n)

(d) O(n log₂ n)

16. 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) threaded tree

(c) 2-tree

(d) complete binary tree

17. A list of integers is read in, one at a time, and a binary search tree is constructed. Next the tree is traversed and the integers are printed. Which traversed would result in a printout which duplicates the original order of the list of integers?

(a) Preorder

(b) Inorder

(c) Postorder

(d) none of the above

18. The five items: A, B, C, D, and E are pushed in a stack, one after the other starting from A. The stack is popped four times and each element is inserted in a queue. Then two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is

(a) A

(b) C

(c) B

(d) D

19. The time required to search an element in a binary search tree having n elements is

(a) O(1)

(b) O(n)

(c) O(log₂n)

(d) O(n log₂ n)

20. Consider that n elements are to be sorted. What is the worst case time complexity of Bubble sort?

(a) O(1)

(b) O(n)

(c) O(log₂ n)

(d) O(n²)

21. Consider that n elements are to be sorted. What is the worst case time complexity of Shell sort?

(a) O(n)

(b) O(n^{1.2})

(c) O(n log₂ n)

(d) O(n²)

22. What is the worst case time complexity of straight insertion sort algorithm to sort n elements?

(a) O(n)

(b) O(n^{1.2})

(c) O(n log₂ n)

(d) O(n²)

23. What is the worst case time complexity of binary insertion sort algorithm to sort n elements?

(a) O(n)

(b) O(n^{1.2})

(c) O(n log₂ n)

(d) O(n²)

24. If each node in a tree has value greater than every value in its left subtree and has value less than every value in its right subtree, the tree is known as

(a) complete tree

(b) binary search tree

(c) full binary tree

(d) threaded tree

25. Which of the following sorting procedure is the slowest?

(a) Quick sort

(b) Shell sort

(c) Heap so t

(d) Bubble sort

26. The infix expression A+ ((B-C) * D) is correctly represented in prefix notation as

(a) A + B – C*D

(b) ABC – D*+

(c) +A*-BCD

(d) A+ BC-D*

27. A list of data items usually words or bytes, with the accessing restriction that elements can be added or removed at one end of the list only, is known as

(a) Stack

(b) Memory

(c) linked list

(d) heap

28. In what order the elements of a pushdown stack are accessed

(a) First In First Out (FIFO)

(b) Last In First Out (LIFO)

(c) Last In Last Out (LILO)

(d) none of the above

29. Which of the following is a tabular listing of contents of certain registers and memory locations at different times during the execution of a program?

(a) Loop program

(b) subroutine program

(c) Program trace

(d) byte sorting program

30. How many value can be held by an array A(-1..m, 1..m)?

(a) m

(b) m(m + 1)

(c) m²

(d) m(m + 2)

31. An undirected graph with n vertices and e edges are represented by Adjacency matrix. What is the time required to determine whether the graph is connected?

(a) O(e)

(b) O(n²)

(c) O(n)

(d) O(e+n)

32. An undirected graph with n vertices and e edges are represented by Adjacency matrix. What is the time required to determine the degree of any vertex?

(a) O(e)

(b) O(n²)

(c) O(n)

(d) O(e+n)

33. A directed graph with n vertices and e edges are represented by Adjacency matrix. What is the time required to determine the in degree of a vertex?

(a) O(e)

(b) O(n²)

(c) O(n)

(d) O(e + n)

34. An undirected graph G with n vertices and e edges are represented by Adjacency list. What is the time required to determine the total number of edges in G?

(a) O(e)

(b) O(n²)

(c) O(n)

(d) O(e+n)

35. Consider an undirected graph G with n vertices and e edges. What is the time taken by Depth First Search (DFS) if the graph is represented by (i) Adjacency matrix, and (ii) Adjacency list?

(a) O(n²), O(n)

(b) O(n²), O(e)

(c) O(e), O(n²)

(d) O(e + n), O(e)

36. Which of the following statements is false?

(a) every tree is a bipartite graph

(b) a tree with n nodes contains n-1 edges.

(c) a tree contains a cycle

(d) a tree is a connected graph

37. An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?

(a) O(n)

(b) O(e+n)

(c) O(e)

(d) O(e²)

38. A graph G with n nodes is bipartite if it contains

(a) n edges

(b) no cycle of odd length

(c) a cycle of odd length

(d) n² edges

39. In what tree, for every node the height of its left subtree and right subtree differ at least by one

(a) binary search tree.

(b) Complete tree

(c) AVL-tree

(d) Threaded binary tree

40. Which of the following sorting method is stable?

(a) straight insertion sort

(b) Shell sort

(c) binary insertion sort

(d) Heap sort

41. A complete binary tree with the property that the value at each node is at least as large as the values at its children is known as

(a) binary search tree

(b) Completely balanced tree (0)

(c) AVL tree

(d) Heap

42. The recurrence relation T(n) = mT(n/2)+an² is satisfied by

(a) T(n) = O(nm)

(b) T (n) = log m

(c) T(n) = O(n log m)

(d) T(n)= O(m log n)

43. The time required to find shortest path in a graph with n vertices and e edges is

(a) O(e)

(b) O(e²)

(c) O(n)

(d) O(n²)

44. The goal of hashing is to produce a search that takes

(a) O(1) time

(b) O(log n) time

(c) O(n²)time

(d) O(n log n) time

45. In which of the following sorting algorithm the number of comparisons needed is the minimum if the items are initially in reverse order and is the maximum if the items are in order?

(a) Straight insertion sort

(b) Heap sort

(c) binary insertion sort

(d) Bubble sort

46. Which of the following best describes sorting?

(a) accessing and processing each record exactly once

(b) finding the location of the record with a given key

(c) arranging the data (record) in some given order

(d) adding a new record to the data structure

47. The order of magnitude of the worst case performance of the linear search over N elements is

(a) N log₂ N

(b) N²

(c) N

(d) log₂ N

48. The order of magnitude of the worst case performance of the binary search over N elements is

(a) N log₂ N

(b) N²

(c) N

(d) log₂ N

49. The order of magnitude of the worst case performance of ordered binary tree with N elements is

(a) N log₂ N

(b) N²

(c) N

(d) log₂ N

50. A search procedure which associates an address with a key value and provides a mechanism for dealing with two or more values assigned to the same address is called

(a) linear search

(b) hash coded search.

(c) binary search

(d) radix search