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
No comments:
Post a Comment