NIELIT A Level July, 2014
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)
1.1 If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the
expected number of collisions involving a particular key x is :
A) less than 1
B) less than n
C) less than m x n
D) less than 2xn
1.2 Let A be an adjacency matrix of a graph G. The ijth entry in the matrix AK , gives
A) The number of paths of length K from vertex Vi to vertex Vj
B) Shortest path of K edges from vertex Vi to vertex Vj
C) Length of a Hamiltonian cycle from vertex Vi to vertex Vj
1.3 The Operating System of a computer may periodically collect all the free memory space to form
contiguous block of free space. This is called
A) Concatenation
B) Garbage collection
C) Collection
D) Dynamic Memory Allocation
1.4 You have to sort a list L consisting of a sorted list followed by a few “random” elements. Which
of the following sorting methods would be especially suitable for such a task?
A) Insertion sort
B) Selection sort
C) Quick sort
D) All the above
1.5 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
A6-R4 Page 2 of 5 July, 2014
1.6 The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is
A) 6
B) 5
C) 7
D) 8
1.7 The complexity of multiplying two matrices of order mxn and nxp is
A) mnp
B) mp
C) mn
D) np
1.8 A full binary tree with 2n+1 nodes contain
A) n leaf nodes
B) n non-leaf nodes
C) n-1 leaf nodes
D) n-1 non-leaf nodes
1.9 A binary tree in which if all its levels except possibly the last, have the maximum number of
nodes and all the nodes at the last level appear as far left as possible, is known as
A) Full binary tree
B) AVL tree
C) Threaded tree
D) Complete binary tree
1.10 Consider a linked list of n elements. What is the time taken to insert an element after an element
pointed by some pointer?
A) O (1)
B) O (log2 n)
C) O (n)
D) O (n log2 n)
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 A mathematical model with a collection of operations defined on that model is called Algorithm.
2.2 Stack data structure is used to perform recursion.
2.3 A tree is an example of list.
2.4 A binary tree of height 3 could contain 20 nodes.
2.5 Minimum number of queues needed to implement the priority queue is two.
2.6 B–trees are for primary indexes and B+ trees are for secondary indexes.
2.7 The best data structure to check whether an arithmetic expression has balanced parentheses is
queue.
2.8 A technique for direct search is hashing.
2.9 In a circular linked list forward and backward traversal within the list is permitted.
2.10 Queue data structure is required for Breadth First Traversal on a graph.
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 Searching method (O(1)) A. Hash table
3.2 Quick Sort B. Right to left digits
3.3 Matrix multiplication C. O(log n)
3.4 A binary tree with n nodes D. V – 1
3.5 Order of binary search E. O(n3)
3.6 Application of queue F. Divide and Conquer
3.7 One source many destination G. Radix sort
3.8 Symmetric adjacency matrix H. n -1 edges
3.9 Radix sort I. Linear data structures
3.10 No. of edges in a minimal spanning J. Dijkstra’s algorithm
tree of vertices V
K. Undirected graph
L. n edges
M. Merge 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. 2n B. 2n+1 – 1 C. 168
D. Rotation E. n + 1 F. Linear data structure
G. Divide and Conquer H. Stack I. Out degree
J. Heap Sort K. Leaf L. 1
M. Merge sort
4.1 Stack and queue are ________.
4.2 A binary tree of height n can have a maximum of ________ nodes.
4.3 Depth First Search (DFS) is implemented using ________.
4.4 For balancing a tree we use ________.
4.5 For a graph with n edges, the sum of degrees of all vertices is ________.
4.6 The maximum balance factor that a height balanced tree can have is ________.
4.7 ________ Sorting technique has makes use of binary tree.
4.8 Merge sort uses ________.
4.9 Given an array X[6][6] whose base address is 100. If each elements occupies 4 bytes and array
is stored row wise, then location X[2][5] is ________.
4.10 For a directed graph, row sum of adjacency matrix is ________.
PART TWO
(Answer any FOUR questions)
5.
a) What is an algorithm? What are the characteristics of a good algorithm?
b) How do you find the complexity of an algorithm? What is the relation between the time and
space complexities of an algorithm? Justify your answer with an example.
c) What are circular queues? Write down routines for inserting and deleting elements from a
circular queue implemented using arrays.
(4+4+7)
6.
a) Explain an efficient way of storing a sparse matrix in memory. Write a module to find the
transpose of a sparse matrix stored in this way.
b) Two linked lists contain information of the same type in ascending order. Write a module to
merge them to a single linked list that is sorted.
c) What are expression trees? Represent the following expression using a tree. Comment on the
result that you get when this tree is traversed in Preorder, Inorder and postorder.
(a-b) / ((c*d)+e)
(4+4+7)
7.
a) Write an algorithm for finding solution to the Tower’s of Hanoi problem. Explain the working of
your algorithm (with 4 disks) with diagrams.
b) What is a Binary Tree? What is the maximum number of nodes possible in a Binary Tree of
depth d. Explain the following terms with respect to Binary tree.
i) Strictly Binary Tree
ii) Complete Binary Tree
c) What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers.
45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48. Traverse the tree in Preorder, Inorder and
postorder.
(5+5+5)
8.
a) Bubble sort algorithm is inefficient because it continues execution even after an array is sorted
by performing unnecessary comparisons. Therefore, the number of comparisons in the best and
worst cases are the same. Modify the algorithm in such a fashion that it will not make the next
pass when the array is already sorted.
b) Write a function to find out the maximum value and the second maximum value in an array of
integers. Write the time complexity of your function.
c) Write an algorithm to merge two sorted arrays into a third array. Do not sort the third array.
(5+5+5)
A6-R4 Page 5 of 5 July, 2014
9.
a) Write an algorithm for binary search. What are the conditions under which sequential search of
a list is preferred over binary search?
b) Obtain the shortest path for the following graph using Dijkstra's algorithm and explain the step
by step procedure.
c) Write short notes on the following:
i) Threaded binary trees
ii) Graph traversal
(5+5+5)
No comments:
Post a Comment