Data Structures — DU B.Sc. (Prog) Physical Science courses pertaining to Computer Science Previous Year Question Papers

(c) Write a program to implement a Stack using a Linked List. Write the code for push and pop operations. (5) Non-Major, B.Sc. (Phy. Sc.)/ 4. Parts of a question must be answered together. for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { (b) Write any two real-life applications of queues. (c) Is an array that is in sorted order a Min-Heap? Explain using a suitable example. (3) (d) What is the role of Stack in the implementation of recursion with the help of a suitable example? (c) Show that : (5) 7n3+10n+50=0 (n3) and find the value of c and n0. 7. (a) Given the following Binary Search Tree: (5) Perform the following deletion operations : (i) Node with one child (70) (ii) Node with two children (50) Explain each case with the help of diagrams. (b) Explain the time complexity of the following basic operations in an array : (i) Access (iii) Insertion (5) List one advantage and one disadvantage of using arrays. 5. (a) Insert the following elements in an AVL tree: Show step-by-step insertion and imbalance, and also perform the required rotation. (5) (e) Differentiate between Linear and Non-Linear data structures. (3) (f) Draw a Binary Search Tree using the following key values : (3) (b) What is a Deque? Write a code snippet to delete an element from the front and rear of the (c) Write short notes on : (i) Binary Tree (g) Given the values of a=3, b=2, c=4, d=2; evaluate the following given postfix expression : Show the stack representation for the calculations. 6. (a) Define a Doubly Linked List. Explain its structure with a neat diagram. Also mention two advantages and disadvantages. (5) (h) Write a C++ programto insert an element at the front of a Singly Linked List. (5) (b) Perform the following stack operations (size = 5): push(10), push(20), pop(), push(5), push(15), push(25), pop(), push(30) Show the stack contents after each operation. (i) Perform Insertion sorton the array [8, 2, 1, 9, 3], and show the steps after each iteration. Also, report the number of comparisons. (5) 2. (a) Write a program for generating first 10 Fibonacci numbers using a recursive function. (5) (b) Write a program to implement a queue using arrays. Write code for insert and delete operations. (c) Solve the following recurrence relation using Master’s Theorem: (5) 3. (a) A binary tree T has 9 nodes. The Inorder and Postorder traversals yield the following : (5) Draw the Binary Tree and write the Preorder (b) Write a code snippet to delete a node from a Circular Linked List. Explain the steps using a suitable example. (5) (c) What is an AVL tree? Why is the AVL tree called a self-balancing tree? Explain LL rotation used for balancing. (5) 4. (a) Construct a max heap using the following array: (i) Build a heap using the bottom-up method (ii) Delete root and reheapify Show all the steps. (5) (b) Determine the number of nodes in a full Binary Tree of height 4. Calculate the number of leaf nodes. (5)