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:                      (210)

             a.  Applications of Stacks are

(A)  Library Management Systems.      

                  (B)  Job Scheduling in operating systems.                                                           

                  (C)  Compilers and postfix and prefix evaluations.

                  (D)  Multiple precision arithmetic.        

b. Examples of Non-linear data structures

                   (A)  Stacks, queues.                            (B)  Graphs, circular linked list.

(C)  Trees, double linked list.               (D)  Trees, graphs.

c.    Matrices with a relatively high proportion of zero entries are called

                   (A)  Unit Matrix.                                  (B)  Triangular Matrix.

(C)  Sparse Matrices.                          (D)  Identity Matrix.

d. In double linked list, assume two deletion operations are done; firstly deleting a node from start/end of double linked list and secondly deleting a node some where other than start/end  of double linked list. How many pointers are to be modified for each deletion operations?

(A)  4, 2                                              (B)  2, 4

                   (C)  4, 4                                              (D)  2, 2

e. An AVL tree of height h  has utmost   the following number of vertices

(A) 2^h–1 – 1                                        (B)  2^h-1 +  1

(C)  2^h+1  +  1                                      (D)  2^h+1 –  1

             f.    Extra memory of O(n) is needed  in

(A)  Insertion Sort.                              (B)  Bubble Sort.

                   (C)  Merge Sort.                                 (D)  Quick Sort.

             g.   The worst case complexity of binary search tree is

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

(C) . (D) .

h.   In Dijkstra’s algorithm

(A) Negative weight edges are sometimes used.   

(B) Negative weight edges are not used.

(C)  Negative weight edges are set to zero.           

(D)  Negative weight edges are always used.        

i.    Worst case performance of Quick sort can happen if

(A) Input array is unsorted.                 (B)  Input array is partially sorted.

(C)  Input array is empty.                    (D)  Input array is sorted.

             j.    In the following hash function method, key is divided into several parts, further combined together and transformed in a certain way to create the target address.

(A)  Folding                                        (B)  Mid Square

(C)  Division                                        (D)  Extraction

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2       a.    Give the algorithm of Dijkstra’s shortest path algorithm and analyze the complexity.                                                                                                   (8)

b. For the Graph G given below, draw sequence of graphs and find Dijkstra’s shortest path. Start from node S.                                                                                                                             (8)

                                                                 1

                                       10

                                            2         3         9         4           6

                                 5                               7

                                                                  2                                                                                       

Q.3     a.   Give a tabular comparison of the following sorting algorithms with respect to average case, best case, worst case and space used                            (8)

                    (i)    Bubble Sort

                    (ii)   Merge Sort

                    (iii)  Quick  Sort

                    (iv)  Heap Sort                                                                                                         

             b.   Write an algorithm to insert in binary search tree and give the analysis.                    (8)

Q.4    a.    Write an algorithm to implement a priority queue. Assume the priorities are from 1 to 3 and size of queue is 50 for each priority. Insertions and deletions are done for each queue. Give an illustration.                                                           (8)

b.   Create AVL search tree for the following set of values:

                                H, I, J, B, A, E                                                                                         (8)

Q.5     a.   Prove that maximum number of nodes on level i of binary tree is 2^i-1                  for .              (7)

b. For the tree given below, give inorder, preorder and postorder traversals.               (9)

  Q.6     a. Write an algorithm to implement polynomial addition.                                              (8)

b. Write a procedure SlinktoDLink, which takes a single linked list and creates double link list containing same number of elements. The nodes in single linked list are to be disposed.                                (8)

Q.7           a.                                                        Define Threaded Binary Trees and give its node structure. Give the advantages of Threaded Binary Trees.                                                                   (8)

b.   The following values are to be stored in a Hash-Table:                                           (8)

                          25, 42, 96, 101, 102, 162, 197, 201

                    Use the Division method of Hashing with a table size of 11. Use the sequential method for resolving collision.

  Q.8     a.   What are the different ways of representing a polynomial using arrays? Discuss the advantages and disadvantages of each method. Represent the following polynomials using the above methods            (10)

                   (i)

(ii)

b. Give the array, DATA, containing elements                                                           (6)

                          DATA

41

56

20

31

59

15

                                                 [1]     [2]     [3]     [4]     [5]     [6]

                 Show the contents of array after each sort given below:

                 (i)  Insertion Sort  (after 3^rd iteration)

                 (ii) Bubble Sort     (after 4^th iteration)

                 (iii) Selection Sort (after 3^rd iteration)

Q.9     a.   Write an algorithm to evaluate a arithmetic expression.                                             (8)

b.   What do you understand by row major ordering and column major ordering in arrays. Derive their formula for calculating the address of an array element in terms of the row number, column number and base address of array.                                              (8)