GITA AUTONOMOUS COLLEGE, BHUBANESWAR
(Affiliated to BPUT Odisha)
3rd Semester [Link] Regular / Back Examination 2023-24
Registration No.
Subject : Data Structure Using “C”
Subject Code : 22BTTES307
Branch : CSE, CST, CSIT, CSEAI, CSEDS, CSEAIML, CSEIOT
Time : 3 Hours Full Marks : 60
Instructions :
Answer question No. 1 (Part I) any ten out of 12 bits, from (Part II) any five out of 7 bits and any two
from (Part III) out of 4 bits.
The figures in the right hand side margin indicate marks
Part – I Marks
01 Short Answer Type Questions (Answer any ten out of twelve) (02 x 10) CO BL PO &
PSO
a) What do you understand by time and space complexity? Express the following 1 2 1,2
expression in BigOh notation: F(x)=5x2+5
b What is sparse matrix. Give an example. What are the disadvantages of 1 2 1, 2
) representing it in normal 2D array.
c) Evaluate the following postfix expression 2 3 1, 2
20 5 + 60 6 / * 4 –
d Explain overflow and underflow condition in circular queue ( using array). Write 2 2 1,3
) the conditions to check these.
e) What is Self-referential structure? Explain with an example 3 2 1,2,3
f) What the following C code will do? Assuming that curr holds address of first node 3 3 1,2,3
of a singly linked list , n is an integer “next” is the link part of the node.
n=0;
while(curr!=NULL)
{ n++;
curr=curr->next ; }
printf(“%d”,n);
g) Find the pre- order and post- order traversal of the given binary tree 4 2 1,3
A
B C
G
D F
E
H
h Represent the following algebraic expression in expression tree 4 3 1,3
) [a + (b – c)] * [(d – e) / (f + g – h)].
i) For a list L = {9, 100, 4, 5, 7, 11}, show the output list at the end of first pass 5 3 1,2
and second pass using bubble sorting method.
Using the hash function ‘key mod 7’, insert the following sequence of keys in 5 3 1,2
j)
the hash table-50, 700, 76, 85, 92, 73,101 Use separate chaining technique for
collision resolution. Show the final hash table.
k Consider the following sequence of operations on an empty stack: push(54); 2 2 1,3
) push(52); pop(); push(55); push(62); s =pop();
Consider the following sequence of operations on an empty queue: Insert(21);
Insert (24); delete();Insert (28); Insert (32);
q = delete (); Find the value of s * q .
l) How many structurally different ( i.e unlabeled) binary trees are possible with 4 3 1,3
three nodes. Draw them.
Part – II Marks
02 Focussed – Short answer type Questions (Answer any five out of seven) (04 x CO BL PO &
PSO
05)
a) Write an algorithm/function to implement binary search. 1 3 1,2
Explain using binary search how to search 15 in the following list(array).
A[]={ 1,2,5,8,9,15,45}
b What is postfix expression? Using a stack to translate the following infix 2 3 1,3
) expression to postfix.
A+B-( C*D-E+F/G)+(H+I*J)
c) Write the required structure to represent a node of doubly linked list. Write an 3 3 1,2,3
algorithm to find largest data value present in a singly linked list.
d Construct the binary tree from the following traversals. 4 3 1,3
) Inorder : D, H, B, E, A, F, C, I, G, J
Postorder: H, D, E, B, F, I, J, G, C, A
After constructing the tree, represent it in a 1D array
e) What is binary search tree (BST) ? For the following given sequence 4 3 1,3
of numbers : 35 , 22 , 70 , 45 , 12 , 54 , 87 , 43 , 98 , 75
i) Construct Binary Search Tree (BST) by inserting the nodes sequentially.
ii) After constructing the BST delete the node 35.
f) Write the program to implement selection Sort 5 3 1,2,3
g) Write the algorithm/functions for insert and delete operations on linear 2 3 1,3
queue(implemented using array).
Part – III Marks
Long Answer type Questions (Answer any two out of four) (10 x 2) CO BL PO &
PSO
03 a) What is stack? Give a real life example of a stack. 4 2 2 1,3
b Write a menu driven program to implement PUSH, POP and DISPLAY 6 2 3 1,3
) operations on stack using array.
04 a) What do you understand by circular linked list. Write a program to create and 3 3 1,2,3
display a singly linked list. Insertion of nodes will continue as long as the
user wishes to do so. After insertion perform display operation.
b Write the adjacency matrix of the following graph and perform BFS 4 3 1,2,3
) traversal by considering start node as A .
05 a) What is an AVL tree? Discuss its properties. 4 2 1,3
b Construct an AVL tree by inserting the following elements into an empty 4 3 1,3
) AVL tree. 9,10,11,3,2,6,4,7,5,8,12,13
06 a) Write a program to implement Insertion sort algorithm. 5 2 1,2
b What is hashing? Briefly discuss the collision handling techniques in hashing. 5 2 1,2
)
NB : BL – Blooms Level 1, 2, 3, CO – Course Outcome, PO – Program Outcome, PSO – Program Specific
Outcome