Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2015 Scheme 2020 January Previous Question Paper 5th Sem 5CS33 Data Structures and Applications
USN
kit "?3 C Fl!KODI
5CS33
Third Semester B.E. Degree Examination, Dee.20
49ge?f\  ?4
.1
> F1/
02
/
0
co
Data Structures and Applications
Time: 3 'hrs.
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module I
1 a. What do you mean by dynamic memory allocation? List and explain various functions
supported by C to carryout dynamic memory allocation. (09 Marks)
b. What is sparse matrix? Show with a suitable example sparse matrix representation starting
as triplets. (03 Marks)
c. Write simple transfer algorithm to transpose the given sparse matrix. (04 Marks)
OR
2 a. Write the Knuth Morris Pratt pattern matching algorithm and apply the same to search the
pattern `abcdabey' in the test `abcxabcdabxabcdabcdabey' (08 Marks)
b. Consider two polynomials A(x) = 4x
L5
+ 3x
4
+ 5 and B(x) = x
4
+ 10x
2
+ 1. Show
diagrammatically how these polynomials can be stored in a 1D array. Also give its C
representation. (03 Marks)
c. What is data structure? List and explain different operation performed on data structure.
(05 Marks)
Module2
3 a. List the disadvantages of linear queue and explain how it is solved in circular queue.
Implement circular queue with supporting functions using array. (08 Marks)
b. Convert the following infix expression into postfix expression:
i) (a + b) * d + e / (f + a * d) + c
ii) ((a / (b ? c + d)) * (e ? a) * c) (04 Marks)
c.
What is recursion? Write recursive function to solve tower of Hanoi problem. (04 Marks)
OR
4 a. Define stack. Implement push and pop functions for stack using arrays with stackfull and
stackempty conditions. (08 Marks)
b. Convert the following infix expression to postfix expression using stack.
((a / b) ? c) + (d * e))? (a * c) (08 Marks)
Module3
5 a. Give the node structure to create singly linked list of integer and write function to perform.
i) Create list
ii) Insert node at the end
iii) Delete first node
iv) Display all nodes. (08 Marks)
b. What are the disadvantages of doubly linked list over singly linked list? Illustrate with
example. Write node structure of doubly linked list. (08 Marks)
1 of 2
FirstRanker.com  FirstRanker's Choice
Max. Marks: 80
USN
kit "?3 C Fl!KODI
5CS33
Third Semester B.E. Degree Examination, Dee.20
49ge?f\  ?4
.1
> F1/
02
/
0
co
Data Structures and Applications
Time: 3 'hrs.
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module I
1 a. What do you mean by dynamic memory allocation? List and explain various functions
supported by C to carryout dynamic memory allocation. (09 Marks)
b. What is sparse matrix? Show with a suitable example sparse matrix representation starting
as triplets. (03 Marks)
c. Write simple transfer algorithm to transpose the given sparse matrix. (04 Marks)
OR
2 a. Write the Knuth Morris Pratt pattern matching algorithm and apply the same to search the
pattern `abcdabey' in the test `abcxabcdabxabcdabcdabey' (08 Marks)
b. Consider two polynomials A(x) = 4x
L5
+ 3x
4
+ 5 and B(x) = x
4
+ 10x
2
+ 1. Show
diagrammatically how these polynomials can be stored in a 1D array. Also give its C
representation. (03 Marks)
c. What is data structure? List and explain different operation performed on data structure.
(05 Marks)
Module2
3 a. List the disadvantages of linear queue and explain how it is solved in circular queue.
Implement circular queue with supporting functions using array. (08 Marks)
b. Convert the following infix expression into postfix expression:
i) (a + b) * d + e / (f + a * d) + c
ii) ((a / (b ? c + d)) * (e ? a) * c) (04 Marks)
c.
What is recursion? Write recursive function to solve tower of Hanoi problem. (04 Marks)
OR
4 a. Define stack. Implement push and pop functions for stack using arrays with stackfull and
stackempty conditions. (08 Marks)
b. Convert the following infix expression to postfix expression using stack.
((a / b) ? c) + (d * e))? (a * c) (08 Marks)
Module3
5 a. Give the node structure to create singly linked list of integer and write function to perform.
i) Create list
ii) Insert node at the end
iii) Delete first node
iv) Display all nodes. (08 Marks)
b. What are the disadvantages of doubly linked list over singly linked list? Illustrate with
example. Write node structure of doubly linked list. (08 Marks)
1 of 2
15CS33
OR
6 a. What a C program to implement linked stack? (08 Marks)
b. Write node structure for linked representation of polynomial. Explain algorithm to add two
polynomial represented using linked lists. (08 Marks)
7 'a.
b.
Module4
What is a tree? Explain with suitable example: i) Binary tree ii) Skewed binary tree
iii) Complete binary tree. (07 Marks)
Draw a binary tree for the following expression 3 + 4 * (7 ? 6) / 4 + 3. Traverse the
generated tree using inorder, preorder and postorder. Also write functions for each traversal.
(09 Marks)
OR
8 a. For a given data, draw a binary search tree and show the array and linked representation of
the same 100, 85, 45, 55, 110, 20, 70, 65. (08 Marks)
b. What is binary search tree? Write an algorithm to search given element in a binary search
tree. (08 Marks)
Module5
9 a. What is collision? What are the methods to resolve collision? Explain linear probing with an
example. (08 Marks)
b. What are the methods used for traversing a graph? Explain any one with example.
(08 Marks)
OR
10 a. Define graph. Differentiate between tree and graph. (03 Marks)
b. For the given graph, show adjacency matrix and adjacency list representation.
(Ref.Fig.Q.10(b). (05 Marks)
Fig.Q.10(b)
c. Briefly explain basic operations that can be performed on a file. Explain indexed sequential
file organization. (08 Marks)
.......,,,.::,
/, C   : '?,
/ :of
.
.0?

?
,
..., !,le: ,
si ."
',.... .1
%
(
I
..
'
s r
, ? 'Cr. ' .I
:
:: .. \
1.
.,.? ( L.U.: * i
, ,,t:?'? 11 % $
' s (..tilf"
.1
''''
? .
c
\


N.,
?/,:
e 0 1
f
e
:'
 ?
2 of 2
FirstRanker.com  FirstRanker's Choice
This post was last modified on 02 March 2020