DOEACC Society 2007 Advanced Level Course In Computer Science A6-R3: DATA STRUCTURES THROUGH ‘C’ LANGUAGE - Question Paper

2.1 The average-case timing analysis is generally more difficult than the worst-case timing analysis
2.2 Binary search performs efficiently on a linked list.
2.3 Any general tree can be converted to a binary tree.
2.4 A pre-order the post-order traversal sequence uniquely describes a tree.
2.5 Merge sort is not a stable sorting algorithm.
2.6 A tree is also a graph.
2.7 Quick soft will be more efficient, if the table to be sorted in initially almost sorted.
2.8 Stack is useful for implementing breadth 1st search.
2.9 A graph represents many to many relationships ranging from nodes.
2.10 Insertion of a new element in a priority queue always occurs at the rear of the quque, irrespective of its priority.

3. Match words and phrases in column X with the nearest related meaning/ word(s)/phrases 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 Partition exchange sort A. Fibonacci tree
3.2 Used in sparse matrix B. Rehashing
3.3 Data structure as described at logical level C. Stack
3.4 Vertex with no incident edges D. Depth-first
3.5 Collision resolution E. Theta notation
3.6 Data structure for backtracking F. Quick sort
3.7 Most sparse AVL tree G. Isolated vertex
3.8 Graph representation H. Circular list
3.9 Complexity measurement I. Abstract data kind
3.10 Pre-order traversal J. Adjacency multilist
K. Radix sort
L. Linked list














4. Each statement beneath has blank space to fit 1 of the word(s) or phrases 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. Insertion B. deletion C. stack
D. queue E. linked list F. 12
G. 2 H. 1 I. Log2n
J. one by one K. doubly linked list L. n+2*e
M. 2*d N. 2*d – 1 O. 2*d + 1
P. ordered set Q. 24

4.1 _______ data structure is used to implement dynamic storage management.
4.2 Copying all or part of a linked list is node by taking 1st null list and inserting elements _______.
4.3 Time complexity of inserting an element to heap of “n” elements is of the order of _______.
4.4 A B-tree of order 24 contains at lowest _______ keys in nor-root node.
4.5 Total number of nodes needed to represent an undirected graph with “n” nodes and “e” edges using adjacency list representation is _______.
4.6 Let a binary tree be such that there is exactly 1 leaf node in every level of the tree (expect at level 1). The number of nodes in such a tree of depth “d” is _______.
4.7 Minimum number of comparisons that may be needed to search a key in a binary search tree is _______.
4.8 List is a/an _______ of elements.
4.9 Linked list is preferred over an array of _______ operation.
4.10 A tree can be traversed level wise using _______.



















PART TWO
(Answer any 4 questions)

5.
a) Write an algorithm to add and multiply 2 large integers, which cannot be represented by built-in kinds.
b) Write a “c” function to obtain recursively the maximum and minimum element of an array A of size “n” elements. obtain also the number of comparisons needed for this.
(6+9)

6.
a) How do you represent a stack and a queue by using one-dimensional array?
b) Write “c” functions for pushing into or popping from a stack.
c) Write “c” functions for adding an element to a queue and removing an element from a queue.
(3+6+6)

7.
a) Define directed and undirected graphs. provide examples. Show that the sum of degrees of all vertices in an undirected graph is twice the number of edges.
b) Define weighted graph and sub-graph. provide examples.
c) Show that the number of vertices of odd degree in a finite graph is even.
(8+4+3)

8.
a) Show that a tree with “n” nodes has exactly (n – 1) edges.
b) Prove that a binary tree with “n” internal nodes has (n + 1) external nodes.
c) If “E” and “I” denote the external and internal path lengths of a binary tree having “n” internal nodes then the subsequent identity holds
E = I + 2*n.
(4+5+6)

9.
a) Determine with the help of an example whether the initial order of elements is preserved in the case of bubble sort.
b) Write a “c” function to sort a list of integers using insertion sort technique where the list is represented through links using pointers.
(7+8)

10.
a) Write a “c” function to generate the incidence matrix of a graph from its adjacency matrix.
b) Write a “c” function to obtain out whether there is a path ranging from any 2 vertices in a graph.
(8+7)

Earning:   Approval pending.