Total No. of Questions : 4] SEAT No.

8
23
P-5389 [Total No. of Pages : 3

ic-
tat
[6186]-515

6s
S.E. (E&TC / Electronics) (Insem)

9:1
02 91
DATA STRUCTURES

0:3
0
31
(2019 Pattern) (204184) (Semester-III)
3/1 13
Time : 1 Hour] [Max. Marks : 30
0
0/2
.23 GP

Instructions to the candidates :

1) Solve Q1 or Q2, Q3 or Q4.
E
81

2) Figures to the right indicate full marks.

8
C

23
3) Neat diagrams must be drawn wherever necessary.

ic-
4) Assume suitable data, if necessary.
16

tat
8.2

6s
Q1) a) State true or false. (each 5 mark) [5]
.24

9:1
i) Variable names are given to memory location_______.
91
49

0:3
ii) No commas or blanks are allowed within constant and variable
30
31

declaration_______.
01
02

iii) If no sign precedes constant it is assumed to be positive______.

0/2
GP

iv) Underscore (___) symbol is allowed as part of variable name______.

3/1

v) If a character constant is declared as ‘10’ it is correct_______.

CE
81

8
23
vi) It is ‘5’ = 5 and ‘5’ = “5” acceptable by complier_______.
.23

vii) 3 && 4 and 3 & 4 are same instructions_____. ic-

16

tat
8.2

viii) C= a.b and c= a*b both are same______.

6s
.24

9:1

ix) / (division operator) returns quotient and % (modulus) operator

91
49

returns remainder after division_______.

0:3
30

x) While loop is entry control loop and do while is exit control loop______.
31
01
02

b) Describe operations on file as open and close. State various modes,

0/2

explain append in file mode? [5]

GP
3/1

c) Declare and define structure, structure variable to demonstrate the

CE

following: A car manufacturing company maintains its database as chassis

81

no, model name, price as information. Explain use of dot operator and
.23

arrow operator to initialize one record in table. [5]

16

OR
8.2

P.T.O.
.24
49
Q2) a) Declare character array of size 10, state various ways to initialize it? Write

8
23
user defined function to find length of given string? [5]

ic-
b) State true or false. (each 1 mark) [5]

tat
i) Array is derived data type. It has memory wastage and no bounds

6s
check as its limitation________

9:1
02 91
ii) Functions can return multiple values, passes multiple values_____.

0:3
0
iii) Functions can return multiple values only if pointers are used

31
iv)
3/1 13
To find memory address of any array element following formula
0
0/2
can be used_______.
.23 GP

Memory add (i) = base address + size of (datatype) / location number

E

where i is the location for which address to be found.

81

8
C

23
v) Unions do not have separate locations for each of their members,

ic-
so their size or equal to the size of largest member among all data
16

tat
members________.
8.2

6s
c) Classify various datatypes used in C programming (in tree form)? List
.24

9:1
91
various format specifiers used to access primary data types.
49

0:3
30

Write storage size required for primary data types in terms of bytes for
31

32/64-bit system? [5]

01
02
0/2
GP

Q3) a) What is stable sorting? Explain all passes/iterations for selection sort with
3/1

following array Arr [5] = {50 40 30 20 10}; Order in ascending. [5]

CE
81

8
23
b) Write algorithm for binary search on array? [5]
.23

c) Match the algorithm with algorithmic complexity. ic-[5]

16

tat
8.2

6s

Algorithm Complexity
.24

9:1

(Worst Case)
91
49

0:3

A. Bubble, 1. 0 (n log (n))

30
31

Selection,
01
02

Insertion sort
0/2
GP

B. Merge sort 2. O(n2)

3/1
CE

C. Quick sort 3. O (log (n))

81

D. Linear search 4. O (n2)

.23
16

E. Binary search 5. O(n)

8.2
.24

[6186]-515 2
49
 OR

8
23
Q4) a) Write pseudo code algorithm for insertion sort? [5]

ic-
b) Explain bubble sort with suitable example. Demonstrate all iterations and

tat
passes by suitable drawings. Arrange all elements in ascending order. Let

6s
array [5] = {50 40 30 20 10}. [5]

9:1
02 91
c) Given array is A [10] = {3, 5, 0, 10, 8, 15, 7, 6, 20, 4} Apply binary

0:3
search for given array to search following cases, write detail steps to

0
31
3/1 13
search number. [5]
0
i) Search 0 (extreme left)
0/2
.23 GP

ii) Search 20 (extreme right)

E

iii) Search 6 (at middle)

81

8
C

23
ic-

16

tat
8.2

6s
.24

9:1
91
49

