Total No. of Questions : 8] SEAT No.
8
23
P-1488 [Total No. of Pages : 4
ic-
[6002]-115
tat
7s
S.E. (E & TC/Electronics)
6:5
02 91
DATA STRUCTURES
0:3
0
(2019 Pattern) (Semester - III) (204184)
31
0/0 13
0
Time : 2½ Hours] [Max. Marks : 70
om
6/2
.23 GP
Instructions to the candidates:
1) Neat diagrams must be drawn wherever necessary.
E
82
rsic-238
.c
2) Figures to the right indicate full marks.
C
3) Assume suitable data, if necessary.
16
tat
8.2
es
Q1) a) Write a ‘C’ Function to Push and POP elements from a stack of
:57
.24
characters using an array.
:36p [6]
02P 91
49
0a
b) Convert the following infix expression to postfix using stack (show
0
31
all the steps properly) : a + b*(c/d$ a)/b [5]
0/0 n13
c) Consider Following circular queue of characters and size 5. [6]
P0
6/2
8 2 io
.23 tG
A C
CE
s
38
ue
c-2
Front Rear
i
16
tat
Q
8.2
Front point to A and Rear Points to C. Show the circular queue contents as
7s
per the following operations at every step.
.24
6:5
PU
91
49
0:3
i) F is added to the queue.
30
31
ii) Two letters are deleted.
SP
01
02
iii) K, L, M are added to the queue
6/2
GP
0/0
iv) Two letters are deleted.
CE
82
v) R is added to the queue.
.23
vi) Two letters are deleted.
16
8.2
OR
.24
49
P.T.O.
Q2) a) Compare Stack and Queue. [4]
8
23
b) What are the applications of Stack.
ic-
Represent stack for decimal to binary conversion: (56)10 to (---)2 [3]
tat
c) Define Queue. What are conditions for ‘Queue empty’ and ‘Queue
7s
full’ when queue is implemented using Array? Explain. [6]
6:5
d) Write a ‘C’ function for deletion in a queue using an array. [4]
02 91
0:3
0
31
Q3) a) Compare circular linked list with singly linked list in terms of pros and
0/0 13
cons. [6]
0
om
6/2
b) What is a singly linked list? Write C function for inserting a node at a
.23 GP
given location into a singly linked list. [6]
E
c) Explain the disadvantages of polynomial representation using an array.
82
rsic-238
.c
C
Represent the following polynomial using a singly linked list. [6]
23x9 + 18x7 + 41x6 + 16x4 + 3
16
tat
OR
8.2
es
:57
Q4) a) What is a doubly linked list? Write a ‘C’ function for Inserting a number
.24
:36p
at the end of the doubly linked list. [6]
02P 91
49
0a
b) Write a ‘C’ function for Inserting a number at the front of the circular
0
31
linked list. [5]
0/0 n13
c) Compare linked representation and array representation with reference
P0
6/2
to the following aspects : [3]
8 2 io
.23 tG
i) Accessing any element randomly
CE
s
ii) Insertion & deletion of an element
38
ue
c-2
iii) Utilization of memory
d) Write a short note on the Circular Linked list. [4]
i
16
tat
Q
8.2
7s
.24
Q5) a) Define the following terms with respect to Trees : [5]
6:5
PU
91
i) Root
49
0:3
30
ii) Subtree
31
SP
iii) Level of node
01
02
iv) Depth of Tree
6/2
GP
v) Siblings
0/0
b) Write a recursive ‘C’ function for inorder, preorder, postorder tree
CE
82
traversal? [6]
.23
c) Construct the Binary Search Tree (BST) from the following data : [6]
16
5, 2, 8, 4, 1, 9, 7
8.2
Also show preorder, postorder and inorder traversal for the same.
.24
49
[6002]-115 2
OR
8
23
Q6) a) Define a tree. Explain with a suitable example how a binary tree can be
ic-
represented using an array. [5]
tat
b) Write an algorithm to implement non-recursive in-order traversal of a
7s
binary search tree. [6]
6:5
c) The postorder and inorder traversals of a binary tree are given below.
02 91
0:3
Is it possible to obtain a unique binary tree from these traversals? If
0
yes, obtain the tree, if not give justification. [6]
31
0/0 13
Inorder Traversal : D B F E G A H I C
0
om
6/2
Postorder Traversal : D F G E B I H C A
.23 GP
E
Q7) a) Define Graph. Explain types of Graph. [6]
82
rsic-238
.c
C
b) Compare DFS and BPS. [6]
c) Find the minimal spanning tree of the following graph using Prim’s
16
tat
algorithm. Show all the steps. [6]
8.2
es
:57
.24
:36p
02P 91
49
0a
0
31
0/0 n13
P0
6/2
8 2 io
.23 tG
Fig : 1
CE
s
38
ue
c-2
Q8) a) Define with an example : [6]
i
16
tat
i) Path
Q
8.2
7s
ii) Cycle
.24
6:5
PU
iii) Connected graph
91
49
0:3
b) Define indegree and outdegree of a vertex in graph. Find the indegree
30
and outdegree of following graph. [6]
31
SP
01
02
6/2
GP
0/0
CE
82
.23
16
8.2
Fig : 2
.24
49
[6002]-115 3
c)
SP
[6002]-115
49
.24
PU 8.2
16
C E
.23 GP
Q 82 0
adjacency list.
0/0 13
49 6/2 0
02 91
.24
ue
8.2 CE 31
16 s
.23 tG
0:3
6:5
P0
4
8 2 io 7s
tat
Fig : 3
0/0 n13
49 6/2 0 ic-
23
.24 02P 91
31 8
8.2
0a
16
CE
.23 GP :36p
82 :57
0/0
6/2
01
30
estat
rsic-238
02 91
31 .c
0:3
6:5 om
7s
tat
i
[6]
Represent the following graph using the adjacency matrix and
c-2
38
