NIELIT A Level July, 2010
A6-R4: DATA STRUCTURE 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 “tear-off” answer sheet attached to the question paper, following instructions therein. (1x10)
in the worst case by the merge sort algorithm will be
A) m*n
B) maximum of m, n
C) minimum of m, n
D) m + n –1
1.2 The postfix equivalent of the prefix * + ab – cd is
A) ab + cd – *
B) abcd + – *
C) ab + cd* –
D) ab + – cd*
1.3 Which of the following statements are true in case of Depth-First-Traversal?
i) DFS is used to determine connected components of an undirected graph.
ii) DFS is used to determine acyclic nature of a graph.
A) only i) is true
B) only ii) is true
C) both i) & ii) are true
D) both i) & ii) are false
1.4 Structure in C++ is a/an
A) user defined data type
B) ADT
C) both A) and B)
D) none of the above
1.5 What is the balancing condition of an AVL tree?
A) Height factor between +2 and –2
B) Height factor between +1 and –1
C) Height factor between 0 and –1
D) None of the above
A6-R4 (New) Page 2 of 5 July, 2010
1.6 The initial configuration of a queue is a, b, c, d (a is in the front of queue). To get the
configuration d, c, b, a one needs minimum of
A) 2 deletions and 3 additions
B) 3 deletions and 2 additions
C) 3 deletions and 3 additions
D) 3 deletions and 4 additions
1.7 A full binary tree with n leaves contains
A) n nodes
B) 2 log n nodes
C) 2n −1 nodes
D) 2n nodes
1.8 In linked list, the logical order of elements
A) is same as their physical arrangement
B) is not necessarily equivalent to their physical arrangement
C) is determined by their physical arrangement
D) none of the above
1.9 A is an array of size m* n , stored in the row major order. If the address of the first
element in the array is M, the address of the element A(i, j )( A(0,0)) is the first
element of the array and each element occupies one unit of memory location in memory
A) M (i j ) m j 1
*
+ − + −
B) M i m j * + +
C) M ( j 1) m i 1
*
+ − + −
D) M (i 1) n j 1
*
+ − + −
1.10 Which is not representation of a graph?
A) Adjacency matrix
B) Edge list
C) Adjacency list
D) None of the above
2. Each statement below is either TRUE or FALSE. Choose the most appropriate one and ENTER in the “tear-off” sheet attached to the question paper, following instructions therein. (1x10)
2.2 Worst case time complexity of the heap sort algorithm is O(n2).
2.3 Complexity expressed in O-notation is upper bound.
2.4 The first node of a linked list is pointed by a generic pointer.
2.5 Queue is useful in implementing heap sort.
2.6 A linear list that allows elements to be added or removed at either end but not in the
middle is called stack.
2.7 Linked lists are not suitable data structures for radix sort.
2.8 The adjacency matrix of an undirected graph is a unit matrix.
2.9 BFS scans adjacent unvisited vertex as soon as possible.
2.10 A simple undirected graph with eight (8) vertices is said to be complete if number of
edges equals to 54.
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 “tear-off” answer sheet attached to the question paper, following instructions therein. (1x10)
X Y
3.1 D-queue A. Height balanced tree
3.2 Time Complexity B. Graph
3.3 Inheritance C. Bubble sort
3.4 Minimal Spanning Tree D. Stack
3.5 Best case complexity of insertion sor E. Double ended queue
3.6 Column major order representation F. Preorder traversal of a tree
3.7 Mostly zero entries G. Recursion
3.8 Adjacency list H. Hashing
3.9 Merge Sort I. Worst time is O(n log n)
3.10 DFS J. Big-Oh notation
K. Building new class from an existing
classes
L. O(n)
M. O(n2)
N. Array
O. Stack
P. Hashing
Q. Prim’s algorithm
R. Sparse Matrix
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 “tear-off” answer sheet attached to the question paper, following instructions therein. (1x10)
D. linked list E. polynomial F. generic pointer
G. constant pointer H. void pointer I. graph
J. time complexity K. space complexity L. open addressing
M. hashing N. tree O. binary search tree
P. B tree Q. AVL tree R. O(n2)
S. O(nlogn) T. O(n) U. Kruskal’s Algorithm
V. Dijkstra’s Algorithm W. bfs X. dfs
4.1 The ________ of an algorithm is the amount of time the computer requires to execute
the algorithm.
4.2 Best case complexity of bubble sort is ________.
4.3 ________ is called a FIFO data structure.
4.4 ________ is a data structure where data can be represented as a chain of nodes.
4.5 Recursive functions are internally evaluated by using ________.
4.6 The declaration int const *p = &a signifies p as a ________.
4.7 ________ is a mathematical tool used to represent a physical problem.
4.8 ________ is also known as the balanced order-n multiway search tree.
4.9 ________ is an algorithm in graph theory that finds the shortest path.
4.10 ________ is a general collision resolution scheme for a hash table.
A6-R4 (New) Page 5 of 5 July, 2010
PART TWO
(Answer any FOUR questions)
5.
a) Create a class ‘shape’ and derive the classes, box, cube, cylinder from it. The class
‘shape’ has functions volume() and whole-surface-area(). Override these two functions in
each of these derived classes. The dimensions of the shapes (box, cube, cylinder) are to
be taken from user. Write a main function to test the classes.
b) Show that the function f (n) defined by
f (1) = 1
f (n) = f(n-1) + 1/n for n > 1
has the complexity O(log n).
(9+6)
6.
a) Consider an array of size 25 × 4. Base address of this array is 200 and the word size
is 4 units. The array is stored in row major form. Find the address of location A (12,3).
Also find the address of the same element assuming that the array is stored in column
major order.
b) Consider the following infix expression:
A + B * (C + D) / F + D * E
Convert the above expression in postfix form using stack.
c) Write an algorithm to delete the last element from a single linked list.
(6+6+3)
7.
a) The following keys are to be inserted in the order shown below into an AVL Tree:
25,45,50,55,60,65,75,85. Show how the tree appears after each insertion.
b) The following keys are to be inserted in the order shown below into an B-tree
(of order 5): a, g, f, b, k, d, h, m, j, e, s, i, r, x. Show how the tree appears after each
insertion.
(8+7)
8.
a) What is heap?
b) Explain with an example how to construct a heap.
c) Write an algorithm for heap sort. Also find the complexity of the algorithm.
(2+5+8)
9.
a) Explain with a suitable example, Prim’s algorithm to find the minimal spanning tree.
b) What is an ADT? For the following graph find out the Breadth First Traversal (BFS).
Show the insert and remove operations in/from the Queue ADT during the traversal in a
tabular fashion.
(7+8)
v1
v2 v3
v4
v5 v6
v7
v8
No comments:
Post a Comment