AMIETE – ET/CS/IT (NEW SCHEME)   –   Code: AE52/AC52/AT52

 

Subject: C & DATA STRUCTURES

Flowchart: Alternate Process: DECEMBER 2009Time: 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.  The variables which can be accessed by all modules in a program are known as

 

                  (A) Local variables                               (B) Internal variables

                  (C) External variables                           (D) Global variables                                             

 

             b. The minimum number of fields in each node of  a doubly linked list are:

 

                  (A) 1                                                    (B) 2

                  (C) 3                                                    (D) 4

 

             c.  How many values can be held by an array A (-1…..m, 1…..m)?

 

                  (A) m                                                   (B) m2

                  (C) m(m+1)                                          (D) m(m+2)

 

             d.  The postfix expression for the expression A+B*(C+D)/F+D*E is  

 

                  (A) AB+CD+*F/D+E*                        (B) ABCD+*F/DE*++

                  (C) A*B+CD/F*DE++                        (D) A+*DE++

 

             e.  What can be said about the array representation of a circular queue when it contains only one element? 

 

                  (A) Front=Rear=Null                            (B) Front=Rear+1

                  (C) Front=Rear-1                                 (D) Front=Rear

 

             f.   In a circular linked list insertion of a node involves modification of 

 

                  (A) no pointer                                       (B) 1 pointer

                  (C) 2 pointers                                       (D) 3 pointers

 

             g. If G is a directed graph with 20 vertices how many boolean values will be  needed to represent G using adjacency matrix?

 

                  (A) 20                                                  (B) 40

                  (C) 200                                                (D) 400

 

             h.  Which of the following statements is used in binary search algorithm to halve the array?

 

(A)  middle=(start+stop)/2                     (B) middle=start+(stop)/2

                  (C) middle=middle/2                             (D) middle=(stop-start)/2

 

             i.   Merge sort uses

 

                  (A) Divide and conquer strategy            (B) backtracking approach

                  (C) Heuristic approach                         (D) Greedy approach

 

             j.   A binary search tree is generated by inserting in order the following integers:

                 

                  50,15,62,5,20,58,91,3,8,37,60,24

                  The number of nodes in the left subtree and right subtree of the root respectively is

 

                  (A) (4,7)                                              (B) (7,4)

                  (C) (8,3)                                              (D) (3,8)

 

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

 

  Q.2     a.   Discuss, with help of examples, the following operations:

                   (i)     Increment and decrement operators

                    (ii)   Sizeof operator

                    (iii)  Shorthand assignment operator

                    (iv)  Conditional operator

                    (v)   Comma operator                                                                                      (10)

                  

             b.   Write a C program to display the largest and smallest of two numbers.                (6)

 

  Q.3     a.   Explain various variations of ‘if’ statement. List out the differences between while and do-while loops.                                                                    (10)

            

             b.   Write a program to swap two numbers using pointers.                                        (6)

 

  Q.4     a.   Differentiate between one-dimensional and two-dimensional arrays. Discuss  the limitation of arrays.                                                                      (6)

       

             b.   Write a recursive function in ‘C’ to generate n fibonacci number. Show the stack contents for n=6.                                                                       (4)

 

             c.   Using suitable example, differentiate between a function call, definition and declaration.                   (6)

            

  Q.5     a.   What is a file? Explain various operations performed on files.                              (6)

 

             b.   Write a program to enter the records of ‘n’ number of students and display them using structures.                                                                          (10)

  Q.6     a.   What is sorting? Comment on the efficiency of Bubble sort with an example.                                   (6)

 

             b.   Write an algorithm to implement Quicksort. Apply the same for the following array and sort the elements.                                                              

                   25        57          48           37          12           92          86          33                   (10)

 

  Q.7     a.   Define the following with an example.

 

                   (i)    Binary tree             (ii)   Strictly binary tree                 (iii)  Complete binary tree

                   (iv)  Binary search tree                                           (12)

 

             b.   A Binary tree T has 9 nodes. Draw a tree whose inorder and preorder traversals yield the following sequence of nodes:

 

                   Inorder:           E     A     C     K     F     H     D     B     G

                   Preorder:         F     A     E     K     C     D     H     G     B

                   Explain your solution                                                                                          (4)

       

  Q.8     a.   What is a ‘stack’? How does it differ from queue? Explain, in detail, the various operations that can be performed on a stack.                          (8)

 

             b.   Write a C program to insert a node at the end and delete a node from the beginning in a doubly linked list.                                                             (8)

                  

Text Box: Q.9      a.   Define a graph. Write the adjacency matrix and adjacency list for the directed graph in Fig. 1                                                                     (8)

 

 

 

 

 

 

 

 

 

             b.   Show the Breadth first Traversal and Depth first Traversal for the graph given below in Fig. 2.                                                                   (8)

Text Box: