SKR Engineering College Department Of Computer Science & Engineering Model Question Paper CS 1151 – Data Structures PART-A 2*10=20 1. Give the prefix form of infix expression (A*B+(C/D))-E 2. State the properties of binary tree 3. What is the time complexity of insertion sort? 4. Compare linear and binary search 5. What are the factors to be considered while choosing a sorting technique? 6. What is NP complete problem? 7. Write the average and best case analysis of heap sort 8. What is AVL tree? 9. What is dequeue? 10. Define terminal node, degree of a node, sibling, depth of a node PART-B 5*16=80 11.a(i) Write an algorithm to perform matrix multiplication and analyze the same. (6) (ii) Explain the complete Merge sort algorithm. Sort the following set of numbers Using Merge sort algorithm (10) (OR) b(i) Explain the concept of Top-down approach (ii) Describe the various operations of Stack. List its applications 12 a(i) Explain the operation of AVL tree (ii) Write a procedure for the following Linked list operation Inserting a new node at the end Deleting a node from the beginning (OR) b(i) Trace the quick sort algorithm for the following list of numbers 86,55,75,32,58,89,90 (ii) Explain the preorder and post order traversal of a binary tree (8) 13 a(i) Explain the Dijikstra’s algorithm with an example (ii) Explain the topological sorting algorithm (8) (8) (8) (8) (8) (8) (OR) b(i)Explain in detail the types of analysis that can be performed on an algorithm (8) (ii) What are strongly connected components? Explain (iii) Distinguish internal and external sorting (6) (2) 14 a(i) Write an algorithm to find the shortest path between any two nodes in a graph using Dijikstra’s algorithm (10) (ii) Define and explain Quick sort (6) (OR) b Write down the merge sort algorithm and give its worst case, best case and Average case analysis (16) 15(a) Show the heap sort processes the input 12,56,89,41,23,45,65,78,2,69,35,49 (16) (OR) b(i) Write down the procedure to convert an infix expression a+b*c+(d*e+f)*g (12) (ii) Find the average search cost of the binary search algorithm (4) SKR Engineering College Department Of Computer Science & Engineering Model Question Paper CS 1151 – Data Structures PART-A 1. What is a graph? 2. What are the benefits of doubly linked list over singly linked list? 3. Define priority queue 4. How do you represent a graph in multi-list organization? 5. Write an algorithm for fibonacci series 6. What are the factor that is involved in radix sort? 7. Write the various types of control structures 8. Define complete binary tree 9. Explain Kruskal’s algorithm 10. What do you mean by Abstract Data Type? PART-B 16*5=80 2*10=20 11 a(i) Write algorithm to locate an element from binary search tree (6) (ii) Define an efficient representation of two STACKS in a given area of memory with ‘n’ words and explain (10) (OR) b(i) What are the different tree traversals? Explain with examples (8) (ii) Explain an algorithm to convert a hexadecimal to decimal representation (8) 12 a(i) Explain in detail about the operation of queue (ii) Describe the various hash functions (iii) Explain unweighted shortest path (OR) 12 b(i) What is biconnectivity (ii) Explain the prim’s algorithm with an example (4) (6) (6) (4) (6) (iii) Construct the heap for the following array structure 15 85 12 23 13 a(i) What are strongly connected components? Explain (ii) Explain the concept of Top-down approach (iii) Explain any one of the sorting techniques (OR) 60 (6) (6) (4) b(i) Explain how to modify Dijikstra’s algorithm to produce a count of the number of different minimum paths from v to w (8) (ii) Explain program verification with example (8) 14 a(i) Briefly explain the need of time complexity in an analysis of algorithms (4) (ii) Explain Topological Sorting with examples (4) (iii) How the efficiency of an algorithm is calculated. Explain it with an example (8) (OR) b(i) Given two sorted lists L1 and L2 write a procedure to compute L1 ∩ L2 using Only the basic operations 15 a(i) Explain the algorithm for insertion and deletion (ii) Devise an algorithm to evaluate the postfix expression (OR) b(i) Explain Separate chaining and Open addressing in detail (8) (ii) Write a procedure to sort the set of ‘n’ numbers using insertion sort algorithm (8) (8) (8)