Download VTU BE 2020 Jan CSE Question Paper 15 Scheme 5th Sem 5CS33 Data Structures and Applications

Max. Marks: 80
USN
kit "?3 C Fl!KODI
5CS33
Third Semester B.E. Degree Examination, Dee.20

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

49ge?f\ --- ?4
.1
> F1/
02
/

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

0
co
Data Structures and Applications
Time: 3 'hrs.
Note: Answer any FIVE full questions, choosing ONE full question from each module.

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

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)

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

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 `abc-dabey' in the test `abcxabcdabxabcdabcdabey' (08 Marks)
b. Consider two polynomials A(x) = 4x

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

L5
+ 3x
4
+ 5 and B(x) = x
4

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

+ 10x
2
+ 1. Show
diagrammatically how these polynomials can be stored in a 1-D array. Also give its C
representation. (03 Marks)

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

c. What is data structure? List and explain different operation performed on data structure.
(05 Marks)
Module-2
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)

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

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)

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

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)

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

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

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

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

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

Max. Marks: 80
USN
kit "?3 C Fl!KODI
5CS33
Third Semester B.E. Degree Examination, Dee.20

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

49ge?f\ --- ?4
.1
> F1/
02
/

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

0
co
Data Structures and Applications
Time: 3 'hrs.
Note: Answer any FIVE full questions, choosing ONE full question from each module.

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

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)

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

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 `abc-dabey' in the test `abcxabcdabxabcdabcdabey' (08 Marks)
b. Consider two polynomials A(x) = 4x

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

L5
+ 3x
4
+ 5 and B(x) = x
4

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

+ 10x
2
+ 1. Show
diagrammatically how these polynomials can be stored in a 1-D array. Also give its C
representation. (03 Marks)

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

c. What is data structure? List and explain different operation performed on data structure.
(05 Marks)
Module-2
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)

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

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)

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

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)

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

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

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

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

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

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.

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

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

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

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)

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

b. What is binary search tree? Write an algorithm to search given element in a binary search
tree. (08 Marks)
Module-5
9 a. What is collision? What are the methods to resolve collision? Explain linear probing with an
example. (08 Marks)

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

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.

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

(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)
.......,,,-.::,-

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

/,--- C - - : --'?,
/ :of
.
.0?
-

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

?
----,
..., !,le: ,
si ."-

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

',.... .1
%
(
I
..

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

'
s r
, ? 'Cr. ' .I
:
:: .. \

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

1.
.,.? ( L.U.: * i
, ,,t:?'? 11 % $
' s (..tilf"
.-1

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

''''
? .
c
\
-

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

-
N.,
?/,:
e 0 1
f

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

e
:'
- ?
2 of 2
FirstRanker.com - FirstRanker's Choice

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