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

NIELIT A Level January, 2011

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)

1.1 For linear search in an array of n elements the time complexity for best case is.
A)
2
n
O
B) O(n)
C) O(1)
D)
 −
2

n 1
O
1.2 Which of the following shows the correct relationship among some of the more common
computing times for algorithm?
A) ( ) ( ) ( )

<
< < < 2
0 n
n
0 log n 0 n 0 n * log n 0 2
B) ( ) ( ) ( )

<

0 n < 0 log n < 0 n * log n < 0 2n 0 n2
C) ( ) ( ) ( )

<
< < < n
0 2
2
0 n 0 log n 0 n * log n 0 n
D) ( ) ( ) ( )
<
0 log n < 0 n < 0 n * log n < 0 n2 0 2n
1.3 The expression which accesses the (i, j) th entry (i = 0, 1,...m-1, j = 0, 1, n-1) of an m× n
matrix (stored in column major order) is
A) n ×(i −1)+ j
B) m× (j−1)+ i
C) n × (i −1)+ (j −1)
D) m× (j−1)+ (i −1)
1.4 The difference between new operator and malloc() is that
A) more memory space is allocated in case of new operator
B) malloc() allocates more space dynamically
C) new can be overloaded
D) malloc() can allocate memory space for any type of data
A6-R4 Page 2 of 5 January, 2011
1.5 A stack is implemented using an array with the following declarations:
int stack[100]; int stacktop = 0;
to perform the POP operation, which of the following is correct?
A) x = stack[stacktop + +]
B) x = stack[+ +stacktop]
C) x = stack[stacktop − −]
D) x = stack[− −stacktop]
1.6 Postfix of a+b*c-d
A) bc+*-d
B) bc+*d-
C) +bc*d-
D) bc*+d-
1.7 A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 52
The number of nodes in the left subtree and right subtree of the root respectively are
A) (2, 3)
B) (3, 2)
C) (4, 3)
D) (3, 4)
1.8 Inserting a new node after a given node in a doubly Linked list requires
A) four pointer exchanges
B) two pointer exchanges
C) one pointer exchanges
D) no pointer exchanges
1.9 Which of the following methods has the best average case complexity for searching?
A) Hashing
B) Sequential
C) Random
D) binary.
1.10 BFS
A) scans all incident edges before moving to the other vertex
B) scans adjacent unvisited vertex as soon as possible
C) is same as backtracking
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.1 A B-Tree is nothing but a binary tree.
2.2 Adding an element to an array (n elements) that does not allow duplicates requires
O(logn).
2.3 The correct big-O expression for 1000n2 + 550n3 + 0.5 2n is O(n2).
2.4 The best case complexity of insertion sort is O(n).
2.5 Arrays are dynamic structures.
2.6 A self-referential structure contains a pointer member that points to itself.
2.7 Linked list nodes are normally stored contiguously in memory.
2.8 A node with no children is called a leaf node.
2.9 BFS uses queue data structure.
2.10 A data structure where elements can be added or removed at either end but not in the
middle is called stack.

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 Stack                                                                       A. Balanced tree
3.2 Time Complexity                                                   B. Hashing
3.3 Polymorphism                                                        C. Prim’s algorithm
3.4 B-tree                                                                     D. Array open at one end
3.5 Best case complexity of quick sort                        E. Double ended queue
3.6 Search technique                                                    F. Malloc()
3.7 Memory Allocation                                               G. Queue using liked list
3.8 Linked queue                                                         H. Matrix with mostly 0 elements
3.9 Minimal spanning tree                                          I. Binary search
3.10 Sparse matrix                                                      J. Big-Oh notation
                                                                                    K. Ability of one type to appear as and be used
                                                                                         like another type
                                                                                     L. O(n2)
                                                                                     M. O(n)

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. Queue                                  B. Stack                                       C. Tree

D. Linked list                            E. AVL tree                                 F. O(n2)
G. Constant pointer                  H. Void                                          I. Graph
J. O(nlogn)                               K. Dijkstra’s                                  L. Class
M. Object

4.1 ________ pointer can be recast to any type.
4.2 Average case complexity of quick sort is ________.
4.3 ________ is called a LIFO data structure.
4.4 In a ________ there is a special node called head node.
4.5 A connected graph without circuit is called ________.
4.6 The big O notation for the expression 1+2+3+….n is ________.
4.7 A ________ is a mathematical tool used to represent a physical problem.
4.8 ________ tree is also known as the height balanced tree.
4.9 ________ algorithm is an algorithm in graph theory that finds the shortest path for a
connected weighted graph.
4.10 A ________ is an abstract description of a set of ________.

PART TWO

(Answer any FOUR questions)

5.
a) Write a program which will overload the operator ‘+=’ on strings (concatenation) and
operator functions = =, < and > to compare string also.
b) Give a suitable representation for polynomials & then write a function to add two
polynomials?
(8+7)
6.
a) Explain the memory representation of lower triangular matrix.
b) Consider the following infix expression:
(A + B) * C – (D – E) / (F + G).
Convert the above expression in postfix form using stack.
c) Write an algorithm to print elements of a single linked list in a reverse order.
(5+5+5)
7.
a) The following keys are to be inserted in the order shown below into an AVL Tree: 8, 12, 9,
11, 7, 6.. Show how the tree appears after each insertion.
b) If we delete a node from a BST and then insert the node again in BST, is the resulting BST
necessarily the same as before? Justify your answer with a suitable example.
c) What is an ADT? Give the array implementation of stack ADT.
(6+4+5)
8.
a) Write an algorithm for quick sort.
b) Find the complexity of the quick sort algorithm.
c) Explain the technique used in quick sort using an unsorted list of elements.
(5+5+5)
9.
a) Explain Kruskal’s algorithm to find the minimal spanning tree, with a suitable example.
b) Explain Linear Probing and Quadratic Probing using a suitable example.
c) Show the stages in growth of an order-4 B-tree when the following keys are inserted in the
order given:
84, 82, 29, 99, 65, 12, 50, 28,
(7+4+4)

Next Set