A6-R3: DATA STRUCTURES THROUGH “C” LANGUAGE
: JULY 2005

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 TEAR-OFFANSWER 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 ONE-40; 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 “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

1.1 In linked list, there are no NULL links in
A) Singly linked list
B) Linear doubly linked list
C) Circular linked list
D) None of the above

1.2 The nth element from the top of the stack S is accessible as
A) S[TOP – n]
B) S[TOP + n]
C) S[TOP – n – 1]
D) None of the above

1.3 If “ABC”, “XXX” and “PQR” are elements of a lexically ordered binary tree then the node which will be traversed first in Preorder is
A) ABC
B) XXX
C) PQR
D) Unpredictable

1.4 A balanced binary tree is a binary tree in which the heights of the two subtrees of every node never differ by more than
A) 2
B) 1
C) 0
D) None of the above

1.5 The result of evaluating prefix expression * / b + – d a c d where a = 3, b = 6, c = 1 and d = 5 is
A) 8
B) 5
C) 10
D) None of the above

1.6 In the array representation of binary tree, the right child of root will be at location of
A) 3
B) 2
C) 5
D) None of the above

1.7 The total number of comparison in bubble sort is
A) O (n2)
B) O (2n)
C) O (nlogn)
D) None of the above

1.8 A dummy header in the linked list contains
A) first record of actual data
B) last record of actual data
C) pointer to the last record of actual data
D) None of the above

1.9 Write the output of the following program.
int a[ ]={1, 2, 3}, *p;
p = &a[0]; printf(“%d”, *(p+3));
A) 3
B) Junk value
C) Runtime error
D) Address of third element

1.10 If the outdegree of Every node is exactly equal to m or 0 and the numbers of nodes at level k is m k – 1 (consider root at level 1) then tree is called as
i) Full m-ary Tree
ii) Complete m-ary Tree
iii) Positional m-ary Tree.
A) Only i)
B) Only iii)
C) Both i) & ii)
D) Both ii) & iii)

2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “tear-off” sheet attached to the question paper, following instructions therein. (1 x 10)

2.1 Selection sort technique is better than quick sort.
2.2 The Unicode format of character representation uses 16 bits.
2.3 Peep operation is used to insert an element on the top of stack.
2.4 Linear probing is a technique used to resolve hash clashes.
2.5 Reverse traversal of list is possible in circular inked list.
2.6 In postorder traversal of tree, the root node is visited at last.
2.7 in Dequeue the insertion need not occur at the rear end of the queue.
2.8 Recursion is an application of linked list.
2.9 The straight selection sort technique has the efficiency of O(n).
2.10 Dynamic hashing is used to reduce space required by the hash table.

3. Match words and phrases in column X with the closest related meaning/ word(s)/phrases in column Y. Enter your selection in the “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

X Y
3.1 Diminishing increment shot A. Static memory allocation
3.2 Root B. Shell sort
3.3 Structure in 'C' C. Cycle
3.4 Array D. Sequence set
3.5 Path from node to itself E. Indegree 0
3.6 Separate chaining F. Quick sort
3.7 Linked list of leaves in B+ trees G. Collection of heterogeneous data types
3.8 Two dimensional array of arcs H. Adjacency path
3.9 Tower of Hanoi I. Hash table
3.10 Queue J. Adjacency matrix
K. Sequence list
L. Application of queue
M. FIFO
N. LIFO
O. Application of stack

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 “tear-off” answer sheet attached to the question paper, following instructions therein. (1 x 10)

A. mixed graph B. tree C. digraph
D. forest E. hashing F. malloc( )
G. O(n2) H. indegree I. free( )
J. head K. O(log n) L. outdegree
M. ascending N. preorder successor 2n-1-1
P. 2n-1-1 Q. descending R. chaining

4.1 _________ is an acyclic graph in which every node has one or no predecessors.
4.2 In right pre – threaded binary trees, the NULL right pointer of node is replaced by _________.
4.3 In two’s complement notation, given n bits the largest number that can be represented is _________.
4.4 In _________ priority queue, items can be inserted arbitrarily but deletion of only the largest item is allowed.
4.5 The graph in which pairs on nodes that makes up the arcs are ordered pairs, the graph is called as _________ graph.
4.6 The _________ of a node n is the number of arcs that have n as the head.
4.7 The efficiency of depth first traversal is _________ for the adjacency matrix graph representation.
4.8 _________ is the hash collision resolution technique in which, secondary hash function is successively applied on the hash key of the item until empty position is found.
4.9 The C function for dynamic memory allocation is _________.
4.10 The time required to search a binary tree is _________. For more questions papers visit www.DoeaccOnline.com, www.IgnouOnline.com

PART TWO
(Answer ALL questions)

5. Define algorithm. Explain the space and time complexity of the algorithm with an example.
(15)

6. a) What is linked list? Write a ‘C’ function to delete every alternate node starting with first node (i.e. first, third, fifth and so on) in a singly linked list.
b) Define hash functions. Explain the Division method, Mid square method and Folding method of hash functions.
(7+8)

7. a) Write a note on priority queue by giving suitable example.
b) Write a C function to evaluate a postfix expression using stack.
(7+8)

8. a) Consider the following values sorted in an array. Sort it in ascending order using Bubble sort technique showing all the iterations:
15, 43, 5, 18, 27, 3, 10
Also write a C function to sort one dimensional integer array in ascending order using Bubble Sort technique.
(15)

9. Explain Kruskal’s algorithm for generating minimum cost spanning tree.
(15)

10. Define B tree. Explain the insertion operation of B tree with example.
(15)