Test Papers / Previous Question Papers of IGNOU CS62 'C' Programming and Data Structure December 2005

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination

CS60 (S) : 'C' PROGRAMMING AND DATA STRUCTURE

Time: 2 hours
Maximum Marks: 60

1. (a) Write an algorithm to sort 'n' numbers using Bubble sort. Also, show that, on average, bubble sort algorithm does O(N²) comparisons while sorting N numbers. Further, sort the following list using Bubble sort.
15, 4, 5, 3, 0, 10, 6, 2, 13, 1 (10)

(b) Write at least two differences between a singly linked list and a doubly linked list. Write a program to split a given list into two lists, such that alternate nodes go into different lists. (7)

(c) Write a program that accepts three numbers and decides (10)
(i) whether these can be lengths of the sides of a triangle.
(ii) if they form an, equilateral, isosceles or scalene triangle.
(iii) if they form a right-angled triangle.

(d) Write an algorithm for multiplication of two matrices. (3)

2. (a) Write an algorithm for insertion and deletion operations for a priority queue Implemented using arrays. (5)

(b) Explain indexed sequential file organisation. Name the data structure most appropiate for this file organisation scheme. List two approaches for implementing indexes. Also, give one difference between these approaches. (5)

3. (a) Develop algorithms to add two polynomials in one variable. You must choose polynomials containing a minimum of four terms. (5)

(b) Construct an AVL tree for the following list of numbers: (5)
10 5 8 12 18 22 1 4 6 30
Show all the steps.

4. (a) Define the following :
(i) Full binary tree
(ii) lndexes w.r.t. files
(iii) Hash function
(iv) Adjacency list
(v) Weakly connected graph

(b) Consider the following graph :
-----DIAGRAM-----
Find the shortest path between the nodes A and I. Show all the intermediate graphs. (5)

5. (a) Using the quicksort algorithm, sort the following in descending order : (5)
14 12 19 10 9 11 8

(b) A dimensional character array X [3] [4] [5] is stored using row-major oder. What will the address of X [2] [2] [4] be if the base address is 100 ? (3)

(c) Write an algorithm for the implementation of Linear Search. (2)