# CUSAT Test Paper Data Structure and Algorithms

B. Tech. Degree IV Semester (Special Supplementary) Examination, March 2007

IT/CS 405

DATA STRUCTURES AND ALGORITHMS

Time: 3 Hours                                                                                                           Maximum Marks: 100

I                                              (a) How do we represent sparse matrices in computer? Write an algorithm to transpose a sparse

matrix.                                                                                                                                                          (8)

(b) Explain the issues in Garbage collection. Discuss the most suitable data structure need for

implementation of a garbage collection.                       (12)

OR

II                                        (a) Explain dynamic memory allocation. Explain how a multidimensional array may be allocated dynamically. Give examples.                                                                                                                         (10)

(b) What do you mean by Abstract Data Type? Illustrate with examples.                                                                                                  (10)

III                                     (a) Explain the implementation of Stack using arrays and linked list.                                                                                 (10)

(b) Write a non-recursive function to copy a Priority Queue. (Clearly mention any assumption you make.)    (10)

OR

IV                                    (a) Explain the concept of stack with an example. Also explain how a stack can be used in recursion removal.                                                                                                                                                         (10)

(b) Explain how to implement the concept of linked list using arrays.                                                                                                                    (10)

V                                        a) What is tree? State and prove any three mathematical properties of a tree.                  (12) b) Write a non-recursive algorithm for in order traversal of a tree.                            (8)

OR

VI                                   (a) What is threaded binary tree? What are the advantages of using it?                                                                                  (8)

(b) Discuss the representation of arbitrary (need not be binary) trees using binary trees.                                                                           (4)

(c) Explain any balanced binary search tree.                                        (8)

VII                               (a) Discuss any two graph traversal algorithms.              (10)

(b) Explain the shortest path algorithm. What is its run time complexity?                                                                    (10)

OR

VIII                          (a) Discuss various data structures used for search applications. Compare the space and time complexities for these data structures,                                                                                                                                           (12)

(b) What are the characteristics of good hash function? Explain in detail.                                                                                                           (8)

IX                                   (a) Explain the relevance of B tree as a data structure suitable for file structures.                                                   (10)

(b) Explain the radix sort with suitable example. Is there any sorting algorithm, which sorts an array of elements without comparing the elements?                                     (10)

OR

X                                        (a) When do you call a sorting algorithm stable? Explain, why a sorting algorithm be stable. (10)

b) Discuss the differences between internal and external sorting.                                                                                                                    (10)

***