Biju Patnaik University of Technology 2008 B.Tech (B Tech) , 2nd semester data structructure using c . - Question Paper

Thursday, 23 May 2013 08:25Web

Page 1 of 2

BPUT(B Tech) , second semester data structructure using c ques. paper.

u

r *

Total number of printed pages *8 B. Tech / MCA

SCSE 3102/PCS 1001/PCS 10

Second Semester Examination - 2008 DATA STRUCTURE USING C Full Marks-70

Time:3 Hours

IWL

Answer Question No. 1 which is compulsory and any five from the rest

Figures in the right hand margin indicate marks.

1. Answer the following questions : 2 x10

(a) Deline data structure. What do you mean by ADT ? Deiine and differentiate between linear and non-tinear data structures.

(b) State applications for which binary tree is most suitable. Explain representation of binary tree in linear array.

(c) Describe ADT representation of queue with commonly used functions.

(d) Write the conditions to test Queue is Empty*, Queue is Full", and 'Queue Contains > 1 for a linear queue implemented in linear array.

(e) Explain the data structure used to represent a sparse matrix.

(f) Why do you have to check the full and empty conditions of a STACK (implemented in linear array) ?

(g) Define with example Height Balance Tree. What is the worst cases height of such tree ?

(h) What , is a symbol table ? Which data structure is most suitable to represent symbol table and Why ?

(i) What is path matrix of a Graph ? Discuss with relevent example.

(j) What is the process of topological sorting? Explain how time complexity of topological sortingialgorithm, depends on the data structure used to represent the graph.

2. (a) Why do you have to check the full and empty conditions of a STACK ? Write a C program to perform insertion and deletion in STACK that implemented using an array. 5

(b) Write a C program to convert a singly linked list to circular linked list. Why header node is used in circular list ?

5

3. (a) Define linear queue. Let QUEUE be a

nonempty Queue implemented using linear array. Write a C program to delete m elements from the QUEUE. 5

(b) Sketch the binary search tree resulting from the insertion of the following integer keys: 39, 24, 12, 11, 43, 73, 26, 35, 29, 13, 6 5

(i) Is the tree almost complete ?

IWL

(ii) Is the tree a AVL ?

(iii) What is the height of the sketched tree ?

(iv) Write the PREORDER traversal of the sketched tree.

4. (a) Write an algorithm that computes the

number of elements and sum of elements in a linear linked list. 5

BCSE 3102 / PCS 1001/PCS 1002 4 Contd,

(b) The in-order traversal of a tree produced the sequence D, B, H, E, A, I, F, J, C, G and the pre*order traversal of the same tree produced A, B, D, E, H, C, F, I, J, G. Draw the binary tree. Give a linear array representation of the above binary tree. Define a Node structure in C, which can be used to implement a tree. 5

5. (a) Describe a node structure of a doubly linked list. Write an algorithm to delete the last node of a non-empty doubly linked list. 5

(b) Define binary Heap. Explain the process of Heap sort. Write an general algorithm to construct a min heap. Construct min-heap from the following list

{21, 6, 56, 61, 44, 7, 9, 76, 75, 32, 34,

4, 49, 33 } 5

6. (a) Define a Graph, What are the different representations of a Graph ? Use suitable data structures to represent the following directed graph in memory. 5

(b) What are the preconditions to perorm BINARY SEARCH on a linear array ? Write a recursive (unction in C to perform binary search on a lineararray,

5

(b) Write a program in C lo sort a fist of floating point numbers (stored in a linear array) using quick sort. In quick sort, why the pivot is chosen from the center of the list rather than from one end ? 5

i

7. (a) Write an algorithm to perform DFS on a

graph. Find out the path from D to K using DFS. *-