NIELIT A Level January, 2014 A6-R4: DATA STRUCTURE THROUGH C++

NIELIT A Level January, 2014

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 “OMR” answer sheet supplied with the question paper, following instructions therein. (1x10)

1.1 If given data is already in sorted then it will be a worst case of

A) Bubble sort

B) Selection sort

C) Insertion sort

D) Quick sort

1.2 Advantage of doubly linked list over singly linked list is in

A) Addition at head

B) Addition at tail

C) Deletion at head

D) Deletion at tail

1.3 Condition of isFull() in a circular queue array implementation of size N is

A) if Front ==0 & Rear ==N-1 and Front ==Rear +1

B) if Front ==0 & Rear ==N and Front ==Rear +1

C) if Front ==0 & Rear ==N-1 and Front ==Rear -1

D) if Front ==1 & Rear ==N and Front ==Rear +1

1.4 A mathematical-model with a collection of operations defined on that model is called

A) Data Structure

B) Abstract Data Type

C) Primitive Data Type

D) Algorithm

1.5 The equivalent postfix expression of

(B+C)*(D*E – F)*G / H is

A) BC + DE*F – GH / **

B) BC + D*EF – GH / **

C) BC + DEF* – GH / **

D) None of the above

A6-R4 Page 2 of 4 January, 2014

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 Let B be an adjacency matrix of a graph G. The jkth entry in the matrix Bi , gives

A) The number of paths of length K from vertex Vi to vertex Vj.

B) Shortest path of i edges from vertex Vj to vertex Vk.

C) Length of a Eulerian path from vertex Vi to vertex Vj.

D) Length of a Hamiltonian cycle from vertex Vi to vertex Vj.

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 The number of non-zero entries in a lower triangular matrix of order nXn

A) (n(n+1)/2)

B) 2n

C) n2

D) None of the above

1.10 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) Bubble sort

B) Selection sort

C) Quick sort

D) Insertion sort

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 You can not create an object of an abstract class.

2.2 public member function of a class can not be directly accesses outside the class.

2.3 Complexity of bubble sort in worst case is O(n2).

2.4 In circular array implementation of queue more space is wasted as compared to linear array.

2.5 Hashing is used to arrange the records in a particular order.

2.6 Arrays requires contiguous block of memory.

2.7 binary search takes more time than linear search.

2.8 B-trees remain balanced after every insertion and deletion.

2.9 Constructor can be a static member of the class.

2.10 To speedup the searching of an element in a linked list, Skip Lists are used.

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 process of accessing data stored in a serial          A. Collision resolution

access memory is similar to manipulating data on

a

3.2 Depth of a complete Binary tree                               B. Standard template library

3.3 Linear search                                                             C. Static template library

3.4 FIFO                                                                          D. Queue

3.5 Quick sort                                                                 E. Log2n + 1

3.6 The best average behavior is shown by                    F. Copy constructor

3.7 Processing each element of a linked list                   G. Quick sort

3.8 STL stands for                                                          H. Bubble sort

3.9 Cannot be overloaded                                               I. O(n)

3.10 Function is designed to copy objects of the           J. Scope resolution operator

same class type?

                                                                                        K. Traversing

                                                                                        L. Stack

                                                                                       M. Divide and conquer

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. Inorder                                B. Postorder                            C. Divide and conquer

D. Preorder successor              E. Threads                              F. Derived

G. Minimum spanning tree     H. Searching                           I. Public

J. Private                                  K. Queue                                L. Array

M. Overflow

4.1 ________ traversal arranges all the keys in ascending order.

4.2 Prim’s algorithm finds ________ for connected weighted graph.

4.3 A non-recursive traversal of a tree can be written using ________.

4.4 ________ is same as recursion.

4.5 ________ members can not be inherited in derived class.

4.6 Breadth first traversal of a tree can be implemented using ________.

4.7 ________ is a linear data structure.

4.8 In linked implementation of stack no ________ condition is required unless memory is

exhausted.

4.9 Hashing is used to speedup ________.

4.10 A base class object can contain the address of ________ class object.

PART TWO

(Answer any FOUR questions)

5.

a) Design a class for circular linked list and write the following functions:

i) To display contents of this list

ii) To add a new node in the beginning

b) Write the method to find middle element of linked list only in one pass?

([2+4+4]+5)

6.

a) Design a class for binary search tree and write a function to count number of leaf nodes.

b) Draw a binary search tree for the following sequence:

50, 20, 30, 60, 65, 55, 80, 15, 8, 35, 70

What is the height of the resultant tree?

(9+6)

7.

a) Evaluate the following postfix expression using stack showing position of stack after each

step.

5 6 2 + * 12 4 / -

b) Write a program to perform binary search and search for 23 using binary search on the

following data:

35 12 45 23 29 67 97

(6+9)

8.

a) A queue is represented in memory using a circular array of size n. Write conditions to check

underflow and overflow for this circular array.

b) Take an initially empty hash table with seven slots, with hash function h(x) = x mod 7, and

with collisions resolved by chaining. Draw a sketch of what happens when inserting the

following sequence of keys into it: 45, 2, 28, 16, 13, 10, 8.

c) Find the minimum spanning tree of the given graph using Prim’s Method considering H1 as

the starting node.

(5+4+6)

9.

a) Perform Bubble Sort on the given input sequence explaining step by step process.

57 25 7 20 19 45 37 66

b) Design a class for complex number and write a program in C++ to overload binary

operator + for adding two complex numbers.

(7+8)

Next Set