AMIETE – CS/IT (OLD SCHEME)

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 the best alternative in the following:                    (2  10)

             a.  A complete binary tree T can have at most ________ nodes at level r.

(A)  2^r-1 (B)  2^r

                  (C)  2^r-2 (D)  2^r+1

b. If the list is already sorted, which one of the following gives worst case complexity

(A)  Selection sort                               (B)  Insertion  sort

(C)  Quick   sort                                  (D)  Merge sort

c.    A queue in which addition and deletion can be done at both the ends is _________

                   (A)  Dequeue                                      (B)  Enque

(C)  Endqueue                                     (D)  Delque

d. To insert a node in the middle of a doubly linked list, ________ number of pointers are to be updated

(A)  one                                              (B)  two

                   (C)  three                                            (D)  four

e. In which tree the balance factor for a node can be either 0,1 or –1?

(A) B Trees                                        (B)  B* Tree

(C)  AVL Tree                                    (D)  B⁺ Tree

             f.    If quadratic probing is used and the table size is prime, then a new key value can always be inserted if the table is at least ___________

(A)  Full                                              (B)  Half Full

                   (C)  One fourth  full                             (D)  Three fourth full

             g.   Activation records are used in the following technique

(A)  Databases                                    (B)  Recursion

(C)  Hash tables                                  (D)  Iteration

h.   In Breadth First Search traversal, the following data structure is used

(A) Queue                                          (B) Array

(C)  Stack                                           (D)  Linked list      

             i.    The extra memory needed in merge sort is

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

(C) O(2n)                                            (D) O(n*n)

             j.    Infinite recursion leads to

(A) Underflow of  run-time stack        (B)  Underflow of  registers usage

(C)  Overflow of I/O cycles                 (D)  Overflow of run-time stack

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2       a.    Mention any four properties of Big-O notation.                                                     (4)

b. Give an example to illustrate best case, average case and worst case complexity of an algorithm.                                                                (6)

c.   Compare and contrast tail recursion and non-tail recursion. Give an example for each. What is meant by indirect recursion?                                                                        (6)

Q.3     a.   Define AVL tree. Explain four rebalancing rotations used during insertion of a node in AVL tree.                                                                (6)

 b.    Construct a Min_Heap using the following list of numbers.  Show all the intermediate steps.

                   24, 28, 67, 74 ,89, 34, 62, 45,96,158 .                                                                 (4)

     c.   Write an algorithm to find the number of terminal and non-terminal nodes in a Binary Tree.                          (6)

Q.4    a.    Differentiate between internal and external sorting. Give at least two examples for each.                                                                                                                  (4)

b.   Give the steps involved in sorting the following numbers using Quick Sort:

                                9, 20, 6, 10, 14, 8, 60, 11                                                                         (4)

              c.   Give the complexity analysis of Heap sort algorithm.                                               (4)

d.   What is collision in hashing?  Explain any two techniques for resolving collision.

(4)

  Q.5           a.                                                        Write an algorithm to insert key X into B-Tree, T of order m (8)

b. Suppose G is a finite undirected graph without cycles. Prove the following:

(i)      If G has at least one edge, then G has a node v with degree 1.

(ii)     If G is connected so that G is a tree and if G has m nodes, then G has m-1 edges.                                                                                              (8)

  Q.6     a. Prove the following:                                                                                               (8)

(i)      A graph with n vertices will have parallel edges or self loop if the           number of edges are more than n(n-1)/2.

                           (ii)    The maximum number of nodes in a binary tree of depth k is 2^k - 1,              k 1.

b. For the algebraic expression given below draw binary tree and give preorder traversal and postorder traversal:.                                                                                                              (6)

[ a +  ( b – c) ] * [ (d – e) / (f + g – h)]

c.  Define threaded binary tree and give an illustration of inorder threading.                    (2)

Q.7   a.  Explain any two efficient method for representing polynomials.  Write an

algorithm to find the sum of two polynomials using your representation.        (7)

b.   Define sparse matrix. For an upper triangular matrix,  give the address A[i][j] for:

(i)      Row-major order         (ii)        Column-major order.                            (5)

c. Write a program for linked list representation for queue data structure. Write all function for queue  operations                                                                             (4)

  Q.8     a.   Dijkstra’s algorithm for finding the single source shortest paths may not produce correct results when edge weights are negative. Now, draw one graph each with negative weight edge for which Dijkstra’s algorithm will produce (i) correct solution  (ii) incorrect solution. Comment on the results.       (6)

b. Give the complexity analysis of the graph traversal algorithms.                    (4)

c.    For the graph given below, apply Kruskal’s algorithm and find minimum cost spanning tree. Give output of graph at each step                                     (6)

Q.9     a.   Define the following terms and give an illustration for each:                                       (8)

(i)      Collision                          (ii)  Linear probing

                           (iii)     Rehashing                    (iv) Chaining

b.   Write an algorithm to delete a node with two children from a Binary Search Tree (BST).                 (8)