Name Subject Code: BCS301
Roll No.
SSLD VARSHNEY ENGINEERING COLLEGE (518), ALIGARH
PRE-UNIVERSITY EXAMINATION 2024-25
B.TECH IIND YEAR (CSE) Semester-III
DATA STRUCTURE
Time: 02:00 Hours Max.Marks:70
Note- Attempt all Questions and Draw a suitable diagram wherever required.
SECTION-A
1. Attempt All questions. 1x10=10
Qno. Question Marks CO
a. What is a sparse matrix? How is it stored in the memory of a computer? 1 1
Rank the following typical bounds in increasing order of growth rate: 1 1
b. O(log n), O(n 4 ), O(1), O(n 2 log n)
c. Convert the following arithmetic infix expression into its equivalent postfix 1 2
expression. (a + (b – c))* ((d – e)/(f + g – h))
d. Explain Tail recursion. 1 2
e. List the different types of representation of graphs. 1 4
f. Construct an expression tree for the following algebraic expression: 1 5
(5a-3b)^2*(3a+5b)^3
g. If the in order traversal of a binary tree is D, J, G, B, A, E, H, C, F, I and its 1 5
pre order traversal is A, B, D, G, J, C, E, H, F, I Determine the binary tree?
h What is collision and resolve collision techniques 1 3
I What is hash function and types of hash function 1 3
J Number of nodes in a complete tree is 100000. Find its depth 1 4
SECTION-B
2. Attempt any THREE questions of the following: 10x3=30
Q.no. Question Marks CO
th
a. Write a C program to insert a node at k position in single linked list. 10 1
b. Convert given infix expression to postfix expression using tabular method. 10 2
A^B-C^D*E$F+G/H-I+J
10 3
c. Explain Tower of Honoi problem and write a recursive algorithm to solve it.
d. Write an algorithm for Breadth First search (BFS) and explain with the help 10 4
of suitable example.
e. What is spanning tree? Write down the kruskal’s algorithm to obtain 10 5
minimum cost spanning tree. Use kruskal’s algorithm to find the minimum
cost spanning tree in the following graph:
SECTION-C
3. Attempt any ONE question of the following: 10x1=10
Qno. Question Marks CO
a. Assume that the declaration of multi-dimensional arrays X and Y to be, 10 1
X (-2:2, 2:22) and Y (1:8, -5:5, -10:5)
(i) Find the length of each dimension and number of elements in X and
Y.
(ii) Find the address of element Y (2, 2, 3), assuming Base address of
Y = 400 and each element occupies 4 memory locations
b. What is Recursion? Write a C program to calculate factorial of number 10 2
using recursive and non- recursive.
4. Attempt any ONE question of the following: 10x1=10
a. (i) Use the merge sort algorithm to sort the following elements in 10 3
ascending order.13, 16, 10, 11, 4, 12, 6, 7.What is the time and space
complexity of merge sort?
(ii) Use quick sort algorithm to sort 15,22,30,10,15,64,1,3,9,2. Is it a
stable sorting algorithm? Justify
b. Show the results of inserting the keys F, S, Q, K ,C, L, H, T, V, W, M, R, 10 4
N, P, A, B in order into a empty B-Tree of order 5
5. Attempt any ONE question of the following: 10x1=10
a. Write the Dijkstra algorithm for shortest path in a graph and also find the 10 5
shortest path from ‘S’ to all remaining vertices of graph in the following
graph.
b. Apply the Floyd warshall’s algorithm in above mentioned graph 10 5
(i.e. in Q.no 5a)
