2ND PUC COMPUTER SCIENCE

PASSING PACKAGE

1. Basic Concepts of OOP - 07 Marks (2+5)

2. Classes and Objects - 06 Marks (1+5)
3. Function Overloading - 06 Marks (1+5)
4. Inheritance - 05 Marks (5)
5. Logic Gates - 04 Marks (1 + 3 )
6. K - Map - 05 Marks (5)
7. Data Structures - 05 Marks (5)
Total : 38 Marks

2nd PUC COMPUTER SCIENCE PASSING PACKAGE

BASIC CONCEPTS OF OOP [ 2 + 5 = 07 Marks ]

1. Explain the concepts / characteristics of OOP.

1) Object: an object is a collection of member data and associated member function
or methods.

2) Class: A class is a way of grouping object having similar characteristics. A class is

a template from which object are created.

3) Data Abstraction: Abstraction is the process of representing essential features

without including background details.

4) Data Encapsulation: Wrapping up of data and functions into one single unit called
class is data encapsulation.

5) Inheritance: The objects of one class acquire the properties of another class
through inheritance.

6) Overloading: Overloading allows objects to have different meaning depending

upon context. There are 2 types of overloading namely:
1) Operator overloading
2) Function overloading
When an existing operator operates on new data type, it is called operator
overloading.
Function overloading means two or more function have same name, but differ in the number
of arguments or datatype of arguments.
7) Polymorphism: The ability of an operator and function to take multiple forms is
known as polymorphism.

8) Dynamic Binding: Dynamic binding is a process of linking procedure call to

function at runtime.
9) Message passing: In OOP, Object may communicate with each other through
message passing.

Page 1
2. Explain advantages of OOPS.
1) The programs are modularized into classes and objects.
2) Data is encapsulated along with function. Therefore cannot be accessed by non-
member function thus providing data security.
3) Object may communicate with each other through message passing.
4) Linking code and object allows related objects to share common code. This
reduces code duplication and code reusability.
5) Easier to develop complex software, because complexity can be minimized through
inheritance.
6) Creation and implementation of OOP code is easy and reduces software
development time

3. Write the difference between procedural programming and object oriented

programming.
OR
Mention any 5 advantages of object oriented programming over procedural
programming.

Object Oriented Programming Language Procedural Programming Language

1) The programs are modularized into 1) Large programs are divided into smaller
classes and objects programs known as functions.

2) Data is encapsulated along with function. 2) Data is not hidden and can be accessed by
Therefore cannot be accessed by non member external functions.
function thus providing data security

3) Object may communicate with each other 3) Data communicate with each other through
through message passing functions.

4) Follows bottom up approach in the program 4) Follows top down approach in the program
design design

5) Emphasize is on data rather than procedure 5) Emphasize is on procedure rather than data

4. Write the disadvantages of object oriented programming.

1. Object oriented programming software development, debugging and testing tools are not
standardized.
2. The adaptability of flowcharts and object oriented programming using classes and
objects is a complex process
3. To convert a real world problem in to an object oriented model is difficult.
4. The classes are overly generalized

5. Write the applications of object oriented programming.

1. CAD / CAM software
2. Object oriented database
3. Computer graphic applications
4. User interface design such as windows
5. Real time systems
6. Simulation and modeling
7. Artificial intelligence and expert systems
8. Hypertext, hyper media
Page 2
 CLASSES AND OBJECTS [ 1 + 5 = 06 Marks ]

1. Explain class definition with syntax and example.

A class definition is a process of naming data members and member functions of
the class.
Syntax :
class user_defined_name
{
private:
member data
member functions
protected:
member data
member functions
public:
member data
member functions
};
Example :
class Date
{
private:
int day;
int month;
int year;
public:
void inputdate();
void displaydate();
};

2. Explain class declaration with syntax and example. OR

Explain defining object of a class with syntax and programming example.
A class declaration specifies the representation of objects of the class and set of
operations.
Syntax:
class user_defined_name
{
private: //members
public: //methods
};
user_defined_name object1, object2,.....;
Example :
class interest
{
private:
double p, t, r, si;
public:
void getdata( );
void compute( );
void putdata( );
};

