UNIT I – DATA ABSTRACTION & OVERLOADING

16-Mark Answers

1. Explain the concept of Data Abstraction and discuss structures, class scope,
and access control mechanisms with suitable examples. (K2–Understand)

Data Abstraction

Data abstraction is the process of hiding implementation details and exposing only
essential information to users.

Advantages

 Reduces complexity
 Enhances security
 Improves maintainability
 Supports modular programming

Structure Example

struct Student
{
int regno;
char name[20];
};

Class Scope

Class scope determines accessibility of class members.

class Test
{
int x;

public:
void show();
};

Access Specifiers

Access Specifier Accessibility

Public Accessible everywhere

Private Accessible within class

Protected Accessible within class and derived classes

Conclusion

Data abstraction improves security and code organization.

2. Illustrate implementation of class members and member functions. (K3–

Apply)

Class Members

Variables declared inside class.

Member Functions

Functions operating on class data.

Program:

#include<iostream>

using namespace std;

class Student
{
int rollno;

public:

void get()
{
cin>>rollno;
}

void display()
{
cout<<rollno;
}
};

int main()
{
Student s;

[Link]();

[Link]();
}

Role in OOP
  Encapsulation
 Data hiding
 Better modularity

3. Compare constructors and destructors and justify significance. (K4–Analyze)

Constructor

Special member function called during object creation.

class A
{
public:

A()
{
cout<<"Constructor";
}
};

Destructor

Special function called during destruction.

~A()
{
cout<<"Destructor";
}

Comparison

Constructor Destructor

Initializes object Destroys object

Called automatically at creation Called automatically at destruction

Can be overloaded Cannot be overloaded

Significance

 Resource initialization
 Memory cleanup
 Object lifecycle management

4. Demonstrate reference variables and initialization. (K3–Apply)

Definition

Reference variable acts as another name for existing variable.

Syntax:

datatype &ref=variable;

Program:

int x=10;

int &y=x;

cout<<y;

Output:

10

Advantages

 Pass-by-reference
 Avoid copying
 Efficient memory usage

5. Analyze role of friend functions and friend classes. (K4–Analyze)

Friend Function

Can access private members.

Program:

class A
{
int x=10;

friend void show(A);

};

void show(A a)
{
cout<<a.x;
}

Friend Class
class B;

class A
{
friend class B;
};

Applications

 Operator overloading
 Data sharing

6. Develop C++ program using dynamic memory allocation. (K5–Evaluate)

Program:

#include<iostream>

using namespace std;

int main()
{
int *p;

p=new int;

*p=10;

cout<<*p;

delete p;
}

Analysis

Advantages:

 Runtime allocation
 Flexible memory usage

Disadvantages:

 Memory leaks possible

Evaluation

new allocates memory dynamically and delete frees memory.

7. Analyze static class members and static member functions. (K4–Analyze)

Program:

class Test
{
static int count;

public:

static void display()

{
cout<<count;
}
};

int Test::count=0;

Applications

 Object counters
 Shared data

Advantages

 Single memory allocation

 Shared by all objects

8. Construct a program involving container classes and iterators. (K6–Create)

Program:

#include<iostream>
#include<vector>

using namespace std;

int main()
{
vector<int>v;

v.push_back(10);

v.push_back(20);

vector<int>::iterator it;
for(it=[Link]();it!=[Link]();it++)
cout<<*it;
}

Proxy Classes

Used as intermediate objects for accessing class members.

Evaluation

Benefits:

 Dynamic size
 Easy traversal
 Reusable structures

9. Develop a program illustrating function overloading. (K6–Create)

Program:

#include<iostream>
using namespace std;

class Add
{
public:

int sum(int a,int b)

{
return a+b;
}

float sum(float a,float b)

{
return a+b;
}
};

Role in Polymorphism

Function overloading supports compile-time polymorphism.

Advantages:

 Improved readability
 Reduced function naming complexity
10. Design program demonstrating operator overloading. (K6–Create)

Program:

#include<iostream>

using namespace std;

class Complex
{
int x;

public:

Complex operator +(Complex c)

{
Complex temp;

temp.x=x+c.x;

return temp;
}
};

