NIELIT A Level January, 2012 A6-R4: DATA STRUCTURES THROUGH C++

NIELIT A Level January, 2012

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 “tear-off” answer sheet attached to the question paper, following instructions therein. (1x10)

1.1 Array M[5,6] is stored in memory in row-major order and base address of M =200. If there are
4 words per memory cell then address of M[2,3] is
A) 250
B) 252
C) 254
D) 256
1.2 Sparse matrices are the matrices with
A) Less proportion of zeros
B) High proportion of zeros
C) No zeros
D) None of the above

1.3 Height of the binary search tree of the given sequence 40, 30 42, 5, 7, 23, 9, 19 is (empty tree
is of height 0):
A) 4
B) 5
C) 6
D) None of the above
1.4 Which of the following data structure is used in recursion?
A) Array
B) Stack
C) Linked list
D) None of the above
1.5 The value of the postfix expression 5 2 2 + * 30 6 / - is
A) 36
B) 16
C) 15
D) None of the above

1.6 The hashing technique belongs to the following file organization method:
A) Direct File Organization
B) Sequential File Organization
C) Index sequential File Organization
D) None of the above
1.7 If i is an integer and p and q are pointers, which of the following assignments is valid?
A) p = *&i;
B) i=&*q;
C) p=&*i;
D) i= *p;
1.8 Protected member of a class in C++
A) Can be inherited by derived class but cannot be accessed directly through an object
B) Cannot be inherited by derived class but can be accessed directly through an object
C) Can be inherited by derived class and can be accessed directly through an object
D) Cannot be inherited by derived class and cannot be accessed directly through an object
1.9 f(n) is O(g(n)) if
A) There exists positive integers c and N such that f(n) cg(n) for all n N
B) There exists positive integers c and N such that f(n) cg(n) for all n N
C) There exists positive integers c and N such that f(n) cg(n) for all n N
D) None of the above
1.10 Which of the following is a method to resolve collision?
A) Chaining
B) Folding
C) Truncation
D) Division Method

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.1 A binary tree can be empty tree.
2.2 It is necessary to define a constructor in every class.
2.3 Stack is a LIFO (Last In First Out) list.
2.4 Queue is useful in implementing heap sort.
2.5 Hashing is used to arrange the records in a particular order.
2.6 The worst case complexity of quick sort is O(logn)
2.7 A binary tree is a tree in which every node can have at least two children.
2.8 Every graph is a connected graph.
2.9 Constructor can be a static member of the class.
2.10 Doubly linked list has no advantage in deletion as compared to singly linked list.

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 Binary search tree                                                                A. Stack
3.2 Contiguous memory allocation                                            B. O(1)
3.3 Finding the location of an element                                      C. O(logn)
3.4 The efficiency of Hashing Technique                                  D. Linked list
3.5 Complexity of selection sort in average case                       E. Array
3.6 Insertion and deletion can take place only from                  F. O(n)
one end
3.7 Lists used to speedup the searching process                       G. Searching
3.8 Every node in a graph is adjacent to every other                H. Traversing
node
3.9 Process of visiting each node exactly once                          I. Depth first traversal
3.10 Preorder traversal is an example of                                   J. Breadth first traversal
                                                                                                  K. Non-linear Data Structure
                                                                                                   L. Self organizing lists
                                                                                                 M. Complete

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)

A. Destructors                             B. Constructors                              C. Inorder
D. Postorder                                E. O(1)                                            F. O(n)
G. General                                  H. In order successor                       I. Header
J. Public                                      K. Private                                         L. Five
M. Sorted
4.1 A linked list with a special node is ________ linked list.
4.2 Constructors are defined in ________ section of a class.
4.3 A tree with any number of children is a ________ tree.
4.4 The left most node in right sub tree of a node is its ________.
4.5 A tree can be drawn if it’s in preorder and ________ traversal is given.
4.6 Number of binary search trees for three nodes is________.
4.7 ________ cannot be declared as virtual.
4.8 ________ members of a class cannot be inherited.
4.9 Binary search can be applied if data is ________.
4.10 If hash table acts like a linked list then the efficiency of search is ________ where size of hash
table is n.
A6-R4 Page 5 of 5 January, 2012
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).
(10+5)
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) Design a class for doubly linked list and write the following functions:
i) Write a function to insert a node at the beginning.
ii) Write a function to insert a node at the end.
(7+8)
7.
a) Design a method for simulating a Queue using stacks. Write pseudo routines for push, pop to
manipulate the stacks.
b) Write a function to print a given input string in reverse order using recursion.
c) Translate the following arithmetic expression into its equivalent infix expression showing each
step of conversion.
P: 12 7 3 - / 2 1 5 + * +
(6+6+3)
8.
a) Perform the Selection Sort on the given input sequence explaining step by step process.
27 15 4 10 19 25 37 66
b) What is heap?
c) Explain with an example how to construct a heap.
(7+2+6)
9.
a) Consider the weighted graph G given below:
Find the weight matrix of G.
b) Find a spanning tree of the graph given in a).
c) A hash function f(key)=key mod5, with linear probing is used to insert the key 27,28,34,10,40
into a hash table indexing 0 to 4. Find the location of 40.
(5+5+5)

Next Set