DipIETE – CS (NEW SCHEME) – Code: DC54

Subject: DATA STRUCTURES

Time: 3 Hours Max. Marks: 100

NOTE: There are 9 Questions in all.

· Question 1 is compulsory and carries 20 marks. Answer to Q.1 must be written in the space provided for it in the answer book supplied and nowhere else.

· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

· Any required data not explicitly given, may be suitably assumed and stated.

Q.1 Choose the correct or the best alternative in the following: (210)

a. The program execution starts from:

(A) the function which is not first defined

(B) main() function

(C) the function which is last defined

(D) other than main()

b. The default return data type in function definition is:

(A) void (B) int

(C) float (D) char

c. The main() function calls in a C program

(A) allows recursive call (B) does not allow recursive call

(C) is optional (D) is a built in function

d. The storage class allowed for parameters is

(A) auto (B) static

(C) extern (D) register

e. Header files include___________ functions.

(A) library (B) block scope

(C) float (D) variable

f. The maximum number of nodes at level i in a binary tree is

(A) (B)

(C) (D)

g. Structure declaration

(A) describes the prototype (B) creates structure variables

(C) defines the structure function (D) is not necessary

h. Union is____________.

(A) a special type of structure (B) a pointer data type

(C) a function data type (D) not a data type

i. The nodes in the linked list are__________.

(A) self-referential structure (B) nested structures

(C) array of structure (D) ordinary structure

j. Related data items of different type are organized using_______.

(A) Linked list (B) structure

(C) binary tree (D) stack

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2 a. Write a C program to accept two positive integers and computes their GCD using recursive function. (5)

b. What do you understand by Scope of variables? Explain the working of external static variables by writing a C routine. (6)

c. Explain memory management C function alloc( ) and malloc( ). Is there any difference between malloc() and calloc() function? (5)

Q.3 a. What is a file? List various operations that can be performed on a sequential file. Write a C program implementing a direct access file. (8)

b. Write a C program that print student name and marks using a structure pointer. (8)

Q.4 a. Arrange an array of elements 15,8,17,12,38,11 in ascending order using Bubble Sort. Show the working of each Pass. (8)

b. Write a C routine to sort a list of elements using Heap Sort. (8)

Q.5 a. By taking a suitable list of characters, show the working of push () and pop() functions to add and delete character elements in stack. (8)

b. Represent a queue in a single one dimensional array. Write a C function to add and delete items in a queue. (8)

Q.6 a. Write a C function to delete the i^th node in a linked list. (8)

b. Write a C function to add polynomial using a linked list. (8)

Q.7 a. Write a procedure for splitting a circular list with 2n nodes into two equal circular lists. (8)

b. Draw a double connected linked list of integers and explain insertion of a node in a doubly connected linked list. (8)

Q.8 a. What is a binary search tree? Write a C program to create such tree. (2+6)

b. Write a function for preorder traversal of a binary tree. (6)

c. Write four properties of a binary tree. (2)

Q.9 a. Find minimum spanning tree of following graph using Kruskal algorithm

Show all the steps of algorithm. (10)

b. What are various ways of representing a graph? Explain with the help of following graph. (6)