Kerala University 2009 B.C.A Computer Application Fourth Semester , , 401 : DATA STRUCTURES AND ALGORITHMS - Question Paper

*2625* (Pages : 2) 2625

Reg. No. : .........................

Name : ..............................

Fourth Semester B.C.A. Degree Examination, May 2009

(2007 Scheme)

BCA 401 : DATA STRUCTURES AND ALGORITHMS



Time: three Hours Max. Marks: 75

part – A (Answer any 10 ques.. every ques. carries three marks.) A1. List the operations permitted in a queue.

A2. provide the algorithm to add to 10×10 matrices represented using arrays. What is the complexity of your algorithm ?

A3. What is a sparse matrix ? What is the advantage of using it ? A4. provide an algorithm to remove a node from a doubly linked list.

A5. What is a binary tree ? Distinguish ranging from complete and non-complete binary tress.

A6. provide any 3 applications of threaded binary trees.

A7. describe a graph. provide any 2 methods of representing a graph. A8. Distinguish ranging from internal and external sorting.

A9. discuss the 'big O' notation with an example.

A10. provide the trace of Bubble sort for the data 1, 2, 15, 14, 12, 65, 56. A11. "Stack is a LIFO data structure". Comment.

A12. What is a hash function ? provide an example of a hash function. A13. discuss the use of a symbol table.

P.T.O.


2625 *2625*
SECTION – B
(Answer any five ques.. every ques. carries six marks.)
B1. Implement a stack using a linked list. provide all the operations.
B2. Compare heap sort and quick sort in terms of space and time complexity.
B3. Explain a non recursive algorithm for the inorder traversal of a binary tree.
B4. Explain the basic operations on a threaded binary tree.
B5. Explain the BFS algorithm on an undirected graph with the help of an example.
B6. Explain the implementation of any 3 basic file operations.
B7. Explain any 1 external sorting algorithm.
B8. Implement the operations on circular linked list.

part – C (Answer any one ques.. every ques. carries 15 marks.)

C1. Alice wants to maintain a list of her friends using a binary tree. Show how the tree will look like after the subsequent names are input in that order.

Latha, Ramesh, Rajesh, Abhilash, Abin, Rama.

Also implement the subsequent routines :

1) Store the list in a binary tree in the alphabetical order of names.

2) Delete the name of a friend.

3) List all the names in alphabetic order.

Also explain the time complexity of every routine.

C2. Let A and B be 2 sparce matrices :

a) Develop an algorithm MADD (A,B,C) to perform the operation C = A + B.

b) Write an algorithm MTRP(A, B) to calculate B as the transpose of A.

c) Analyze the algorithms.


––––––––––––––


PDF to Word

Earning:   Approval pending.