Unary Operator Example

operator ++();

Binary Operator Example

operator +();

Justification

Operator overloading:

 Makes code intuitive

 Improves readability
 Supports user-defined data types

Conclusion

Operator overloading enhances flexibility and enables natural object manipulation in

C++.
UNIT II – INHERITANCE & POLYMORPHISM

16-Mark Answers

1. Explain the concepts of base classes and derived classes with suitable
examples. Discuss various forms of inheritance in C++. (K2–Understand)

Introduction

Inheritance is an Object-Oriented Programming feature through which a class acquires

properties and behaviors from another class.

Base Class

A class whose members are inherited by another class.

Derived Class

A class that inherits properties from the base class.

Syntax

class Base
{
};

class Derived : public Base

{
};

Example

class Animal
{
public:
void eat()
{
cout<<"Eating";
}
};

class Dog:public Animal

{
};

Dog inherits eat() from Animal.

Types of Inheritance
 1. Single Inheritance

A→B

2. Multiple Inheritance

A,B → C

3. Multilevel Inheritance

A→B→C

4. Hierarchical Inheritance

A
/ \
B C

5. Hybrid Inheritance

Combination of multiple inheritance types.

Advantages

 Code reuse
 Reduced redundancy
 Supports polymorphism

2. Develop a program demonstrating public, protected, and private inheritance.

(K3–Apply)

#include<iostream>
using namespace std;

class Base
{
public:
int x=10;

protected:
int y=20;

private:
int z=30;
};

class Derived:public Base

{
public:

void display()
{
cout<<x;
cout<<y;
}
};

int main()
{
Derived d;

[Link]();
}

Comparison

Inheritance Public Members Protected Members

Public Remain Public Remain Protected

Protected Become Protected Remain Protected

Private Become Private Become Private

Analysis

Public inheritance supports "is-a" relationship.

3. Analyze constructors and destructors in derived classes. (K4–Analyze)

Constructor

Special function called during object creation.

Destructor

Special function called during object destruction.

Example:

class Base
{
public:
Base()
{
cout<<"Base Constructor";
}

~Base()
{
cout<<"Base Destructor";
}
};

class Derived:public Base

{
public:

Derived()
{
cout<<"Derived Constructor";
}

~Derived()
{
cout<<"Derived Destructor";
}
};

Execution Order

Creation:

Base → Derived

Destruction:

Derived → Base

Significance

 Initializes objects
 Releases resources

4. Illustrate implicit derived-to-base conversion and class object conversion.

(K3–Apply)

Implicit Conversion

Derived object automatically converts into base object.

Example:

class Base{};
class Derived:public Base{};

Derived d;

Base b=d;

Class Object Conversion

Converts one class object into another.

class A
{
};

class B
{
public:
B(A x)
{
}
};

Applications

 Data conversion
 Inter-class communication

5. Compare composition and inheritance. (K5–Evaluate)

Inheritance

Represents is-a relationship.

Example:

Dog is an Animal

Composition

Represents has-a relationship.

Example:

Car has an Engine

Comparison
Inheritance Composition

is-a relationship has-a relationship

Strong coupling Loose coupling

Static design Flexible design

Evaluation

Use inheritance for hierarchy.

Use composition for modular design.

6. Develop a C++ program demonstrating function overriding. (K6–Create)

#include<iostream>
using namespace std;

class Base
{
public:

virtual void show()

{
cout<<"Base";
}
};

class Derived:public Base

{
public:

void show()
{
cout<<"Derived";
}
};

int main()
{
Base *p;

Derived d;

p=&d;

p->show();
}

Output:

Derived

Role in Runtime Polymorphism

Function call decided during runtime.

7. Explain virtual functions and dynamic binding. (K4–Analyze)

Virtual Function

Declared using keyword:

virtual

Example:

virtual void display();

Dynamic Binding

Function binding occurs during runtime.

Example

Base *ptr;

ptr=&d;

ptr->show();

Advantages

 Runtime polymorphism
 Flexible code
 Better extensibility

