Total No. of Questions : 8] SEAT No.
8
23
PB3624 [6261]-29 [Total No. of Pages :3
ic-
S.E. (E & TC)
tat
DATA STRUCTURES AND ALGORITHMS
4s
8:2
(2019 Pattern) (Semester-III) (204184)
02 91
3:3
Time : 2½ Hours] [Max. Marks : 70
0
41
Instructions to the candidates:
7/0 13
1) Answer Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8.
0
2) Neat diagrams must be drawn wherever necessary.
5/2
.23 GP
3) Figures to the right indicates full marks.
4) Use of Calculator is followed.
E
5) Assume suitable data if necessary.
82
8
C
23
ic-
16
tat
Q1) a) Compare Stack and Queue. What are the advantages of circular queue
8.2
4s
over liner queue? [6]
.24
8:2
91
b) Write a function PUSH and POP in ‘C’ for stack using linked list. [6]
49
3:3
30
41
c) What are the applications of Queue? Explain two applications in detail.[5]
01
02
OR
5/2
GP
7/0
Q2) a) Write a short note on circular queue. Compare it with linear queue. [5]
CE
82
8
23
b) Convert the following prefix expression into infix form. Show all the
.23
steps and stack contents: [6] ic-
16
tat
8.2
4s
*-A/BC-/AKL
.24
8:2
91
c) Write ADD and DETETE function in ‘C’ for Queue using array [6]
49
3:3
30
41
01
02
Q3) a) Compare array and linked list. [5]
5/2
GP
7/0
b) Write a ‘C’ function to delete a number from singly linked list. [6]
CE
82
c) Explain doubly linked list (DLL). What are the advantages of DLL over
.23
SLL. [6]
16
8.2
OR
.24
[6261]-29 1 P.T.O.
49
Q4) a) Draw and explain circular linked list. State the limitations of single linked
8
23
list. [5]
ic-
tat
b) Write ‘C’ function to insert a number at end in to the single linked list.[6]
4s
c) Differentiate singly linked list and doubly linked list. [6]
8:2
02 91
3:3
0
41
7/0 13
Q5) a) Construct Binary search tree of the following. [6]
0
5/2
.23 GP
MAR, OCT, JAN, APR, NOV, FEB, MAY, DEC, JUN, AUG, JUL, SEP
E
82
8
b) Write a pseudo code to search an element in binary search tree using
C
23
arrays. [6]
ic-
16
tat
c) Explain with suitable example how binary tree can be represented using:[6]
8.2
4s
.24
8:2
i) Array
91
49
3:3
30
ii) Linked List
41
01
02
OR
5/2
GP
7/0
Q6) a) Define BST? Create a BST for the following data: [6]
CE
82
8
23
14,15,4,9,7,18,3,5,7.
.23
ic-
16
tat
b) Define binary tree. Name and explain with suitable example the following
8.2
4s
terms [6]
.24
8:2
91
49
i) Root node
3:3
30
41
ii) Left sub tree and right sub tree
01
02
5/2
iii) Depth of tree
GP
7/0
c) Construct the binary search tree from the following elements: [6]
CE
82
.23
15,4,16,8,2,18,14
16
8.2
Also show preorder, inorder and postorder traversal for the same
.24
[6261]-29 2
49
Q7) a) Draw adjacency list and adjacency matrix for the following graph: [6]
8
23
ic-
tat
4s
8:2
02 91
3:3
0
41
7/0 13
0
5/2
.23 GP
E
82
8
b) What is MST? Explain with suitable example Kruskal’s Algorithm to
C
23
find out MST. [6]
ic-
16
tat
c) Define DFS and BFS graph with example. [6]
8.2
4s
OR
.24
8:2
91
49
Q8) a) Explain Kruskal algorithm? Find the minimum spanning tree for below
3:3
figure Using Kruskal’s Algorithm. [6]
30
41
01
02
5/2
GP
7/0
CE
82
8
23
.23
ic-
16
tat
8.2
4s
.24
8:2
91
49
3:3
30
41
01
02
b) Explain Dijkstra’s algorithm with example. [6]
5/2
GP
c) Explain with suitable example the techniques to represent a graph. [6]
7/0
CE
82
Note: consider graph of minimum 6 vertices
.23
16
8.2
.24
[6261]-29 3
49
