Data Structures & Algorithms — CACS201 (3rd Sem)

i. . ° ° am wf ae Tribhuvan University TN , i : XO Sy Faculty of Humanities & Social Sciences SAE Se OFFICE OF THE DEAN Y 2021 Bachelor in Computer Applications Full Marks: 60 Course Title: Data Structures & Algorithms Pass Marks: 24 Code No: CACS201 Time: 3 hours Semester: III : Batch: 2020 Candidates are required to answer the questions in their own words as far as possible. Group B Attempt any SIX questions. [6x5 = 30} : 2- What is abstract data type? convert a$b*c-d+e/f/(gth) into postfix expression using stack. [1+4] 3: What is linked list? Describe types of linked list. Write an algorithm to insert and delete node from beginning of doubly linked list. [1+4] 4. Describe Prim's algorithm to solve MST problem with suitable illustration. [5] Se What is the limitation of linear queue over circular queue? Write an algorithm to insert and delete node in circular queue. [1+4] £&< What is hashing? Describe the types of collision resolution techniques with suitable example. [1+4] GH Define divide and conquer algorithm. What is binary search? Write an algorithm to search an item using binary search with suitable illustration. [1+1+3] & What is minimax algorithm? Create Huffman Tree and calculate Huffman code for the following characters along with their frequencies using Huffman algorithm. [1+4] iChaaaees ANNE 1 ee RA LO SS eS EL LORE ha15 4 | 13 J Group C Attempt any TWO questions. [2x10 = 20} 2 What is stack? List the application of the stack. Write an algorithm to perform PUSH and POP operation in stack. Describe linked list implementation of stack operations. [1+2+3+4] 10. What is external sorting? Explain heap sort algorithm and trace it to sort the data: 8-90-16, 12.15.77, 5; 23,25, 32 Jk Differentiate between BST and AVL tree. Given the following AVL Tree: . _fa)-Draw the resulting BST after 5 is removed, but before any rebalancing takes place. Label each node in the resulting tree with its balance factor. Replace a node with both children using an appropriate value from the node's left child. (Que rebalance the tree that results from (a). Draw a new tree for each rotation that =F occurs when rebalancing the AVL Tree. [2+4+4]