Page 3
 void interest::getdata( )
{
cout<<"Enter principal amount, time and rate"<<endl;
cin>>p>>t>>r;
}
void interest::putdata( )
{
cout<<"Simple Interest:"<<si;
}
void interest::compute( )
{
si = (p*t*r)/100;
}

void main( )
{
interest s;
clrscr( );
cout<<setprecision(2);
s.getdata( );
s.compute( );
s.putdata( );
getch();
}

3) What are access specifier? Explain different access specifier with example.
Access specifiers define the scope of data . Access specifier help in controlling the access of
data members. There are three types of access specifier namely private, public and protected..
i) private
Members declared under private are accessible only within the class. If no access
specifier is mentioned, then by default, members are private.
Example:
class Date
{
private:
int day;
int month;
int year;
……….
};
ii) public
public access means that members can be accessed by any function outside the
class also.
Example:
class Date
{
private:
int day;
int month;
int year;

Page 4
 public:
void inputdate();
void displaydate();
};
iii) protected:
The members which are declared using protected can be accessed only by the
member functions, friends of the class and also member functions derived from
this class. The members cannot be accessed from outside. The protected access specifier is
therefore similar to private specifier.
protected:
int day;
int month;
int year;

4) Explain member functions inside class definition and outside class definition
with an example.
Inside class definition
The member function defined within a class is called as inside function. Only small
functions are defined inside class definition. To define member function inside a
class, the function declaration within the class is replaced by actual function definition inside
the class.

Syntax:
return type member-function( )

Example :
class rectangle
{
int length, breadth;
public:
void get_data()
{
cin>>length>>breadth;
}
void put_data()
{
cout<<length<<breadth;
}
};

Outside class definition

To define a member function outside a class, scope resolution operator(::) is used.
Scope resolution operator identifies the function as a member of a particular class.
Large functions are defined outside the class.

Syntax:
return-type classname :: memberfunction(arg1,arg2…)
{
function body;
}
Example:
class rectangle
{
Page 5
 private:
int length, breadth;
public:
void get_data();
void put_data();
};

void rectangle::get_data()
{
cin>>length>>breadth;

}
void rectangle::put_data()
{
cout<<length<<breadth;
}

5) What is array of object? Give an example.

An array having set of class type elements is known as array of objects.

#include<iostream.h>
#include<conio.h>
class student
{
int rollno, maths, science;
public:
void getdata( );
void putdata( );
};
void student::getdata( )
{
cout<<“Enter roll no: ”;
cin>>rollno;
cout<<“Enter maths marks: ”;
cin>> maths;
cout<<“Enter science marks: ”;
cin>> science;
}
void student::putdata( )
{
cout<<“Roll no: ”<<rollno<<endl;
cout<<“Maths marks: ”<<maths<<endl;
cout<<”Science marks: ”<<science<<endl;
}

Page 6
void main()
{
student stud[3];
clrscr();

for(int i =0; i<3;i++)

stud[i].getdata( );

for(int i =0; i<3;i++)

stud[i].putdata( );
}

FUNCTION OVERLOADING [ 1 + 5 = 06 Marks ]

1) What is meant by function overloading? Explain the need for function overloading
Function overloading means two or more functions have same name, but differ in the number of
arguments or datatype of arguments. Therefore it is said that function name is overloaded.
Function overloading is the process of defining the same function name to carry out similar types of
activities with various data items.

Need for function overloading (Advantages of function overloading):

1) The main factor in function overloading is a function’s argument list. If there are two functions
having same name and different types of arguments or different number of arguments, then function
overloading is invoked automatically by the compiler. Thus the code is executed faster.
2) It is easier to understand the flow of information and debug.
3) Code maintenance is easy
4) Easier interface between programs and real world objects.
5) Function overloading is also known as compile time polymorphism.

2) Explain function overloading with an example program.

Function overloading means two or more functions have same name, but differ in the number of
arguments or datatype of arguments. Therefore it is said that function name is overloaded.
Example :
class funoverloaded
{
public:
int area (int l, int b)
{
return (l * b);
}
float area (float r)
{
return (3.14 * r * r);
}

float area (float b, float h)

{
return (0.5 * b * h);
}
};
Page 7
void main ( )
{
funoverloaded f;
clrscr ();
cout<<” Area of Rectangle :”<<f.area(4,6)<<endl;
cout<<”Area of circle :”<<f.area(10)<<endl;
cout<<”Area of Triangle:”<<f.area(3.0,7.0)<<endl;
}

