END TERM EXAMINATION |
|
| Third Semester[BTech] | Dec 2024 |
| Paper Code: CSIT-124 | Subject : Data Structure Using C |
| Time:3 Hour | Maximum Marks:60 |
| Note: Attempt all questions as directed. Internal Choice is indicated. | |
| SECTION-A | |
| Q1 Attempt any four of the following questions : (4*6=24) | |
| 1. Write an algorithm to merge two sorted array into single sorted array. | |
| 2. Convert infix expression to prefix expression. Also write complexity of algortithm
Infix : A + B * (C^D-E)^(F+G*H)-I |
|
| 3. Find the minimum spanning tree using the Kruskal algorithm?
|
|
| 4. What do you understand by Hashing? Discuss various hashing function with the help of example. What is the key property to define a good hash function? | |
| 5. Construct a binary tree having the following pre-order and in-order traversal sequence:
Inorder : B C A E G D H F I J Preorder : A B C D E G F H I J |
|
| SECTION-B (20 Marks) | |
| (Attempt any two questions out of three. Each question carries 10 marks) | |
| 6. Discuss left skewed and right skewed binary tree. How AVL trees are better than Binary Search Tree? Construct an AVL tree by inserting the following elements in the order of their occurrence : 21, 26, 30,9,4,14, 28,18,15,10,2,3,7. | |
| 7. (a) You are given a queue that can only support enqueue (insertion) and dequeue (removal) operations. The queue is implemented using two stacks : Stack1 and Stack2. Write an algorithm to perform the following operations:
i) enqueue(x) : Add element x in the end of the queue. ii) dequeue(x) : Remove the element from the front of the queue and return it. (6 Marks) |
|
| (b) Suppose multidimensional array B is declared using B(1:8, -5:5, -10:5). Consider the length of each dimension and the number of elements in B. Consider the element B[3,3,3] in B. Find the address of the element, assuming Base (B) =400 and there are w= 4 words per memory location. (4 marks) | |
| 8. (a) Given the following element, draw the heap: 52, 32, 42, 22, 12, 27, 37, 12, 7, 35, 24, 10. Which element is deleted when the delete algorithm is called twice? (6 Marks) | |
| (b) G is an undirected graph with vertex set (v1, v2, v3, v4, v5, v6, v7) and edge set ((v1,v2), (v1,v3), (v1,v4), (v2,v4), (v2,v5), (v3,v4), (v4,v5), (v4,v6), (v5,v6), (v6,v7)). Perform BFS with v1 as the root node. (4 marks) | |
| Section C (Compulsory) | |
| 9. You are developing a task management system for a project. The system needs to manage a list of tasks where each task has a unique identifier, a description, a priority level and a status (e.g. pending, in-progress, completed). The system should support the following operation efficiently :
You need to choose an appropriated data structure to implement the task management system. Write an algorithm to perform the following operations: (16 marks : 4 marks each task) a) Add task : Add a new task to the system. a) Deletion task : Remove an existing task based on its idenfier. a) Update task : Search and update the detail of an existing task. a) Add task : List all the task. |
|
