DipIETE – CS (OLD SCHEME)

              

Flowchart: Alternate Process: JUNE 2010Code: 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.       An ordered arrangement of data (such as a table of numbers) identified by a single name is called a/an ___________. 

 

                   (A)  array                                            (B)  stack

(C)  queue                                          (D)  series

                                                          

b.      What is not true about an array?

                                                                                                              

                   (A)  An array may contain other arrays.                                                                        

                   (B)  It organizes data into lists/tables.

(C)  Its elements cannot be considered as individual variables.                                    

(D)  It can have any dimensions.

 

             c.   Adding items to a stack is called _________.

                                                                                                                                              

                   (A)  LIFO                                          (B)  pushing in

(C)  popping                                       (D)  overflowing

 

             d.   The prefix form of A-B/(C*D$E) is ___________.

 

(A)  -/*$ACBDE                               (B)  –ABCD*$DE

(C)  –A/B*C$DE                              (D)  –A/BC*$DE

    

             e.   A full binary tree with a n non-leaf nodes contains _________.

                                                                                                                                              

(A)  nodes                              (B)  n+1 nodes

(C)  2n nodes                                     (D)  2n+1 nodes

 

             f.    A characteristics of the data that binary search uses but the linear search ignores is the ________.

 

(A)  order of the list                           (B)  length of the list

(C)  maximum value in the list           (D)  mean of data value

 

             g.   Recursive procedures are implemented by _________.

 

(A)  queues                                         (B)  stacks

(C)  linked lists                                  (D)  strings

 

 

h.      The tree shown in Fig.1 represents the Inorder expression
 
 

 

 


(A)   ABDGCEHIF                           

(B)    DGBAHEICF

(C)  GDBHIEFCA                           

(D)  ABHIEFCDG

 

                                                                                  Fig.1

 i.     An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components? 

 

(A)   O(n)                                            (B)  O(e)

(C)  O(e+n)                                        (D)  O(e2)

 

             j.    Consider that n elements are to be sorted. What is the worst case time complexity of Bubble Sort?

 

(A)    O(1)                                            (B)  O()

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

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

 

  Q.2     a.   Define the term Data Structure. Differentiate between data type and data structure.               (4)

 

             b.   List four important operations associated with linear data structures. Describe each.                (4)

                                                                             

             c.   Given a one dimensional array A [15] with base address of A as 100, and each element occupies 2 bytes, find the location of A [10].     (8)

 

  Q.3     a.   Binary Search is to be used on the following sorted array to search for 30 & 60.                      (8)

 

                   Array                                                

                   Index: 0     1      2       3        4       5        6        7         8          9

                   Value: 11   22   30    33       40     44     55      60       66        70

 

                   Give the index of the elements that would be compared with every step. Repeat the process replacing 30 by 60.

 

             b.   Comment on the efficiency of Linear search and Binary Search in relation to the number of elements in the list being searched.                   (8)

 

 

            

 

 

  Q.4     a.   Write a C function by applying selection sort algorithm on an array ARR containing 8 elements: 71, 31, 41, 9, 84, 11, 60, and 51.             (8)

                  

             b.   Define the terms: stack, queue, static data structure, dynamic data structure.               (8)

                                                                                                                                                

  Q.5     a.   BANK is linked list in which each node has the name of a bank client and his balance. Develop an algorithm for counting and displaying the number of clients who are worth more than Rs. 1 lakh. START points to BANK.                  (8)

 

             b.   Write an algorithm to swap first and last nodes of a linked list L.                  (8)

 

  Q.6     a.   Write an algorithm for Bubble sort sorting procedure.                                    (8)

 

             b.   What is the difference between an array and a stack housed in an array? Why stack is called a LIFO data structure? Explain how push and pop operations are implemented on a stack?      (8)

 

  Q.7     a.   Write an algorithm to insert an element in a circular queue.                            (8)   

 

             b.   Given the following inorder and preorder traversal reconstruct a binary tree.                (8)

                             Inorder sequence D G B H E A F I C

                             Preorder sequence A B D G E H C F I

 

Q. 8     a.   When deleting an entry from a linked queue, checking for underflow condition

                   is must, but when adding an entry, there is no need to check for overflow, Why?                    (8)

 

             b.  By taking an inorder arithmetic expression E= (2a +5b) 3 (d–7y) 3.

                   Draw a Binary Tree.                                                                                         (8)          

 

  Q.9     a.   By using Dijkastra’s algorithm, find the shortest path in the following graph (Fig.2):               (8)

                                Start from node ‘A’             

 
 

 

 

 

 

 

 

 

 


                                                                         Fig.2

             b.  Explain Kruskal’s algorithm for creating a minimum spanning tree from a weighted graph.                  (8)