** UNIT -1 INTRODUCTION TO DATA STURCTURE**

** (2 , 4 & 8 MARKS QUESTIONS)**

**1) Define data structure and give it’s classification.**

**(Definition – 1 Mark, Classification -1 Mark)**

**Ans:** A data structure is a specialized format for organizing and storing data.

**2) Enlist various types of operation on data structure.(Any 4 operations – 2 M)**

**Ans:** Operations on Data Structure:-

Insertion

Deletion

Searching

Sorting

Traversing

Merging

**3) Define data structure? Enlist approaches to design an algorithm.**

**(Definition-1M,list- 1M)**

**Ans:** Data structure is the branch of computer science that unleashes the knowledge of **how data should be organized, how the flow of data** should be controlled and **how a data structure should be designed and implemented** to reduce the complexity & increase the efficiency of the algorithm.

Different approaches for designing an algorithm:

Top-down approach

Bottom up approach

**4) Explain the two approaches to designing an algorithm.**

**( 2 Marks each for the approaches)**

**Ans:** The two approaches to design an algorithm are

**a) Top down approach:**

A **top-down** approach is also known as stepwise design, is essentially the breaking down of a system to gain insight into its compositional sub-systems.

**Example** is c programming

**b) Bottom up approach:** A bottom-up approach is the piecing together of systems to give rise to more complex systems, thus making the original systems sub-systems of the emergent system.

**Example** is C++ programming

**5) Define primitive and non-primitive data structure. (Each definition carries-1M)**

**Ans:**

**PRIMITIVE DATASTRUCTURE** the primitive data structures are the basic data

types that are available in most of the programming languages.

The primitive data structures are used to represent single values.

**Example:** Integer, character, string, Boolean

**NON-PRIMITIVE DATASTRUCTURE** The data structure that are derived from

primary data structure is known as non-Primitive data structure.

These data types are used to store group of values.

**Example:** Arrays, Structure, Union, linked list, Stacks, Queue etc.

**6) Explain time complexity and space complexity.**

**(2M for time complexity and 2M for space complexity)**

**Ans:**

**Time complexity:-**

Time complexity of a program/algorithm is the amount of computer time that it needs to run to completion.

While calculating time complexity, we develop frequency count for all key statements which are important and basic instructions of an algorithm.

**Example:** Consider three algorithms given below:-

Algorithm A: – a=a+1

Algorithm B: – for x = 1 to n step 1 a=a+1 Loop

Algorithm C:- for x=1 to n step 1 for y=1 to n step 1 a=a+1

Loop Frequency count for algorithm A is 1 as a=a+1 statement will execute only once.

Frequency count for algorithm B is n as a=a+1 is key statement executes n time as the loop runs n times.

Frequency count for algorithm C is n as a=a+1 is key statement executes n2 time as the inner loop runs n times, each time the outer loop runs and the outer loop also runs for n times.

**Space complexity:-**

Space complexity of a program/algorithm is the amount of memory that it needs to run to completion.

The space needed by the program is the sum of the following components:-

Fixed space requirements: – It includes space for instructions, for simple variables, fixed size structured variables and constants.

**Variable time requirements: –** It consists of space needed by structured variables whose size depends on particular instance of variables.

**Example: –** additional space required when function uses recursion.

void main()

{

int i ,n, sum ,x;

sum=0;

printf(“\n enter no of data to be added”);

scanf(“%d”, &n);

for(i=1;i<=n; i++)

{

scanf( “%d”, &x);

sum= sum + x;

}

printf(“\n sum =%d”, sum);

}

Space required to store the variables i, n, sum and x=2+2+2+2=8

(int requires 2 bytes of memory space)

**7) Define recursion. Write a ‘C’ program to calculate the factorial of number**

**using recursion.(Definition – 2 Marks, Program – 6 Marks)**

**OR**

**7) WAP using recursion to print the factorial of a number(Program–3m,O/P– 1M)**

**Ans:** A function is called by itself is called as recursion

#include<stdio.h>

int fact(int n)

{

if(n==0)

return 1;

else

return n*fact(n-1);

}

main( )

{

int n;

printf(“Enter the number \n”);

scanf(“%d”, &n);

printf(“The factorial of %d=%d\n”, n, fact(n));

}

