CS/BCA(A)/ODD/SEM-3/300071/2024-2025/I043
MAULANA ABUL KALAM AZAD UNIVERSITY OF TECHNOLOGY, WEST BENGAL
Paper Code : BCAC303 Data Structure and Algorithm
UPID : 300071
Time Allotted : 3 Hours Full Marks :70
The Figures in the margin indicate full marks.
Candidate are required to give their answers in their own words as far as practicable
Group-A (Very Short Answer Type Question)
1. Answer any ten of the following : [ 1 x 10 = 10 ]
(I) Which of the following c code is used to create new node?
a) ptr=(NODE*)malloc(sizeof(NODE));
b) ptr=(NODE*)malloc(NODE);
c) ptr=(NODE*)malloc(sizeof(NODE*));
d) ptr=(NODE)malloc(sizeof(NODE));
(II) The process of inserting an element in the stack is called
a) Enqueue
b) Insert
c) Push
d) Pop
(III) A dequeue operation removes an element
a) From the front of the queue
b) From any place in the queue
c) From the rear of the queue
d) None of above
(IV) In linked list each node contains minimum of two fields. One field is data field to store the data second field is?
a) Pointer to character
b) Pointer to integer
c) Pointer to node
d) Node
(V) If the height of a BST is h, the maximum no. of nodes possible in the tree is ------
a) 2 h-1 -1
b) 2 h -1
c) 2 h +1
d) 2 h-1 +1
(VI) The average time complexity of quick sort for sorting n numbers is
a) O(n2)
b) O(nlog2n)
c) O(n)
d) O(log2n)
(VII) What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
(VIII) What is the best-case time for binary search finding a single item in an array?
a) Quadratic time
b) Linear time
c) Logarithmic time
d) Constant time
(IX) If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will
they be removed?
a) ABCD
b) DCBA
1/2
c) DCAB
d) ABDC
(X) A threaded binary tree is a binary tree in which every node that does not have right child has a thread
to its
a) Pre-order successor
b) In-order successor
c) In-order predecessor
d) Post-order successor
(XI) Match the following:
(a) Completeness (i) How long does it take to find a solution
(b) Time Complexity (ii) How much memory is needed to perform the search.
(c) Space Complexity (iii) Is the strategy guaranteed to find the solution when there in one.
a) A-iii, B-ii, C-i
b) A-i, B-ii, C-iii
c) A-iii, B-i, C-ii
d) A-i, B-iii, C-ii
(XII) A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front
Group-B (Short Answer Type Question)
Answer any three of the following : [ 5 x 3 = 15 ]
2. Write an algorithm to count number of nodes in a binary search tree. [5]
3. What is Queue? What are the different types of queue? [5]
4. What is priority queue? What are their applications? [5]
5. Write an algorithm to transpose a given matrix. [5]
6. A binary tree has 9 nodes. The inorder and preorder traversal of the tree yields the following [5]
sequence of nodes:
Inorder : E A C K F H D B G
Preorder: F A E K C D H G B
Draw the binary tree.
Group-C (Long Answer Type Question)
Answer any three of the following : [ 15 x 3 = 45 ]
7. Write the recursive algorithm for preorder traversal in a tree . [8+7]
Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into initially empty AVL tree.
8. Write an algorithm for merge sort technique. Illustrate with an example. Give its complexity. [5+4+1
Illustrate the bubble sort algorithm on input [30,20,10,60,70,40]. Show the results at each step. +5]
9. What is meant by a double ended queue? Explain the different types of double ended queue. [ 2+3 +5+5
Write a function or an algorithm to implement insertion of a data in dequeue using ‘front’ pointer ]
delete a data in dequeue using ‘rear’ pointer.
10. What are the limitations of Recursion? Write an algorithm to find factorial of a number using [ 5 +5 +5 ]
recursion. Explain tail recursion with the help of a suitable example.
11. Create a binary search tree for the following sequence: [6+3+3
50, 20, 30, 60, 65, 55, 80, 15, 8, 35, 70 +3]
Write preorder, inorder and post-order traversal in the above tree.
*** END OF PAPER ***
2/2