0:3
30
31
01
02
0/2
GP
3/1
CE
81

8
23
.23

ic-
16

tat
8.2

6s
.24

9:1
91
49

0:3
30
31
01
02
0/2
GP
3/1
CE
81
.23
16
8.2
.24

[6186]-515 3
49
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
6/2
.23 GP

Instructions to the candidates:

1) Neat diagrams must be drawn wherever necessary.
E
82

8
2) Figures to the right indicate full marks.
C

23
3) Assume suitable data, if necessary.

ic-
16

tat
8.2

7s
Q1) a) Write a ‘C’ Function to Push and POP elements from a stack of
.24

6:5
characters using an array. [6]
91
49

0:3
b) Convert the following infix expression to postfix using stack (show
30
31

all the steps properly) : a + b*(c/d$ a)/b [5]

01
02

c) Consider Following circular queue of characters and size 5. [6]

6/2
GP

A C
0/0
CE
82

8
 

23
.23

Front Rear
ic-
16

tat
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
91
49

0:3

i) F is added to the queue.

30
31

ii) Two letters are deleted.

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
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

8
C

23
Represent the following polynomial using a singly linked list. [6]

ic-
23x9 + 18x7 + 41x6 + 16x4 + 3
16

tat
OR
8.2

7s
Q4) a) What is a doubly linked list? Write a ‘C’ function for Inserting a number
.24

at the end of the doubly linked list.

6:5 [6]
91
49

0:3
b) Write a ‘C’ function for Inserting a number at the front of the circular
30
31

linked list. [5]

01
02

c) Compare linked representation and array representation with reference

6/2

to the following aspects : [3]

GP
0/0

i) Accessing any element randomly

CE
82

ii) Insertion & deletion of an element

8
23
iii) Utilization of memory
.23

d) Write a short note on the Circular Linked list. ic-

[4]
16

tat
8.2

7s
.24

Q5) a) Define the following terms with respect to Trees : [5]

6:5
91

i) Root
49

0:3
30

ii) Subtree
31

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
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

8
C

23
b) Compare DFS and BPS. [6]

ic-
c) Find the minimal spanning tree of the following graph using Prim’s
16

tat
algorithm. Show all the steps. [6]
8.2

7s
.24

6:5
91
49

0:3
30
31
01
02
6/2
GP
0/0

Fig : 1
CE
82

8
23
.23

Q8) a) Define with an example : [6]

ic-
16

tat
i) Path
8.2

7s

ii) Cycle
.24

6:5

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
01
02
6/2
GP
0/0
CE
82
.23
16
8.2

Fig : 2
.24
49

[6002]-115 3
 c)

[6002]-115
49
.24
8.2
16
C E
.23 GP
82 0
adjacency list.

0/0 13
49 6/2 0
02 91
.24
8.2 CE 31
16 0:3
.23 GP 6:5

4
82 01 7s
tat
Fig : 3

0/0 30  ic-

49 6/2 23
.24 02
31
91 8
8.2 CE
16 0:3
.23 GP 6:5
82 01 7s
0/0 30 tat
6/2 ic-
23
02
31
91 8
0:3
6:5
7s
tat
[6]
Represent the following graph using the adjacency matrix and

ic-
23
8
Total No. of Questions : 4] SEAT No. :

8
23
PC395 [Total No. of Pages : 2
[6359]-515

ic-
tat
S.E. (Electronics/E&TC/Electronics(VLSI Design & Tech.)/Electronics &

5s
Communication-Advanced Communication Technology) (Insem)

3:1
02 91
DATA STRUCTURES

0:4
0
(2019 Pattern) (Semester-III) (204184)

41
1/1 13
0
Time : 1 Hour] [Max. Marks : 30
0/2
.23 GP

Instructions to the candidates:

1) Answer Q1 or Q2, Q3 or Q4.
E
81

8
C

2) Neat diagrams must be drawn wherever necessary.

23
ic-
3) Figures to the right indicates full marks.
16

tat
4) Assume suitable data, if necessary.
8.2

5s
Q1) a) Define [Link] pointer declaration, initialization, pointer arithmetic
.24

3:1
91
with suitable example? [5]
49

0:4
30
41

b) Explain call by value and call by Address for the example of swapping
01
02

two numbers. [6]

0/2
GP
1/1

c) Explain the difference between structure and union with suitable Example?
CE
81

8
[4]

23
.23

ic-
16

OR
tat
8.2

5s
.24

3:1

Q2) a) What is String? How to declare string in C? Write user defined function
91
49

to calculate length of string? [5]

0:4
30
41

b) List different types of operators in C? Explain Bitwise operator in detail?

01
02

[5]
0/2
GP
1/1

