Department of Computer Science

DATA STRUCTURES - QUESTION BANK

Even semester 2020-2021

Programme: BSc-II
Name of the faculty: Sreeparna Chakrabarti

Unit 1: Introduction to Data Structures

2 Marks
1. Mention data structure operations.
2. Explain the classification of data structures with examples.
3. Define data structure.
4. What are linear and non-linear data structure. Give example for each.
5. What are primitive and non-primitive data structures?
6. Mention any two factors on which choice of data structure depends.
7. What is recursion?
8. What is homogenous data structure? Give examples.
9. Differentiate between * and & operators.
10. Write the differences between static and dynamic memory allocation.
11. Write the recursive formula for GCD of two numbers.
12. Write a recursive function in C to find the factorial function of a given number.
13. What is a pointer?
14. Differentiate between iterative and recursive methods
5 Marks
15. List the applications of data structures.
16. Explain the following operations with examples.-traversing, searching and sorting.
17. What is recursion? Write a recursive program to print fibonacci series.
18. Explain the operations performed on data structure.
19. Explain dynamic memory allocations in C with example.
20. Explain classification of data structure.
21. Write a C program to explain Tower Of Hanoi.
22. Write a C program to find the binomial coefficient using recursion.
23. Write the recursive program for GCD of two numbers.
24. Explain static and dynamic memory allocations.
25. Explain the usage of malloc and free using an example program.
10 Marks
26. What are the applications of data structures?
27. Define pointer. Explain the usage of pointer to access the value and address of a
variable with an example.
28. Explain any 3 dynamic memory allocation functions.
Unit2: Searching and Sorting
2 Marks
29. Differentiate between linear search and binary search.
30. Write the algorithm to implement bubble sort.
31. List any 2 advantages of binary search.
32. Write an algorithm for searching an element using sequential search among n
elements.
33. Define sorting
34. Write one disadvantage of binary search over sequential search.
35. Name any four sorting procedures.
5Marks
36. Explain quick sort with an example.
37. Explain linear search algo with an example.
38. Explain binary search with an algo.
39. Write a C program to implement selection sort.
40. Write a C program to perform binary search on N integers using iterative approach.
41. Write a C program to search for the smallest element in a set of number using
sequential search.
42. Write an algorithm for sorting n elements using insertion sort.
43. Write a C program to search an element using linear search.
10 Marks
44. Write a C program to implement Merge sort. Show the illustration of merge srt in the
data set: 89, 3, 34, 118, 13, 10, 95, 43, 93
45. Explain the advantages of binary search over sequential search. Write a program in C
to search for an element in array using binary search.
Unit3: Stack and queue
2 Marks
46. Differentiate between stack overflow and underflow.
47. Write any two applications of stack.
48. What is a stack?
49. What is the disadvantage of linear queue?
50. Define double ended queue.
51. What is a prefix expression? Convert the following infix expression to postfix
expression: (a+b)*(c-d).
52. What is a priority queue?
53. Define infix, prefix and postfix expressions with examples.
54. What are the different types of queues?
55. What are the operations that can be performed on stack?
56. Define queue.
5Marks
57. What is a queue? Explain the different types of queue.
58. Write a C program to implement stack using array. The operations to be supported are
push, pop and display.
59. What is stack? Write a C program code for the functions push and pop.
60. Explain circular queue
61. Write a C program to simulate a linear queue using an array.
10 Marks
62. Write an algorithm to implement insert, delete and display operations in a linear
queue.
Write a C program to evaluate a postfix expression.
63. Write a C program to implement a linear queue using an array.
Write an algorithm to evaluate a postfix expression.
64. Write C functions to implement the insertion, deletion and display operations in a
circular queue.
65. Write an algorithm to convert an infix expression to postfix expression using stack.
What is a queue? Explain the different types of queues.
66. Write a C program to implement operations on a stack.
67. Write an algorithm to convert an infix expression to postfix expression using stack.
Evaluate the given postfix expression 854^2 +*62^93/- using stack

Unit4: Linked List

 2 Marks
