NIELIT A Level January, 2015
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)
in the queue ,if FRONT =10 and REAR =3,will be
A) 3
B) 4
C) 5
D) 6
1.2 +/-MNP^+QR-UV is the prefix equivalent of
A) M-N/P+Q+R^U-V
B) MN-P/QR+UV-^+
C) MNP/-Q+R^UV-+
D) None of the above
1.3 What does the following code segment do?
void fn( ){
char c;
cin.get(c);
if (c != ‘\n’) {
fn( );
cout.put(c);
}
}
A) The string entered is printed as it is.
B) The string entered is printed in reverse order.
C) It will go in an infinite loop.
D) It will print an empty line.
A6-R4 Page 2 of 6 January, 2015
1.4 If a node having two children is deleted from a binary tree, it is replaced by its
A) Inorder predecessor
B) Inorder successor
C) Preorder predecessor
D) None of the above
1.5 Consider a linked list of n elements. The time taken to insert an element after an element
pointed by some pointer is
A) O (1)
B) O (log2 nı)
C) O (n)
D) O (n log2 nı)
1.6 Following the heapify operation on the list: 3, 96, 62, 24, 55, 29, 78, the order (left to right) of the
values in the leaves
A) 24, 29, 3, 62, 78
B) 3, 24, 55, 29, 62
C) 3, 24, 29, 62
D) None of the above
1.7 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.8 Using linear probing to resolve collision when applying the hash function (key %10) to the
following keys: 1, 15, 75, 81, 65, 32, 120, 19, 156, 23, the order of the storage of entries is
A) 1, 15, 19, 23, 32, 65, 75, 81, 120, 156
B) 120, 1, 81, 32, 23, 15, 75, 65, 156, 19
C) 1, 15, 75, 81, 65, 32, 120, 19, 156, 23
D) None of the above
1.9 Given the inorder sequence, A, C, E, F, G, H, and the following binary trees,
Which of the given trees corresponds exactly with the given inorder sequence:
A) I, II
B) II, III
C) I, II, III
D) None of the above
A
F
C H
E G
H
F
E
C
G
E
A
C
G
F H
A
I II. III
1.10 The program section:
int **p;
p = calloc(5, sizeof(int));
for(i=0; i<5; i++)
p[i] = calloc(10, sizeof(int));
is equivalent to the declaration:
A) int p[5][10];
B) int p[10][5];
C) int p[5][5];
D) int p[10][10];
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)
in successive rehashes is called secondary clustering.
2.2 In a linked list, the logical order of the elements is determined by the physical arrangement of
the elements.
2.3 +AB*/CD-%EF equals (A+B*C)/D-E%F.
2.4 The maximum number of nodes on level ‘l’ of a binary tree is 2l-1.
2.5 The straight selection sort implements the descending priority queue as an unordered array.
2.6 For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is
equal to 2e.
2.7 The searching technique that takes O (1) time to find an element from a set is Linear Search.
2.8 If a node in a BST has two children, then its inorder predecessor has no right child.
2.9 For a large table of size l, the average number of probes required for a successful retrieval in a
table organized using linear rehashing is approximately (2*l – n+1)/(2*l – 2*n+2), where
n = number of items currently in the table.
2.10 Friend keyword can be used on main().
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)
X Y
3.1 The phenomenon where two keys that hash into A. Array
different values compete with each other in
successive rehashes
3.2 Diagonal of an adjacency matrix has all ones B. Front = Rear
3.3 Empty condition in a queue C. Graph has self loops
3.4 A digraph in which the out degree equals the in D. Primary clustering
degree
3.5 Allows direct access of elements E. Symmetric
3.6 Radix sort [‘m’ digits and ‘n’ elements] F. Internal path length
3.7 You have to sort a list L consisting of a sorted list G. External path length
followed by a few “random” elements. Which of the
following sorting methods would be especially
suitable for such a task?
3.8 Sum of all the levels of all the nodes in a binary tree H. O(100)
3.9 Merging 4 sorted files containing 50, 10, 25 and 15 I. Inheritance
records will have time
3.10 The process of building new classes from existing J. O(200)
K. Secondary clustering
L. Linked list
M. Insertion sort
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)
A. Linear Probing B. Stack C. (2p+1-1)
D. Better E. O(1) F. 2(p-1)
G. Queue H. 10 I. 5
J. O(n2) K. Heap L. O(log2log2n)
M. 1
4.1 The maximum number of nodes in a binary tree of depth ‘p’ is ________.
4.2 Time complexity of interpolation search having n elements is ________.
4.3 In the implementation of priority queues using linked lists, insertions at the front can be done in
________ time.
4.4 The ________ function may be applied successively until an empty position is found where an
item may be inserted, on the occasion of a hash collision.
4.5 New operators allocate memory blocks from the _______.
4.6 Algorithm A requiring n2 days is _______ than Algorithm B requiring n3 secs, to solve a
problem, for n=106.
4.7 The number of binary trees with 3 nodes which when traversed in post order gives the sequence
A, B, C is _______.
4.8 The number of swapping needed to sort numbers 8, 22,7,9,31,19,5,13 in ascending order using
bubble sort is _______.
4.9 The data structure used in traversing a given graph by breadth first search is _______.
4.10 In a balanced binary tree the height of two sub-trees of every node can not differ by more than
_______.
PART TWO
(Answer ANY FOUR questions)
5.
a) What do you mean by time complexity and space complexity of an algorithm?. Suppose youhave two functions n2 and 2n/4 for various values of n. Determine when second becomes larger
than first.
b) Sort the following sequence of keys using merge sort.
66, 77, 11, 88, 99, 22, 33, 44, 55.
Show the results at each step.
([4+4] +7)
6.
a) Write an algorithm for polynomial representation and addition using linked list.
b) The following values are to be stored in a hash table
25, 42, 96, 101, 102, 162, 197
Describe how the values are hashed by using division method of hashing with a table size of 7.
Use chaining as the method of collision resolution.
(7+8)
7.
a) Write an algorithm to simulate the deletion of a node, at any position, in a circular doubly linked
list. Clearly state assumptions, if any.
b) What is an AVL tree? Show the steps required to balance the following tree:
(7+8)
8.
a) What is a thread? What are the rules to construct a threaded binary tree?
b) Construct the binary tree, with respect to the following traversals of the tree.
INORDER : H K D B I L E A F C M J G
PREORDER : A B D H K E I L C F G J M
(8+7)
45
B K
H
G
M
N
P
Z
P
A6-R4 Page 6 of 6 January, 2015
9.
a) What is a minimum Spanning tree of a graph? Apply Kruskal’s algorithm to find the
minimum.spanning tree of the following graph:
b) Write an algorithm to evaluate Postfix expression with the help of a stack.
(9+6)
No comments:
Post a Comment