c) Explain need of File Handling in C? Explain the difference between text

CE
81

and binary file? What are different file handling modes? [5]
.23
16
8.2
.24

P.T.O.
49
Q3) a) Write step by step procedure for performing Binary search on following

8
23
array [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100] to search for the

ic-
element 45. [5]

tat
b) Explain Time and Space Complexity? Explain the significance of Big O,

5s
Big Theta, and Big Omega notations? [5]

3:1
02 91
0:4
0
c) Compare Bubble, Insertion, Selection, Merge and Quick Sort with respect

41
1/1 13
to stability, worst case time complexity, Adaptivity? [5]
0
OR
0/2
.23 GP

Q4) a) Show All steps for performing insertion sort on [12, 15, 17, 11, 9, 13,
18, 16]. [5]
E
81

8
C

23
b) What will be big(O) for the following code? Write main function to

ic-
perform addition of n elements entered by user using array for the following
16

tat
code? [5]
8.2

5s
int sum(int arr[], int n)
.24

3:1
91
{
49

0:4
30

int i, total = 0;
41

for (i =0; i < n; i++) {

01
02
0/2

total += arr[i];
GP
1/1

}
CE
81

8
return total;

23
.23

ic-
}
16

tat
8.2

5s

c) Compare Linear and Binary Search. Write an Algorithm to search the

.24

3:1
91

element in a list using Linear Search. [5]

49

0:4
30
41
01
02
0/2
GP

eeee
1/1
CE
81
.23
16
8.2
.24

[6359]-515 2
49
Total No. of Questions : 8] SEAT No. :

7
23
PD-4066 [Total No. of Pages : 3

ic-
[6402]-25

tat
5s
S.E. (E & TC/Electronics)

4:4
DATA STRUCTURES

02 91
9:3
(2019 Pattern) (Semester - III) (204184)

0
50
Time : 2½ Hours]
2/0 13 [Max. Marks : 70
0
Instructions to the candidates:
5/2
.23 GP

1) Answer Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8.

2) Neat diagrams must be drawn wherever necessary.
E
72

7
3) Figures to the right indicate full marks.
C

23
4) Use of Calculator is allowed.

ic-
5) Assume Suitable data if necessary.
16

tat
8.2

5s
Q1) a) Compare Stack and Queue. What are the advantages of circular queue
.24

4:4
over liner queue? [6]
91
49

9:3
b) Write a function PUSH and POP in ‘C’ for stack using linked list. [6]
30
50

c) Write a short note on circular queue. Compare it with linear queue.[5]

01
02
5/2
GP

OR
2/0

Q2) a) What are the applications of Queue? Explain two applications in detail.
CE
72

7
23
[5]
.23

b) Convert the following prefix expression into infix form. Show all the ic-
16

tat
steps and stack contents:
8.2

5s
.24

4:4

*–A/BC–/AKL [6]
91
49

9:3

c) Write ADD and DELETE function in ‘C’ for Queue using array. [6]
30
50
01
02
5/2
GP

Q3) a) Compare array and linked list. [5]

2/0
CE

b) Write a ‘C’ function to delete a number from singly linked list. [6]
72
.23

c) Differentiate singly linked list and doubly linked list. [6]

16

OR
8.2
.24

P.T.O.
49
Q4) a) Draw and explain circular linked list. State the limitations of single

7
linked list. [5]

23
ic-
b) Write a ‘C’ function to insert a number at end in to the singly linked

tat
list. [6]

5s
4:4
c) Explain doubly linked list (DLL). What are the advantages of DLL

02 91
over SLL. [6]

9:3
0
50
2/0 13
0
Q5) a) Construct Binary search tree for the following
5/2
.23 GP

MAR, OCT, JAN, APR, NOV, FEB, MAY, DEC, JUN, AUG. .JUL,
E
72

SEP [6]

7
C

23
ic-
b) Write a pseudo code to search an element in binary search tree using
16

tat
arrays. [6]
8.2

5s
c) Define binary tree. Name and explain with suitable example the
.24

4:4
91
following terms [6]
49

9:3
30

i) Root node
50
01
02

ii) Left sub tree and right sub tree

5/2
GP

iii) Depth of tree

2/0
CE
72

7
OR

23
.23

Q6) a) Define BST? Create a BST for the following data:

ic-[6]
16

tat
8.2

14,15,4,9,7,18,3,5,7.
5s
.24

4:4

b) Explain with suitable example how binary tree can be represented

91
49

9:3

using: [6]
30
50

i) Array
01
02
5/2

ii) Linked List

GP
2/0

c) Construct the binary search tree from the following elements: [6]
CE
72

