DS Unit 1 Notes

 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.

datastructure

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.

Leave a Reply

Your email address will not be published. Required fields are marked *