BCS304

Model Question Paper-I with effect from 2023-24 (CBCS Scheme)

USN

Third Semester B.E. Degree Examination

Data Structures and Applications
TIME: 03 Hours Max. Marks: 100

Note: 01. Answer any FIVE full questions, choosing at least ONE question from each MODULE.

*Bloom’s
Module -1 Taxonomy Marks
Level
Q.01 a Define data structures. With a neat diagram, explain the classification of
L2 5
data structures with examples.
b What do you mean by pattern matching? Outline the Knuth Morris Pratt
(KMP) algorithm and illustrate it to find the occurrences of the following
pattern. L3 8
P: ABCDABD
S: ABC ABCDAB ABCDABCDABDE
c Write a program in C to implement push, pop and display operations for
L3 7
stacks using arrays.
OR
Q.02 a Explain in brief the different functions of dynamic memory allocation. L2 5
b Write functions in C for the following operations without using built-in
functions
i) Compare two strings. L3 8
ii) Concatenate two strings.
iii) Reverse a string
c Write a function to evaluate the postfix expression.
Illustrate the same for the given postfix expression: L3 7
ABC-D*+E$F+ and assume A=6, B=3, C=2, D=5, E=1 and F=7.
Module-2
Q. 03 a Develop a C program to implement insertion, deletion and display
L3 10
operations on Linear queue.
b Write a program in C to implement a stack of integers using a singly
L3 10
linked list.
OR
Q.04 a Write a C program to implement insertion, deletion and display operations
L3 10
on a circular queue.
b Write the C function to add two polynomials. Show the linked
representation of the below two polynomials and their addition using a
circular singly linked list
P1: 5x3 + 4x2 +7x + 3 L3 10
P2: 6x2 + 5
Output: add the above two polynomials and represent them using the
linked list.

Page 01 of 03
 BCS304
Module-3
Q. 05 a Write recursive C functions for inorder, preorder and postorder traversals
of a binary tree. Also, find all the traversals for the given tree.

L3 8

b Write C functions for the following

i) Search an element in the singly linked list. L2 6
ii) Concatenation of two singly linked list
c Define Sparse matrix. For the given sparse matrix, give the linked list
representation:

L3 6

OR
Q. 06 a Write C Functions for the following
i) Inserting a node at the beginning of a Doubly linked list L3 8
Deleting a node at the end of the Doubly linked list
b Define Binary tree. Explain the representation of a binary tree with a
L2 6
suitable example.
c Define the Threaded binary tree. Construct Threaded binary for the
L3 6
following elements: A, B, C, D, E, F, G, H, I
Module-4
Q. 07 a Design an algorithm to traverse a graph using Depth First Search (DFS).
Apply DFS for the graph given below.

L3 8

b Construct a binary tree from the Post-order and In-order sequence given
below
L2 6
In-order: GDHBAEICF
Post-order: GHDBIEFCA
c Define selection tree. Construct min winner tree for the runs of a game
given below. Each run consists of values of players. Find the first 5
winners.
10 9 20 6 8 9 90 17 L2 6
15 20 20 15 15 11 95 18
16 38 30 25 50 16 99 20
28

Page 02 of 03
 BCS304
OR
Q. 08 a Define Binary Search tree. Construct a binary search tree (BST) for the
following elements: 100, 85, 45, 55, 120, 20, 70, 90, 115, 65, 130, 145.
L3 8
Traverse using in-order, pre-order, and post-order traversal techniques.
Write recursive C functions for the same.
b Define Forest. Transform the given forest into a Binary tree and traverse
using inorder, preorder and postorder traversal.

L2 6

c Define the Disjoint set. Consider the tree created by the weighted union
function on the sequence of unions: union(0,1), union(2,3), union(4,5),
L2 6
union(6,7), union(0,2), union(4,6), and union(0,4). Process the simple
find and collapsing find on eight finds and compare which find is efficient.
Module-5
Q. 09 a What is chained hashing? Discuss its pros and cons. Construct the hash
table to insert the keys: 7, 24, 18, 52, 36, 54, 11, 23 in a chained hash table L3 10
of 9 memory locations. Use h(k) = k mod m.
b Define the leftist tree. Give its declaration in C. Check whether the given
binary tree is a leftist tree or not. Explain your answer.

L2 5

c What is dynamic hashing? Explain the following techniques with

examples:
L2 5
i) Dynamic hashing using directories
ii) Directory less dynamic hashing
OR
Q. 10 a What is a Priority queue? Demonstrate functions in C to implement the
Max Priority queue with an example.
i) Insert into the Max priority queue L3 10
ii) Delete into the Max priority queue
iii) Display Max priority queue
b Define min Leftist tree. Meld the given min leftist trees.

L2 5

c Define hashing. Explain different hashing functions with examples. L2 5

Discuss the properties of a good hash function.

Page 03 of 03