3) What is inline function? Write a simple program for it.

OR
Explain inline function with programming example.
The inline function is a short function in which the compiler replaces a function call
with the function body.
The keyword inline is used to define inline functions. The inline function consists of
function call along with function code.
Example :
class assign
{
private :
int n;
public :
assign(int nn)
{
n = nn;
}
int cube( );
};
inline int assign::cube( )
{
return(n*n*n);
}
void main( )
{
int x;
clrscr( );
cout<<"Enter the number: ";
cin>>x;
assign obj = x;
cout<<"Cube of "<<x<<" = "<<obj.cube( );
}

4) Write the advantages , disadvantages and restrictions of inline functions.

Advantages:
1) The inline member functions are compact function calls.
2) Therefore the size of the object is considerably reduced
3) The speed of execution of a program increases
4) Very efficient code can be generated.
5) The readability of the program increases

Page 8
Disadvantages:
1) As the body of inline function is substituted in place of a function call, the size of the executable
file increases and more memory is needed.
Restrictions:
The inline function may not work some times for one of the following reasons:
1) If the inline function definition is too long or too complicated.
2) If the inline function is recursive.
3) If the inline function has looping constructs.
4) If the inline function has a switch or goto

5) Describe briefly the use of friend function in C++ with example.

A friend function is a non-member function that is a friend of a class that has
permission to access both private and protected members
Characteristics:
1) The friend function is declared by prefixing it with the keyword friend
2) friend function should be declared within a class but friend function should be defined outside the
class.
3) A friend function although not a member function, has full access right to the private and
protected members of the class.
4)The friend declaration can be placed anywhere in the class definition. It is not affected by the
access control keywords (public, private and protected)
5) It cannot access the member variables directly and has to use an objectname.membername(Here .
is a membership operator)
6) A friend function cannot be called using the object of that class. It can be invoked like any
normal function.Ex: function_name(object)
7) Since friend function is a non-member function while defining friend function it does not use
scope resolution operator.

Example :
class myclass
{
private:
int a,b;
public:
void set_val(int i,int j);
friend int add(myclass object);
};
void myclass::set_val(int i,int j)
{
a = i;
b = j;
}
int add(myclass object)
{
return (object.a + object.b);
}

Page 9
void main()
{
myclass object;
object.set_val(34,56);
cout<<"Sum of 34 and 56 is "<<add(object);
}

INHERITANCE [ 5 marks ]

1) What is Inheritance? Explain briefly the types of inheritance

Inheritance is the capability of one class to inherit properties from another class.
New class is the derived class and an existing class is the base class.
Based on this relationship, inheritance can be classified into five forms:
1) Single inheritance
2) Multiple inheritance
3) Multilevel inheritance
4) Hierarchical inheritance
5) Hybrid inheritance.

I Single inheritance:
If a class is derived from a single base class, it is called as single inheritance

Base Father
class

Derived Son
class

II Multiple inheritance:
If a class is derived from more than one base class, it is known as multiple inheritance
Base class-1 Base class-2 ---- Base class-n King Queen

Prince

Derived class

Page 10
 III Multilevel inheritance:
The classes can also be derived from the classes that are already derived. This type of inheritance
is called multilevel inheritance

Base Grand Father

class

Derived
Father
class-1

Derived
class-2 Son

Derived class-
n

IV Hierarchical inheritance:
If a number of classes are derived from a single base class, it is called as hierarchical inheritance

Base
class

Derived Derived Derived

class-1 class-2 class-3
Staff

Lecturers Office staff Group - D

V Hybrid inheritance:
Hybrid inheritance is combination of Hierarchical and multilevel inheritance.
Base
class

Derived class-1 Derived class-2

Derived class

