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

NIELIT A Level  January, 2013

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 If the address of A[1,1] and A[2][1] are 1000 and 1010 respectively and each element
occupies 2 byte of memory, then the array has been stored in
A) row major order
B) column major order
C) matrix major order
D) None of the above
1.2 One difference between a queue and a stack is:
A) Queues require dynamic memory, but stacks do not.
B) Stacks require dynamic memory, but queues do not.
C) Queues use two ends of the structure; stacks use only one.
D) Stacks use two ends of the structure, queues use only one

1.3 Number of nodes of left and right subtree of a binary tree of the given sequence 40, 30 42,
5, 7, 23, 9, 19 is:
A) 2,5
B) 1,6
C) 6,1
D) None of the above
1.4 If the characters 'A', 'B', 'C', 'D' are placed in a queue (in that order), and then removed one
at a time, in what order will they be removed?
A) BCDA
B) ABDC
C) DCBA
D) ABCD
A6-R4 Page 2 of 5 January, 2013
1.5 The infix form of the following postfix expression is A B C + * D E / -
A) (A*B+C – (D/E))
B) (A*(B+C) – (D/E))
C) ((A*B)+C – (D/E))
D) None of the above
1.6 In a class if you don’t write any keyword, default access right is
A) public
B) private
C) protected
D) none of the above
1.7 Which one of the following is not correct?
A) Base class object can be assigned to derived class object
B) Derived class object can be assigned to base class reference
C) Derived class object address can be assigned to base class pointer
D) Derived class object can be assigned to base class object
1.8 In which of the following hashing methods, we first divide keys into parts and then add them
to get Hash value?
A) Truncation Method
B) Folding Method
C) Mid Square Method
D) Modular Method
1.9 Which of the following operations is performed more efficiently by doubly linked list than by
singly linked list?
A) Deleting a node whose location is given
B) Searching of an unsorted list for a given item
C) Inverting a node after the node with given location
D) Traversing a list to process each node
1.10 An ADT is defined to be a mathematical model of a user-defined type along with the
collection of all ________ operations on that model.
A) Cardinality
B) Assignment
C) Primitive
D) Structured

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 Constructors are always defined in public section.
2.2 Linked list is a linear data structure.
2.3 Static function defined in base class can also be overridden in derived class.
2.4 If a preorder and postorder traversal of a binary tree generates the same output then tree
contains only one node.
2.5. While destroying objects of derived classes the order of invocation of destructors is same as
the order of invocation of constructors.
2.6 Binary search can be applied on linked list if nodes are arranged in sorted manner.
2.7 It is necessary to define a destructor in every class to destroy the object.
2.8 Maximum value in a binary Search Tree is the right most node in right sub tree of root node.
2.9 Function overloading is an example of runtime polymorphism.
2.10 If a function or a class is a friend of a base class they will not be a friend of its derived class
by default.

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 Level by level traversal of Binary tree is done                     A. Constant function
using
3.2 Functions defined inside class                                              B. Deque
3.3 Cannot be defined as virtual                                                 C. Folding
3.4 Tree of height h containing at least 2 h-1 and at                   D. Binary search tree
most 2 h -1 nodes.
3.5 A method to resolve collision                                               E. Queue
3.6 Function that cannot change the data of the class                 F. Chaining
3.7 Lists used to speedup the searching process                        G. Stack
3.8 Redefined in derived class and accessed through                H. Virtual function
base class pointer
3.9 Process of inserting an element in queue                             I. Inline functions
3.10 Data structure used in backtracking                                   J. Constructors
                                                                                                  K. Complete binary tree
                                                                                                  L. Skip lists
                                                                                                M. Enque

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. Deleting by copying                     B. Direct                                C. Five
D. Array                                            E. Static                                 F. Three
G. Tree                                              H. Height                               I. Private
J. Threads                                         K. Linked list                         L. Abstract
M. Deleting by merging

4.1 In ________ hashing key is the address without any algorithmic manipulations.
4.2 The ________ of a binary search tree depends on the order in which insertion are
performed.
4.3 A stack less traversal of a tree can be done using ________.
4.4 A tree remains height balanced after deletion in ________.
4.5 ________ functions cannot be declared as virtual.
4.6 Number of binary search trees for three nodes is________.
4.7 Objects cannot be created for ________ classes.
4.8 ________ members of a class are not accessible outside the class directly with class
objects.
4.9 When number of insertion and deletion are more than ________ is a preferred data
structure.
4.10 Removing duplicates values from a given list of integers is an application of ________.

PART TWO

(Answer any FOUR questions)

5.

a) What is a Binary Search Tree (BST)? Make a BST for the following sequence of numbers.
55, 36, 70, 23, 89, 100, 58, 39, 41, 60, 65, 25
Write Preorder, Inorder and postorder traversal of this tree.
b) Write a function in C++ to count number of leaves in a binary search tree.
(8+7)
6.
a) Write a program in C++ to add two large integers using stack.
b) Design a class for singly linked list and write the following functions:
i) Write a function to insert a node in the middle.
ii) Write a function to insert a node at a given location.
(7+8)
7.
a) Define a sparse matrix. Show how a lower triangular array is stored in memory. Evaluate
the method to calculate address of any element ajk of a matrix stored in memory.
b) A function is defined as follows:
f(n)=0 if n=0
f(n)=n-1 if n>5
f(n)=f(n+f(n+2)) if n<=5
Write a recursive program for the above function.
(8+7)
8.
a) An AVL tree is implemented such that every node has a ptr to its parent. Design a
procedure to insert and another to delete a node from AVL tree. You must take care of the
height balanced and empty tree.
b) Design a class for generic queue with data type T and size s, also give definition for
inserting and deleting elements in the queue with overflow and underflow conditions.
(7+8)
9.
a) Consider the following graph:
Draw all possible spanning trees for this given graph.
b) What is the difference between multiple inheritance and multilevel inheritance in C++?
Explain with the help of suitable example.
c) What is a Heap? Explain with an example how to construct a heap?
(5+5+5)

Next Set