ITM UNIVERSITY,GWALIOR

Data StructureQuestion Bank

1. What is an algorithm? What are the characteristics of a good algorithm?

2. How do you find the complexity of an algorithm? What is the relation between the
time and space complexities of an algorithm? Justify your answer with an example.
3. Define the term array. How are two-dimensional arrays represented in memory?
Explain how address of an element is calculated in a two dimensional array.
4. What do you mean by complexity of an algorithm? Explain the meaning of worst case
analysis and best case analysis with an example.
5. What is a linear array? Explain how two-dimensional arrays are represented in
memory.
6. Define data type and abstract data type. Comment upon the significance of both.
7. Explain the concept of primitive data structures.
8. Explain data types & why do we need data types?
9. What is a data structure and what are the difference between data type, abstract data
type and data structure ?
10. What are the different ways of analyzing algorithm.
11. Define data structure. Differential between linear and nonlinear data structure. Give a
brief description of the following operations with example.
(i) Traversing
(ii) Sorting
(iii) Searching
12. Define array with example. Give representation of array in memory. Write to traverse
a linear array algorithm.
13. Define the following with:
(i) Record
(ii) Recursion
(iii) Dequeue
(iv) Priority queue
14. What is primitive and non-primitive data structures? Explain different operations,
which are generally performed on any linear structure.
15. Write briefly the advantages and disadvantages of storage elements as a linear array.

16.What is sparse matrix?

17. What is header linked list? Discuss various types of headers linked list with
example and also write the use of header node in linked list.
18. Differentiate between array and linked list.
19. Using a bubble sort algorithm, find the number C of comparisons and the number
D of interchanges which alphabetize the n=6 letter in PEOPLE.

20.Is it possible to create a circular doubly-linked list from a normal doubly-linked

list? If yes, then explain with an example?
 ITM UNIVERSITY,GWALIOR

21. Convert the following infix expressions into its equivalent postfix
expressionsWhat is stack? Write down the code for the procedure push,
pop and initialize.
22. Write a recursive procedure to solve tower of Hanoi problem.
23. Using the stack operations write algorithms for converting an expression from infix
to postfix.
24. Consider the following arithmetic expression p written in postfix notation
P = 3,4,5, +, *,2, *
Show the equivalent infix expression
25. Why is stack known as LIFO structure?
26. Consider the following arithmetic expression P written in postfix notation:
a) P: 5, 6, 2, +, *, 12, 4, /, -
b) P: 3, 5, +, 6, 4, -, *, 4, 1, -, 2, ↑, +
c) P: 3, 1, +, 2, ↑, 7, 4, -, 2, *, +, 5, -
Convert each expression into infix notation and then evaluate.

27.Convert the following expression into prefix and postfix notations using stack:
(i) a+b-c
(ii) a+b*c/d+e
28. What are circular queues? Write down routines for inserting and deleting
elements from a circular queue implemented using arrays.
29. Declaring a queue type data structure, write procedures to add and delete item
from a
30. Circular queue implemented as an array.
31. What is queue? Write an algorithm to add an element in the queue
32. Explain circular queue and priority queue.
33. Explain different type of queue with the help of examples.
34. Define a queue. Explain in brief why circular implementation is better than linear
implementation.
35. Give algorithms for the following:
a. Deletion operation of input-restricted dequeue
b. Addition operation for output-restricted dequeue.

36. What is queue? What are applications of queue and stack.

37. What are the limitations of linear queue and how is it solved by circular queue?

38. Find the average case time complexity of a quick sort algorithm.

39. What is tower of Hanoi problem? Find the moves to transfer the n=3 numbers
of disks from peg A to Peg C using auxiliary peg B.
TOWER (3, A, B, C).
40. Write the steps to implement a queue using two stacks.

41. Consider the following infix expression Q:

Q: A*(B+D)/E-F*(G+H/K)
Use the algorithm to translate Q into its equivalent postfix expression P.
 ITM UNIVERSITY,GWALIOR

42. Write an algorithm to insert a node in the beginning of the linked list.
43. Write an algorithm INSERT that takes a pointer to a sorted list and a pointer to
a nodeand inserts the node into its correct position in the list.
44. Let P be a pointer to a singly linked list. Show how this list may be used as a
stack.That is, write algorithms to push and pop elements. Specify the value
of P when thestack is empty.
45. Write a complete program in C/C++ to create a single linked list. Write
functions to do the following operations
(i) Insert a new node at the end
(ii) Delete the first node
46. Devise a representation for a list where insertions and deletions can be made
at eitherend. Such a structure is called Deque (Double ended queue). Write
functions for inserting and deleting at either end.
47. Write a procedure to reverse a singly linked list.
48. Write a procedure to insert a node into a linked list at a specific position and
draw thesame by taking any example?
49. Design an algorithm for reversing a singly link list.
50. What is doubly link list? Write the procedure for creating a doubly
link list anddeleting an element from this list.
51. Give a detailed comparative study of linked and contiguous allocation Schemes.
52. What is link list? Write an algorithm to insert a node in the beginning of a link list.
53. Explain the merits and demerits of link list.
54. Explain doubly link list. give its only one difference from one way list.
55. Describe traversal in circular list.
56. Define the following :
a. link list
b. header link list
c. doubly link list
d. circular link list
57. Write an algorithm to insert a given item follows the node with location LOC.
58. Write an algorithm for the following:
a. Searching of an specified item in an unsorted list
b. Traversing of link list
59. Define link list. Explain various types of link list with the help of an example.
Write an algorithm for inserting an element into sorted link list. Assuming that the link
list is implemented as a single linked list.
60. What do you understand by linked allocation? Explain the advantages of
allocationover sequential allocation.
61. How link list can be represented in memory? Explain following in context of
link listwith the help of algorithm
a. Traversing
 ITM UNIVERSITY,GWALIOR

