Fundamental of Data Structure Numerical and Computational Theory 2018 MCA 4th Sem AKTU

Printed Pages: 02 Sub Code: RCAA02

Paper Id: 214425 Roll No. _____________________

MCA

(SEM IV) THEORY EXAMINATION 2017-18

Fundamental of Data Structure Numerical and Computational Theory

Time: 3 Hours Total Marks: 70

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief. 2 x 7 = 14

1. What are arrays? Explain the types with suitable example?
2. Define the Insertion Sort and Bubble Sort with its complexity analysis?
3. What is Binary Search Tree? How Insertion and Deletion Performed in BST?
4. Define Curve Fitting? Explain principle of Least Squares?
5. How do you find the complexity of an algorithm?
6. Define a NFA and compute its language?
7. What are regular expressions and why they are used?

SECTION B

2. Attempt any three of the following: 7 x 3 = 21

1. What are Linked Lists? How insertion and Deletion performed in Linked Lists, Explain?
2. By the method of least squares, find the straight line that best fits the following data:

x:	0	1	2	3	4
y:	1	1.8	3.3	4.5	6.3

3. Define: (1) Chomsky Hierarchy and (2) Turning Machine Model?
4. Explain any two of the following in detail:
   1. Lexical phase errors
   2. Syntactic phase errors
   3. Semantic phase errors.
5.  Discuss the algorithm for constructing a NFA from a regular expression and then converting it to the corresponding DFA?

SECTION C

3. Attempt any one part of the following: 7 x 1 = 7

1. What is data structure? List out the areas where data structures are applied extensively?
2. Define: Two Way Merge Sort and Two-Way Header List?

4. Attempt any one part of the following: 7 x 1 = 7

1. Define Heap Sort with the complexity analysis? Compare Merge Sort and Heap Sort?
2. What is a data type? Find the difference between primitive, Non-primitive, abstract and polymorphic data types.

5. Attempt any one part of the following: 7 x 1 = 7

1. What are regressions? Explain Linear and Non-Linear Regressions?
2. Write an algorithm for fitting a straight line of the form for a given set of data points?

6. Attempt any one part of the following: 7 x 1 = 7

1. Define: Chi-square test, t-test and F-test with its applications?
2. What are forecasting models and why these models are used?

7. Attempt any one part of the following: 7 x 1 = 7

1. Eliminate left recursion and left factor the following grammar.
2. Draw NFA for the regular expression

Thank You!