Data Structures And Algorithms Past Paper PDF BT-3/D-22 PC-CS-201A

## Data Structures And Algorithms ### **BT-3/D-22** ### **PC-CS-201A** **Roll No. .............................................. Total Pages: 03** **43139** **Time: Three Hours] [Maximum Marks: 75** **Note:** Attempt Five questions in all, selecting at least one question from each Unit. All ques...

## Data Structures And Algorithms ### **BT-3/D-22** ### **PC-CS-201A** **Roll No. .............................................. Total Pages: 03** **43139** **Time: Three Hours] [Maximum Marks: 75** **Note:** Attempt Five questions in all, selecting at least one question from each Unit. All questions carry equal marks. ### **Unit I** * **1.** Differentiate between different Dynamic memory allocation methods used in C. Explain the problems associated with these methods and how to overcome those problems. Also, implement a C program to store and display record of an Employee dynamically and the record contains Name, age and ID. **15** * **2.** Answer the following questions related with sorting and searching : * **(a)** Write down the pseudo code of Insertion sort and compute the time complexity of insertion sort in all the three cases i.e. worst case, average case and best case. **8** * **(b)** Explain step by step how to perform searching with Binary search if given data is : 15, 23, 45, 66, 78, 99, 125, 150, 266, 280 and searched item in the given array is 150. **7** ### **Unit II** * **3.** Consider the following arithmetic expression X, written in Infix notation. Translate X, into its equivalent Postfix expression with the help of Infix to Postfix expression algorithm : * X: K + L - M * N + (O ^ P) * W / U / V * T + Q * Also, discuss the advantages of Postfix and Prefix expressions over Infix expression. **15** * **4.** Discuss the difference between simple queue and circular queue. Also, consider any array and write the pseudo code for how elements are enqueued and dequeued from the circular queue along with their overflow and underflow conditions. **15** ### **Unit III** * **5.** What is linked list? Why do you add header node in the linked list? Also define circular linked list and write a function of how to add an element at the specified position and at the end of the circular linked list. **15** * **6.** * **(a)** What is the difference between singly linked list and doubly linked list? Also discuss pros and cons of these. **8** * **(b)** Write an algorithm to construct a simple linked list with 5 nodes and print the content of linked list starting from the given node. **7** ### **Unit IV** * **7.** What is Balanced Multiway Search Tree? Explain its construction and applications. Consider a graph with five vertices and six edges, then explain how to find out Minimum Spanning Tree (MST). Also explain Warshal's algorithm. **15** * **8.** What is AVL tree? Explain its need. With input data 125, 112, 117, 130, 15, 69, 115, 114, 137, 127, 140, 129, 128 depict step by step construction of an AVL Tree. Also, delete 140, 129, 128 from the AVL tree and draw the final one after deletion. **15** **L-43139 2** **L-43139 3 1,200**