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

push(1), push (2), pop, push(1), push(2), pop, pop, pop, push(2), pop.
The sequences of popped out values are
A) 2, 2, 1, 2, 1
B) 2, 2, 1, 1, 2
C) 2, 1, 2, 2, 1
D) 2, 1, 2, 2, 2
C2-R3 Page two of six January, 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 All primitive recursive functions can be solved iteratively.
2.2 Breadth – 1st search algorithm can only be used for undirected graph.
2.3 De-referencing operator * has the identical effect when it is applied to a pointer or to a
structure.
2.4 Binary search performs efficiently on a linked list.
2.5 A symbol table can be constructed using binary tree.
2.6 A pre-order and post-order traversal sequence uniquely describes a tree.
2.7 If an undirected graph is of “n” vertices and “e” edges then the sum of degrees of all vertices
is 2e.
2.8 The adjacency matrix corresponding to a graph consisting of “n” nodes but no edges is a
unit matrix.
2.9 Recursion cannot be removed without using a stack.
2.10Pointers are used for dynamically allocated memory.
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 Order notation A. Stack
3.2 trend matching B. Dynamic storage allocation
3.3 Dynamic data structure C. Two’s compliment
3.4 Height Balanced Trees D. Primitive data kind
3.5 Data structure for back tracking E. Finite automata
3.6 Circular list with “head” pointing to the last
node
F. Adjacency list
3.7 Suitable data structure for efficiently computing
adjacent vartices of a provided vertex
G. Adjacency matrix
3.8 Partition exchange sort H. AVL Trees
3.9 Stable sorting Algorithm I. Adjacency multi list
3.10 Unique representation for zero J. Queue
K. Tree
L. Breadth – first
M. Depth – first
N. Quick sort
O. merge sort
P. Complexity measurement
C2-R3 Page three of six January, 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. circular queue B. stack C. simple queue
D. band E. sparse F. many-to-many
G. one-to-many H. depth-first-search I. breadth-first search
J. log2 n K. n log2 n L. E / (n + 1)
M. Insertion N. Log2 n + one O. recursive
P. Compaction Q. N
4.1 Matrices in which non-zero entries tend to cluster around the middle of every row are
called __________ matrix.
4.2 A graph represents ________ relationship ranging from nodes.
4.3 ___________ can be used to obtain the shortest distance ranging from provided 2 nodes in a
graph.
4.4 Time complexity of inserting an element to a heap of “n” elements is of the order of
_________.
4.5 If “E” is the total external length of a binary tree with “n” nodes then avg. number of
comparisons for unsuccessful search is ________________.
4.6 _________ data structure may provide overflow error, even though the current number of
elements in it is less than its size.
4.7 Conversion of infix arithmetic expression to prefix expression requires the use of
__________.
4.8 The minimum number of edges in a connected cyclic graph of “n” vertices is_________.
4.9 Linked list is preferred over an array for _________ operation.
4.10 Recursion often provides elegant solution to programming task but _______ function
chew up a lot of memory.
C2-R3 Page four of six January, 2006
PART TWO
(Answer any 4 questions)
5.
a) elaborate the limitations of array data structure?
b) Show with the help of an example, how the above limitations can be avoided by “linked”
representation of lists?
c) Show the representation of linked lists using arrays.
d) What do you mean by linear list and generalized list?
(4+4+4+3)
6.
a) Write a “C” function to copy 1 stack to a different assuming the stack is implemented using
array.
b) Write an algorithm to evaluate Postfix expression with the help of a stack.
(8+7)
7.
a) Write a “C” function to implement the Knuth Mooris Pratt algorithm for string searching.
b) A function A(m,n) is described as follows.
A(m,n) = n + 1, if m = 0
= A ( m – 1, 1), if n = 0
= A(m – 1, A(m, n-1)), otherwise
write a recursive “C” function to calculate A(m,n)
(8+7)
8.
a) Prove that the maximum number of nodes in a binary tree of height “k” is 2k+1-1.
b) Consider the subsequent binary tree
Indicate the output in the subsequent cases: -
i) When the tree is traversed in an “inorder” fashion.
ii) When the tree is traversed in an “preorder” fashion.
iii) When the tree is traversed in an “Postorder” fashion.
(6+[3×3])
C2-R3 Page five of six January, 2006
9.
a) Show with the help of an example that the simple selection sort is not data sensitive.
b) obtain the time complexity of the simple selection sort.
c) Write a recursive “C” function to implement binary search.
(6+3+6)
10.
a) Write a “C” function to calculate the in-degree and out-degree of a vertex of a directed graph
when the graph is represented by an adjacency list.
b) What is a spanning tree? What do you mean by minimal spanning tree?
(9+[3+3])
C2-R3 Page six of six January, 2006

Earning:   Approval pending.