68. What is a circular linked list?
69. What is doubly linked list?
70. List any two advantages of linked list.
71. Compare linked list and array.
72. What is a circular linked list?
73. What is a circular doubly linked list?
74. Write any two disadvantages of linked list.
75. Define the node structure of a doubly linked list.
76. What is a self-referential structure? Give an example for the same.
77. What is a singly linked list? Define the operations that can be performed on a singly
linked list.
5Marks
78. Write C functions to implement push and pop operations in a linked implementation
of stack.
79. Write a C code to create a single linked list to store the details of a student
(rollnumber, name) and display the same.
80. Write a C function to:
a. Display all nodes in a doubly linked list.
b. Insert a node at the beginning of a doubly linked list.
c. Create a doubly linked list.
81. Write an algorithm to perform insert, delete and display operations of a linear queue
using singly linked list.
82. Compare singly linked list with doubly linked list.
83. Write a C program to implement the operations of a queue using linked list.
10 Marks
84. Write a C function to perform the following operations in a double linked list:
a. Create
b. Insert a node in front
c. Delete a node
d. Display
85. a. Write a C program to create a singly linked list consisting of the following
information in each node. Rollno(Integer), Name(Character String). The operations to
be supported are: deleting a node based on rollno and displaying the list.
b. Briefly explain the types of linked list.
86. What is a singly linked list.
Write a C function to perform the following operations in a singly linked list:
a. Create
b. Insert a node in front
c. Delete a node
d. Display
87. Explain the operations on singly linked list
List the advantages and disadvantages of linked list.
88. Write a C program to implement basic queue operations using linked list.
89. Explain any two types of insertion operations on a singly linked list.

Unit5: Tree
 2 Marks
90. Define complete binary tree with example. Draw an example.
91. What is a binary tree?
92. Define depth and height of a tree.
93. Construct a max-heap for the following values:14,28,34,10,60
94. Define heap.
95. Differentiate between binary tree and complete binary tree.
96. Define max-heap and min-heap.
97. Define level of a tree.
98. Define tree. What is a binary search tree?
99. Define degree of a node and degree of a tree.
5Marks
100. Construct a binary tree from the following pre-order and in-order traversal.
Inorder: D B E A F C G
PreOrder: A B D E C F G
Generate Post Order traversal of the same.
101. Explain the array representation and linked list representation of binary with
an example.
102. Construct a binary tree from the following pre-order and in-order traversal.
Inorder: E D U C A T I O N
PreOrder: C D E U I T A N O
Generate Post Order traversal of the same
103. Show the step by step construction of a BST for the following data.
[50, 23, 94, 85, 63, 42, 17, 11, 19, 76]
10 Marks
104. What is a binary search tree? Construct a binary search tree for the following
elements:
{ 12, 45, 23, 43, 10, 6, 11 }
Write a C program to create a binary tree and display the same using any one of the
tree traversal techniques.
105. A. Construct a max heap for the following elements [23, 44, 67, 89, 34, 12, 9,
94]
B. Write a recursive C function to display the inorder traversal of a binary tree.
C. Show the step by step construction of a BST for the following data.
[46,35,12,67,42,53,72,8]
106. Explain all three traversal of binary tree with an algorithm and an example.
107. What is a binary search tree? Construct a binary search tree for the following
elements:
[98, 53, 135, 32, 71, 18, 9, 24, 65, 88]
Also write the steps for inorder, preorder and postorder traversal for the above drawn
tree.
Dynamic memory allocation and pointers
1. Differentiate between * and & operators.
2. If m and n are declared as integers and p1 and p2 are pointers to integers, then find
out the error if any, in the following.
a. p1=&m;
b. P2=n;
c. *p1=&n;
3. What is dynamic memory allocation? What are the advantages of dynamic memory
allocation over static memory allocation?
4. Give an example for accessing a variable through its pointer variable.
5. Explain the following functions
a. malloc()
b. calloc()
c. delete()
 d. realloc()
e. free()
6. What is a pointer variable? What is the size of the pointer variable of different data
types?
7. What is a void pointer?
8. How do you initialize a pointer?
9. How memory can be deallocated?
10. Write the differences between static and dynamic memory allocation.
11. List the application of pointers.
12. Explain how array elements are accessed using pointers in one dimensional array.
13. List the advantages of pointers.
14. What is a pointer to pointer?
15. Explain how pointers are passed in function call with an example.
16. What is a heap?
17. What is garbage collection?
18. List the advantage of dynamic memory allocation.
19. What is a dangling pointer? Explain with an example.
20. What are the common errors that could occur during dynamic memory allocation?
21. Differentiate between static variables and dynamic variables.

