MONARK UNIVERSITY
FACULTY OF ENGINEERING & TECHNOLOGY
COURSE: B.E. SEM: 3rd AY: 2023-24
BRANCH: CE/IT
SUBJECT NAME: DATA STRUCTURE
SUBJECT CODE: 10230304
FREQUENTLY ASKED QUESTIONS
SR. Questions
NO.
1 Define Data Structure.
List the various linear and non-linear Data Structures and Explain them in brief.
2 Define Time and space complexity of an algorithm.
Discuss best case, average case and worst case time analysis with example
3 Write short note on Storage representation of 2 Dimensional array.
OR
Explain row-major representation and column-major representation of array with suitable
examples
4 What is Stack? Write an algorithm to implement basic primitive operations(Push,
Pop) of the stack using Linear array.
5 Write an algorithm to convert infix to postfix (or reverse polish) expression and
explain it with example
6 Write an algorithm for evaluation of postfix expression
7 What is recursion? Explain Recursion with the help of an Example
8 Trace the conversion of infix to postfix form in tabular form.
a) A + ( B - C ) * D
b) A ^ B * C \ D
c) (A + B) \ C * D ^ E
d) (A + B) * C – D ^ E ^ (F * G )
9 Evaluate the following postfix expression showing every status of stack in tabular
form.
a) 5 4 6 + * 4 9 3 / + *
b) 7 5 2 + * 4 1 1 + / -
c) 9 3 4 * 8 + 4 / -
d) 5 6 2 + * 1 2 4 / - +
10 Write an algorithm/program to perform insert and delete operations on a Queue
11 Write an algorithm/program to perform insert and delete operations on a Circular
Queue.
12 Explain Difference between Stack and Queue.
13 Write short note on 1) Double Ended Queue( DQUEUE) 2) Priorit y Queue
MONARK UNIVERSITY
FACULTY OF ENGINEERING & TECHNOLOGY
COURSE: B.E. SEM: 3rd AY: 2023-24
14 Explain following searching method. Also write their algorithm.
1) Linear Search (Sequential Search) method 2) . Write its algorithm Binary Search
method
15 Explain the trace of bubble sort on following data. 42,23,74,11,65,58,94,36,99,87
Explain the trace of selection sort on following data.
42,23,74,11,65,58,94,36,99,87
16 Write an algorithm or function in 'C' for following sorting methods
1) Bubble Sort 2) Selection Sort 3) Quick Sort 4) Insertion sort
17 Write an algorithm/program to insert a node (1) at Begin 2) at End in a singl y linked
list.
18 Write an algorithm/program to delete a node (1) at Begin 2) at End in a singl y linked
list.
19 Write an algorithm/program to count number of nodes in a singl y linked list.
20 Write a ‘C’ program to implement stack and Queue using linked list.
21 Write a program to search an element in a linked list.
22 Write an algorithm to insert and delete an element from a doubl y link list.
23 Compare Linked-list and Array
24 Discuss following with reference to trees. 1) Binary tree 2) Binary search tree 3)
Complete binary tree 4) Tree 5) intermediate node 6) leaf node 7) adjacent node 8)
Node 9) Height of the tree 10) Balanced Tree 11) Spanning tree 12) Depth of a tree
13)
25 Write recursive algorithm/program to implement traversal(in -order, pre-order and
post order) of the Binary Search Tree.
Explain the Preorder, Inorder and Postorder traversal techniques of the binary tree
with suitable example.
26 How a general tree can be converted to binary tree?
With a suitable example, explain steps for conversion of a general tree into a binary
tree.
27 Explain Threaded binary trees with suitable examples.
28 Explain AVL tree with the help of an example als o show insertion and deletion with
the help of an example.
What is an AVL tree? Explain the different types of rotations used to create an AVL
tree with suitable examples
MONARK UNIVERSITY
FACULTY OF ENGINEERING & TECHNOLOGY
COURSE: B.E. SEM: 3rd AY: 2023-24
29 Construct binary search tree for the following data. Find its inorder, preorder and
postorder traversal.
1) 10,3,15,22,6,45,65,23,78,34,5
2) 50 ,25 ,75, 22,40,60,80,90,15,30
3) 50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5
4) 8,3,11,5,9,12,13,4,6,20
5) 40, 65,25, 55, 10,70,30,50,15,80,75
30 A) Construct a tree for the given inorder and postorder traversals.
Inorder DGBAHEICF
Postorder GDBHIEFCA
B) Construct a binary tree from the traversals given below:
Inorder: 1, 10, 11, 12, 13, 14, 15, 17, 18, 21
Postorder: 1, 11, 12, 10, 14, 18, 21, 17, 15, 13
A) Given the following traversals create a binary tree from that. Also give the
postorder traversal for the same.
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
B) Construct a binary search tree from the following traversals:
Inorder: 3 4 5 6 7 9 17 20 22
Preorder: 9 4 3 6 5 7 17 22 20
31 Discuss following with reference to graphs.
1) Directed graph 2) Undirected graph 3) Degree of vertex 4) Null graph
5) In-degree 6) C ycl e 7) Graph 9 ) Indegree & outdegree of a vertex
10) Minimum spanning tree 11) Weighted graph 12) Adjacent nodes.
32 What is a Graph? Explain the adjacency list and adjacency matrix representation of
Graph with example.
33 Explain Depth First Search and Breadth First Search operation in graphs with an
example.
34 What is Hashing? Explain various Hashing Functions (or methods for hashing)
35 Explain various Hash collision resolution techniques with examples.
PREPARED BY: Prof. Manoj Patel
