Download Visvesvaraya Technological University (VTU) BE ( Bachelor of Engineering) CSE 2018 Scheme 2020 January Previous Question Paper 3rd Sem 18CS32 Data Structures and Applications
t
LCBRARY\
k C 18CS32
Third Semester B.E. Degree Examination, Dec.2401ii.2020
Data Structures and Applications
Time: 3 hrs. Max. Marks: 100
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-1
, .,
F2 1 a. What is data structure? What are the various types of data structure? Explain. (05 Marks)
cz ' b. What is structure? How it is different from array? Explain different types of structure
. %)
.-.
differences declaration with examples and give erences between Union and Structure.
-.
(10 Marks)
,.. ?)
c. Define pointers. How to declare and initialize pointers, explain with example. (05 Marks) .....
ti)
1, ..?,
ct ?
a. =
:-.- OR
...., ,
2 a. D5plain dynamic memory allocation functions in detail. (06 Marks)
V', 11 b. Write the Knuth Morris Pratt pattern matching algorithm and apply the same to search the
,.... - pc
..-2. 4-
.= r'l pattern `abcdabcy' in the text: `abcxabcdabxabcdabcdabcy' (08 Marks)
-.:, --t-
c. Write a C program to:
( i) Comparing strings
- =
a
-
(ii) Concatenate two strings (06 Marks)
:-. -,-
-..,'
,
c,
Module-2 - --
un . .?.
E 0- 3 a. Define stack. Give the implementation of push, pop and display functions. Include check for
t., .
c
Tc t empty and full conditions. (07 Marks)
-
o -d
ti) c b. Write the postfix form of the following expressions using stack:
o c,. .,
? -u .5
(i) A S B * C - D + EIF1(G + H)
.- . .. .-i
.
..,
(ii) A - B1(C * D S E)
. - 5 . ,
(06 Marks)
?, -- c.
Write an algorithm to evaluate a postfix expression and apply the same for the given postfix
? = 0
tn ? expression. ABC- D*+ESF+ and assume A = 6, B =3, C = 2, D = 5, E = 1 and F -= 7.
c ,?
. c._ (07 Marks)
E c-
o c
3
o ,2-
OR
4 a. Define recursion. Write a recursive functions for the following:
(i) Factorial of a number
(ii) Tower of Hanoi
._.
(07 Marks)
b. What is the advantage of circular queue over ordinary queue? Write a C program to simulate
c
', -
the working of circular queue of integers using array. Provide the following operations:
-6- I- ' -
0
, - ,
(i) Insert
P
(ii) Delete r-
0 ?
(iii) Display
r.;
_
(08 Marks)
c. Write a note on Dequeue and priority queue.
a.)
(05 Marks)
'a Module-3
cl
t
p
5 a. What is a linked list? Explain the different types of linked lists with neat diagram. (07 Marks)
E b. Write a C function to insert a node at front and delete a node from the rear end in a circular
linked list. (08 Marks)
c. Write a C function for the concatenation of two doubly linked lists. (05 Marks)
FirstRanker.com - FirstRanker's Choice
USN
t
LCBRARY\
k C 18CS32
Third Semester B.E. Degree Examination, Dec.2401ii.2020
Data Structures and Applications
Time: 3 hrs. Max. Marks: 100
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-1
, .,
F2 1 a. What is data structure? What are the various types of data structure? Explain. (05 Marks)
cz ' b. What is structure? How it is different from array? Explain different types of structure
. %)
.-.
differences declaration with examples and give erences between Union and Structure.
-.
(10 Marks)
,.. ?)
c. Define pointers. How to declare and initialize pointers, explain with example. (05 Marks) .....
ti)
1, ..?,
ct ?
a. =
:-.- OR
...., ,
2 a. D5plain dynamic memory allocation functions in detail. (06 Marks)
V', 11 b. Write the Knuth Morris Pratt pattern matching algorithm and apply the same to search the
,.... - pc
..-2. 4-
.= r'l pattern `abcdabcy' in the text: `abcxabcdabxabcdabcdabcy' (08 Marks)
-.:, --t-
c. Write a C program to:
( i) Comparing strings
- =
a
-
(ii) Concatenate two strings (06 Marks)
:-. -,-
-..,'
,
c,
Module-2 - --
un . .?.
E 0- 3 a. Define stack. Give the implementation of push, pop and display functions. Include check for
t., .
c
Tc t empty and full conditions. (07 Marks)
-
o -d
ti) c b. Write the postfix form of the following expressions using stack:
o c,. .,
? -u .5
(i) A S B * C - D + EIF1(G + H)
.- . .. .-i
.
..,
(ii) A - B1(C * D S E)
. - 5 . ,
(06 Marks)
?, -- c.
Write an algorithm to evaluate a postfix expression and apply the same for the given postfix
? = 0
tn ? expression. ABC- D*+ESF+ and assume A = 6, B =3, C = 2, D = 5, E = 1 and F -= 7.
c ,?
. c._ (07 Marks)
E c-
o c
3
o ,2-
OR
4 a. Define recursion. Write a recursive functions for the following:
(i) Factorial of a number
(ii) Tower of Hanoi
._.
(07 Marks)
b. What is the advantage of circular queue over ordinary queue? Write a C program to simulate
c
', -
the working of circular queue of integers using array. Provide the following operations:
-6- I- ' -
0
, - ,
(i) Insert
P
(ii) Delete r-
0 ?
(iii) Display
r.;
_
(08 Marks)
c. Write a note on Dequeue and priority queue.
a.)
(05 Marks)
'a Module-3
cl
t
p
5 a. What is a linked list? Explain the different types of linked lists with neat diagram. (07 Marks)
E b. Write a C function to insert a node at front and delete a node from the rear end in a circular
linked list. (08 Marks)
c. Write a C function for the concatenation of two doubly linked lists. (05 Marks)
18k.
OR
6 a. Describe the doubly linked lists with advantages and disadvantages. Write a C function tc
delete a node from a circular doubly linked list with header node. (08 Marks)
b. For the given sparse matrix, give the diagrammatic linked representation.
a=
0 1 2
3 0 0
0 0 0
(04 Marks)
c. Write a C function to add two-polynomials represented as circular list with header node.
(08 Marks)
Module-4
7 a. What is a tree? With suitable example, define:
(i) Binary tree
(ii) Level of the binary tree
(iii) Complete binary tree
(iv) Degree of the tree (09 Marks)
b. Write the C routines to traverse the tree using:
(i) Pre-order traversal
(ii) Post-order traversal. (06 Marks)
c. For the 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. (05 Marks)
OR
8 a. What is the advantage of the threaded binary tree over binary tree? Explain the construction
of threaded binary tree for 10, 20, 30, 40 and 50. (07 Marks)
b. Define expression tree. For a tree given in Fig.Q8(b) traverse the tree using in-order,
preorder and post-order traversals.
Fig.Q8(b) (07 Marks)
c. Construct a binary search tree by using the following in-order and preorder traversals:
Inorder : BCAEDGHFI
Preorder : ABCDEFGHI (06 Marks)
S OC:rt
? ? .
2 of 3
FirstRanker.com - FirstRanker's Choice
USN
t
LCBRARY\
k C 18CS32
Third Semester B.E. Degree Examination, Dec.2401ii.2020
Data Structures and Applications
Time: 3 hrs. Max. Marks: 100
Note: Answer any FIVE full questions, choosing ONE full question from each module.
Module-1
, .,
F2 1 a. What is data structure? What are the various types of data structure? Explain. (05 Marks)
cz ' b. What is structure? How it is different from array? Explain different types of structure
. %)
.-.
differences declaration with examples and give erences between Union and Structure.
-.
(10 Marks)
,.. ?)
c. Define pointers. How to declare and initialize pointers, explain with example. (05 Marks) .....
ti)
1, ..?,
ct ?
a. =
:-.- OR
...., ,
2 a. D5plain dynamic memory allocation functions in detail. (06 Marks)
V', 11 b. Write the Knuth Morris Pratt pattern matching algorithm and apply the same to search the
,.... - pc
..-2. 4-
.= r'l pattern `abcdabcy' in the text: `abcxabcdabxabcdabcdabcy' (08 Marks)
-.:, --t-
c. Write a C program to:
( i) Comparing strings
- =
a
-
(ii) Concatenate two strings (06 Marks)
:-. -,-
-..,'
,
c,
Module-2 - --
un . .?.
E 0- 3 a. Define stack. Give the implementation of push, pop and display functions. Include check for
t., .
c
Tc t empty and full conditions. (07 Marks)
-
o -d
ti) c b. Write the postfix form of the following expressions using stack:
o c,. .,
? -u .5
(i) A S B * C - D + EIF1(G + H)
.- . .. .-i
.
..,
(ii) A - B1(C * D S E)
. - 5 . ,
(06 Marks)
?, -- c.
Write an algorithm to evaluate a postfix expression and apply the same for the given postfix
? = 0
tn ? expression. ABC- D*+ESF+ and assume A = 6, B =3, C = 2, D = 5, E = 1 and F -= 7.
c ,?
. c._ (07 Marks)
E c-
o c
3
o ,2-
OR
4 a. Define recursion. Write a recursive functions for the following:
(i) Factorial of a number
(ii) Tower of Hanoi
._.
(07 Marks)
b. What is the advantage of circular queue over ordinary queue? Write a C program to simulate
c
', -
the working of circular queue of integers using array. Provide the following operations:
-6- I- ' -
0
, - ,
(i) Insert
P
(ii) Delete r-
0 ?
(iii) Display
r.;
_
(08 Marks)
c. Write a note on Dequeue and priority queue.
a.)
(05 Marks)
'a Module-3
cl
t
p
5 a. What is a linked list? Explain the different types of linked lists with neat diagram. (07 Marks)
E b. Write a C function to insert a node at front and delete a node from the rear end in a circular
linked list. (08 Marks)
c. Write a C function for the concatenation of two doubly linked lists. (05 Marks)
18k.
OR
6 a. Describe the doubly linked lists with advantages and disadvantages. Write a C function tc
delete a node from a circular doubly linked list with header node. (08 Marks)
b. For the given sparse matrix, give the diagrammatic linked representation.
a=
0 1 2
3 0 0
0 0 0
(04 Marks)
c. Write a C function to add two-polynomials represented as circular list with header node.
(08 Marks)
Module-4
7 a. What is a tree? With suitable example, define:
(i) Binary tree
(ii) Level of the binary tree
(iii) Complete binary tree
(iv) Degree of the tree (09 Marks)
b. Write the C routines to traverse the tree using:
(i) Pre-order traversal
(ii) Post-order traversal. (06 Marks)
c. For the 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. (05 Marks)
OR
8 a. What is the advantage of the threaded binary tree over binary tree? Explain the construction
of threaded binary tree for 10, 20, 30, 40 and 50. (07 Marks)
b. Define expression tree. For a tree given in Fig.Q8(b) traverse the tree using in-order,
preorder and post-order traversals.
Fig.Q8(b) (07 Marks)
c. Construct a binary search tree by using the following in-order and preorder traversals:
Inorder : BCAEDGHFI
Preorder : ABCDEFGHI (06 Marks)
S OC:rt
? ? .
2 of 3
7
18CS32
Module-5
9 a. Define graph. For the given graph, show the adjacency matrix and adjacency list
representation of the graph [Ref. Fig.Q9(a)]
Fig.Q9(a) (05 Marks)
b. What are the methods used for traversing a graph? Explain any one with example and write
C function fig the same. (08 Marks)
c. Write a C function for insertion sort. Sort the following list using insertion sort:
50, 30, 10, 70, 40, 20, 60 (07 Marks)
OR
10 a. What is collision? What are the methods to resolve collision? Explain linear probing with an
example. (07 Marks)
b. Explain in detail about static and dynamic hashing. (06 Marks)
c. Briefly explain basic operations that can be performed on a file. Explain indexed sequential
file organization. (07 Marks)
3 of 3
FirstRanker.com - FirstRanker's Choice
This post was last modified on 02 March 2020