##
NIELIT A Level July, 2013
A6-R4: DATA STRUCTURES THROUGH ‘C++’

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 “OMR” answer sheet supplied with the question paper, following instructions therein. (1x10)

The sequence after the 3rd iteration of insertion sort is:

A) 13, 26, 52, 95, 38

B) 13, 52, 95, 26, 38

C) 13, 26, 38, 52, 95

D) 13, 26, 52, 95, 38

1.2 Given the following unbalanced tree:

Q

M

N

P

O

R

The correct balanced alternative is:

A)

B)

C)

D) None of the above

1.3 The expression + 3 * 2 * / - 3 5 4 2 equals:

A) -1

B) 5

C) 1

D) 0

M

P O

R N Q

Q

P O

R N M

N

P M

R Q O

A6-R4 Page 3 of 8 July, 2013

1.4 Considering the following circular linked list:

The possible sequence of steps leading to the deletion of B:

i) A -> next = B -> next; C -> prev = B -> prev; B = Null;

ii) A -> next = A -> next -> next; C -> prev = C -> prev -> prev; B = Null;

iii) A -> next = C -> prev; C -> prev = B-> prev; B = Null;

Which of the following options highlights the correct alternatives?

A) i), ii)

B) ii), iii)

C) i), ii), iii)

D) i), iii)

1.5 Following the heapify operation on the list: 4, 92, 65, 19, 52, 23, 75, the order (left to right) of the

values in the leaves

A) 19, 23, 4, 65, 75

B) 4, 19, 52, 23, 65

C) 4, 19, 23, 65

D) None of the above

1.6 After the second iteration of the radix sort, on the list: 107, 43, 90, 76, 34, 42, 84, 47, the order of

the elements is

A) 34, 42, 43, 47, 76, 84, 90, 107

B) 90, 42, 43, 34, 84, 76, 107, 47

C) 107, 34, 42, 43, 47, 76, 84, 90

D) None of the above

1.7 -*+ABC^-DE+FG is the prefix equivalent of

A) A+B*C-D-E^F+G

B) AB+C*DE-FG+^-

C) ABC*+D-E^FG+-

D) None of the above

1.8 Breadth First Search:

A) Scans all incident edges, before moving on to the next vertex.

B) Scans adjacent unvisited vertices, as soon as possible.

C) Same as back tracking.

D) None of the above

1.9 The necessary conditions for “queue full” and “queue empty” respectively are:

A) Full : FRONT = REAR = 0; Empty : FRONT = REAR – 1;

B) Full : FRONT = 0; (REAR + 1) = n; Empty : FRONT = REAR;

C) Full : FRONT = REAR + 1; Empty : FRONT = REAR – 1;

D) None of the above

1.10 Given a hash table, the technique of partitioning the key into several parts and combining the

parts in a convenient way (often using addition or multiplication) to obtain the index, is known

as:

A) Truncation.

B) Folding.

C) Hash – function.

D) Scatter – storage.

Head A B C

2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “OMR” answer sheet supplied with the question paper, following instructions therein. (1x10)

2.1 For a large table size, the average number of probes required for a successful retrieval in a

table organized using linear rehashing is approximately (2*tablesize – n+1)/(2*tablesize –

2*n+2), where n = number of items currently in the table.

2.2 ABCDEF may be the BFS and DFS traversals of the same binary tree.

2.3 The maximum number of nodes on level ‘l’ of a binary tree is 2l-1.

2.4 x[2][5] is equivalent to *(*(x+2)+5).

2.5 A dequeue is a queue from which items may be deleted at either end and into which elements

may be inserted at either end.

2.6 The midsquare hash function yields uniform hash values.

2.7 Insertion into a random binary search tree with n nodes requires O(log n) steps, but may

degenerate to n steps.

2.8 For a sufficiently small number of inputs, the sequential search is more efficient than the binary

search.

2.9 The Heap sort technique is far superior compared to the Quick sort in the worst case.

2.10 Structures may be passed as arguments to functions using the ‘Call by value’ technique.

3. Match words and phrases in column X with the closest related meaning/word(s)/phrase(s) in column Y. Enter your selection in the “OMR” answer sheet supplied with the question paper, following instructions therein. (1x10)

