# 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 **

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

**SECTION B**

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

- What are Linked Lists? How insertion and Deletion performed in Linked Lists, Explain?
- 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 |

- Define: (1) Chomsky Hierarchy and (2) Turning Machine Model?
- Explain any two of the following in detail:
- Lexical phase errors
- Syntactic phase errors
- Semantic phase errors.

- 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 folloing: 7 x 1 = 7 **

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

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

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

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

- What are regressions? Explain Linear and Non-Linear Regressions?
- 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 folloing: 7 x 1 = 7 **

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

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

- Eleminate left recursion and left factor the following grammar.
- Draw NFA for the regular expression