Page 11
2) What is Inheritance? What are the advantages of inheritance?
Inheritance is the capability of one class to inherit properties from another class.
Inheritance has following advantages:
1) Reusing existing code – since all the features of base class are repeated in derived
class.
2) Faster development time – as the main code need not be written again.
3) Easy to maintain – as the testing need not be done once again for derived class.
4) Memory utilization – is less as we reuse the existing code.
5) Easy to extend – because in derived class in addition to the existing features of base class we can
add new features

3) What is visibility mode? What is its role? OR

What is the difference between public, private and protected access specifiers in inheritance?
The visibility mode basically controls the access specifier to be for inheritable member of base class
in the derived class.If no visibility mode is specified, then by default the visibility mode is
considered private.
Derived class
Base class public mode private mode protected mode

public public private protected

private Not inherited Not inherited Not inherited
protected protected private protected

I Public inheritance:
This is the most used inheritance mode. In this
1) The public members of a base class become pubic members of the derived class.
2) The private members of a base class cannot be inherited to the derived class
3) The protected members of a base class stay protected in a derived class.
II private inheritance:
1) The public members of a base class become the private members of the derived class.
2) The private members of a base class cannot be inherited to the derived class
3) The protected members of a base class stay protected in a derived class.
III protected inheritance:
1) The public members of a base class become protected in a derived class.
2) The private members of a base class cannot be inherited to the derived class
3) The protected members of a base class stay protected in a derived class.
Inheritance syntax :
class school
{
private:
int rollno;
char name[20];
public:
void input();
void output();
};

Page 12
Example :
class college : public school
{
private:
int marks;
public:
void getdata();
void display();
};

4) What is virtual base class? Give example.

.

Base class - A

Derived class – B Derived class – C

get one copy of get one copy of base
base class data class data

Derived class –
D
In the public inheritance, B and C inherit
get 2one copy
copies of of the base class data where as derived class D
inherited from B and C get two copiesbase class
of the data
base class data.

When two or more objects are derived from a common base class, we can prevent multiple copies in
the base class by declaring the base class as virtual when it is being inherited. Such a base class is
known as virtual base class. This can be achieved by preceding the base class name with the
keyword virtual.

Ex: class A
{
__________
___________
};
class B: virtual public A
{
___________
___________
};
class C: virtual public A
{
____________
_____________
};
class D: public B, public C
{
_____________
_____________
};
Page 13
Page 14
Page 15
Page 16
Page 17
 K - MAP
1. Given the Boolean function
F ( W, X, Y, Z ) = ∑ ( 0, 4, 8, 9, 10, 11, 12, 13, 15 ).
Reduce it using Karnaugh map. [A2015]

Y’ Z’ Y’ Z Y Z Y Z’

00 01 11 10

W’ X’ 00 1 0 0 0
0 1 3 2

W’ X 01 1 0 0 0
4 5 7 6

WX 11 1 1 1 0
12 13 15 14

W X’ 10 1 1 1 1
8 9 11 10

Q1 Q2 Q3
Q1 = Y’ Z’
Q2 = WZ
Q3 = W X’

F ( W, X, Y, Z ) = Y’ Z’ + WZ + WX’

Page 18
2. Reduce F(A,B,C,D) = ∑ (1, 2, 3, 4, 5, 7, 9, 11, 12, 13, 15)

using K- Map. [S2015]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 0 1 1 1
0 1 3 2

A’ B 01 1 1 1 0
4 5 7 6

AB 11 1 1 1 0
12 13 15 14

A B’ 10 0 1 1 0
8 9 11 10

Q1 O1 P1

O1 = D
Q1 = B C’

P1 = A’ B’ C

F(A,B,C,D) = D + B C’ + A’ B’ C

Page 19
3. Using K-Map, simplify the following expression in four variables
F(A,B,C,D) = m1 + m2 + m4 + m5 + m9 + m11 + m12 +m13 [A2016]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 0 1 0 1
0 1 3 2

A’ B 01 1 1 0 0
4 5 7 6

AB 11 1 1 0 0
12 13 15 14

A B’ 10 0 1 1 0
8 9 11 10

Q1 Q2 P1 S1

Q1 = B C’
Q2 = C’ D
P1 = A B’ D

S1 = A’ B’ C D’

F(A,B,C,D) = B C’ + C’ D + A B’ D + A’ B’ C D’

