DOEACC Society 2007 DOEACC B Level B2.1 Data Structure through 'C' Language - Question Paper

B) In a deque, insertion and deletion of elements can take place on either end
C) In a priority queue, insertion of new elements always takes place at 1 end
D) None of the above
1.9 The number vertices in a full m-ary tree with i internal nodes is
A) mi + 1
B) 2mi – 1
C) Mi
D) two mi-1
1.10 The number of comparisons needed to merge-sort a list of n elements is
A) O(n log n)
B) O(n log log n)
C) O(n)
D) O(n log n2 )
B2.1-R3 Page two of five January, 2007
2. every statement beneath is either actual or FALSE. select the most improper one
and ENTER in the “tear-off” sheet attached to the ques. paper, subsequent
instructions therein. (1 x 10)
2.1 The Structures cannot contain a pointer to itself.
2.2 A simple graph is connected if and only if it has a spanning tree.
2.3 Insertion of an element in an array requires shifting of a few elements of the array by
one position.
2.4 2 sorted lists with m elements and n elements can be merged into a sorted list using
no more than m+n-1 comparisons.
2.5 The number of disk accesses needed for most operations on a B tree is inversely
proportional to the height of the tree.
2.6 The time needed to perform a sequence of data structure operations is averaged over
all the operations performed in an Amortized analysis.
2.7 All the terminal nodes are traversed in the identical order from left to right in in-order,
preorder and post-order traversals of a binary tree.
2.8 A complete binary tree with n internal nodes has (n-1) leaves.
2.9 AVL trees, 2-3 trees and B trees permits searches, inserts, deletes in O(log n) time.
2.10 The in-degree of a vertex is the number of edges leaving it.
3. Match words and phrases in column X with the nearest related meaning/
word(s)/phrase(s) in column Y. Enter your selection in the “tear-off” ans sheet
attached to the ques. paper, subsequent instructions therein. (1 x 10)
X Y
3.1 Typedef A. sensitive
3.2 C variables B. situation dependent
3.3 O(log n) C. Elements are stored in hash table
3.4 Stack D. FIFO
3.5 Queue E. Suffers primary clustering
3.6 Conversion of 1 data kind to a different F. Suffers secondary clustering
3.7 Strongly connected component G. kind coercion
3.8 Prim’s algorithm functionality H. Dijkstra’s algorithm
3.9 Open addressing I. Depth 1st search
3.10 Linear probing J. Breadth 1st search

Earning:   Approval pending.