Term-End Examination
December, 2006
CS-62 : C PROGRAMMING AND DATA STRUCTURE
Time : 2 hours Maximum Marks : 60
Note : Question no. 1 is compulsory. Answer any three questions from the rest. All algorithms should be
written nearer to 'C' Language.
1. (a) Show how the array
would appear in memory when stored in
(i) Row major order
(ii) Column major order
(iii) Logical representation (10)
(b) What is a Binary Search Tree (BST) ? Write algorithms for inserting and deleting nodes in a
BST. Explain them with the help of an example each. (10)
(c) Assume A is a N x N square matrix . Write the algorithm for the following operations in the matrix
A. (10)
(i) Find the product of the diagonal elements of A.
(ii) Find the sum of the elements above the diagonal elements.
2- (a) Construct a Height Balanced Tree for the following list of elements : (5)
2, 6, 13, g, 4, 3, 18 7 , 1, 8, 11
(b) Write an algorithm to convert an infix expression to a postfix expression. Also, explain the logic with
the help of an example. (Use stack implementation) (5)
3 (a) Write and explain the hash function method, "Division - Remainder Hashing". Also explain (5)
where this can be used.
(b) For the digraph shown below find (5)
(i) the indegree and outdegree of each vertex
(ii) its adjacency matrix representation
(iii) its adjacency list representation
(iv) its strongly connected component
4. (a) Write an algorithm to construct a doubly linked List and search for a data. (5)
(b) Write an algorithm for addition and deletion of an element into a queue. (5)
5. Define the following and give an example for each : (10)
(i) UNION in C language
(ii) Circular linked list
(iii) Post order traversal of a binary tree
(iv) Insertion sort
(v) K-way merging