Page 20
4. Reduce F ( A, B, C, D) = ∑ ( 1, 5, 9, 10, 11, 12, 13, 14 )
using K – map. [S2016]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 0 1 0 0
0 1 3 2

A’ B 01 0 1 0 0
4 5 7 6

AB 11 1 1 0 1
12 13 15 14

A B’ 10 0 1 1 1
8 9 11 10

P1 Q1 P2 P3

Q1 = C’D
P1 = ABC’
P2 = AB’D
P3 = ACD’

F(A, B, C, D) = C’D + ABC’ + AB’D + ACD’

Page 21
5. Reduce F(A, B, C, D ) = ∑ ( 0, 4, 6, 7, 8, 12, 14, 15 )
using K – map. [A2017]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 1 0 0 0
0 1 3 2

A’ B 01 1 0 1 1
4 5 7 6

AB 11 1 0 1 1
12 13 15 14

A B’ 10 1 0 0 0
8 9 11 10

Q1 Q2

Q1 = C’ D’
Q2 = B C

F ( A, B, C, D) = C’ D’ + B C

Page 22
6. Reduce using K-map.
F(A,B,C,D) = ∑ (2, 3, 5, 6, 7, 10, 13, 14, 15) [A2017(2)]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 0 0 1 1
0 1 3 2

A’ B 01 0 1 1 1
4 5 7 6

AB 11 0 1 1 1
12 13 15 14

A B’ 10 0 0 0 1
8 9 11 10

Q1 Q2 Q2

Q1 = B D
Q2 = A’ C
Q3 = C D’

F ( A, B, C, D) = B D + C D’ + A’ C

Page 23
7. Simplify the following Boolean expression using K – Map
F ( A, B, C, D ) = ∑ ( 0, 2, 5, 7, 8, 10, 13, 15 ). [S 2017]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 1 0 0 1
0 1 3 2

A’ B 01 0 1 1 0
4 5 7 6

AB 11 0 1 1 0
12 13 15 14

A B’ 10 1 0 0 1
8 9 11 10

Q1 Q2

Q1 = B’ D’
Q2 = B D

F ( A, B, C, D ) = B’ D’ + B D

Page 24
8. Simplify the following Boolean function using K-map.
F(A, B, C, D ) = ∑ (1, 2, 3, 5, 7, 8, 9, 11, 13, 15) [A2018]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 0 1 1 1
0 1 3 2

A’ B 01 0 1 1 0
4 5 7 6

AB 11 0 1 1 0
12 13 15 14

A B’ 10 1 1 1 0
8 9 11 10

P2 O1 P1

O1 = D

P1 = A’ B’ C
P2 = A B’ C’

F(A, B, C, D ) = D + A’ B’ C + A B’ C’

Page 25
9. Simplify the following Boolean expression using K – MapF (
A, B, C, D ) = ∑ ( 0, 2, 4, 5, 6, 7, 8, 10,12, 13, 14, 15 )
[S2018]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 1 0 0 1
0 1 3 2

A’ B 01 1 1 1 1
4 5 7 6

AB 11 1 1 1 1
12 13 15 14

A B’ 10 1 0 0 1
8 9 11 10

O1 02
O1 = D’
O2 = B

F(A, B, C, D ) = D’ + B

Page 26
10. Given Boolean Function
f(a, b, c, d) = ∑( 0, 1, 2, 3, 4, 6, 8,10, 12, 14) Reduce it using
Karnaugh map. [A2019]

c’ d’ c’ d cd c d’

00 01 11 10

a’ b’ 00
1 1 1 1
0 1 3 2
a’ b 01
1 0 0 1
4 5 7 6
ab 11
1 0 0 1
12 13 15 14
a b’ 10
1 0 0 1
8 9 11 10

O1 Q1

O1 = d’
Q1 = a’ b’

f(a, b, c, d) = d’ + a’ b’

Page 27
11. Given Boolean Function
F(A, B, C, D) = ∑( 0, 1, 2, 3, 5, 6, 9,10, 13, 14) Reduce it
using Karnaugh map. [S2019]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00
1 1 1 1
0 1 3 2
A’ B 01 0 0
4 1 7 1
5 6
AB 11 0 1 0
12 13 15 1
14
A B’ 10 0 0 1
8 1 9 11 10

