DOEACC Society 2005 DOEACC A Level Data Structure Through C Lanaguage  Question Paper
A6R3: DATA STRUCTURES THROUGH C LANGUAGE
NOTE:
1. There are TWO PARTS in this Module/paper. PART ONE contains FOUR questions and PART TWO contains FOUR questions.
2. PART ONE is to be answered in the TEAROFFANSWER SHEET only, attached to the question paper, as per the instructions contained therein. PART ONE is NOT to be answered in the answer book.
3. Maximum time allotted for PART ONE is ONE HOUR. Answer book for PART TWO will be supplied at the table when the answer sheet for PART ONE is returned. However, candidates who complete PART ONE earlier than one hour, can collect the answer book for PART TWO immediately after handing over the answer sheet for PART ONE.
TOTAL TIME: 3 HOURS TOTAL MARKS: 100
(PART ONE40; PART TWO 60)
PART ONE
(Answer all the questions)
1. Each question below gives a multiple choice of answers. Choose the most appropriate one and enter in the tearoff answer sheet attached to the question paper, following instructions therein. (1 x 10)
1.1 A linear collection of data elements where the linear node is given by means of pointer is called:
A) linked list
B) node list
C) primitive list
D) none of these
1.2 p is a pointer to the structure. A member mem of that structure is referenced by
A) *p.mem
B) (*p).mem
C) *(p.mem)
D) none of these
1.3 Which of the following cannot be performed recursively?
A) binary Search
B) quick sort
C) depth First Search
D) none of the above
1.4 Which of the following data structure may give overflow error, even though the current number of elements in it is less than its size?
A) stack
B) circular queue
C) simple queue
D) none of the above
1.5 An adjacency matrix representation of a graph cannot contain information of
A) nodes
B) edges
C) direction of edges
D) parallel edges
1.6 Which of the following is a hash function?
A) floding
B) quadratic probing
C) chaining
D) open addressing
1.7 Number of all possible binary trees with 4 nodes is
A) 14
B) 34
C) 24
D) none of the above
1.8 n elements of the queue are to be reversed using another queue. The number of ADD and REMOVE required to do so is
A) 2*n
B) 4*n
C) n
D) the task can not be accomplished
1.9 If the inorder preorder traversal of a binary tree are D,B,F,E,G,H,A,C and A,B,D,E,F,G,H,C respectively then
A) D,F,G,A,B,C,H,E
B) F,H,D,G,E,B,C,A
C) D,F,H,G,E,B,C,A
D) C,G,H,F,E,D,B,A
1.10 A stack cannot be used to
A) evaluate an arithmetic expression in postfix form
B) implement recursion
C) convert infix form to postfix from of an expression
D) allocate resources by operating system
2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the tearoff sheet attached to the question paper, following instructions therein. (1 x 10)
2.1 The averagecase timing analysis is generally more difficult than the worstcase 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 preorder the postorder traversal sequence uniquely defines 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 first search.
2.9 A graph represents many to many relationships between 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 closest related meaning/ word(s)/phrases in column Y. Enter your selection in the tearoff answer sheet attached to the question paper, following 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 defined at logical level 
C. 
Stack 
3.4 
Vertex with no incident edges 
D. 
Depthfirst 
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 type 
3.10 
Preorder traversal 
J. 
Adjacency multilist 


K. 
Radix sort 


L. 
Linked list 
4. Each statement below has blank space to fit one of the word(s) or phrases in the list below. Enter your choice in the tearoff answer sheet attached to the question paper, following instructions therein. (1 x 10)
A. 
Insertion 
B. 
deletion 
C. 
stack 
D. 
queue 
E. 
linked list 
F. 
12 
G. 
2 
H. 
1 
I. 
Log_{2}n 
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 first 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 Btree of order 24 contains at least _______ keys in norroot node.
4.5 Total number of nodes required 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 one leaf node in each 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 required 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 FOUR questions)
5.
a) Write an algorithm to add and multiply two large integers, which cannot be represented by builtin types.
b) Write a c function to find recursively the maximum and minimum element of an array A of size n elements. Find also the number of comparisons required for this.
(6+9)
6.
a) How do you represent a stack and a queue by using onedimensional 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. Give 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 subgraph. Give 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 following 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 find out whether there is a path between any two vertices in a graph.
(8+7)
Earning: Approval pending. 