3.1 A digraph in which the outdegree equals the indegree A. O(m*n)

3.2 The height of a null tree B. Secondary clustering

3.3

Most of the table to be searched is stored in auxiliary C. Graph has no self loops

storage.

3.4 Radix sort [‘m’ digits and ‘n’ elements] D. Symmetric

3.5 Diagonal of an adjacency matrix has all zeroes E. Data structure for backtracking

3.6 Empty condition in a queue F. Front = Rear + 1

3.7 G. Ascending priority queue

Priority queue where the insertion of an element is

arbitrary, but only the smallest element can be

removed

3.8 The shell sort is also known as H. -1

3.9 Circular list I. Diminishing increment sort

3.10

The phenomenon where two keys that hash into

different values compete with each other in successive

rehashes.

J. Front = Rear

K. Asymmetric

L. External search.

M. Graphs has parallel edges

4. Each statement below has a blank space to fit one of the word(s) or phrase(s) in the list below. Enter your choice in the “OMR” answer sheet supplied with the question paper, following instructions therein. (1x10)

D. Internal E. 2 log N F. Random

G. Breadth-first-search H. One I. End

J. Contiguous K. O(n2) L. Depth-first-search

M. Quadratic

4.1 The sum, over all vertices that are not leaves, of the number of branches from the root to the

vertex equals to the ________ path length.

4.2 A sorting function is called ________ if, whenever two entries have equal keys, then these two

entries will be in the same order after the completion of the sorting algorithm, as they were

before the commencement of the sorting algorithm.

4.3 ________ probing is excellent in avoiding clustering.

4.4 Post-order traversal is also known as ________ order traversal.

4.5 The ________ traversal is naturally formulated as a recursive algorithm.

4.6 In the implementation of priority queues using linked lists, insertions at the front can be done in

________ time.

4.7 If the file size ‘n’ be small, an ________ sort is more efficient.

4.8 Evaluation of an exponential (e.g. x62) by halving the powers requires at most ________

multiplications.

4.9 The number of ________ required by a hashing scheme is the average number of table

positions that needs to be examined while searching for a particular value.

4.10 When the bucket size is ________, collisions and overflows occur simultaneously.

PART TWO

(Answer any FOUR questions)

5.a) Write a function to merge two linked lists. The input lists have their elements in sorted order

from lowest to highest. The output list should also be sorted from lowest to highest. The

algorithm should run in time on the length of the output list.

b) Write a recursive function to compute binomial coefficient. Also write down recursive algorithm

to find out the

[ ] n

m

c) If fn=amnm+......a1n+a0 then

Prove f(n)=O(nn).

(5+6+4)

6.

a) There are two arrays A having 25 elements and B having 30 elements. Write a function to

create array C that are common to A and B.

b) Suppose you have a queue of certain capacity. Write a C++ code to double the size of the

queue. What is the time complexity of the method adopted?

c) Write a linear time algorithm to reverse a list.

(4+6+5)

7.

a) Prove that for any non-empty binary tree T if n0 is the no. of leaf node and n2 no. of nodes of

degree2 then n0=n2+1.

b) What is max heap? Write a C++ code to construct a heap. Suppose you are given a set of

elements 14, 10, 20,2,15. Create a max heap. Then insert a new element 21 and show structure

of heap. Analyze the time complexity of push and pop in a heap.

(5+10)

8.

a) What is a thread? What are the rules to construct a threaded binary tree? Write a C++ function

to insert r as right child of s in a threaded binary tree.

b) Write a C++ function to traverse a tree with a queue.

(8+7)

A6-R4 Page 7 of 8 July, 2013

9.

a) Write a C++ function for depth first search under the assumption that graphs are represented

using adjacency list. Give the analysis of Depth First Search. Find the Depth First Search order

for the following graph.

b) What is a minimum cost spanning tree? Apply the Kruskal’s algorithm to find the minimum cost

spanning tree for the following graph.

14

0

1

6 2

3

4

5

10

28

24

25

18

22

16

12

0

1

3 4

7

2

5

6

A6-R4 Page 8 of 8 July, 2013

c) What is the equivalent binary tree of the following forest?

(6+6+3)

1

2 3

4 7 5 6

9

8

12

13

16

91

11