Gateway Classes

B.TECH (III-SEM)
Theory Examination 2024-25
DATA STRUCTURES (BCS301)
Model Paper-1

Time: 3 Hours Total Marks: 70

SECTION A
1. Attempt all Sections. If require any missing data; then choose suitably. 2 x 7 = 14
a. Define best case, average case, and worst case for analyzing the complexity of an algorithm.
b. Write the conditions for empty and full circular queue.
c. Define priority queue and its uses.
d. What do you understand by tail recursion? Give one example of tail recursion.
e. Differentiate between linear and binary search.

f. Construct an expression tree for the following algebraic expression ∶ (a − b) / ((c ∗ d) + e)

g. How graph can be represented?

SECTION B

2. Attempt any three of the following: 7 x 3 = 21

a. Assume that the declaration of multi − dimensional arrays X and Y to be,
X (−2: 2, 2: 22)and Y (1: 8, −5: 5, −10: 5)
(i) Find the length of each dimension and the number of elements in X and Y.
(ii) Find the address of element Y (2, 2, 3), assuming the Base address of Y = 400 and each element
occupies 4 memory locations.
b. Differentiate between iteration and recursion. Write a recursive function to print the first n terms of the
Fibonacci series.
c. Write an algorithm for Quick Sort. Use the Quick sort algorithm to sort the following elements: 2, 8, 7, 1,
3, 5, 6, 4
d. The order of nodes of a binary tree in inorder and postorder traversal are as follows:
In order ∶ B, I, D, A, C, G, E, H, F.
Post order: I, D, B, G, C, H, F, E, A.
(i) Draw the corresponding binary tree.
(ii) Write the pre − order traversal of the same tree.
 Gateway Classes
𝒆. Write the Dijkstra algorithm for shortest path in a graph and also find the shortest path from ‘S’ to all
remaining vertices of graph in the following graph:

SECTION C
3. Attempt any one part of the following: 7x1=7

𝒂. How to represent the polynomial using a linked list? Write a C program to add two polynomials using
a linked list.
𝐛. Discuss the doubly linked list. Write an algorithm to insert a node after a given node in the singly linked
list.
4. Attempt any one part of the following: 7x1=7
a. Write an algorithm for converting infix expressions into postfix expressions. Trace your algorithm for
infix expression Q into its equivalent postfix expression P, Q: A + ( B * C – ( D / E ^ F) * G ) * H
b. What is a circular Queue? Write a C code to insert an element in the circular queue.

5. Attempt any one part of the following: 7x1=7

a. Write algorithm of insertion sort. Implement the same on the following numbers and also calculate the
time complexity: 8, 3, 6, 9, 19, 30

b. Explain hashing and various collision resolution techniques with examples.

6. Attempt any one part of the following: 7x1=7

a. Explain the Huffman tree. Create a Huffman tree from the following data and their frequency of
occurrence.

Data: A B C D E F G H
Frequency: 22 5 11 19 2 11 25 5

b. What is a B-Tree? Write the various properties of B- Tree. Show the results of inserting the keys F, S, Q,
K, C, L, H, T, V, W, M, R, N, P, A, B in order into an empty B-Tree of order 5.
 Gateway Classes
7. Attempt any one part of the following: 7 x 1 =7
a. Apply the Kruskal algorithm to calculate the cost of the minimum spanning tree for the below
graph.

b. Differentiate between DFS and BFS. Draw the breadth − first tree for the following graph:
 Gateway Classes
B.TECH – (III-SEM)
Theory Examination 2024-25
DATA STRUCTURES (BCS301)
Model Paper-2
Time: 3 Hours Total Marks: 70
SECTION A
1. Attempt all Sections. If require any missing data; then choose suitably 2 x 7 = 14
a. What is the sparse matrix? How can you represent a sparse matrix in memory?
b. Explain Tail recursion.
c. Define priority queue. Give one application of priority queue.
d. Explain indexed sequential searching.
e. Define extended binary tree, full binary tree, strictly binary tree, and complete binary
tree.
f. In a complete binary tree if the number of nodes is 1000000. What will be the height of the complete
binary tree?

g. Define the transitive closure of a graph. Find the

transitive closure of the following graph: -

SECTION B
2. Attempt any three of the following: 7 x 3 = 21
a. Write a program in c to delete a particular element in the single linked list. A doubly linked list takes

more space than a single linked list for storing one extra address. Under what conditions, could a
double − linked list be more beneficial than a single − linked list?
b. Write algorithm for Push and Pop operations in the stack. Transform the following expression into
its equivalent postfix expression using stack: A + (B * C − (D / E ↑ F) * G) * H
c. Write an algorithm for Heap Sort. Use the Heap sort algorithm to sort the following elements: 2, 8, 7, 1,
3, 5, 6, 4.

d. Write the advantages of AVL tree over Binary Search Tree(BST). Insert the following sequence of
elements into an AVL tree- 7, 4, 9, 6, 30, 4, 8, 5, 3

e. Find the minimum spanning tree in the following graph using Kruskal's algorithm:
 Gateway Classes

SECTION C
3. Attempt any one part of the following: 7x1=7
a. Define the Time and Space Complexity of an algorithm. Explain the role of Asymptotic notations in
determining the complexity of the Algorithm.
𝒃. How to represent the polynomial using a linked list? Write a C program to add two polynomials using
a linked list.
4. Attempt any one part of the following: 7x1=7

a. Explain circular queue. Write an algorithm to insert an item and delete an item from the Circular
queue.

b. Differentiate between iteration and recursion. Write a recursive function to print the first n
terms of the Fibonacci series.
5. Attempt any one part of the following: 7x1=7
a. Why is quick sort named as quick? Show the steps of quick sort on the following set of
elements: 25, 57, 48, 37, 12, 92, 86, 33 Assume the first element of the list to be the pivot
element.
𝐛. What is hashing? Give the characteristics of the hash function. Explain the collision
resolution technique in hashing.

6. Attempt any one part of the following: 7x1=7

a. Explain all Steps used to build Huffman Tree where the following characters are given with their
frequencies ∶
a: 5, b: 9, c: 12, d: 13. e: 16, f: 45
b. What is a B-Tree? Generate a B-Tree of order 4 with the alphabet (letters) arriving in the
sequence as follows:
agfbkdhmjesIrxclntup
 Gateway Classes
7. Attempt any one part of the following: 7x1=7
𝐚. Describe the Dijkstra algorithm to find the shortest path. Find the shortest path in the
following graph with vertex 'S" as the source vertex.

𝐛. Write and explain the Floyd Warshall algorithm to find the all − pair shortest path. Use the Floyd
Warshall algorithm to find the shortest path among all the vertices in the given graph ∶