8. Construct a program illustrating the this pointer. (K6–Create)

#include<iostream>

using namespace std;

class Test
{
int x;

public:

void set(int x)
{
this->x=x;
}

void display()
{
cout<<this->x;
}
};

int main()
{
Test t;

[Link](10);

[Link]();
}

Importance

 Refers current object

 Resolves ambiguity
 Supports method chaining

9. Analyze abstract base classes and concrete classes. (K4–Analyze)

Abstract Base Class

Contains pure virtual function.

virtual void show()=0;

Cannot create objects.

Concrete Class

Implements all functions.

class A
{
public:
void show()
{
}
};

Example

class Shape
{
virtual void area()=0;
};

class Circle:public Shape

{
void area()
{
}
};

Advantages

 Supports abstraction
 Provides interface

10. Design a program demonstrating virtual destructors. (K6–Create)

#include<iostream>
using namespace std;

class Base
{
public:

virtual ~Base()
{
cout<<"Base Destructor";
}
};

class Derived:public Base

{
public:

~Derived()
{
cout<<"Derived Destructor";
}
};

int main()
{
Base *p=new Derived();

delete p;
}

Output:

Derived Destructor

Base Destructor

Evaluation

Without virtual destructor:

Derived destructor may not execute.

Benefits

 Prevents memory leaks

 Ensures proper resource deallocation
 Supports polymorphism

Conclusion

Virtual destructors are essential when deleting derived objects through base pointers.
UNIT III – LINEAR DATA STRUCTURES

16-Mark Answers

1. Explain Big-O, Omega, and Theta notations with suitable examples and
compare their significance in algorithm analysis. (K2–Understand)

Definition

Asymptotic notations are mathematical tools used to analyze algorithm efficiency.

Big-O Notation

Represents the upper bound or worst-case complexity.

Example:

[
f(n)=3n^2+5n+2
]

Big-O:

[
O(n^2)
]

Omega (Ω) Notation

Represents the lower bound or best-case complexity.

Example:

[
\Omega(n)
]

Theta (Θ) Notation

Represents the exact bound.

[
\Theta(n^2)
]

Comparison:
Notation Meaning

O Upper bound

Ω Lower bound

Θ Tight bound

Significance

 Predicts algorithm performance

 Compares algorithms
 Helps choose efficient methods

2. Analyze best, worst, and average case complexities. (K4–Analyze)

Best Case

Minimum execution time.

Example:

Linear search finds element at first position.

[
O(1)
]

Worst Case

Maximum execution time.

Element found at last position.

[
O(n)
]

Average Case

Expected execution over all inputs.

[
O(n/2)
]

Example:
Array:

10,20,30,40,50

Search 30 → Average case

Comparison:

Case Complexity

Best O(1)

Average O(n)

Worst O(n)

3. Develop a program to represent and manipulate arrays. (K3–Apply)

Array Representation

One-dimensional:

int a[5];

Two-dimensional:

int a[3][3];

Program

#include<iostream>
using namespace std;

int main()
{
int a[5]={10,20,30,40,50};

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

cout<<a[i];
}

Analysis

Advantages:

 Random access
 Easy implementation
Disadvantages:

 Fixed size
 Memory wastage

4. Construct an algorithm for stack implementation. (K6–Create)

Stack Principle

LIFO (Last In First Out)

Algorithm

PUSH

if(top==MAX-1)

Overflow

else

top++

stack[top]=item

POP

if(top==-1)

Underflow

else

item=stack[top]

top--

Example:

Push:

10,20,30

Pop:

30

Complexity:
Push:

O(1)

Pop:

O(1)

5. Develop linked list implementation of stack. (K6–Create)

Structure

struct node
{
int data;

node*next;
};

Push

Insert at beginning

Pop

Delete first node

Program:

void push(int x)
{
node*temp=new node;

temp->data=x;

temp->next=top;

top=temp;
}

Complexity

Push:

O(1)

Pop:
O(1)

Advantages:

 Dynamic memory allocation

6. Construct linked list implementation of queue. (K6–Create)

Queue Principle

FIFO

Program:

