M.C.A. (Science) (Semester II)(CBCS) Examination, 2017
DATA STRUCTURE
Day Date: Friday, 21-04-2017 Max. Marks: 70
Time: 10.30 AM to 01.00 PM
Instruction Question 1 and 2 are compulsory
Attempt any Three from Q.3 to Q.7
Figures to the right indicate full marks.
Q.1 Choose the correct alternatives: 10
If binary tree contains n nodes, then its possible maximum height
is minimum height is respectively.
n log2(n+1) log2n&n 2n-1 n 2n&n+1
Which of the following algorithm works by taking a decision that
appears best at that moment?
Greedy algorithm Divide conquer
Backtracking All of these
Match the following.
1 Completeness How long does it take to find solution
2 Time Complexity ii) How much memory needs to perform the
Serach
3 Space Complexity iii) Is the strategy guaranteed to find the
solution when there is one
1-iii, 3-i 3-iii 1-iii, 3-ii 2-iii, 3-ii
Two or more nodes which have same parent is called
Sibling Brothers both a b none of these
The node which has only incoming edges but not having outgoing
edge is called
Source Sink both a b none of these
Merge sort has performance.
O(nlogn)
Which of the following abstract data type can be used to represent
a one to many relation?
Tree only Graph only
Both a b None of these
Page 1 of 2
Which of the following statement is False?
Every tree is bipartite graph
A tree cannot contain cycle
A tree with n nodes can contain n+1 edge
A tree is connected graph
If every node u in G has same degree then it is known as
Graph
Isolated regular finite Strongly connected
10) Which of the following searching technique may be work with
sorted as well as unsorted data?
Linear search Hashing
Linked search Binary search
State whether True or False: 04
Topological sorting is not possible if there is a cycle.
random numbers are used to take decision in backtracking
algorithm.
Quick Sort also known as partition exchange sort.
Extended binary tree also known as complete tree.
Q.2 What is an AVL tree? Explain AVL rotations with example 06
What is an abstract Data Type? Explain List ADT, Stack ADT Queue
ADT
08
Q.3 What is data structure? Explain linear Non-Linear data structure 06
Explain how to reverse string using stack. Explain with appropriate
example
08
Q.4 What is Queue? Explain Array implementation of Queue using
appropriate functions
06
What is binary search? Write an algorithm for binary search. Give one
example.
08
Q.5 What is circular Queue? Explain process of inserting deleting node
from circular queue.
06
Explain concept of polynomial arithmetic with linked list. Give
appropriate example.
08
Q.6 What is binary tree? Explain linked representation with example. 06
Sort following data using bubble sort: 23, 12, 20, 42, 88, 92, 56.
Give analysis.
08
Q.7 What is Hashing? Explain different hashing functions with example 06
What is traversing? Explain Traversing technique in graph. 08