B.E.
Computer Science & Engineering (Model Curriculum) Semester - III
SE102CS - Data Structure and Algorithms
P. Pages : 2 GUG/S/23/13802
*2539*
Time : Three Hours Max. Marks : 80
_____________________________________________________________________
Notes : 1. All questions are compulsory.
2. All questions carry equal marks.
3. Assume suitable data wherever necessary.
1. a) Explain Asymptotic notations in details with example? 8
b) What is linear search and write a C - program to implement linear search? 8
OR
2. a) What is abstract data types? Explain data structure operations with the help of example? 8
b) What is binary search and write a C - program to implement binary search? 8
3. a) Write a C - program to count number of nodes in a singly linked list? 8
b) Write a C - program to implement doubly linked list? 8
OR
4. a) Write a C - program to reverse a singly linked list? 8
b) Write a C - program to implement circular linked list? 8
5. a) Explain push and pop function for stack? Write application of stack? 8
b) Convert following infix expression to prefix and postfix. 8
i) ( ( A + B − D ) / ( E − F) + G )
ii) ( A B C) / ( D E ( G F))
OR
6. a) Write a menu driven program in C to implement the following functions of queue? 8
i) Enqueue
ii) Dequeue
iii) Display
iv) Exit
GUG/S/23/13802 1 P.T.O
b) Write a C - program to implement circular queue? 8
7. a) What is binary search tree? Write a function for insert, delete and search operation in 8
BST?
b) Write a C - program for tree traversal method? 8
OR
8. a) Write preorder, inorder and postorder for the following tree? 6
A
B H
C F I J
D E G
b) Explain following tree terminologies 2
i) Degree
ii) Complete binary tree.
c) Write a short note on AVL tree? Explain types of rotations with the help of suitable 8
example?
9. a) Sort the following array using quick sort. 8
65, 70, 75, 80, ,85, 60, 55, 50, 45
Also write the algorithm.
b) Explain bubble sort algorithm with suitable example? 8
OR
10. a) What is hashing? Solve given example by using division method with linear probing? 8
3, 2, 9, 6, 11, 13, 9, 12 m = 10
And h(k) = 2k + 3
b) Explain graph traversal technique with suitable example? 8
************
GUG/S/23/13802 2