Recursion
1. What data structure is used for performing recursion?
2. Mention the advantages of using recursive function.
3. Mention the disadvantages of using recursive function.
4. When is a recursive function said to be well defined?
5. Explain Towers of Hanoi problem as an example for recursion. Give the solution for
disks.
6. Write a recursive program to find the product of two numbers.
7. Explain the types of recursion.
8. Write a recursive program to find the sum of first n natural numbers.
9. Write a recursive program to print numbers 1 to n in descending order using
recursion.
10. Write a recursive function to find the sum of first n natural numbers.
11. Define recursion.
12. Write a c program to find the binomial coefficient using recursion.
13. Write a c program to find the GCD of any given two numbers using recursion.
Illustrate with an example.
14. Write a c program to find the factorial of a number using recursion.
15. Write a c program to generate the Fibonacci series using recursion.
16. Write a recursive program to reverse a string.
17. Write a recursive program to find the length of a given stirng?
18. explain how power(x,n) can be found.
19. Write a C program to print numbers 1 to n in descending order using recursion.
20. Explain the towers of Hanoi problem.
21. What is the output of the following recursive function?
Int function(int x)
{
a. If(x<3)
 i. return (1);
b. else
i. return(function(x-
1)+function(x-2)); } main()
{
c. int I,n=5;
d. for(i=1;i<=n;i++)
i. printf(“\n%d”,functio
n(i)); }
22. Explain the difference between iterative and recursive methods.

Searching and Sorting

1. Define sorting.
2. Define searching.
3. Mention the different objectives of sorting algorithm.
4. Explain linear search with an example.
5. Discuss complexity of linear search algorithm.
6. What are the advantages and disadvantages of binary search?
7. What is the disadvantage of linear search?
8. What is searching? Explain the advantage of binary search over linear search
technique.
9. Write an algorithm and C program to search for an element using binary search.
10. Write an algorithm to search for an element using linear search.
11. In which situation binary search will be useful.
12. Write a C program to sort a set of elements using bubble sort technique.
13. Write a c program to sort the array using merge sort.
14. Write a note on searching techniques.
15. Explain quick sort algorithm and demonstrate the sorting with an example.
16. Explain binary search with an example.
17. Write a C program to sort names in alphabetical order.
18. What are the efficiency parameters to be considered while selecting a suitable sorting
technique?
19. Explain advantages and disadvantages of different sorting algorithms.
20. Write an algorithm and C program to sort for an array using insertion sort.
21. Write an algorithm and C program to sort for an array using selection sort.
22. Write an algorithm and C program to sort for an array using selection sort.
23. Construct a max heap for the following data 76,23,45,12,99,67,34,17,88

Stacks and Queues

1. Write a C program to simulate the working of a circular queue using an array.
2. What is a FIFO list?
3. What is the advantage of circular queue over linear queue?
4. Explain the different types of Queue.
5. What is the advantage of circular queue over linear queue?
6. Explain queue overflow an underflow.
7. What is input restricted queue?
8. What is output restricted queue?
 9. What are the types of priority queue?
10. What is a double ended queue?
11. Differentiate between input restricted queue and output restricted queue.
12. Differentiate between ascending priority queue and descending priority queue.
13. Write an algorithm for displaying the elements of a circular queue.
14. Explain the concept of priority queue.
15. Write an algorithm for adding an element to a circular queue.
16. Write an algorithm for deleting an element from a circular queue.
17. Explain the queue conditions with a diagram.
18. Explain priority queue.
19. List any three applications of queue.
20. Write an algorithm for displaying adding an element into priority queue.
21. Write an algorithm for displaying adding an element into priority queue.
22. Explain the memeory representation of a priority queue.
23. Confert the following expression from infix to prefix and postfix

A+B*C+D

a. (A + B) * (C + D)
b. A * B + C * D
c. A + B + C + D
d. A/B^C-D
e. (d-e)/(p+q)2
f. ((p+q)*(a-n))/((t-r)+(b-u)3)
24. Convert A * (B + C) * D to postfix notation. Show the state of the stack.
25. Convert A+(B*C-(D/E-F)*G)*H to postfix notation. Show the state of the stack
26. Evaluate the post fix expression 2 3 4 + * 5 *
27. Write an algorithm to convert an infix expression to postfix expression. Trace the
algorithm to indicate the content of stack for the expression (a-b)/(c-d)+e.

