UPTU Questions Paper 2006-07

MCA (Sem-I) Examination (Paper Id: 1449)

DATA & FILE STRUCTURE USING 'C'

Time: 3 Hours                                                           Total Marks: 100

Note (1) Attempt all questions.

(2) All questions carry equal marks.

(3) In case of numerical problems assume data wherever not provided.

(4) Be precise in your answer.

1. Attempt any four parts of the following:                        5x4=20

(a) Describe briefly the types of structures used for storing strings.

(b) Derive and explain in brief a formula to obtain an address of any element in three dimensional ARRAY stored in row mazor order.

(C) Define the two way linked list. Discuss the advantages of two linked list over the one way linked list in case of deleting a node whose location LOC is given.

(d) Suppose a linked list consists some numeric values. Design an algorithm to find maximum value in the list.

(e) Translate the following infix expressions into Postfix notations:-

(i). ((A+B)*D) ↑ (E-F)

(ii). A + (((B-C) * (D-E) + F)/G) ↑ (H-J)

(f) Define the QUEUE data structure. Write an algorithm to delete and insert an item from the queue and into the QUEUE-

2. Attempt any four parts of the following :                    5x4=20

(a) Write a function / procedure to revers; a linked list so that the last element becomes the first one and second last become the second element and so on.

(b) Define the binary tree. Draw two binary trees that are similar, and draw two binary trees that are equivalent.

(C) Define the inorder traversing. Write an algorithm/Program for inorder/traversing method.

(d) What is the graph'? Explain the adjacency matrix to represent the directed graph.

(e) Write an algorithm/program to traverse the graph using the breadth first traversal method.

(f) What are the threaded binary trees'? Explain the one-way and two-way murder threading.

3. Attempt any two parts of the following:-

(a) How merge sort works ? Explain it with suitable example. On what types of data set the method is suitable; explain in brief.

(h) Write the sequential search and binary search algorithm on the data stored in an array. Compare these two methods.

(c) What is hashing'? Explain various methods to find hash functions. How collision situation can be avoided?

4. Attempt any two parts of the following:                       10x2=20

(a) Define the heap. How a priority queue he implemented using the Heap.

(h) What is an AVL tree '? How the insertion and deletion can he performed in the AVL tree '?

(c) How the deletion can be performed from a binary search tree ? Write and explain the algorithm.

5. Attempt any two parts of the following:                        10x2=20

(a) Write a recursive and non-recursive versions of the procedure which calculate the factorial of ‘n’ numbers. Examine and compare the execution of both in teens of space and time as n become larger.

(b) Write an algorithm for selection sort. Explain how the selection sort is more efficient than bubble sort.

(c) Write short notes on the following

(i) doubly linked list

(ii) circular linked list.