Master of Computer Application I (Science)
Examination: Oct Nov 2016 Semester II (Old CGPA)
SLR No. Day
Date Time Subject Name Paper
No. Seat No.
SLR U
12
Saturday
19/11/2016
10:30 A.M
to
01:00 P.M
Data Structures
Instructions: Question no. 1 2 are compulsory
Attempt any three questions from Q. No. 3 to Q. No. 7
Figures to the right indicate full marks
Total Marks: 70
Q.1 Choose the most correct alternatives 10
A full binary tree with n leaves contains
n nodes log2 n nodes
2n-1 nodes 2n nodes
Consider linked list of n elements which is pointed by an external pointer.
What is time taken to delete the element which is successor of the element
pointed by a given pointer?
O O (log
O O (nlogn)
In linear search algorithm the worst case occurs when
The time is somewhere in the middle of the array
The time is not in the array at all
The item is the last element in the array
The item is the last element in the array or is not there at all
Running out of memory may occur due to
Non-recursive function call Recursive function call
Use of global variable None of these
A linear collection of data element the linear node is given by mean of
pointer is called
Linked list node list
primitive list none of the above
A connected graph T without any cycles is called
A tree graph free tree
A tree All of above
Which of the following abstract data type can be used to represent a many 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 contain cycle
A tree with n nodes can contain n-1 edges.
A tree is connected graph
If every node u in G adjacent to every other node v in A graph is said to
be
Isolated Complete
finite Strongly connected u
10) Which of the following sorting technique is slowest?
Quick sort Heap sort
Shell sort Bubble sort
State true or false 04
Complexity of binary tree is 0 (log2n)
Binary Search is always better than linear search.
To store retrieve data we may be use different hash function.
Complete binary tree is also known a Tree.
Q.2 What is traversal in graph? Explain DFS with example. 06
Sort following data using selection sort 13, 32, 20, 62, 68, 52, 38, 46. Give
analysis.
08
Q.3 Explain some common approaches for designing algorithm. 06
Explain tree traversals with approach example. 08
Q.4 What is Queue? Explain basic operation on it using appropriate function. 06
Explain process of creating binary tree from following preorder inorder
traversal
Preorder ABDHECFG
Inorder DHBEAFCG
08
Q.5 Define binary tree. Explain how to represent algebraic expression using binary
tree with appropriate example.
06
What is a binary search? Write an algorithm for binary search? Give one
example.
08
Q.6 What is Hashing? Explain different hashing methods/functions. 06
Explain process of deleting node and edge from adjacency matrix adjacency
List.
08
Q.7 Explain with function to insert new value/node at all possible position in singly
linked list.
06
Create B tree from following Data:
10, 70 20, 110, 40, 80, 130, 100, 50, 190, 90, 180, 240, 30, 120,140,160.