Biju Patnaik University of Technology 2008-2nd Sem M.C.A Data Structure - Question Paper
(b)
Second Semester Examination - 2008 DATA STRUCTURE USING C Full Marks - 70Time : 3 Hours
(c)
 |
(d) (e) |
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*10
(a) Define data structure. What do you mean by ADT ? Define and differentiate between linear and non-linear data structures.
State applications for which binary tree is most suitable. Explain representation of binary tree in linear array.
Describe ADT representation of queue with commonly used functions.
Write the conditions to test Queue is Empty, Queue is Full, and Queue Contains > 1 for a linear queue implemented in linear array.
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 sorting algorithm, 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 ?
(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
(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 function in C to perform binary search on a linear array.
5
7. (a) Write an algorithm to perform DFS on a graph. Find out the path from D to K using DFS. 5
(b) Write a program in C to sort a list 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
8. (a) Use linked list to represent the following polynomial
P (x, y, z) = 2xy2z3 + 3x2yz2 + 4xy3z + 5x2y2 + 8xy2z5 + 19 2.5
(b) Describe the data structure used to represent a General tree. 2.5
(c) Define circular queue. Sketch to explain the placement of FORNT and REAR pointers when Queue is Full and Queue Containing single element. 2.5
(d) Covert the following infix expression to post fix expression using STACK 2.5
(C- D ) + (E/-F) + F/(H+W) *A/-B.
BCSE 3102 / PCS 1001/PCS 1002 8 -C
|
Attachment: |
| Earning: Approval pending. |