b. Searching (list is unsorted)

62. What do you understand by static & dynamic link list?
63. Explain some important applications of a link list ?
64. Write an algorithm to insert and delete items from a doubly link list ?
65. Write an algorithm for traversing a link list ?
66. Explain the condition of overflow and underflow in link list ?

67. Find the complexity of heap sort.

68. Find the final tree by inserting the following numbers in an empty binary search
tree.
14, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 23

69. Construct a binary tree whose nodes in inorder and preorder are given as
follows:
Inorder: 10,15,17,18,20,25,30,35,38,40,50
Preorder: 20,15,10,18,17,30,25,40,35,38,50

70. Construct a B-tree of order 3 by inserting the following keys in the order shown
into an empty B-tree.
MQANPWXTGEJ

71. Draw a complete binary tree with exactly six nodes. Put a different value in
each node. Then draw an array with six components and show where each of
the six node values would be placed in the array (using the usual array
representation of a complete binary tree).
 ITM UNIVERSITY,GWALIOR

72. Explain what is Linear (Sequential) Search and when may we use one.
73. Compare Binary Search vs Linear Search
74. What is Binary Search and find item =33
in data-11,22,33,44,55,66,77,88,99
75. What is quick sort? Sort the following array using quick sort method. 24 56
47 35 1090 82 31
76. Describe insertion sort with a proper algorithm. What is the complexity of
insertionsort in the worst case?
77. Show the various passes of bubble sort on an unsorted list 11, 15, 2, 13, 6
78. Compare and contrast various sorting techniques with respect to memory
space andcomputing time.
79. Write down the algorithm of quick sort.
80. Write down the algorithm of bubble sort.
81. Write down the algorithm of insertion sort.
82. Write an algorithm for selection sort. Describe the behaviors of selection
sort whenthe input is already sorted.
83. Compare bubble sort with insertion sort and find out which one is preferable.
84. What is Radix sort? Sort the following array using radix sort method. 24 56
47 35 1090 82 31
85. What is Merge sort? Sort the following array using merge sort method. 24
56 47 3510 90 82 31

86. Difference between connected graph and complete graph.

87. Write the steps to detect cycle in a graph.

88. What is spanning tree? Consider the given graph and find the possible
spanning trees of the graph.

89. Explain DFS traversal algorithm.

90. Apply the kruskal’s algorithm on the following graph and find minimum cost
spanning tree –
 ITM UNIVERSITY,GWALIOR

91. The degree of a node is the number of children it has. Show that in any
binary tree,the number of leaves is one more than the number of nodes of
degree 2.
92. Taking a suitable example explains how a general tree can be represented as a
BinaryTree.
93. Draw the expression tree of the following infix expression. Convert it in to
94. Prefix and Postfix expressions. K + L - M*N + (O^P) * W/U/V * T + Q
95. Construct a binary tree whose nodes in inorder and preorder are given as
follows:
Inorder : 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50
Preorder: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50
96. What do you understand by tree traversal? Write a procedure for traversing
a binarytree in preorder and execute it on the following tree.
97. Define a tree? How degree of a tree can be computed? Discuss the
properties of abinary tree.
98. Define general tree? Give its example.
99. Explain:
a. Sibling (ii) Leaf (iii) degree (iv) Depth (v) Path (vi) Forest
100. What do you understand by tree traversal? Explain various tree traversing
schemeswith the help of example?
101. Distinguish between full binary tree and complete binary tree?
102.Explain the representations of graph. Represent the given graph using any two
methods
103. Give the adjacency matrix for the following graph:
104. When does a graph become a tree?
105. Define a graph. Give various schemes for representing a graph in program.
106. Explain:
(i) Path (ii) Cycle (iii) Connect Graph (iv) Degree (v) Complete Graph (vi) Weighted
Graph
107. List the nodes of the following tree below in preorder, postorder,
inorderTraversal
 ITM UNIVERSITY,GWALIOR

108. Consider following tree-

Answer the following Question-

a. Write the name of Root Node
b. Write the name of Leaf Node
(ii) Write the name of Terminal Node
(iii) Write the name of Non-Terminal Node
(iv) What is the Degree of tree
(v) What is the Height of tree
(vi) How many siblings of above tree also write its name
(vii) How many levels of above tree.
(viii) Who is the parent of G.
(ix) Who is the left child of B.
(x) Who is the right child of I

109. Differentiate between the internal sorting and external sorting. Why external
sorting is more efficient than internal sorting? Explain.
110. Discuss the case of collision in hashing technique with example and name any
three collision resolution techniques.
111. Write the properties of a heap. Explain with the help of an example.
112. What is hashing? Discuss the different types of hashing techniques with
example.
113. What are the algorithmic steps of insertion sort method? Sort the following
data elements using insertion sort method. 7, 8, 5, 2, 4, 6, 3
114. Use the RADIX sort algorithm to sort the following numbers, and also
compute its time complexity in various cases.
348,143,361,423,538,000,000,000,000
 ITM UNIVERSITY,GWALIOR

115. Traverse the given graph to find the minimum path from A to J using the DFS
and BFS.