DipIETE – CS (OLD SCHEME)

Code: DC08                                                                                  Subject: DATA STRUCTURES

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. To traverse an array means

(A)  to process each element in an array.

                   (B)  to delete an element from an array.

(C)  to insert an element into an array. 

(D)  to combine two arrays into a single array.

b. Index of an array containing __________ elements varies from 0 to n–1.

(A)  n²                                                 (B)  n–1

(C)  n                                                  (D)  0

             c.   A matrix is called sparse matrix when

(A)  most of its elements are non-zero.

                   (B)  most of its elements are zero.

(C)  all of its elements are non-zero.    

(D)  none of the above.

             d.   Adding an element to the stack means

(A)  placing an element at the front end.    

(B)  placing an element at the top.

(C)  placing an element at the rear end.     

(D)  none of the above.

             e.   Queue is a

(A)  Linear data structure.                    (B)  Non-linear data structure.

(C)  both (A) and (B).                         (D)  none of the above.

             f.    The end from which an element gets removed from the queue is called

(A)  bottom.                                        (B)  rear.

(C)  top.                                              (D)  front.

             g.   If depth of a binary tree is d and d>0 then the maximum number of nodes in the binary tree will be

(A)  d                                                  (B)  2^d

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

h. A linear list in which elements can be added or removed at either end but not in the middle is called a _________

(A) Queue                                          (B)  Deque

(C)  Stack                                           (D)  None of the above

 i.     What is the postfix form for (A+B)*C/D?

(A)   AB+C*D/                                   (B)  ABC+*D/

(C)   AB+CD*/                                   (D)  AB+C*/D

             j.    The complexity of insertion sort for worst case is

(A) O(n²)                                           (B)  O(n^1/2)

(C)  O(log n)                                        (D)  O(n)  

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   Let A(n) = a_m n^m + … … +a₁n + a₀ is a polynomial of degree m then show that A(n) = O(n^m). Is A(n) = O(n^m) true when n>0?                         (4)

     b.   What is an array? Describe briefly the operations which can be performed on an array?                  (4)

             c.   What are the two methods of representing arrays in contiguous memory? Show by example row major ordering method.                                 (8)

Q.3     a.   Write “C” function to compute the addition of two polynomials represented as singly linked lists of nonzero terms.                                                  (8)

             b.   Represent the given sparse matrix A by linked list.                                     (4)

             c.   What are the advantages and disadvantages of a circular list?                              (4)

Q.4     a.   Define a stack. Write the “C” functions for “push” and “pop” operations for a stack represented as a linked list.                                                      (8)

b.   Convert the following infix expression into postfix notation by using stack.

(8)

Q.5     a.   Consider the following queue of character, where QUEUE is a circular array which is allocated six memory cells:

                   FRONT=2,  REAR=4 ;       QUEUE:  __,A,C,D,__,__ . 

                   Describe the queue as the following operation take place (8)

(i) F is added to the queue.

(ii) Two letters are deleted.

(iii) K, L and M are added to the queue

(iv) Two letters are deleted.

(v) R is added to the queue.

(vi) Two letters are deleted.

(vii) S is added to the queue.

(viii) Two letters are deleted.

     b.   Write down the algorithm of Bubble Sort.  Sort the following elements by using bubble sort (11, 15, 2, 13, 6).                                                                                                                     (8)

  Q.6     a. Write a “C” function to sort elements of an array using Shell Sort. Sort the following element using shell sort (83, 87, 12, 51, 18, 70, 97, 43).          (8)

             b.   What is hash table? Describe Division Remainder Method and Mid Square Method of hash function.                                                                     (8)

Q.7     a.   What is a Tree?  What are the different types of trees? Write any four properties of binary tree.                                                                 (8)

b.   Write an algorithm for postorder traversal of a binary tree traversal; and implement the same using ‘C’.                                                                  (8)

Q.8     a.   Define the following term in relation to graph:                                                      (8)

                   (i) Degree

                   (ii) Path

                   (iii) Connected graph

                   (iv) Cycle

             b.  Write an algorithm for ‘Breadth First Search’. Apply ‘Breadth First Search’ on the following sample graph.                                                            (8)

Fig. ‘A Sample graph’

Q.9     a.   Compute the shortest path of the following graph using, ‘Dijkstra’s algorithm. Start from node ‘A’.                                                            (8)

             b.  Define the adjacency list. Represent the given graph using adjacency list.             (8)