void enqueue(int x)
{
node*temp=new node;

temp->data=x;

rear->next=temp;

rear=temp;
}

Advantages over Array

 Dynamic size
 No overflow until memory full
 No shifting needed

Complexity:

Enqueue:

O(1)

Dequeue:

O(1)

7. Analyze singly linked list operations. (K4–Analyze)

Structure

struct node
{
int data;

node *next;
};

Operations:

1. Insertion
2. Deletion
3. Traversal
4. Searching

Example:

10→20→30→NULL

Insert 25:

10→20→25→30

Delete 20:

10→25→30

Complexity:

Insertion:

O(n)

Deletion:

O(n)

8. Apply stack operations to evaluate postfix expression. (K3–Apply)

Expression:

532*+

Steps:

Push 5

Push 3

Push 2
Multiply:

3×2=6

Push 6

Add:

5+6=11

Result:

11

Algorithm:

Scan expression

If operand push

If operator pop operands

Perform operation

Push result

9. Develop algorithm using stacks for expression evaluation. (K6–Create)

Algorithm:

For each character:

If operand

Push

Else

Pop operands

Perform operation

Push result

Program:

for(each symbol)
{
if(operand)
push()

else

evaluate()
}

Efficiency:

Time Complexity:

[
O(n)
]

Space Complexity:

[
O(n)
]

Applications:

 Compiler design
 Calculator evaluation

10. Design linked list-based polynomial addition. (K6–Create)

Polynomial:

[
3x^2+2x+1
]

[
2x^2+5x+4
]

Result:

[
5x^2+7x+5
]

Node Structure:

struct node
{
int coeff;

int power;

node *next;
};

Algorithm:

1. Compare powers
2. Add coefficients
3. Insert into result list
4. Move pointers

Program:

if(p1->power==p2->power)
{
sum=p1->coeff+p2->coeff;
}

Performance Analysis

Time Complexity:

[
O(m+n)
]

Advantages:

 Dynamic storage
 Efficient polynomial operations

Applications

 Symbolic computations
 Mathematical software
UNIT IV – NON-LINEAR DATA STRUCTURES

16-Mark Answers

1. Explain the structure and properties of trees and binary trees with suitable
examples. (K2–Understand)

Definition of Tree

A tree is a hierarchical non-linear data structure consisting of nodes connected by

edges.

Terminologies

 Root node
 Parent node
 Child node
 Leaf node
 Sibling
 Subtree
 Degree
 Height

Example

A
/|\
B C D
/\
E F

Root = A
Leaf Nodes = C,D,E,F

Binary Tree

A binary tree is a tree in which each node has at most two children.

A
/\
B C
/\ \
D E F

Properties

1. Maximum nodes at level i:

[
2^i
]

2. Maximum nodes in height h:

[
2^{h+1}-1
]

3. Minimum height:

[
\log_2(n+1)-1
]

Applications

 Expression trees
 Binary search trees
 Huffman coding

2. Develop a program for binary tree representation and traversal techniques.

(K6–Create)

Linked Representation

struct node
{
int data;
node *left,*right;
};

Traversal Algorithms

Preorder

Root → Left → Right

Inorder

Left → Root → Right

Postorder

Left → Right → Root

Program
void preorder(node*root)
{
if(root!=NULL)
{
cout<<root->data;
preorder(root->left);
preorder(root->right);
}
}

Example

A
/\
B C
/\
D E

Preorder:

ABDEC

Inorder:

DBEAC

Postorder:

DEBCA

Complexity:

O(n)

3. Analyze various binary tree representations. (K4–Analyze)

Array Representation

Nodes stored sequentially.

Parent:

[
i
]

Left Child:
[
2i
]

Right Child:

[
2i+1
]

Advantages

 Easy implementation
 Fast access

Limitations

 Memory wastage
 Suitable only for complete trees

Linked Representation

Uses nodes and pointers.

Advantages

 Dynamic memory allocation

 Flexible structure

Limitations

 Extra memory for pointers

Array Linked

Static Dynamic

Fast indexing Flexible

4. Explain threaded binary trees and advantages. (K4–Analyze)

