DOEACC Society 2006 DOEACC C Level C2 Data Structure through 'C' Language ( ) - Question Paper

C2-R3: DATA STRUCTURE THROUGH ‘C’ LANGUAGE
NOTE:
1. There are 2 PARTS in this Module/Paper. PART 1 contains FOUR
ques. and PART 2 contains 6 ques..
2. PART 1 is to be answered in the TEAR-OFF ans SHEET only, attached
to the ques. paper, as per the instructions contained therein. PART 1 is
NOT to be answered in the ans book.
3. Maximum time allotted for PART 1 is 1 HOUR. ans book for PART
TWO will be supplied at the table when the ans sheet for PART 1 is
returned. However, candidates, who complete PART 1 earlier than 1 hour,
can collect the ans book for PART 2 immediately after handing over the
ans sheet for PART ONE.
TOTAL TIME: three HOURS TOTAL MARKS: 100
(PART 1 – 40; PART 2 – 60)
PART ONE
(Answer all the questions)
1. every ques. beneath provide a multiple option of answers. select the most
improper 1 and enter in the “tear-off” ans sheet attached to the ques.
paper, subsequent instructions therein. (1 x 10)
1.1. Adjacency matrix for a digraph is
A) Unit Matrix
B) Symmetric Matrix
C) Asymmetric matrix
D) none of the above
1.2. Time complexity of insertion sort algorithm in the best case is
A) O(n)
B) O(n log2 n)
C) O(n2)
D) none of the above
1.3. The prefix expression for the infix expression a * ( b + c ) /e - f is
A) /* a + bc – ef
B) -/ * + abc ef
C) - / * a + bcef
D) none of the above
1.4. In linked list representation, a node contains at lowest
A) node address field, data field
B) node number, data field
C) next address field, info field
D) none of the above
C2-R3 Page one of six January, 2006
1.5. Number of nods in a complete binary tree of depth k is
A) 2k
B) 2k
C) 2k-1
D) none of the above
1.6. The smallest number of keys that will force a B-Tree of order three to have a height three is:
A) 12
B) 10
C) 7
D) none of the above
1.7. provided 2 sorted lists of size “m” and “n” respectively, the number of comparisons needed
in the worst case by the merge sort will be:
A) m*n
B) max(m,n)
C) min(m.n)
D) m + n – 1
1.8 Any string of bits of length n represents a unique non-negative integer ranging from
A) 0 and 2n-1 -1
B) 0 and 2n-1
C) one and 2n-1
D) none of the above
1.9 Which of the subsequent expressions accesses the (i,j)th entry of a m ´ n matrix stored in a
column major form ?
A) m * ( i –1 ) + j
B) m * ( j –1 ) + i
C) m * ( n – j ) + i
D) m * ( m – i ) + j
1.10 The subsequent sequence of operation is performed on a stack

Earning:   Approval pending.