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

K. keyword
L. LIFO
M. Binary search
N. Linear search
B2.1-R3 Page three of five January, 2007
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. Floor of log n! B. Ceiling of log n! C. m+n-1
D. m+n E. 2^n F. 2^n-1
G. 2000 H. 1000/2 I. Static
J. Dynamic K. p+q L. p+q-2
M. Logical properties N. Physical properties O. Segment violation
P. Block overflow Q. AB/C**DE*+AC* R. AB/C**DEAC*+
S. Strings T. Pointers U. inorder
4.1 A sorting algorithm on n elements based on binary comparisons requires at lowest
_______ comparisons.
4.2 2 sorted lists with m elements and n elements can be merged into a sorted list using
no more than _________ comparisons.
4.3 argv an array of pointers to _________.
4.4 The minimum size of an array to store a binary tree of n levels is ________.
4.5 The number of edges in a full binary tree with 1,000 internal vertices is ____________.
4.6 An fault caused by a program trying to access memory outside its address space is
known as ________.
4.7 The storage class of a variable declared inside a function which allows retention of its
previous value is termed as _________.
4.8 An abstract data kind is a(n) __________.
4.9 Number of nodes needed to store the adjacency list of a directed graph that has “p”
vertices and ‘q’ edges is __________.
4.10 The postfix form of the expression A/B ** C + D*E- A*C is _____________.
B2.1-R3 Page four of five January, 2007
PART TWO
(Answer any 4 questions)
5.
a) Let A and B be 2 structures of kind Linked List. Write a ‘C’ function to create a new
Linked List C that contains elements alternately from A and B beginning with the first
element of A. If you run out of elements in 1 of the lists, then append the remaining
elements of the other list to C.
b) define the implementation methods insertBefore(p,e), InsertFirst(e) and InsertLast(e)
of the list ADT, assuming the list is implemented using a doubly linked list.
(8+7)
6.
a) Let A and B be 2 n x n lower triangular matrices. The total number of elements in the
lower triangles of the 2 matrices is n(n+1). Write a ‘C’ program to represent both triangles
in an array d[n+1][n].
b) Let P be of kind of linked list. Write a ‘C’ function split to create 2 linked lists Q & R. Q
contains all elements in odd positions of P and R contains the remaining elements. Your
function should not change list P. What is the complexity of your program?
(8+7)
7.
a) Write an algorithm to delete an element x from a binary search tree t. explain your method
with an example.
b) Show the outcomes of inserting the keys F, S, Q, K, C, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z,
E in order into an empty B tree.
(8+7)
8.
a) Use the bubble sort to put the numbers 3, 2, 4, 1, five into increasing order. Illustrate the
output returned in every pass clearly. Also write the pseudo algorithm to it.
b) replace bubble sort algorithm in more efficient form so that it stops when no interchanges are
needed.
(8+7)
9.
a) Suppose that a Graph G has a minimum spanning tree already calculated. How quickly can
the minimum spanning tree be updated if a new vertex and incident edges are added to G?
b) Suppose that the graph G = (V,E) is represented as an adjacency matrix. provide a simple
implementation of Prim’s algorithm for this case that runs in O(V2) time.
c) What is the running time of heap sort on an array A of length n that is already sorted in
increasing order?
(5+6+4)
B2.1-R3 Page five of five January, 2007

Earning:   Approval pending.