15,4,16,8,2,18,14
.23
16

Also show preorder, inorder and postorder traversal for the same.
8.2
.24
49

[6402]-25 2
Q7) a) Draw adjacency list and adjacency matrix for the following graph: [6]

7
23
ic-
tat
5s
4:4
02 91
9:3
0
50
2/0 13
0
5/2
.23 GP
E
72

7
C

23
b) What is MST? Explain with suitable example Kruskal’s Algorithm to

ic-
find out MST. [6]
16

tat
8.2

5s
c) Define DFS and BFS graph with example. [6]
.24

4:4
OR
91
49

9:3
Q8) a)
30

Explain Kruskal algorithm? Find the minimum spanning tree for below
50

figure. Using Kruskal’s Algorithm. [6]

01
02
5/2
GP
2/0
CE
72

7
23
.23

ic-
16

tat
8.2

5s
.24

4:4
91
49

9:3

b) Explain Dijkstra’s algorithm with example. [6]

30
50

c) Explain with suitable example the techniques to represent a Graph. [6]

01
02
5/2

Note: consider graph of minimum 6 vertices

GP
2/0


CE
72
.23
16
8.2
.24
49

[6402]-25 3
Total No. of Questions : 8] SEAT No. :

8
23
PA-1193 [Total No. of Pages : 4

ic-
[5925]-215

tat
S.E. (E & TC/Electronics)

5s
DATA STRUCTURES

2:5
02 91
(2019 Pattern) (Semester - III) (204184)

3:3
0
31
Time : 2½ Hours] 1/0 13 [Max. Marks : 70
0
Instructions to the candidates:
2/2
.23 GP

1) Attempt Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8.

2) Neat diagrams must be drawn wherever necessary.
E
80

3) Figures to the right side indicate full marks.

8
C

23
4) Assume suitable data, if necessary.

ic-
16

tat
Q1) a) What is ADT? Explain stack as an ADT. [4]
8.2

5s
b) Write a structure for stack using array. Write PUSH and POP function
.24

2:5
91
for stack using array. [8]
49

3:3
c) Evaluate following postfix expression with the help of stack. [6]
30
31