Definition

Threaded binary trees replace NULL pointers with predecessor/successor links.

Types
 1. Single Threaded
2. Double Threaded

Example

A
/\
B C

Unused pointers become threads.

Advantages

 No recursion needed
 Faster traversal
 Better memory utilization

Disadvantages

 Complex insertion/deletion

5. Construct algorithms for Union and Find operations. (K6–Create)

Find Algorithm

Find(x)

while(parent[x]!=x)

x=parent[x]

return x

Union Algorithm

Union(x,y)

root1=Find(x)

root2=Find(y)

parent[root2]=root1

Example

Set1:

{1,2}
Set2:

{3,4}

After Union:

{1,2,3,4}

Complexity

Find:

O(log n)

Union:

O(log n)

6. Develop a program implementing Union-Find operations. (K6–Create)

int parent[10];

int Find(int x)
{
while(parent[x]!=x)
x=parent[x];

return x;
}

void Union(int x,int y)

{
parent[Find(y)] = Find(x);
}

Evaluation

Advantages:

 Efficient set management

 Fast connectivity checking

Applications:

 Network connectivity
 Kruskal algorithm
7. Explain graph representations using adjacency matrix and adjacency list.
(K4–Analyze)

Adjacency Matrix

Uses 2D matrix.

Example:

ABC

A 011

B 101

C 110

Complexity

Space:

[
O(V^2)
]

Adjacency List

A → B→C

B → A→C

C → A→B

Complexity

[
O(V+E)
]

Comparison

Matrix List

More memory Less memory

Fast lookup Suitable for sparse graphs

8. Develop algorithms for graph traversals BFS and DFS. (K6–Create)

BFS Algorithm

[Link] source node into queue

[Link] node

[Link] adjacent nodes

[Link]

DFS Algorithm

Visit node

Recursively visit adjacent nodes

Complexity

BFS:

[
O(V+E)
]

DFS:

[
O(V+E)
]

Applications:

 Shortest path
 Cycle detection

9. Analyze connected components and methods for identifying them. (K4–

Analyze)

Definition

Connected components are groups of vertices where every node can reach another.

Example:

A—B C—D
Two connected components:

{A,B}

{C,D}

Methods

1. DFS
2. BFS
3. Union-Find

Applications

 Social network analysis

 Image segmentation

10. Construct a C++ program using STL for tree or graph operations. (K6–
Create)

Program

#include<iostream>
#include<vector>

using namespace std;

int main()
{
vector<int>graph[5];

graph[0].push_back(1);

graph[0].push_back(2);

for(int x:graph[0])

cout<<x<<" ";
}

Benefits of STL

 Reusable components
 Faster development
 Efficient algorithms
 Dynamic memory handling

Conclusion
STL simplifies implementation of complex tree and graph structures and improves
coding efficiency.
UNIT V – SORTING & SEARCHING

16-Mark Answers

1. Explain the working of Insertion Sort with an example and analyze its time
complexity. (K2–Understand)

Definition

Insertion Sort is a sorting technique that builds a sorted array one element at a time
by inserting elements into their correct positions.

Algorithm

1. Assume first element is sorted.

2. Select next element.
3. Compare with previous elements.
4. Shift larger elements.
5. Insert in proper position.

Example

Array: 25, 15, 40, 10

Pass 1:
15 < 25

15,25,40,10

Pass 2:

15,25,40,10

Pass 3:

10,15,25,40

Sorted Array:

10,15,25,40

C++ Program

