Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2017 Scheme 2020 January Previous Question Paper 3rd Sem 1533 Data Structures And Applications
, ?
o
t
,..
/
:_
\\

i'1
,
CHIKODI
,p
:?, . ICS/1533
.?/ Q... /
'"!?,.?:?/,
, .. , f
INJit;?,/'
Third Semester B.F. Degree Examination, Dec.20101?tf".1020
Data Structures & Applications
Time: 3 hrs. Max. Marks: 100
Note: Answer any FIVE full questions, choosing ONE full question from each module.
ModuleI
1 a. Differentiate between Structures and Unions with example. (05 Marks)
b. Explain the functions supported by 'C' to carry out dynamic memory allocation. (05 Marks)
c. Express the given sparse matrix as triplets and find its transpose and also write a fast
transpose algorithm to transpose a sparse matrix
15 0 0 22 0 ?15
0 11 3 0 0 0
0 0 0 ?6 0 0
(10 Marks)
0 0 0 0 0 0
tt.4)
rl

91 0 0 0 0 0
0 0 28 0 0 0
OR
2 a. How would you represent polynomial using array of structures and also write a function to
as 2 polynomials. (to Marks)
b. Find the table and corresponding graph tier the second pattern matching algorithm where the
pattern is P = ababab. (10 Marks)
Module2
3 a. Convert the following Infix expression to Postfix expression :
(i) ((((a/b) ? c) + ((d*e)) ? a * c)) (ii) A ? B I (C * D $ E)
b. Write a function to evaluate Postfix expression.
c. Define Recursion and Evaluate A(1, 3) using Ackermann's function.
(06 Marks)
(08 Marks)
(06 Marks)
OR
4 a. Explain with suitable example disadvantages of ordinary queue and how it is solved using
circular queue, write functions for circular queue insertion and deletion. (10 Marks)
b. Define stack. Give 'C' implementation of PUSH and POP functions. Include check for
empty and full conditions of stacks. (06 Marks)
c. Evaluate the following Postfix expression
623 + ? 382 I + * 2 $ 3 + (04 Marks)
Module3
5 a. Write 'C' function to perform the following :
(i) Assume a four node single linked list with data value 15, 25, 40, 50
(ii) Insert a node with data value 30 in between the nodes 25 and 40.
(iii) Delete a mode with data value '40'.
_.,
(iv) Search a mode with data value '25'
4
9
c c/
.
0,
;'> So' ''''
,
..
:7
4
s
v
........,,
,ki
?,
ft
I of 2 I*
LIEIRP?P,1
\ *
,
C HKODi r'
ii..) 4
(15 Marks)
FirstRanker.com  FirstRanker's Choice
USN
, ?
o
t
,..
/
:_
\\

i'1
,
CHIKODI
,p
:?, . ICS/1533
.?/ Q... /
'"!?,.?:?/,
, .. , f
INJit;?,/'
Third Semester B.F. Degree Examination, Dec.20101?tf".1020
Data Structures & Applications
Time: 3 hrs. Max. Marks: 100
Note: Answer any FIVE full questions, choosing ONE full question from each module.
ModuleI
1 a. Differentiate between Structures and Unions with example. (05 Marks)
b. Explain the functions supported by 'C' to carry out dynamic memory allocation. (05 Marks)
c. Express the given sparse matrix as triplets and find its transpose and also write a fast
transpose algorithm to transpose a sparse matrix
15 0 0 22 0 ?15
0 11 3 0 0 0
0 0 0 ?6 0 0
(10 Marks)
0 0 0 0 0 0
tt.4)
rl

91 0 0 0 0 0
0 0 28 0 0 0
OR
2 a. How would you represent polynomial using array of structures and also write a function to
as 2 polynomials. (to Marks)
b. Find the table and corresponding graph tier the second pattern matching algorithm where the
pattern is P = ababab. (10 Marks)
Module2
3 a. Convert the following Infix expression to Postfix expression :
(i) ((((a/b) ? c) + ((d*e)) ? a * c)) (ii) A ? B I (C * D $ E)
b. Write a function to evaluate Postfix expression.
c. Define Recursion and Evaluate A(1, 3) using Ackermann's function.
(06 Marks)
(08 Marks)
(06 Marks)
OR
4 a. Explain with suitable example disadvantages of ordinary queue and how it is solved using
circular queue, write functions for circular queue insertion and deletion. (10 Marks)
b. Define stack. Give 'C' implementation of PUSH and POP functions. Include check for
empty and full conditions of stacks. (06 Marks)
c. Evaluate the following Postfix expression
623 + ? 382 I + * 2 $ 3 + (04 Marks)
Module3
5 a. Write 'C' function to perform the following :
(i) Assume a four node single linked list with data value 15, 25, 40, 50
(ii) Insert a node with data value 30 in between the nodes 25 and 40.
(iii) Delete a mode with data value '40'.
_.,
(iv) Search a mode with data value '25'
4
9
c c/
.
0,
;'> So' ''''
,
..
:7
4
s
v
........,,
,ki
?,
ft
I of 2 I*
LIEIRP?P,1
\ *
,
C HKODi r'
ii..) 4
(15 Marks)
17CS/IK
b.
Write a note on linked
given sparse matrix
0 5 3
I 0 0
0 0 0
representation of sparse matrix. Give linked representation of the
(05 Marks)
OR
6 a. Write a note on Doubly linked lists and also write functions to insert at front and delete at
front using D.L.L. (08 Marks)
b. Write a function to add 2 polynomials using Single Linked lists. (08 Marks)
c. Write a function to Concatenate 2 Single Linked lists. (04 Marks)
Module4
7 a. With suitable example define the following :
(i) Binary tree (ii) Full binary tree (iii) Almost complete B.T
(iv) Strict Binary tree (v) Level of B.T (05 Marks)
b. Create expression tree for the Postfix expression given below.
AB/C*D*E+ and traverse the resulting expression tree using inorder and preorder traversals.
(05 Marks,
c. Write a note on Threaded Binary tree for a given Binary tree in Fig.Q7(c), Insert 'r' as
right child of `S' in a Threaded Binary tree and write the function to insert (10 Marks)
Fig.Q7(c)
OR
8 a. Define BST. Write a function to insert an item into BST. (10 Marks)
b. Show that for any nonempty btree T, if n
o
is the number of leaf nodes and n2 is the number
of nodes of degree 2 than no = n2,1.
(05 Marks)
c. Write 'C' functions to illustrate copying of binary tree. (05 Marks)
Module5
9 a. Define graph. Give adjacency matrix and adjacency lists for the graph given below
Fig.Q9(a) :
Fig.Q9(a) (06 Marks)
b. Write an algorithm for DFS, show BFS and DFS traversals for the graph given in Q.No.9(a).
(10 Marks)
c. Write a note on Hashing functions. (04 Marks)
OR
10 a. What is collision? What are the methods to resolve collision? Explain linear probing with an
example. (it) Marks)
b. Suppose 9 cards are punched as follows 348, 143, 361, 423, 538,.,1 32l, 543, 366.
Apply Radix sort to sort them in 3 phases and give its complexity.
'
CSoc,.7, (10 Marks)
. Ne
* * * * *
2 of 2
7
LIP ^
FirstRanker.com  FirstRanker's Choice
This post was last modified on 02 March 2020