Download VTU BE 2020 Jan CSE Question Paper 17 Scheme 3rd Sem 1533 Data Structures And Applications

USN
, ?
o
t
,..

--- Content provided by FirstRanker.com ---

/
:_
\\

-

--- Content provided by FirstRanker.com ---

i-'1
,
CHIKODI
,p
---:?, . ICS/1533

--- Content provided by FirstRanker.com ---

.?/ Q... /
'"-!-?,.---------?:?-/,
, .. , f
INJit;?,/'
Third Semester B.F. Degree Examination, Dec.20101?tf".1020

--- Content provided by FirstRanker.com ---

Data Structures & Applications
Time: 3 hrs. Max. Marks: 100
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-I
1 a. Differentiate between Structures and Unions with example. (05 Marks)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

0 0 0 ?6 0 0
(10 Marks)
0 0 0 0 0 0
tt.4)
rl

--- Content provided by FirstRanker.com ---

-
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

--- Content provided by FirstRanker.com ---

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)
Module-2
3 a. Convert the following Infix expression to Postfix expression :

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

(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

--- Content provided by FirstRanker.com ---

empty and full conditions of stacks. (06 Marks)
c. Evaluate the following Postfix expression
623 + ? 382 I + * 2 $ 3 + (04 Marks)
Module-3
5 a. Write 'C' function to perform the following :

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

4-
9
c-- c/
.
0,

--- Content provided by FirstRanker.com ---

-;'> So' ''''
,

..
:7

--- Content provided by FirstRanker.com ---

4

s
v
........----,,

--- Content provided by FirstRanker.com ---

,ki
?,
ft
I of 2 I*
LIEIRP?P,1

--- Content provided by FirstRanker.com ---

\ *
,
C HKODi r'
ii..) 4
(15 Marks)

--- Content provided by FirstRanker.com ---

FirstRanker.com - FirstRanker's Choice
USN
, ?
o
t

--- Content provided by FirstRanker.com ---

,..
/
:_
\\

--- Content provided by FirstRanker.com ---

-
i-'1
,
CHIKODI
,p

--- Content provided by FirstRanker.com ---

---:?, . ICS/1533
.?/ Q... /
'"-!-?,.---------?:?-/,
, .. , f
INJit;?,/'

--- Content provided by FirstRanker.com ---

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.
Module-I

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

0 11 3 0 0 0
0 0 0 ?6 0 0
(10 Marks)
0 0 0 0 0 0
tt.4)

--- Content provided by FirstRanker.com ---

rl
-
91 0 0 0 0 0
0 0 28 0 0 0
OR

--- Content provided by FirstRanker.com ---

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)
Module-2

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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

--- Content provided by FirstRanker.com ---

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)
Module-3

--- Content provided by FirstRanker.com ---

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'.
_.----,

--- Content provided by FirstRanker.com ---

(iv) Search a mode with data value '25'
4-
9
c-- c/
.

--- Content provided by FirstRanker.com ---

0,
-;'> So' ''''
,

..

--- Content provided by FirstRanker.com ---

:7
4

s
v

--- Content provided by FirstRanker.com ---

........----,,
,ki
?,
ft
I of 2 I*

--- Content provided by FirstRanker.com ---

LIEIRP?P,1
\ *
,
C HKODi r'
ii..) 4

--- Content provided by FirstRanker.com ---

(15 Marks)
17CS/IK
b.
Write a note on linked
given sparse matrix

--- Content provided by FirstRanker.com ---

0 5 3
I 0 0
0 0 0
representation of sparse matrix. Give linked representation of the
(05 Marks)

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

Module-4
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.

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

OR
8 a. Define BST. Write a function to insert an item into BST. (10 Marks)
b. Show that for any non-empty b-tree T, if n
o
is the number of leaf nodes and n2 is the number

--- Content provided by FirstRanker.com ---

of nodes of degree 2 than no = n2,1.
(05 Marks)
c. Write 'C' functions to illustrate copying of binary tree. (05 Marks)
Module-5
9 a. Define graph. Give adjacency matrix and adjacency lists for the graph given below

--- Content provided by FirstRanker.com ---

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)

--- Content provided by FirstRanker.com ---

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.

--- Content provided by FirstRanker.com ---

'
CSoc,.7, (10 Marks)
. Ne
* * * * *
2 of 2

--- Content provided by FirstRanker.com ---

7-
LIP ^
FirstRanker.com - FirstRanker's Choice