**Output :** Enter an number : 6 The factorial of 6 = 720

**8) Define recursion. Write a ‘C’ program for multiplication of natural numbers using recursion. (Definition -1Mark, Logic of program- 3Marks)**

**Ans:**

**Definition: –** Process of calling function itself is known as recursion in C

programming.

**Program:-**

#include<stdio.h>

int multiply(int, int);

int main( )

{

int a ,b , product;

printf(“Enter any two integers: “);

scanf(“%d%d”, &a, &b);

product = multiply(a ,b);

printf(“Multiplication of two integers is %d”, product);

return 0;

}

int multiply(int a, int b)

{

static int product=0, i=0;

if( i < a){

product = product + b;

i++;

multiply(a,b);

}

return product;

}

**9) Explain the big ‘O’ notation. (4 marks)**

**Ans:**

Big O notation characterizes functions according to their growth rates:

different functions with the same growth rate may be represented using the

same O notation.

The letter O is used because the growth rate of a function is also referred to

as order of the function.

A description of a function in terms of big O notation usually only provides

an upper bound on the growth rate of the function.

Associated with big O notation are several related notations, using the

symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.

**10) What is the need of Data Structure.**

**Ans:-**

1) A data structure helps us to understand the relationship of one data element

with the other.

2) Data structure help us to analyze the data in a logical or mathematical manner.

3) Data structure helps us to store the data and organize in a logical or

Mathematical manner.

4) Modern day computing problems are complex and large, so there is need to

handle large amount of data which is overcome using data structure.

5) The collection of data and shrink dynamically over time is organized by using various efficient algorithm in data structure

**11) What are the USER-DEFINED data type and ABSTRACT DATA TYPE.**

**Ans:**

**USER DEFINED DATA TYPE:**

Many programming languages provide the facility of defining our own data types

i.e. we can create our own type and give it a name.

We can also rename an existing data type and give it a user defined name.

**Example:**

typedef, structure, union, enumeration

**1) typedef:** The typedef is used to define new data items that are equivalent to

existing data types.

The main advantage of typedef is that we can create meaningful data

type names for increasing the readability of the program

**Syntax:**

typedef datatype new_datatype;

Where,

typedef is a keyword for declaring the new data items and

datatype is an existing datatype being converted to the new name.

**Example:**

typedef int units;

units batch1, batch2;

**2) Enumeration:**

The identifier is a user defined enumerated data type which can be used to declare variables that can have one of the values enclosed within thebraces(known as enumeration constant).

It is defined as follows:

**enum identifier { value1,value2,……,value n};**

**Example:**

enum day ={Monday, Tuesday,……,Sunday};

enum day week_st, week_end;

week_st =Monday;

week_end=Friday;

The compiler automatically assigns integer digits beginning with 0 to all

the enumeration constants.

**ABSTRACT DATA TYPE:**

ADT stands for abstract data type. Data type is collection fo values and a set of operations on these values.

ADT refers to the mathematical concept that defines the data type.

An ADT is a set of operation which is related to the mathematical

abstractions.

It is useful tool for specifying the logical properties of a data type.

It involves two parts

i) First the description of the way in which the components are related to each other.

ii) Second are the statements of the operations that can be performed on elements of ADT.

ADT are generally constructed by the user or by a higher level language.

A book is an ADT with attributes like name, author(s), ISBN, number of pages, subject, etc.

**12) Differentiate between linear data structure and non-linear data**

**structure.[4m]**

**Ans:**

Linear data structure |
Non-Linear data structure |

1) In linear data structure, data elements are organized sequentially. |
1) In non-linear data structures, data elements can be attached to several other data elements to represent specific relationships that exist among them. |

2) They are easy to implement in the computer’s memory. |
2) They are slightly difficult to implement in the computer’s memory than Linear Data Structure. |

3) All the data can be traversed in a single run. |
3)All the data items cannot be traversed in a single run. |

4) It is implemented using array. | 4) It is implemented using pointers. |

5) If we traverse from an element, we can strictly reach only one other element. |
5) Traversing from an element can lead to more than one element. |

6) Examples of linear structure are arrays, linked list, stacks and queues. |
6) Examples of non-linear structure multidimensional array, trees, and graphs. |