for(i=1;i<n;i++)
{
key=a[i];
j=i-1;
while(j>=0 && a[j]>key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}

Time Complexity

Best Case: O(n)

Average Case: O(n²)

Worst Case: O(n²)

Advantages

 Simple implementation
 Efficient for small datasets

Disadvantages

 Not suitable for large data

2. Develop an algorithm for Merge Sort and illustrate the sorting process. (K6–
Create)

Definition

Merge Sort follows Divide and Conquer strategy.

Algorithm

MergeSort(A,low,high)

if(low<high)

mid=(low+high)/2

MergeSort(A,low,mid)

MergeSort(A,mid+1,high)

Merge(A,low,mid,high)

Example
Input:

38,27,43,3,9,82,10

Split:

38,27,43,3

9,82,10

Merge:

3,9,10,27,38,43,82

Complexity

Time Complexity:

O(nlogn)

Space Complexity:

O(n)

Advantages

 Stable sorting
 Efficient for large datasets

3. Analyze the working of Quick Sort and compare complexities. (K4–Analyze)

Definition

Quick Sort selects a pivot and partitions elements around it.

Algorithm

QuickSort(A,low,high)

pivot=A[low]

Partition array

QuickSort(left)

QuickSort(right)

Example
Input:

50,30,70,20,90

Pivot=50

Partition:

30,20 |50|70,90

Sorted:

20,30,50,70,90

Complexity Comparison

Case Complexity
Best O(nlogn)
Average O(nlogn)
Worst O(n²)

Worst case occurs when pivot selection is poor.

Advantages

 Faster in practice
 Requires less memory

4. Construct a Heap Sort algorithm and evaluate performance. (K6–Create)

Definition

Heap Sort uses Binary Heap.

Algorithm

Build Max Heap

Swap root with last element

Reduce heap size

Heapify

Repeat

Example
Input:

15,8,20,5

Heap:

20

/\

15 8

Sorted:

5,8,15,20

Time Complexity

Build Heap:

O(n)

Sorting:

O(nlogn)

Advantages

 In-place sorting
 Better worst-case complexity

5. Compare Insertion Sort, Merge Sort, Quick Sort and Heap Sort. (K5–Evaluate)

Algorithm Best Average Worst Space

Insertion O(n) O(n²) O(n²) O(1)
Merge O(nlogn) O(nlogn) O(nlogn) O(n)
Quick O(nlogn) O(nlogn) O(n²) O(logn)
Heap O(nlogn) O(nlogn) O(nlogn) O(1)

Evaluation

Insertion Sort → Small datasets

Merge Sort → External sorting

Quick Sort → General-purpose sorting

Heap Sort → Memory-constrained systems

6. Develop a program for Linear Search and analyze complexity. (K6–Create)

Program

for(i=0;i<n;i++)
{
if(a[i]==key)
{
cout<<"Found";
break;
}
}

Example

Array:

10,20,30,40

Search:

30

Output:

Found at position 3

Complexity

Best:

O(1)

Worst:

O(n)

Average:

O(n)
7. Construct a program for Binary Search with example. (K6–Create)

Program

low=0;

high=n-1;

while(low<=high)
{
mid=(low+high)/2;

if(a[mid]==key)

return mid;

else if(a[mid]<key)

low=mid+1;

else

high=mid-1;
}

Example

Array:

10,20,30,40,50

Search:

30

mid=30

Element Found

Complexity

O(logn)

8. Analyze Linear Search and Binary Search. (K4–Analyze)

Linear Search Binary Search

Sequential search Divides search space
Linear Search Binary Search
Works on unsorted data Requires sorted data
O(n) O(logn)

Preferred Situations

Linear Search:

 Small datasets
 Unsorted data

Binary Search:

 Large sorted datasets

9. Evaluate sorting algorithms and recommend one for large datasets. (K5–
Evaluate)

Comparison

Insertion Sort:
Simple but inefficient

Merge Sort:
Efficient and stable

Quick Sort:
Fast average performance

Heap Sort:
Better worst case

Recommendation

For large datasets:

Merge Sort or Quick Sort

Reason:

 O(nlogn)
 Better scalability
 Efficient performance
10. Design an application integrating sorting and searching techniques. (K6–
Create)

Application: Student Record Management System

Functions:

 Store student records

 Sort records by marks
 Search by register number

Working

Step 1:
Input student details

Step 2:
Sort using Quick Sort

Step 3:
Search using Binary Search

Justification

Quick Sort:
Fast sorting

Binary Search:
Efficient searching

Advantages

 Faster retrieval
 Efficient data management
 Reduced search time

Conclusion: Combining sorting and searching techniques improves system

performance significantly.