Download VTU BE 2020 Jan CSE Question Paper 18 Scheme 3rd Sem 18CS32 Data Structures and Applications

USN
t
LCBRARY\
k C 18CS32
Third Semester B.E. Degree Examination, Dec.2401ii.2020

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

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

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

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.

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

-.
(10 Marks)
,.. ?)
c. Define pointers. How to declare and initialize pointers, explain with example. (05 Marks) .....
ti)

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

1, ..?,
ct ?
a. =
:-.- OR
...., ,

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

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)

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

-.:, --t-
c. Write a C program to:
( i) Comparing strings
- =
a

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

-
(ii) Concatenate two strings (06 Marks)
:-. -,-
-..,'
,

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

c,
Module-2 - --
un . .?.
E 0- 3 a. Define stack. Give the implementation of push, pop and display functions. Include check for
t., .

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

c
Tc t empty and full conditions. (07 Marks)
-
o -d
ti) c b. Write the postfix form of the following expressions using stack:

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

o c,. .,
? -u .5
(i) A S B * C - D + EIF1(G + H)
.- . .. .-i
.

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

..,
(ii) A - B1(C * D S E)
. - 5 . ,
(06 Marks)

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

?, -- 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 ,?

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

. c._ (07 Marks)
E c-
o c
3

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

o ,2-
OR
4 a. Define recursion. Write a recursive functions for the following:
(i) Factorial of a number
(ii) Tower of Hanoi

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

._.
(07 Marks)
b. What is the advantage of circular queue over ordinary queue? Write a C program to simulate
c
', -

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

the working of circular queue of integers using array. Provide the following operations:
-6- I- ' -
0
, - ,
(i) Insert

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

P
(ii) Delete r-
0 ?
(iii) Display
r.;

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

_
(08 Marks)
c. Write a note on Dequeue and priority queue.
a.)
(05 Marks)

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

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

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

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

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

t
LCBRARY\
k C 18CS32
Third Semester B.E. Degree Examination, Dec.2401ii.2020
Data Structures and Applications

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

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)

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

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

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

(10 Marks)
,.. ?)
c. Define pointers. How to declare and initialize pointers, explain with example. (05 Marks) .....
ti)
1, ..?,

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

ct ?
a. =
:-.- OR
...., ,
2 a. D5plain dynamic memory allocation functions in detail. (06 Marks)

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

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-

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

c. Write a C program to:
( i) Comparing strings
- =
a
-

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

(ii) Concatenate two strings (06 Marks)
:-. -,-
-..,'
,
c,

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

Module-2 - --
un . .?.
E 0- 3 a. Define stack. Give the implementation of push, pop and display functions. Include check for
t., .
c

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

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

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

? -u .5
(i) A S B * C - D + EIF1(G + H)
.- . .. .-i
.

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

..,
(ii) A - B1(C * D S E)
. - 5 . ,
(06 Marks)
?, -- c.

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

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)

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

E c-
o c
3

o ,2-

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

OR
4 a. Define recursion. Write a recursive functions for the following:
(i) Factorial of a number
(ii) Tower of Hanoi
._.

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

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

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

-6- I- ' -
0
, - ,
(i) Insert
P

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

(ii) Delete r-
0 ?
(iii) Display
r.;
_

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

(08 Marks)
c. Write a note on Dequeue and priority queue.
a.)
(05 Marks)
'a Module-3

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

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

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

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

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

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

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

0 0 0
(04 Marks)

c. Write a C function to add two-polynomials represented as circular list with header node.
(08 Marks)

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

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

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

(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

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

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,

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

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)

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

S OC:rt
? ? .
2 of 3
FirstRanker.com - FirstRanker's Choice
USN

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

t
LCBRARY\
k C 18CS32
Third Semester B.E. Degree Examination, Dec.2401ii.2020
Data Structures and Applications

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

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)

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

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

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

(10 Marks)
,.. ?)
c. Define pointers. How to declare and initialize pointers, explain with example. (05 Marks) .....
ti)
1, ..?,

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

ct ?
a. =
:-.- OR
...., ,
2 a. D5plain dynamic memory allocation functions in detail. (06 Marks)

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

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-

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

c. Write a C program to:
( i) Comparing strings
- =
a
-

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

(ii) Concatenate two strings (06 Marks)
:-. -,-
-..,'
,
c,

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

Module-2 - --
un . .?.
E 0- 3 a. Define stack. Give the implementation of push, pop and display functions. Include check for
t., .
c

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

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

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

? -u .5
(i) A S B * C - D + EIF1(G + H)
.- . .. .-i
.

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

..,
(ii) A - B1(C * D S E)
. - 5 . ,
(06 Marks)
?, -- c.

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

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)

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

E c-
o c
3

o ,2-

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

OR
4 a. Define recursion. Write a recursive functions for the following:
(i) Factorial of a number
(ii) Tower of Hanoi
._.

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

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

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

-6- I- ' -
0
, - ,
(i) Insert
P

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

(ii) Delete r-
0 ?
(iii) Display
r.;
_

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

(08 Marks)
c. Write a note on Dequeue and priority queue.
a.)
(05 Marks)
'a Module-3

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

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

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

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

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

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

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

0 0 0
(04 Marks)

c. Write a C function to add two-polynomials represented as circular list with header node.
(08 Marks)

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

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

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

(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

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

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,

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

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)

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

S OC:rt
? ? .
2 of 3
7
18CS32

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

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

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

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

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

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

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

FirstRanker.com - FirstRanker's Choice