Q1 Q2 Q3

Q1 = C’ D
Q2 = A’ B’
Q3 = C D’

F(A, B, C, D) = C’ D + A’ B’ + C D’

Page 28
12. Given Boolean Function
F(A, B, C, D) = ∑( 0, 1, 2, 3, 6, 10, 13, 14,15) Reduce it
using Karnaugh map. [A2020]

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 1 1 1 1
1 3 2

A’ B 01 0 0
4 5 7 1
6

AB 11 0 1 1
12 13 1
14

A B’ 10 0 0 0
8 9 11 1 10
15
P1 Q1 Q2

Q1 = A’ B’
Q2 = C D’
P1 = A B D

F(A, B, C, D) = A’ B’ + C D’ + A B D

Page 29
13. Simplify the following Boolean function. Explain its
types.
[S2020]
F(A,B,C,D) = ∑(0, 2, 4, 6, 10, 14)

C’ D’ C’ D C D C D’

00 01 11 10

1 1
A’ B’ 00 0 1 3 2

1 0 0 1
A’ B 01 4 5 7 6

0 1
AB 11 12 13 15 14

0 0 0 1
A B’ 10 8 9 11 10

Q1 Q2

Q1 = A’ D’
Q2 = C D’

F(A, B, C, D) = A’ D’ + C D’

Page 30
14. Given Boolean Function
F(W, X, Y, Z) = ∑( 0, 5, 7, 8, 13, 15) Reduce it using
Karnaugh map. [A2021]

Y’ Z’ Y’ Z Y Z Y Z’

00 01 11 10

W’ X’ 00 1 0 0 0
0 1 3 2

W’ X 01 0 1 1 0
4 5 7 6

WX 11 0 1 1 0
12 13 15 14

W X’ 10 1 0 0 0
8 9 11 10

P1 Q1
Q1 = X Z

P1 = X’ Y’ Z’

F(W,X,Y,Z) = X Z + X’ Y’ Z’

Page 31
15. Simplify the following Boolean function.

[A2022]
F(A,B,C,D) = ∑(0, 1,4,5,7,8,9,12,13,15)

C’ D’ C’ D C D C D’

00 01 11 10

A’ B’ 00 1 1 0 0
0 1 3 2

A’ B 01 1 1 1 0
4 5 7 6

AB 11 1 1 1 0
12 13 15 14

A B’ 10 1 1 0 0
8 9 11 10

O1 Q1

O1 = C’
Q1 = BD

F(A,B,C,D) = C’ + BD

Page 32
16. Simplify the following Boolean function.

[S2022]
F(A,B,C,D) = ∑(1, 3, 5, 7, 9, 11, 12, 13, 15)

C’ D’ C’ D C D C D’

00 01 11 10

0 1 1 0
A’ B’ 00 0 1 3 2

0 1 1 0
A’ B 01 4 5 7 6

1 1 1 0
AB 11 12 13 15 14

0 1 1 0
A B’ 10 8 9 11 10

P1 O1

O1 = D

P1 = A B C’
F(A,B,C,D) = D + A B C’

Page 33
 DATA STRUCTURES [ 1 + 3 + 5 + 5 = 14 Marks ]

1) What are data structures?

Data structure is a specialized format for organizing and storing data.

2) What are primitive data structures? Give examples.

Data Structures that are directly operated upon by machine-level instructions are known as primitive data
structures.
Ex: integers, character, floating point, pointers.

3) What are non-primitive data structures? Give examples.

Non primitive Data structures are derived from the primitive data structures.
Ex: Arrays, lists and files

4) Explain linear data structures with examples.

Linear data structures is a data structure that has homogenous elements and hey are arranged in a sequential
structure.Ex: Arrays, Stacks, Queues and linked lists

5) What are non-linear data structures?

In Non linear data structure, the data elements are not arranged in a sequential structure. Ex: Trees and graphs.

6) Explain different operations performed on primitive data structures.

i) Create: Create operations is used to create a new data structure. Ex: int x;
ii) Destroy: Destroy operation is used to destroy or remove the data structure from the memory space.
iii) Select: Select operation is used by programmers to access the data within the data structure.
iv) Update: Update operation is used to change data of data structures.