Linked Lists
1. Write an algorithm to create a singly linked list.
2. Mention the disadvantages of static memory allocation.
3. What are the disadvantages of linked list?
4. Explain the components of a linked list with a diagram.
5. How is linked list represented in memory?
6. What are the advantages and disadvantages of singly linked list.
7. What is a header node? Explain.
8. Compare singly and doubly linked list.
9. What is a circular linked list?write one advantage and disadvantage of circular
linked list.
10. What is garbage collection?
11. What is the difference between linked list and an array?
12. Write an algorithm to insert a node after a node in a linked list.
13. Write an algorithm to delete a node from a linked list.
 14. Write an algorithm to count the number of nodes in a linked list.
15. Write an algorithm to count the number of nodes in a circular linked list.
16. What is a linked list? What are the advantages of linked list over array?
17. Write an algorithm to implement a stack using linked list.
18. Write a C program to implement a queue using linked list.
19. What is the advantage of singly linked list over a doubly linked list?
20. What is the disadvantage of singly linked list over a doubly linked list?
21. Explain the concept of doubly linked list.
22. Explain how a node is created in a linked list.
23. Explain the various types of linked list.
24. Explain how the elements in a linked list can be displayed.
25. Explain how an element can be searched in a sorted linked list.
26. Explain how an element can be searched in a unsorted linked list.
27. Explain how a node can be inserted at the beginning of a linked list with an
algorithm.
28. Explain the insertion of a node at a particular position in a linked list.
29. Explain the deletion of anode from the beginning of the list, from a particular
position.

Trees

1. Mention the different properties of binary tree.

2. List some application of trees.
3. Define the following terminologies.
Root, node, parent, child, sibling, link, path, path length, degree of a node, degree of
a tree, leaf node, terminal node, non terminal node, level, depth of a node, height of a
node, height of a tree, ancestor of a node, descendant of a node, climbing a tree,
descending a tree, forest
4. Differentiate between terminal node and non terminal node in a tree.
5. What are the properties of a binary tree.
6. What is the difference between a general tree and a binary tree?
7. What is a left skewed treee?
8. What is a right skewed tree?
9. What is a complete binary tree?
10. What is an extended binary tree?
11. What is a Heap tree?
12. What is a min heap?
13. What is a max heap?
14. Explain the memory representations of a binary tree.
15. What is a sequential representation of a binary tree?
16. What is linked list representation of a tree?
17. Differentiate between a BST and heap.
18. Explain ancestor node in a tree.
19. Define a complete binary tree.
20. Define heap.
21. Give an example of a complete binary tree?
22. Define leaf node?
23. What is a binary tree?
24. Explain the sequential memory representation of a tree?
25. Explain the linked representation of binary tree.
26. Obtain the prefix of the following
a) (A+B)*C
b) (A-B)*(D/E)
27. What is tree traversal?
28. Arrange the following numbers in ascending order using heap sort technique. Use a
max heap. Show stepwise construction of the heap.50, 25, 30, 75, 100, 45, 80.
29. What is a binary search tree?
30. Construct a BST for the following elements.8,16,31,6,13,24,29,5,2,11,7.
31. Convert the following infix expression into a prefix expression.
a) A+B^C+D*E-E-G*H
32. Write the prefix and postfix notation for (A+B)*C/D
33. Explain the various tree traversal techniques with a recursive algorithm..
34. Define degree of a node.
35. Define degree of a tree.
36. Define height of a tree.
37. Explain Polish notation and reverse polish notation.
38. What is the difference between min heap and max heap?
39. Explain the memory representation of a binary tree.
40. Explain the construction of Binary search tree with a suitable example.
41. Explain how a node is added to a binary search tree.
42. Explain how a node is deleted from a binary search tree.
43. Construct a binary tree for the following preorder and inorder traversal and print the
post order.
44. Preorder : A,B,D,G,H,C,E,F,I,K,J
45. Inorder : B,G,H,D,A,E,C,I,K,F,J
46. Construct a BST.assume that the following numbers are entered one after the other in
following sequence.49,23,20,89,79,88,25..
47. Delete node 49 from the constructed BST.after deleting node 49,insert node 70 into
BST
48. Construct a BST for the following data.72,85,36,43,21,49,90,65,50,49..write the
preorder,inorder and postorder traversals for the above constructed BST.
49. Represent the following arithmetic expression using binary tree.((6+(3-2)*5)*2+3)