5 3 + 6 2/*3 5*+
01
02

OR
2/2
GP

Q2) a) What is Queue? Explain insertion and deletion operation in Queue with
1/0

suitable diagram. [6]

CE

b) Explain with example: [6]

80

8
23
i) Linear Queue
.23

ii) Circular Queue ic-

16

tat
c) Write C functions for : [6]
8.2

5s

i) Enqueue in Linear Queue

.24

2:5
91

ii) Dequeue in Circular Queue

49

3:3
30
31

Q3) a) Write structure definition for single Linked list. Differentiate between
01
02

static memory and dynamic memory allocation. [6]

2/2

b) Write following C functions in SLL: [6]

GP
1/0

i) Insert a node at the beginning

CE

ii) Delete a node at the end

80

c) State the limitations of single linked list. Represent following polynomial

.23

using linked list. [5]

16

20 x9 + 15 x 7 + 10 x5 + 5 x + 50
8.2

OR
.24
49

P.T.O.
Q4) a) Write structure definition for double Linked list. Differentiate between

8
23
array and linked list. [6]

ic-
b) State the limitations of array. Draw and explain double linked list. [5]

tat
5s
c) Write following C functions in circular in SLL. [6]

2:5
i) Insert a node at the end

02 91
3:3
0
ii) Delete all nodes in the list

31
1/0 13
0
2/2
.23 GP

Q5) a) Define binary tree. Explain following terms with suitable examples: [7]
E

i) Root node
80

8
C

23
ii) Left and right sub tree

ic-
16

tat
iii) Depth of tree
8.2

5s
.24

2:5
b) Construct the Binary Search Tree (BST) from the following data: [5]
91
49

3:3
CAR, BAG, MAN, ADD, SAD, FAN, TAN
30
31

c) Write recursive function for in-order, pre-order and post-order traversal

01
02

of Binary tree. [6]

2/2
GP
1/0

OR
CE
80

8
Q6) a) Define the following terms with suitable example with respect to Binary

23
.23

tree: [6]
ic-
16

tat
i) Strictly Binary Tree
8.2

5s
.24

ii) Completely Binary Tree

2:5
91
49

3:3

iii) Binary Search Tree

30
31

b) Construct the binary search tree (BST) from the following elements: [6]
01
02
2/2

45, 20, 80, 40, 10, 90, 70

GP
1/0

Also, show pre-order and post-order traversal for the same.

CE
80

c) What is AVL tree? Explain all the rotations in AVL tree. Construct AVL
.23

tree for the following data: [6]

16
8.2

1, 2, 3, 4, 5, 6
.24

[5925]-215
49

2
Q7) a) What do you mean by adjacency matrix and adjacency list? Give the

8
23
adjacency matrix and adjacency list for the graph shown below: [6]

ic-
tat
5s
2:5
02 91
3:3
0
31
1/0 13
0
2/2
.23 GP
E
80

8
C

23
ic-
16

tat
8.2

5s
b) Explain with suitable example, DFS and BFS traversal of a graph. [5]
.24

2:5
91
c) Define with an example: [6]
49

3:3
30
31

i) Undirected Graph
01
02

ii) Directed Graph

2/2
GP
1/0

iii) Weighted Graph

CE
80

8
OR

23
.23

Q8) a) Define indegree and outdegree of a vertex in graph. Find the indegree ic-
16

tat
and outdegree of following graph. [6]
8.2

5s
.24

2:5
91
49

3:3
30
31
01
02
2/2
GP
1/0
CE
80
.23
16
8.2
.24

[5925]-215
49

3
 b) Find out Minimum Spanning Tree of the following graph (figure 3) using

8
23
Kruskal’s algorithm. [6]

ic-
tat
5s
2:5
02 91
3:3
0
31
1/0 13
0
2/2
.23 GP
E
80

8
C

23
ic-
16

c) Find the shortest path from node ‘a’ to all nodes in the graph shown in

tat
8.2

fig.4 using Dijkstra’s algorithm. [6]

5s
.24

2:5
91
49

3:3
30
31
01
02
2/2
GP
1/0
CE
80

8
23
.23

ic-
16

tat
8.2

5s
.24

2:5
91
49

3:3
30


31
01
02
2/2
GP
1/0
CE
80
.23
16
8.2
.24

[5925]-215
49

4
Total No. of Questions : 4] SEAT No. :

8
23
PA-7 [Total No. of Pages : 2

ic-
[5931]-10

tat
3s
S.E. (E & TC/Electronics)

0:5
DATA STRUCTURES

02 91
0:4
(2019 Pattern) (Semester - I) (204184)

0
31
0/0 13
Time : 1 Hour] [Max. Marks : 30
0
1/2
Instructions to the candidates:
.23 GP

1) Solve Q1 or Q2, Q3 or Q4.

E

2) Figures to the right indicate full marks.

82

8
C

23
3) Neat diagrams must be drawn wherever necessary.

ic-
4) Assume suitable data, if necessary.
16

tat
8.2

3s
Q1) a) What is pseudo code? Write a pseudo code to find the factorial of n
.24

0:5
91
number. [5]
49

0:4
30
31

b) Write a C function with pointers to arrays for checking whether the

01

given string is a palindrome or not.

02

[4]
1/2
GP

c) What is a pointer? What are the advantages of using a pointer? Explain

0/0

the Pointer declaration and its initialization with an example. [6]

CE
82

8
23
OR
.23

ic-
16

tat
Q2) a) Explain the following : [6]
8.2

3s
.24

0:5

i) Call by value
91
49

0:4

ii) Call by reference

30
31
01
02

b) Write the following functions in ‘C’ : [6]

1/2
GP

i) STRCOPY() to copy a string to another string using an array.

0/0
CE
82

ii) STRLENGTH() to find the length of the string using an array.

.23

Note : do not use standard library functions.

16
8.2

c) Explain bitwise operators with examples. [3]

.24
49

P.T.O.
Q3) a) Explain the binary search algorithm with an example. [5]

8
23
b) Sort the following numbers 38, 27, 43, 3, 9, 82, 10 using Bubble sort.

ic-
[5]

tat
3s
c) Compare linear search and binary search. Write an algorithm to search

0:5
elements in a list using linear search. [5]

02 91
0:4
OR

0
31
0/0 13
Q4) a) Write a C function for linear search. Explain its time complexity. [5]
0
1/2
.23 GP

b) What is the difference between internal sorting and external sorting?

Sort the following numbers using selection sort. [5]
E
82

8
C

23
25, 17, 31, 13,2

ic-
c) Sort the following data using merge sort
16

[5]

tat
8.2

3s
27, 10, 12, 25, 34, 16, 15, 31
.24

0:5
91
49

0:4
30
31


01
02
1/2
GP
0/0
CE
82

8
23
.23

ic-
16

tat
8.2

3s
.24

0:5
91
49

0:4
30
31
01
02
1/2
GP
0/0
CE
82
.23
16
8.2
.24
49

[5931]-10 2
Total No. of Questions : 8] SEAT No. :

8
23
P-9700 [Total No. of Pages : 4

ic-
[6179]-229A

tat
9s
S.E. (E & TC/Electronics)

4:1
DATA STRUCTURES

02 91
1:4
(2019 Pattern) (Semester - III) (204184)

0
41
Time : 2½ Hours]
5/0 13 [Max. Marks : 70
0
Instructions to the candidates:
1/2
.23 GP

1) Answer Q1 or Q2, Q3 or Q4, Q5 or Q6 and Q7 or Q8.

2) Figures to the right indicate full marks.
E
80

8
3) Assume suitable data, if necessary.
C

23
4) Neat diagrams must be drawn wherever necessary.

ic-
16

tat
Q1) a) Write a ‘C’ function to Push and POP elements from a stack of characters
8.2

9s
using an array. [6]
.24

4:1
91
49

b) What are the disadvantages of the linear queue? Suggest a suitable method
1:4
30

to overcome them. [6]

41
01
02

c) Convert the given infix expression to a postfix expression using stack :

1/2

(a^b)*c–d/d [5]
GP
5/0

Note : ^=Exponent operator.

CE
80

8
23
OR
.23

ic-
16

tat
Q2) a) Identify the expression and convert them into the remaining two forms :
8.2

9s

[6]
.24

4:1
91
49

1:4

i) AB + C * DE – FG + + $
30
41

ii) – A / B * C $ DE
01
02
1/2

Note $ = Exponent operator

GP
5/0

b) Write a ‘C’ function to insert and delete element from queue using an
CE
80

array. [6]
.23

c) Define Queue. What are conditions for ‘Queue empty’ and ‘Queue full’
16

when queue is implemented using Array? Explain. [5]

8.2
.24
49

P.T.O.
Q3) a Explain traversal operations in a singly linked list. [6]

8
23
b) A doubly linked list with numbers to be created. Write node structure and

ic-
a ‘C’ function to create a double linked list. [6]

tat
c) Draw and explain the circular linked list. State the limitations of a singly

9s
linked list. [6]

4:1
02 91
OR

1:4
Q4) a) Write limitations of arrays over linked list? Represent the following

0
41
5/0 13
polynomial using a singly linked list. [6]
23x9 + 18x7 + 41x6 +16x4 + 3
0
1/2
.23 GP

b) What is a singly linked list? Write C function for inserting a node at a given
location into a singly linked list. [6]
E
80

8
C

c) Write a’C’ function for Inserting a number at the front of the circular

23
linked list. [6]

ic-
16

tat
8.2

9s
Q5) a) Write are cursive ‘C’ function for inorder and preorder traversal of Binary
.24

4:1
Search Tree. [6]
91
49

1:4
b) Explain with suitable example how binary tree can be represented using :
30
41

i) Array
01
02

ii) Linked List

1/2
GP

[6]
5/0

c) Write an algorithm to insert an element in a binary search tree implemented

CE
80

8
using linked representation. [5]

23
.23

OR
ic-
16

tat
Q6) a) Construct the Binary Search Tree (BST) from the following data : [6]
8.2

9s

5, 2, 8, 4, 1, 9, 7
.24

4:1

Also show preorder, postorder and inorder traversal for the same.
91
49

1:4

b) Explain basic concept of AVL tree. Also explain four rotations in AVL tree.
30
41

[6]
01
02

c) Define the following terms with respect to Trees : [5]

1/2
GP

i) Root
5/0

ii) Subtree
CE
80

iii) Level of node

.23

iv) Depth of Tree

16

v) Siblings
8.2
.24
49

[6179]-229A 2
Q7) a) Represent the following graph using the adjacency matrix and adjacency

8
23
list. [6]

ic-
tat
9s
4:1
02 91
1:4
0
41
5/0 13
Fig. 1
0
1/2
.23 GP

b) Define indegree and outdegree of a vertex in graph. Find the indegree

and outdegree of following graph. [6]
E
80

8
C

23
ic-
16

tat
8.2

9s
.24

4:1
91
49

1:4
30
41
01
02

Fig. 2
1/2
GP

c) Define with an examples : [6]

5/0

i) Undirected Graph
CE
80

8
23
ii) Directed Graph
.23

iii) Weighted Graph

ic-
16

tat
OR
8.2

9s
.24

Q8) a) Find out Minimum spanning Tree of the following graph (figure 3) using
4:1
91

Kruskal’s algorithm. [6]

49

1:4
30
41
01
02
1/2
GP
5/0
CE
80
.23
16

Fig. 3
8.2

b) Explain with suitable example, DFS and BFS traversal of a graph. [6]
.24
49

[6179]-229A 3
 c)

49

[6179]-229A
.24
8.2
16
C E
.23 GP
80 0
5/0 13
49 1/2 0
02 91
.24
8.2 CE 41
16 1:4
.23 GP 4:1

4
80 9s
fig. 4 using Dijkstra’s algorithm.

5/0
01 Fig. 4
tat
30 ic-

49 1/2 23
.24 02
41
91 8
8.2 CE
16 1:4
.23 GP 4:1
80 01 9s
5/0 30 tat
1/2 ic-
23
02
41
91 8
1:4
4:1
9s
tat
[6]
Find the shortest path from node ‘a’ to all nodes in the graph shown in

ic-
23
8
Total No. of Questions : 8] SEAT No. :

7
23
PC2805 [6352]-29 [Total No. of Pages : 3

ic-
tat
S.E. (Electronics/Electronics & Telecommunication)

4s
DATA STRUCTURES

2:5
02 91
(2019 Pattern) (Semester - III) (204184)

9:4
0
40
Time : 2½ Hours] 9/1 13 [Max. Marks : 70
0
Instructions to the candidates:
2/2
.23 GP

1) Answer Q1 or Q2, Q3 or Q4, Q5 or Q6, Q7 or Q8.

2) Neat diagrams must be drawn wherever necessary.
E
70

7
3) Figures to the right indicate full marks.
C

23
ic-
4) Use of calculator is allowed.
16

tat
5) Assume suitable data if necessary.
8.2

4s
.24

Q1) a) Compare Stack and Queue. What are the advantages of circular queue
2:5
91
over liner queue? [6]
49

9:4
30
40

b) Write a function PUSH and POP in ‘C’ for stack using linked list. [6]
01
02

c) What are the applications of Queue? Explain two applications in detail.[5]

2/2
GP
9/1

OR
CE
70

7
Q2) a) Write a short note on circular queue. Compare it with linear queue. [5]

23
.23

b) Convert the following prefix expression into infix form. Show all the ic-
16

tat
steps and stack contents: [6]
8.2

4s
.24

2:5

*-A/BC-/AKL
91
49

9:4

c) Write ADD and DETETE function in ‘C’ for Queue using array. [6]
30
40
01
02
2/2
GP

Q3) a) Compare array and linked list. [5]

9/1

b) Write a ‘C’ function to delete a number from singly linked list. [6]
CE
70
.23

c) Explain doubly linked list (DLL). What are the advantages of DLL over
SLL. [6]
16
8.2

OR
.24
49

P.T.O.
Q4) a) Draw and explain circular linked list. State the limitations of single linked

7
23
list. [5]

ic-
tat
b) Write a ‘C’ function to insert a number at end in to the singly linked list.[6]

4s
c) Differentiate singly linked list and doubly linked list. [6]

2:5
02 91
9:4
0
40
Q5) a)
9/1 13
Construct Binary search tree for the following : [6]
0
2/2
.23 GP

MAR, OCT, JAN, APR, NOV, FEB, MAY, DEC, JUN, AUG, JUL, SEP
E
70

7
b) Write a pseudo code to search an element in binary search tree using arrays.[6]
C

23
ic-
c) Explain with suitable example how binary tree can be represented using: [6]
16

tat
8.2

4s
i) Array
.24

2:5
91
49

9:4
ii) Linked List
30
40

OR
01
02
2/2
GP

Q6) a) Define BST? Create a BST for the following data: [6]
9/1
CE
70

14, 15, 4, 9, 7, 18, 3, 5, 7.

7
23
.23

b) Define binary tree. Name and explain with suitable example the following
ic-
16

tat
terms [6]
8.2

4s
.24

2:5

i) Root node
91
49

9:4
30

ii) Left sub tree and right sub tree

40
01
02

iii) Depth of tree

2/2
GP
9/1

c) Construct the binary search tree from the following elements: [6]
CE
70

15, 4, 16, 8, 2, 18, 14

.23
16

Also show preorder, inorder and postorder traversal for the same.
8.2
.24
49

[6352]-29 2
Q7) a) Draw adjacency list and adjacency matrix for the following graph: [6]

7
23
ic-
tat
4s
2:5
02 91
9:4
0
40
9/1 13
0
2/2
.23 GP

b) What is MST? Explain with suitable example Kruskal’s Algorithm to

E

find out MST. [6]

70

7
C

23
c) Define DFS and BFS graph with example. [6]

ic-
16

tat
OR
8.2

4s
.24

2:5
Q8) a) Explain Kruskal algorithm? Find the minimum spanning tree for below
91
figure. Using Kruskal’s Algorithm. [6]
49

9:4
30
40
01
02
2/2
GP
9/1
CE
70

7
23
.23

ic-
16

tat
8.2

4s
.24

2:5

b) Explain Dijkstra’s algorithm with example. [6]

91
49

9:4

c) Explain with suitable example the techniques to represent a Graph. [6]

30
40

Note: consider graph of minimum 6 vertices

01
02
2/2
GP
9/1


CE
70
.23
16
8.2
.24
49

[6352]-29 3
Total No. of Questions : 8] SEAT No. :

7
23
PD-4066 [Total No. of Pages : 3

ic-
[6402]-25

tat
5s
S.E. (E & TC/Electronics)

4:4
DATA STRUCTURES

02 91
9:3
(2019 Pattern) (Semester - III) (204184)

0
50
Time : 2½ Hours]
2/0 13 [Max. Marks : 70
0
Instructions to the candidates:
5/2
.23 GP

1) Answer Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8.

2) Neat diagrams must be drawn wherever necessary.
E
72

7
3) Figures to the right indicate full marks.
C

23
4) Use of Calculator is allowed.

ic-
5) Assume Suitable data if necessary.
16

tat
8.2

5s
Q1) a) Compare Stack and Queue. What are the advantages of circular queue
.24

4:4
over liner queue? [6]
91
49

9:3
b) Write a function PUSH and POP in ‘C’ for stack using linked list. [6]
30
50

c) Write a short note on circular queue. Compare it with linear queue.[5]

01
02
5/2
GP

OR
2/0

Q2) a) What are the applications of Queue? Explain two applications in detail.
CE
72

7
23
[5]
.23

b) Convert the following prefix expression into infix form. Show all the ic-
16

tat
steps and stack contents:
8.2

5s
.24

4:4

*–A/BC–/AKL [6]
91
49

9:3

c) Write ADD and DELETE function in ‘C’ for Queue using array. [6]
30
50
01
02
5/2
GP

Q3) a) Compare array and linked list. [5]

2/0
CE

b) Write a ‘C’ function to delete a number from singly linked list. [6]
72
.23

c) Differentiate singly linked list and doubly linked list. [6]

16

OR
8.2
.24

P.T.O.
49
Q4) a) Draw and explain circular linked list. State the limitations of single

7
linked list. [5]

23
ic-
b) Write a ‘C’ function to insert a number at end in to the singly linked

tat
list. [6]

5s
4:4
c) Explain doubly linked list (DLL). What are the advantages of DLL

02 91
over SLL. [6]

9:3
0
50
2/0 13
0
Q5) a) Construct Binary search tree for the following
5/2
.23 GP

MAR, OCT, JAN, APR, NOV, FEB, MAY, DEC, JUN, AUG. .JUL,
E
72

SEP [6]

7
C

23
ic-
b) Write a pseudo code to search an element in binary search tree using
16

tat
arrays. [6]
8.2

5s
c) Define binary tree. Name and explain with suitable example the
.24

4:4
91
following terms [6]
49

9:3
30

i) Root node
50
01
02

ii) Left sub tree and right sub tree

5/2
GP

iii) Depth of tree

2/0
CE
72

7
OR

23
.23

Q6) a) Define BST? Create a BST for the following data:

ic-[6]
16

tat
8.2

14,15,4,9,7,18,3,5,7.
5s
.24

4:4

b) Explain with suitable example how binary tree can be represented

91
49

9:3

using: [6]
30
50

i) Array
01
02
5/2

ii) Linked List

GP
2/0

c) Construct the binary search tree from the following elements: [6]
CE
72

15,4,16,8,2,18,14
.23
16

Also show preorder, inorder and postorder traversal for the same.
8.2
.24
49

[6402]-25 2
Q7) a) Draw adjacency list and adjacency matrix for the following graph: [6]

7
23
ic-
tat
5s
4:4
02 91
9:3
0
50
2/0 13
0
5/2
.23 GP
E
72

7
C

23
b) What is MST? Explain with suitable example Kruskal’s Algorithm to

ic-
find out MST. [6]
16

tat
8.2

5s
c) Define DFS and BFS graph with example. [6]
.24

4:4
OR
91
49

9:3
Q8) a)
30

Explain Kruskal algorithm? Find the minimum spanning tree for below
50

figure. Using Kruskal’s Algorithm. [6]

01
02
5/2
GP
2/0
CE
72

7
23
.23

ic-
16

tat
8.2

5s
.24

4:4
91
49

9:3

b) Explain Dijkstra’s algorithm with example. [6]

30
50

c) Explain with suitable example the techniques to represent a Graph. [6]

01
02
5/2

Note: consider graph of minimum 6 vertices

GP
2/0


CE
72
.23
16
8.2
.24
49

[6402]-25 3