B.C.A. (Semester III) (CGPA) Examination, 2017
DATA STRUCTURE USING
Day Date: Tuesday, 11-04-2017 Max. Marks: 70
Time: 02.30 PM to 05.00 PM
N.B. Q.1 and Q.7 are compulsory.
Attempt any two questions from Q. 3 and 4.
Attempt any one question from Q. 5 and 6.
Figures to the right indicate full marks.
Q.1 Choose the single correct alternatives: 14
The postfix form of is

In what kind of storage we can easily insert, delete,
concatenate and rearrange substrings?
Queue Linked List Stack Array
The data structure required to check whether an expression
contains balanced parentheses is
Stack Queue Array Tree
A stack is not First In First Out (FIFO) data structure.
True False
If the elements "C" and "D" are placed in a queue
and are deleted one at a time, in what order will they be
removed?
DCBA CADB ABCD None of these
A data structure in which elements can be inserted or deleted
at/from both the ends but not in the middle is
queue circular queue
priority queue dequeue
A variant of linked list in which last node of the list points to
the first node of the list is
singly linked list doubly linked list
circular linked list None of these
Which type of traversal of binary search tree outputs the value in
sorted order?
Pre-order In-order
Post-order None of these
Page 1 of 2
SLR-U 11
When converting binary tree into extended binary tree, all the
original nodes in binary tree are
internal nodes on extended tree external nodes on extended tree
vanished on extended tree None of the above
10)If the given array is sorted on nearly, which of the following
algorithm gives best performance?
Insertion sort Selection sort Quick sort Merge sort
11)Which of the following sorting procedure is slowest?
Quick sort Merge sort Shell sort Bubble sort
12) Which of the following is not a logical data structure?
Tree List Stack None of these
13)The post-order traversal of a binary tree is DEBFCA. Find out
the pre-order traversal.
ABFCDE ADBFEC ABDECF ABDCEF
14)Stack can be implemented using
array, binary tree linked list, graph
array, linked list queue, linked list
Q.2 What is data structure? Explain array as ADT with suitable
example.
07
Write an algorithm to-
insert data item into a queue
delete data from a queue
07
Q.3 Explain in brief a linked list with its types. 07
Write a program in C to insert an element in an array at given
position.
07
Q.4 What are the three traversal techniques for binary trees? 07
Explain binary tree representation. 07
Q.5 Write the algorithm for selection sort and give a suitable example. 07
Write and explain linear search procedure with a suitable
example.
07
Q.6 Covert the following infix expressions into postfix form

A B D
07
Explain Exchange sort with example. 07
Q.7 Write short notes on the following (Any two) 14
Indexed sequential search
Threaded binary tree
AVL Tree