ALCCS

Code: CS21                                    Subject: DATA STRUCTURES & ALGORITHM DESIGN

Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE:  

· Question 1 is compulsory and carries 28 marks. Answer any FOUR questions from the rest.  Marks are indicated against each question.

· Parts of a question should be answered at the same place.

Q.1      a. Differentiate between best, average, and worst case complexities.

b. Derive the equation for computing the address of the memory location of an element stored in a two-dimensional array.

             c.  How does doubly linked list differ from singly linked list?

             d.  Convert the following infix expression into postfix expression

                               A+B*C-D/A*F

             e.  Differentiate between Stack and Queue data structure.

             f.   Compute minimum height of binary tree of n nodes

             g. Make a complete graph of 4 vertices and compute adjacency matrix for it.              (7  4)

Q.2       a. Differentiate between big-O, Ω, and θ notations used to specify algorithmic complexity.     

             b.  Obtain the values of c and n₀ for the following.                                                                  

             c.  Show which of the following function grows faster? Also define the order.

(6+6+6)

Q.3     a.  Assume that a lower triangular matrix  is stored in a linear array  in lexicographical order. If  is stored in , where is  stored in array B for n=100?           

             b.  What are the advantages of circular linked list over linked list?                                           

             c.  Write an algorithm for binary search method. Also derive its time complexity.         (6+6+6)

  Q.4     a.  Show the outcome of different passes for sorting the following sequence of data using quick sort algorithm. 

                                        25, 57, 48, 37, 12, 92, 86, 33

             b.  Show the step to evaluate the following expression using a stack. Also compute the final value for A=8, B=2, C=3, D=1,E=4.                                                                                                               

             c.  Construct AVL tree for the following set of data for the months of year based on their lexicographical order. Initial order of the month is as occur from January to December.                            (6+6+6)

Q.5     a.  In a circular queue show the conditions that differentiate between empty queue and full queue.          Also explain the disadvantages of implementing queue (non circular) using array.                        

             b.  Construct a binary tree for the following preorder and inorder traversal sequences.            

                  Preorder: ABCDEFGHIJKLMPRQNO

                  Inorder:   BDEFCAIJKHGRPQMNOL

             c.  Delete 14 from the following B-Tree of order 5. Show all the steps of deletion. In the figure, children of the node(100, 120) are not shown since it does not affect the deletion.                        (6+6+6)

Q.6     a.  What is linked representation of a graph? Explain with the help of an example. Also write its advantages over other representations of graph.                                                                                          

             b.  Define a connected graph. For a connected graph of n vertices, how many minimum and how many maximum edges should be in the graph? Prove it.                                                                              

c.  Write Kruskal algorithm to find a minimum spanning tree of a Graph.                     (6+6+6)

Q.7       a.  What is Garbage? Write advantages of best-fit and worst-fit memory allocation methods.  

             b.  Write an algorithm that reverses a given string of length n.                                                  

c.  Write an algorithm that adds two polynomials of degree n and m.                          (6+6+6)