Principles of Data Structures — Major (End Semester) 2024 question paper

Paper details

• Subject: Principles of Data Structures (BCS-214)
• Branch: Computer Science and Engineering
• Semester: 3
• Exam: Major (End Semester) 2024
• Questions: 25

Questions asked in Principles of Data Structures Major (End Semester) 2024

1. Q1(a). Write a function in C to reverse the elements of a linked list. [2 marks]
2. Q1(a). Suppose that there is an array A[LB_1,UB_1] [LB_2,UB_2] [LB_3,UB_3] [LB_4,UB_4] [LB_5,UB_5] [LB_6,UB_6] where LB_1 denotes the sixth dimension while LB_6 denotes the first dimension then find out the formula to find the address of element A[i][j][k][l][m][n] if the base address of array is BA and size of element is w in row major order. The row of matrices is stored in reverse order like last… [3 marks]
3. Q1(b). Given an array, arr[1:9][-4:1][5:10] with a base value of 400 and the size of each element is 2 Bytes in memory find the address of element arr[5][-1][8] with the help of row-major order and column major order. [2 marks]
4. Q1(b). Find out the values of following postfix expression using stack: 23 - 4 + 567 * + * [2 marks]
5. Q1(c). Find out the transformation function to store the below sparse matrix into a linear array: [[1, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0], [1, 1, 1, 1]] [2 marks]
6. Q1(c). Given two sorted linked lists consisting of N and M nodes respectively. Write a program in C to merge both of the lists (in place) and return the head of the merged list. Input a: 5->10->15, b: 2->3->20. Output: 2->3->5->10->15->20. [2 marks]
7. Q1(d). Write a function in C to implement deque operation of the queue. [2 marks]
8. Q1(e). Write a function in C to implement left rotation of a binary tree. [2 marks]
9. Q1(f). Write a function in C to find the sum of value of all the nodes of a binary tree. [2 marks]
10. Q1(g). Write a function in C to implement the merge sort. [2 marks]
11. Q2(a). Given a linked list and a value x, Write a Program in C to partition it such that all nodes less than x come first, then all nodes with a value equal to x, and finally nodes with a value greater than x. The original relative order of the nodes in each of the three partitions should be preserved. Input: 1 -> 4 -> 3 -> 2 -> 5 -> 2 -> 3, x = 3. Output: 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 5. [3 marks]
12. Q2(a). Write a function in C to reverse the elements of a stack. [5 marks]
13. Q2(b). Given two singly linked lists that merge into a single Y-shaped list. The two lists initially have distinct paths but eventually converge at a common node, forming a Y-shape. Write a program in C with time complexity O(n) to find and return the node where the two lists merge. [2 marks]
14. Q2(b). Write the algorithm to convert an infix expression into postfix expression using stack. Convert the following infix expression into postfix expression using stack: (a+b*c-d-f)*(i+j/k/l+m-n)+p-q/r [5 marks]
15. Q2(c). Write a function in C to implement modified binary search algorithm where random index is chosen to divide the array instead of mid index. [5 marks]
16. Q2(c). Given an array A consisting of only 0s, 1s, and 2s. Write a program in C to sort the array, i.e., put all 0s first, then all 1s and all 2s in last. [2 marks]
17. Q3(a). Write a function in C to delete a node with given value from the singly linked list. [5 marks]
18. Q3(b). Write a function in C to implement the deque and enqueue operation of queue implemented using the stack. Also discuss its time complexity. [5 marks]
19. Q3(c). Given a linked list where in addition to the next pointer, each node has a child pointer, which may or may not point to a separate list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. Write a function in C to flatten the list so that all the nodes appear in a single-level linked list in a way that all nodes at the first level… [5 marks]
20. Q4(a). Consider the modified Post Order traversal of binary tree which traverses right subtree then it prints the node and finally it traverses left subtree. Write a function in C to implement the above modified Post Order traversal without recursion. Example traversal: 7, 3, 6, 1, 5, 2, 4. [5 marks]
21. Q4(b). Write the C function to find the unbalance node of an AVL tree after insertion of a node into existing AVL tree. Consider a modified AVL which allows balance factor from -2 to +3. Draw the modified AVL by inserting following values: 78, 45, 55, 1, 2, 3, 90, 80, 84, 100, 99, 98. Also, delete the following nodes: 100, 80, 90, 3, 1. [5 marks]
22. Q4(c). Write a function in C to implement deletion of node with unique value from modified binary search tree. The modified binary search tree is a tree where the left child containing values greater than the parent node and the right child containing values lesser than the parent node. [5 marks]
23. Q5(a). Write a function in C to implement the quick sort. Also discuss the effect of choosing the pivot element randomly, first element, last element and mid element on time complexity of quick sort. [5 marks]
24. Q5(b). Write a function in C to implement Kruskal Algorithm to find the minimum cost spanning tree. Also find the minimum cost spanning tree of following graph using Prim's Algorithm. (Refer to graph with vertices A, B, C, D, E, F, G). [5 marks]
25. Q5(c). Write a function in C to implement the Breadth First Search (BFS) traversal of a graph. Find out the BFS traversal of following graph. (Refer to graph with 10 nodes). [5 marks]