DipIETE – CS (OLD SCHEME)

Code: DC08 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: (2 10)

a. Merging refers to

(A) inserting elements into an array

(B) processing elements of an array

(C) combining two arrays into a single array

(D) deleting elements from an array

b. In the linked representation of a sparse matrix, the head node for a column list stores

(A) a pointer to the next column head node

(B) a pointer to the first node in column list

(C) column number

(D) all of the above

c. Pushing an element to a stack means

(A) adding a new element to the stack

(B) removing an element from the stack

(C) searching a given element in the stack

(D) sorting the element in the stack

d. The end at which a new element gets added to a queue is called

(A) front (B) bottom

(C) top (D) rear

e. Consider an array P[1971 : 1977]. The number of elements in this array are

(A) 5 (B) 6

(C) 7 (D) 8

f. What is the postfix form for

(A) (B)

(C) (D)

g. The depth d of a binary tree, that contain n elements, where n0 is at most n and at least ________

(A) (B)

(C) (D)

h. A 2-D array is also called _________

(A) Vector (B) Quadratic

(C) Matrics (D) None of the above

i. The complexity of the merge sort algorithm for worst case is

(A) O(n) (B) O(n log n)

(C) O(log n) (D)

j. An operation in which a list of elements is arranged either in ascending order or in descending order

(A) searching (B) traversing

(C) sorting (D) none of the above

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2 a. Define polynomial as an abstract data type. Write a “C” function to add two polynomials and to return the sum. Analyze the time complexity. (8)

b. Write a “C” function to find out the maximum and the second maximum values in an array of integers. What is the time complexity of function? (8)

Q.3 a. Explain an efficient way of storing sparse matrix in memory. Write a function in C to count the number of non-zero elements in a sparse matrix. (8)

b. Describe an algorithm to insert a node “t” after a node pointed to by “X” in a singly connected list “p” as shown below. (8)

Q.4 a. Write down Quick Sort algorithm. What is the complexity of Quick Sort in the

(i) Best Case

(ii) Worst Case (8)

b. Convert the following infix expression into postfix expression using stack.

(8)

Q.5 a. A linked queue Q and an AVAIL list maintained as a linked stack are as shown below. Trace the contents of the memory after the execution of the following operations on the linked Q. (8)

	INFO	LINK
23	56	NULL
24	8	29
25	12	34
26	5	NULL
27	76	30
28	123	31
29	09	33
30	45	23
31	23	26
32	56	25
33	78	28
34	123	24

32

23

27

AVAIL : LINKED QUEUE Q: FRONT : REAR :

(i) Insert 567

(ii) Delete 76

(iii) Delete 45

(iv) Insert 67

b. Write down the algorithm of insertion sort. Sort the following array of elements using insertion sort (25, 15, 30, 9, 99, 20, 26) (8)

Q.6 a. How fast can one search? (5)

b. Show the pointer implementation of binary tree diagrammatically. Explain briefly. (5)

c. A binary tree T has 9 nodes. The inorder and preorder traversal of T yield the following sequences of nodes:

Inorder :	E	A	C	K	F	H	D	B	G
Preorder :	F	A	E	C	K	D	H	G	B

Draw the tree T. (6)

Q.7 a. What is a Binary Search Tree? What is its average running time? Write a “C” function to insert a node into a binary search tree. (8)

b. Explain B-tree. What are the general applications of trees? (8)

Q.8 a. Write Dijkstra’s shortest path algorithm. (10)

b. Define the following terms in relation to graph

(i) Spanning tree (ii) Minimal spanning tree

(iii) Incidence (iv) Degree (6)

Q.9 a. Define the adjacency matrix representation of graph. Represent the given graph using adjacency matrix. (8)

b. Explain hashing. Describe any two commonly used hash functions. (8)