7) Explain the different operations performed on linear data structure. OR

Explain the different operations performed on one-dimensional array.

i) Traversal: The process of accessing each data element once to perform some operation is called traversing.
ii) Insertion: The process of adding a new element into the given collection of data elements is called insertion.
iii) Deletion: The process of removing an existing data element from the given collection of data elements is called
deletion.
iv) Searching: The process of finding the location of a data element in the given collection of data elements is
called as searching.
v) Sorting: The process of arrangement of data elements in ascending or descending order is called sorting.
vi) Merging: The process of combining the data elements of two structures to form a single structure is called
merging.

8) Define an array.
An array is a collection of homogeneous elements that are arranged in adjacent memory location.

34
9) How are arrays classified?
There are three types of Arrays:
1) One-dimensional array
2) Two-dimensional array
3) Multi-dimensional array

10) Write the features of arrays.

i) Array size should be positive number only.
ii) String array always terminates with null character (‘\0’).
iii) Array elements are counted from 0 to n-1.
iv) Useful for multiple reading of elements.

11) Write the applications / Advantages of arrays.

i) Arrays are used to implement other data structures such as linked list,trees, graphs, queues, stacks and strings.
ii) Arrays are used to implement mathematical vectors and matrices.
iii) Many database include one-dimensional arrays whose elements are records.
iv) It is used to represent multiple data items of same type by using only single name.
v) Two-dimensional arrays are used to represent matrices.

12) Write the dis-advantages of arrays.

i) Array size must be known in advance.
ii) Array is a static structure.
iii) Array size is fixed so memory is wasted.
iv) Array elements are stored in consecutive memory locations, hence insertion and deletion is difficult.

13) What do you mean by traversal in data structure? Write an algorithm and
explain with an example?
Traversing: Accessing each element of the array exactly once to do some operations.
Algorithm:
Step 1: for LOC = LB to UB
PROCESS A[LOC]
End of for
Step 2: Exit

35
14) Write an algorithm to search an element in an array using linear search method.
Step 1: LOC = -1 [Assuming that the element does not exist]
Step 2: for I = 0 to N – 1
if (ELE= A[I])
LOC = I
GOTO step 3
End of if
End of for
Step 3: if(LOC >=0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: Exit

15) Write an algorithm to search an element in an array using binary search

method.
Step 1: Set LB=BEG, UB=END, LOC = -1
Step 2: while(BEG<=END)
MID=(BEG+END)/2
if(ELE=A[MID])
LOC=MID
GOTO step 3
else
if(ELE<A[MID])
END=MID-1
else
BEG=MID+1
End of if
End of while
Step 3: if(LOC>=0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: Exit

16) Write an algorithm to insert an element in an array.

Step 1: for I = N-1 down to P
M[I+1]=M[I]
End of for
Step 2: M[P]=ELE
Step 3: N=N+1
Step 4: Exit

36
17) Write an algorithm to delete an element from the array
Step 1: ELE=A[P]
Step 2: for I = P to N-1
A[I]=A[I+1]
End of for
Step 3: N = N – I
Step 4: Exit
18) Write an algorithm to sort an array using insertion sort.
Step 1: for I = 1 to N – 1
Step 2: J=I
while(J>=1)
if(A[J]<A[J-1])
temp = A[J]
A[J] = A[J-1]
A[J-1]=temp
if end
J = J-1
while end
for end
Step 3: Exit
19) What is a stack ? Explain the operations performed on the stacks.
A Stack is an ordered collection of items where the insertion of new items and the
removal of existing items always takes place at the same end.
This ordering principle is called Last In First Out i.e LIFO.
Stack operations:
i) stack(): creates a new stack that is empty. It needs no parameters and returns an empty stack.
ii) push(item): adds a new item to the top of the stack.It needs the item as parameters and returns nothing.
iii) pop(): removes the top item from the stack.It needs no parameters and returns the item. The stack is
modified.
iv) peek(): returns the top item from the stack but does not remove it. It needs no parameters. The stack is not
modified.
v) isempty(): tests whether the stack is empty. It needs no parameters and returns a Boolean value.
vi) size():returns the number of items on the stack. It needs no parameters and returns an integer.

