DATA STRUCTURES-MARCH-2009

FOURTH SEMESTER DIPLOMA EXAMINATION IN ENGINEERING/TECHNOLOGY-MARCH, 2009

DATA STRUCTURES

PART-A

(Maximum marks:15)

v  Answer the following questions in one or two sentences:

1.Define pointer.

2.What is a structure?

3.Identify the number of comparisons required for binary search to find the element 60 in the list given:

12

16

20

35

42

47

50

55

60

65

4.Give two sorting techniques which apply divide and conquer method to sort a list.

5.Write about the best,worst and average performance of the linear search.

6.What output will be produced by the following C code?Node is a self referential structure with a member named data.

                  Void fun(struct node *f)

                   {

                             Struct node q=f,p=NULL;

                              While(q!=p)

                              {

                                             Printf(“%d”,q->data);

                                             Q=q->link;

                              };

7.Write the prefix notation of(2+7)*(8/6-(3+1))).

8.List two applications of the datastructure queue.

9.Write about ‘degree of a node’.

10.Draw a tree to represent the expression(5-x)*y+6/(x+z)

PART-B

(Maximum marks:60)

(Answer one full question from each unit)

Unit-1

v  (a)Write a recursive function in C language to reverse a string.(8)

          (b)Give the pointer representation of a two dimensional array.Explain how the array elements are processed.(6)

OR

v  (a)Compares structure and union.(6)

(b)Write notes on: (i)Passing structure to pointers

                            (ii)Pointer to pointer.(6)

Unit-2

v  (a)Write an algorithm for bubble sort.(7)

(b)Trace the execution of quick sort algorithm on the list given below:

65

70

75

80

85

60

(5)

         

OR

v  (a)Explain merge sort with example.(7)

          (b)Compare linear search and binary search.(5)

UNIT-3

v  (a)Explain the operations insert and delete performed on singly linked list.(6)

          (b)Write an algorithm to search an element in the linked list.(6)

OR

v  (a)Explain doubly linked list with example.(6)

          (b)Write about the operations performed on it.(6)

UNIT-4

v  (a)Illustrate with suitable diagram the evaluation of the expression:

*

+

2

7

/

8

+

-

6

3

1

(7)

(b)Write an algorithm to implement push operation on a stack.(5)

OR

v  (a)Define queue.Explain the operations performed on queue.(6)

          (b)Write notes on(i)dqueue           (ii)priority queue.(6)

UNIT-5

v  (a)Write a recursive procedure for inorder traversals of binary tree.(6)

          (b)Write about the binary search tree.(6)

OR

v  Explain Dijkstra algorithm to find shortest path.(12)