NIELIT A Level July, 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)
A) A-B/C+D+E^F-G
B) AB-C/DE+FG-^+
C) ABC/-D+E^FG-+
D) None of the above
1.2 The most efficient search technique used in an ordered array is
A) Sequential search
B) Binary search
C) Interpolation search
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.
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 The expression +3*2*/-3542
A) -1
B) 5
C) 1
D) 0
1.6 Given the sequence of numbers 13, 52, 95, 26, 38. 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, 38, 95
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 Suppose there is a set of elements 1,2,3,4,6,8 and three tree diagrams:
Which of the given trees corresponds to the BST of the above sequence:
A) I
B) II
C) III
D) None of the above
6
8
4
3
3
4
2
1
6
6
2
4
8
8 1
I II. III.
3
2
1
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)
from the same table.
2.2 In a linked list, the successive elements need not occupy continuous space in memory.
2.3 +MN*/OP-%QR equals (M+N*O)/P-Q%R.
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 Binary
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 In a queue (where rear & front pointer points to the two ends of a queue),the number of
elements at any time (rear- front-1).
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)
A B3.1 Time complexity of quicksort for an ordered array A. Array
of size ‘n’
3.2 Diagonal of an adjacency matrix has all ones B. Front = Rear
3.3 Empty condition in a queue C. Graphs has self loops
3.4 A digraph in which the out degree equals the in D. O(100)
degree
3.5 Allows direct access of elements E. Symmetric
3.6 Which type of memory allocation is suitable for F. O(n2)
recursion?
3.7 You have to sort a list L consisting of a sorted list G. Inheritance
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 H. Balanced
tree
3.9 Merging 4 sorted files containing 50, 10, 25 and I. Internal Path length
15 records will have time
3.10 The process of building new classes from existing J. Dynamic
one
K. Bubble sort
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)
D. Better E. 14 F. O(1)
G. Singly H. 10 I. 5
J. Queue K. Balanced L. O(log2log2n)
M. 1
4.1 In ________ link list there is only forward movement.
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 A digraph in which outdegree is same as indegree is called ________.
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?b) Let i and j be nonnegative integers,suppose NUM be function defined recursively as
NUM(i,j)=NUM(j,i) if i<j
=I if j=0
=NUM(j,MOD(i,j)) otherwise
Find the values of NUM(5,9),NUM(10,5)
c) 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) Design a class in C++ that will overload the binary operator + and use it to add the
corresponding elements of 2 arrays into a third array.
b) Taking an initially empty hash table with 10 locations, with hash function f(x) = x mod 10
and linear probing as the collision resolution mechanism; illustrate what happens when
we insert the following keys into it: 15,42,66,25,22,73,44
(8+7)
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) Convert the following expression from infix to postfix notation using stack:
a+b*(c*(d+e)-f)/g.
Show the contents of stack and output at each stage.
(7+8)
8.
a) With respect to a singly linked list, write an algorithm toi)
Delete a node from the end of the list
ii) Insert a node at the front of the list
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)
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.
A6-R4 Page 6 of 6 July, 2015
b) What is an adjacency matrix and adjacency list? Illustrate with an example.
c) Apply Breadth First Search technique from vertex A on the following graph and show
each step.
(7+4+4)
H
G
D
E
F
B C
A
No comments:
Post a Comment