BCS304

USN 1 B Y

BMS INSTITUTE OF TECHNOLOGY AND MANAGEMENT

(An Autonomous Institute affiliated to Visvesvaraya Technological University, Belagavi)
SEMESTER END EXAMINATION MODEL QUESTION PAPER

Third Semester B.E. Degree Examination

Regular / Make-up / Arrears / Supplementary

Data structures and Applications

Time: 3 hrs. Max. Marks: 100

Note: Answer FIVE full questions, choosing ONE full question from each module.

CO,
Q. No Module – 1 Marks
RBT
Define data structures. Explain in detail different types of data structures with
1a. 10 CO1, K2
neat diagram and its operations.
Write a C program to evaluate a postfix expression and apply the same for the
1b. given postfix expression. ABC-D*+E$F+ and assume A=6, B=3, C=2, D=5, 10 CO2, K4
E=1, F=7.
OR
2a Explain dynamic memory allocation functions with syntax and examples. 10 CO1, K2
Write a C program to convert a parenthesized infix expression to postfix. Apply
2b. the algorithm and show the contents of stack for the given expression. (A + B * 10 CO2, K4
C) * ((D + E –F) / J)
Module – 2
What is a linear queue? What are the applications of linear queue?
3a. Implement/Write a C program to simulate the 1) insert 2) delete 3)display 10 CO1, K2
operations.
Write implementation for circular queue using array. Also write following
3b. 10 CO2, K3
routine of circular queue. 1) insert 2) delete 3) display
OR
Explain the working of double ended queue and priority queue with neat
4a. 10 CO1, K2
diagram and its applications
Define recursion. Write recursive functions for the following: (i) Factorial of a
4b. 10 CO2, K3
number (ii) Tower of Hanoi
Module – 3
What is a linked list? Explain the different types of linked lists with neat
5a. 10 CO2, K2
diagram.
5b. Write a C program to simulate linear queue operations using singly linked lists. 10 CO3, K3
OR
Write C functions for the following operations on circular linked list:
6a. (i) Insertion at the beginning 10 CO2, K2
(ii) Insertion at the end

Page 1 of 2
 BCS304

(iii) Deletion at the beginning

(iv) Deletion at the end
6b. Write a C function for the concatenation of two doubly linked lists 10 CO3, K3
Module – 4
What is a tree? With suitable example, define:
(i) Binary Tree
7a. (ii) Level of the binary tree 10 CO3, K2
(iii) Complete binary tree
(iv) Degree of the tree
Write a C program to build binary search tree and tree traversals and apply
7b. 10 CO3, K3
traversals for the following 20,15,30, 40, 25, 8,17, 21,100.
OR
8a. Discuss BST insertion and deletion operations. 10 CO4, K2
8b. Write a recursive function inorder, preorder and postorder with an eample. 10 CO4, K3
Module – 5
What is collision? What are the methods to resolve collision? Explain linear CO4, K2
9a. 10
probing with an example.
Define graph. For the following graph, show the adjacency matrix and CO4, K2
adjacency list representation of the graph (Fig Q9b)

9b. 10

Fig Q9b

OR
10a. Discuss hash function and hash table. 10 CO4, K2
10b. Write an algorithm Warshal’s algorithm with an example. 10 CO4, K2

Course Outcomes (COs):

COs At the end of the course, the student will be able to

CO-1
Illustrate different types of linear data structures, its operations and algorithms to solve a given
problem.
CO-2
Illustrate different types of non-linear data structures, its operations and algorithms to solve a
given problem.
CO-3 Examine any given problem, recommend and implement solutions using suitable data structures.
CO-4 Design and implement applications using suitable data structures.
K1- Remembering K2 - Understanding K3 – Applying K4- Analyzing K5 - Evaluating K6 -Creating

“Satisfaction lies in the effort, not in the attainment, full effort is full victory”

BMS INSTITUTE OF TECHNOLOGY AND MANAGEMENT Page 2 of 2