OCTOBER/NOVEMBER-2010(C09)

C-09-CM-305

3231

BOARD DIPLOMA EXAMINATION, (C09)

OCTOBER/NOVEMBER-2010

DCM-III SEMESTER EXAMINATION

DATA STRUCTURES THROUGH C

TIME: 3 HOURS TOTAL MARKS:80

PART-A 10*3=30

Instruction: (1) answer all questions.

(2) Each question carries three marks.

1) Define data structures and classify them.

2) Explain about non linear data structures.
3) Explain about dummy header.
4) Explain briefly about stack.
5) List the applications of a queue.
6) List advantages of sparse matrix over ordinary matrix.
7) Define binary search tree.
8) List applications of tree.
9) Write the method of bubble sort.
10) Differentiate between linear and binary search.

PART-B 5*10=50

Instruction: (1) answer any five questions.
(2) Each question carries ten marks.

11) (a) Explain about various operations on singly linked list. (b) Write an algorithm for minimum element in singly linked list.
12) (a) Write an algorithm to create a singly circular linked list. (b) Write a program to create a doubly linked list.
13) (a) Write a program to implement queue operations. (b) Write a program to create sparse matrix and its transpose.
14) (a) Convert the given infix expression to postfix (A+B)*(C-D)/F+G-H (b) Write an algorithm to evaluate a postfix expression.
15) (a) Explain about the operations on binary tree. (b) Write the preorder traversal for the given binary tree.

16) Construct binary tree given inorder and postorder traversals. Inorder : DGBAHEICF Postorder: GDBHIEFCA
17) (a) Write a algorithm to implement insertion sort and mention its time complexity. (b) Write a program to implement selection sort.
18) (a) Explain with an example about quick sort. (b) Write a program to implement linear search.