MAULANA ABUL KALAM AZAD UNIVERSITY OF TECHNOLOGY, WEST BENGAL BCA 3rd Semester Data Structures and Algorithms Exam 2023-2024 PDF

# Maulana Abul Kalam Azad University of Technology, West Bengal ## CS/BCA(A)/ODD/SEM-3/300071/2023-2024/1031 **Paper Code:** BCAC303 Data Structure and Algorithm **UPID:** 300071 **Time Allotted:** 3 Hours **Full Marks:** 70 ## Group-A (Very Short Answer Type Question) **1. Answer any ten of the fo...

# Maulana Abul Kalam Azad University of Technology, West Bengal ## CS/BCA(A)/ODD/SEM-3/300071/2023-2024/1031 **Paper Code:** BCAC303 Data Structure and Algorithm **UPID:** 300071 **Time Allotted:** 3 Hours **Full Marks:** 70 ## Group-A (Very Short Answer Type Question) **1. Answer any ten of the following:** [1 * 10=10] (i) Recursion is a method in which the solution of a problem depends on a) larger instances of different problems b) larger instances of the same problem c) smaller instances of the same problem d) smaller instances of different problems (ii) The number of nodes in a full binary tree at level 'L' is (Level starts with 0) a) 2 b) $2^{L-1}$ c) $2^{L+1} - 1$ d) $2^{L} - 1$ (iii) Which of the following data structure is more appropriate for implementing quick sort iteratively? a) Deque b) Queue c) Stack d) Priority queue (iv) The goal of hashing is to produce a search that takes a) O(1) time b) O(n²)time c) O(log n) time d) O(n log n) time (v) **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 is 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 (vi) Which of the following data structure is linear type? a) Array b) Tree c) Graphs d) Hierarchy (vii) With an array-based stack, the algorithm for push is a) increment top and add item to the new top location. b) add item to the top location and then increment top. c) return the top item and increment top. d) return the top item and decrement top. (viii) Which of the following data structure permits insertion and deletion operations only on one end of the structure? a) Linked list. b) Array c) Stack d) Queue (ix) Which of the following principle does queue use? a) LIFO b) FIFO c) Both of a & b d) None of the above (x) What is a hash function? a) A function has allocated memory to keys... b) A function that computes the location of the key in the array. c) A function that creates an array. d) A function that computes the location of the values in the array. (xi) A binary tree is created with 13 nodes. What is the minimum possible height of the tree? a) 13 b) -1 c) 4 d) None of these. (xii) Time complexity of bubble sort in best case is a) O(n) b) O(nlogn) c) O(n²) d) O(n(logn)²) ## Group-B (Short Answer Type Question) **Answer any three of the following:** [5 * 3 = 15] 2. Differentiate between Linear and Non-Linear data structure. 3. Differentiate between row major and column major array index notation. How is index calculated in both. 4. Write a program in C to insert an elements (new node) in a singly linked list at the third position from the start node. 5. a) Write an algorithm for evaluating a postfix expression. b) Evaluate the following postfix expression using the algorithm AB+CD/AD-EA^ +*, where A=2, B=7, C=9, D=3, E=5. 6. Consider a circular queue represented using a circular array of size n. Write conditions to check underflow and overflow for this circular array. ## Group-C (Long Answer Type Question) **Answer any three of the following:** [15 * 3 = 45] 7. Write a function or an algorithm to push and pop elements in a stack. Explain the application of stack? Evaluate the following postfix expression using stack showing position of stack after each step. 5 6 2 + * 1 2 4 / - [3 + 3 + 3 + 6] 8. Differentiate between static & dynamic memory allocation. What is a sparse matrix? Write an algorithm to add two polynomials. [5 + 3 + 7] 9. Explain a Doubly Linked List with proper example. Write an algorithm to insert and delete a node in Doubly Linked List. [5 + 5 + 5] 10. What is a stack? How it is different from queue? Write an algorithm to implement stack using linked list. Convert the following infix expression to postfix form using stack: (Describe the stack at every stage) (A + B * C) / (D - E) + F [2 + 3 + 5 + 5] 11. Write an algorithm for quick sort technique. Illustrate with an example. Give its complexity.: Write algorithm or a function for Insertion sort. [6 + 4 + 1 + 4] *** END OF PAPER ***