20) Write an algorithm for push and pop operation in stack using array.
Algorithm for push operation:
Step 1: If TOP=N-1 then [Check overflow]
Print ‘Stack is full’
Exit
End of if
Step 2: Top = Top+1 [Increment the top]
Step 3:Stack[top]=item [Insert the item]
Step 4: Return

37
 Algorithm for pop operation:
Step 1: If TOP=-1 then [Check underflow]
Print ‘Stack is empty’
Exit
End of if
Step 2: item=Stack[top] [Copy the top element]
Step 3: Top = Top-1 [Decrement the top]
Step 4: Return

21) Write the applications of stacks.

i) To reverse a word.
ii) undo mechanism in text editors.
iii) Compiler’s syntax check for matching braces is implemented by using stack.
iv) Conversion of decimal number to binary.
v) Expression evaluation and syntax parsing.
vi) Conversion of infix expression into prefix and postfix.
vii) To solve tower of Hanoi.
viii) Backtracking.
22) What is a queue? Explain the different types of queues with a neat diagram.
A queue is an ordered collection of items where an item is inserted at one end called
the rear and an existing item is removed at the other end, called the front. Insertion
and deletion is performed according to the First-in-First-out principle(FIFO).
Types of queues:
Queues can be of four types:
1) Simple queues
2) Circular queues
3) Priority queues
4) Double ended queue(Dequeue)
1) Simple queue: In simple queue, insertion occurs at the rear end of the list and deletion occurs at the front end
of the list.
Front Rear

A B C
0 1 2 3 4
Front = 1, Rear = 3

2) Circular queue: In circular queue, the last node is connected back to the first
node to make a circle.
3 2

4
1

5
0 Front=0
6 7
Rear=7
38
 3) Priority queue:
A priority queue is a queue that contains items that have some preset priority. An
element can be inserted or removed from any position depending on some priority.

4) Dequeue(Double Ended Queue):

It is a queue in which insertion and deletion takes place at both the ends.
Insertion Deletion

Deletion Q[0] Q[1] Q[2] Q[3] Q[4]

23) Explain the various operations performed on the queue.

A queue is an ordered collection of items where an item is inserted at one end called the rear and an existing item is
removed at the other end, called the front.

Operations on Queue:
i) Queue(): creates a new queue that is empty. It needs no parameters and returns an empty queue.
ii) Enqueue(item): Adds a new item to the rear of the queue. It needs the item and returns nothing.
iii) Dequeue() : Removes the item from the front of the queue. It needs no parameters and returns the item.
iv) Isempty(): test to see whether the queue is empty. It needs no parameters and returns a Boolean value.
v) size(): returns the number of items in the queue. It needs no parameters and returns an integer.

24) Write an algorithm to insert a data element at the rear end of the queue.
Algorithm for insertion:
Step1: If REAR = N-1 then (Check for overflow)
print “overflow”
Exit
Step2: If FRONT=NULL, then (Check whether Queue is empty)
FRONT=0
REAR=0
else
REAR=REAR+1 (Increment REAR pointer)
Step3:Queue[REAR] = ITEM (Copy Item to REAR position)
Step4: Return

39
25) Write an algorithm to delete an data element from the front end of the queue.
Algorithm for deletion:
Step1: If FRONT=NULL, then (Check whether queue is empty)
print “underflow”
Exit
Step2: ITEM=QUEUE[FRONT]
Step3: If FRONT=REAR, then (If Queue has only one element)
FRONT=NULL
REAR=NULL
else
FRONT = FRONT + 1 (Increment FRONT pointer)
Step 4: Return

26) Write the applications of queues?

i) Simulations
ii) Various features of operating system.
iii) Multi-programming platform systems
iv) Different type of scheduling algorithms.
v) Round robin algorithm
vi) Printer server routines

27) Explain the types of linked list.

i) Singly linked list : Singly linked list contains two parts - data part and link part.
ii) Circular linked list : In circular linked list, the link field of the last node contains the address of the first node.
iii) Doubly linked list : Doubly linked list contains contains three parts – forward, backward, and data.

*********

40