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

D) binary search is always inferior to sequential search.
1.9 In an 16-bit computer, 30 digit integer can be stored in
A) an integer variable
B) floating point variable
C) a circular list
D) none of the above
1.10 A stack can be used to
A) allocate resources by the operating system
B) to schedule jobs on round-robin basis
C) process procedure call in a program
D) none of the above
B2.1-R3 Page two of five July, 2006
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 For a binary search tree with n-nodes, External Path Length = Internal Path Length +
log2n.
2.2 Implementation of priority queue using list is advantageous than that using array.
2.3 In a Circular linked list 1 can traverse the list backward.
2.4 For an ordered data set, partition exchange sort is better than bubble sort.
2.5 If the hash table is maintained in external storage on a disk, time is the critical factor for
hashing.
2.6 Queues can be created by setting up an ordinary contiguous array to hold the items.
2.7 In an expression tree, leaves at the last level are either operands or operators.
2.8 Recursive algorithms always terminate without any condition.
2.9 In-fix expression can be converted to post-fix expression using a data structure called
stack.
2.10Automatic variables can be declared within any block and remain in existence until the
block is terminated.
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 Interpolation search A. * - * + - / ABCDEAC
3.2 Stack B. Expression valuation
3.3 Prefix notation of A/B-C+D*E-A*C C. Identity Matrix
3.4 Matrix in which many of the entries are zero D. log logn
3.5 Binary tree with nodes having either empty left
sub-tree or empty right sub-tree
E. - + - / ABC * DE * AC
3.6 Heaps F. Iterative procedure
3.7 LRV(L=Left sub-tree, R=right sub-tree,
V=roots)
G. calloc
3.8 Adjacency matrix H. one –ary tree
3.9 Stable sorting function I. Sparse Matrix
3.10 Dynamic memory allocation J. Priority Queue
K. Skewed Binary tree
L. In-order traversal
M. Post-order traversal
N. Merge Sort
O. Bubble Sort
P. realloc
Q. log n
R. directed graph
B2.1-R3 Page three of five July, 2006
4. every statement beneath has a blank space to fit 1 of the word(s) or phrase(s) in
the list beneath. Enter your option in the “tear-off” ans sheet attached to the
ques. paper, subsequent instructions therein. (1 x 10)
A. Degree H. front=0, rear= n-1 O. n+1
B. n log n I. n P. Dangling pointer
C. one J. two Q. Maximum
D. n2 K. Call by reference R. Call by value
E. three L. Free space S. minimum
F. front= rear = 0 M. -1
G. level N. 2e
4.1 During initial creation of heap, root contains __________ element.
4.2 The number of sub-tree of a node is called its __________.
4.3 In hashing, collision and overflow occurs simultaneously when the bucket size is ______.
4.4 In a circular queue, initial condition provided is __________.
4.5 If unsorted file contains n numbers line ranging from 100–999, then the number of passes
needed to sort the file using radix sort is ________.
4.6 Passing a structure to a function can be performed by _________.
4.7 Suppose in the subsequent union definition
union
{
int a;
char b;
}item;
int requires two bytes and char requires one byte. Number of bytes allocated to item will be
______.
4.8 If p is a pointer and if free(p) is executed, p will create ______.
4.9 For a connected, undirected graph G with n vertices and e edges, the sum of degrees of
vertices is ______.
4.10Empty queue is represented by the queue in which rear = _____.
B2.1-R3 Page four of five July, 2006
PART TWO
(Answer any 4 questions)
5.
a) What do you mean by Performance analysis? elaborate the other criteria for judging
programs?
b) Suppose you have an array of number denoted by num[ ]. Write the iterative and recursive
procedure to obtain the sum of 1000 elements. What is the space requirement in both the
cases?
(7+8)
6.
a) What is a circular list? Write an algorithm for inserting a node at the front.
b) Suppose you are provided two polynomials. Represent the polynomial in a suitable data structure
and write an algorithm/ function to add two polynomials.
(6+9)
7.
a) What is a binary tree? Write down various properties of a binary tree.
b) Write down the iterative algorithm for in-order traversal of a binary tree. What will be the
performance analysis of the algorithm?
(6+9)
8.
a) Write the algorithm of sorting a set of numbers in descending order using Straight
selection sort. Analyze the algorithm.
b) Show the steps of sorting the subsequent sequence.
25 57 48 37 12 92 86 33
in ascending order using quick sort method.
(6+9)
9.
a) What is hashing? provide the characteristics of hash function. Name various hash
functions.
b) elaborate the various methods of handling overflow in hashing?
(8+7)
B2.1-R3 Page five of five July, 2006

Earning:   Approval pending.