Code: AC06/AT06                                                                   Subject: DATA STRUCTURES &

                                                                                                                  ALGORITHM DESIGN

Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 9 Questions in all.

· Question 1 is compulsory and carries 20 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

· Any required data not explicitly given, may be suitably assumed and stated.

Q.1       Choose the correct or best alternative in the following:                       (2x10)

             a.  Which is better computing time (in analysis of algorithm)?

(A) O(n)                                               (B) O(2n)

(C) O(log2n)                                        (D) None of these

             b.  In 2D array char a[5][6] is stored at “1000”, in column-major manner. The address of a[i][j] would be 

(A) 1000 + i + j*5                                (B) 1000 + i*4 + j

(C) 1000 + i + j * 6                              (D) 1000 + i*6 + j

             c.  Which of the following is essential for converting an infix expression to the postfix expression efficiently?

(A) An operator stack                         

(B) An operand stack

(C) An operand stack and  operator stack

(D) A parse tree

             d. A dynamic data structure where we can search for desired records in O(log n) time is

(A) heap                                               (B) binary search tree

(C) circularly linked list                         (D) array

             e.  The inorder traversal of some binary tree produced the sequence CBDA, and the postorder traversal of the same tree produced the sequence CDBA. Which of the following statement is TRUE for the given tree?

(A) Left subtree is empty, and the total number of nodes in its right subtree is 3.

(B) Right subtree is empty, and the total number of nodes in its left subtree is 3.

(C) Both left subtree and right subtree must be nonempty

(D) None of the above

             f.   A threaded binary tree has the following problems.

(A) More time consuming tree traversal

(B) Nonsequential memory allocation

(C) Additional storage requirement

(D) None of these

             g.  The maximum possible height of an AVL tree with 7 nodes is :

(A) 3                                                    (B) 4

(C) 5                                                    (D) None of these

             h.  The best sorting technique when the data is almost sorted is:

(A) Selection sort                                 (B) Bubble sort

(C) Quick sort                                      (D) Insertion sort

             i.   Breadth first search:

(A) Scans all incident edges before moving to other vertex

(B) Scans adjacent unvisited vertex as soon as possible

(C) Is same as backtracking

(D) None of these

             j.   Which of the following is a hash function?

(A) Quadratic probing                          (B) Chaining

(C) Open addressing                            (D) Folding

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2    a.    Explain how an array can be used to represent polynomials. Represent the following polynomial in 3 different ways using arrays.

(6)

             b.    Write an algoritm to compute the sum of two polynomials represented this way. Show that if n and m are the number of terms in the polynomials, then finding the sum can be carried out in time O(n+m).           (10) (4)

   Q.3    a.    Write an algorithm to convert an infix expression to a postfix expression. Execute your algorithm with the following infix expression as your input

(8)

             b.    Sketch an algorithm to find the minimum and maximum elements from a set of n elements. Your algorithm should not take more than number of comparisons where n is an exact power of 2.      (8)

   Q.4    a.    Write an algorithm which takes a binary tree and swaps the left and right children of every node.              (8)

             b.    Give an O(n) time non-recursive procedure that reverses a singly linked list of n nodes. The procedure should use no more than constant storage beyond that needed for the list itself.                   (8)

   Q.5    a.    The Inorder and Pre-order traversals of a binary tree produces the following sequence.

                    Inorder:       D      B       F       E       G      H      I        A      C     

                    Pre-order:   A      B       D      E       F       G      H      I        C     

                    Construct the tree.                                                                                                      (6)

             b.    Consider a graph representing an airline’s network: each node represents an airport, and each edge represents the existence of a direct flight between two airports. Suppose that you are required to write a program that uses this graph to find a flight route from airport p to airport q. Would you use breadth-first search or depth-first search? Explain your answer.                                                       (4)

             c. Consider the following undirected graph.

                    Draw a DFS and BFS tree for the graph starting at node A. If several nodes can be chosen at some step, pick the vertex that is alphabetically first                                                                      (6)

   Q.6    a.    Define B-tree of order m [minimum degree m]? When is it preferred to use

B-trees?                                                                                                                     (4)

             b.    Write an algorithm to search a key in a B-tree? What is the worst case of searching in a B-tree? List the possible situations that can occur while inserting a key in a B-tree?                                                 (8)

             c.    Write an algorithm to count the number of internal nodes in a Binary Tree.                    (4)

   Q.7    a.    Suppose the characters 'a', 'b', 'c', 'd', 'e', 'f', 'g' are stored in a Binary Search Tree (BST). Draw a BST that is as tall as possible and contains these characters. Also draw a BST that is as short as possible and contains the characters 'a', ..., 'g'.                                                                                                    (8)

             b.    Ackermann’s function A(m,n) is defined as follows:

                    Write a recursive procedure for computing this function. Measure the time complexity of your procedure.           (8)

Q.8    a.    Consider inserting keys 20, 44, 62, 8, 30, 56, 34, 176, 118 in a hash-table of length m=11 using open addressing with the primary hash function Illustrate the result of inserting these keys using linear probing, and double hashing with (8)

             b.    Here are 16 integers

                    44, 72, 12, 158, 52, 90, 150, 26, 62, 124, 54, 152, 66, 32, 126, 94

                    Sort them using

                    (i) heap sort                            (ii) quick sort                                                                    

                    show the steps.                                                                                                           (8)

   Q.9    a.    Consider the following graph. Using Kruskal’s algorithm, calculate the minimum spanning tree, listing edges in the minimal spanning tree in the order they are added to the tree.                                                                                                          (8)

(8)

             b.    What are threaded binary trees. Explain Inorder threading with the help of an example. Write Inorder traversal algorithm for a threaded binary tree.                                                              (8)