CD3291-DATA STRUCTURES AND ALGORITHMS
QUESTION BANK
UNIT-I
ABSTRACT DATA TYPES
PART-A
1. What is a data structure?
A data structure is a method for organizing and storing data which would allow efficient data retrieval and usage. A
data structure is a way of organizing data that considers not only the items stored, but also their relationships to each
other.
2. Why do we need data structures?
● Data structures allow us to achieve an important goal: component reuse.
● Once data structure has been implemented, it can be used again and again in various applications.
3. List some common data structures.
● Stacks
● Queues
● Lists
● Trees
● Graphs
● Tables
4. Define ADT (Abstract Data Type) with example
An abstract data type (ADT) is a set of operations and mathematical abstractions , which can be viewed as how the
set of operations is implemented. Objects like lists, sets and graphs, along with their operation, can be viewed as
abstract data types, just as integers, real numbers and Booleans.
5. Mention the features of ADT.
a. Modularity
i. Divide program into small functions
ii. Easy to debug and maintain
iii. Easy to modify
b. Reuse
i. Define some operations only once and reuse them in future
c. Easy to change the implementation
6. What is a Linear data structure?
1
Linear data structures is a continuous arrangement of data elements in the memory. It can be constructed by using
array data type. The following list of operations applied on linear data structures.
1. Add an element
2. Delete an element
3. Traverse
4. Sort the list of elements
5. Search for a data element
For example Stack, Queue, Tables, List, and Linked Lists.
7. State the difference between arrays and linked lists?
8. What are the advantages of modularity?
• It is much easier to debug small routines than large routines.
It is easier for several people to work on a modular program simultaneously
• A well-written modular program places certain dependencies in only one routine, making changes easier.
9. Define class.
A class is a user-defined data type. It consists of data members and member functions, which can be accessed and
used by creating an instance of that class. It represents the set of properties or methods that are common to all
objects of one type. A class is like a blueprint for an object.
Example: Consider the Class of Cars. There may be many cars with different names and brands but all of them will
share some common properties like all of them will have 4 wheels, Speed Limit, Mileage range, etc. So here, Car is
the class, and wheels, speed limits, mileage are their properties
2
10. Define Object.
The Object is an instance of a Class. When a class is defined, no memory is allocated but when it is instantiated (i.e.
an object is created) memory is allocated. An object has an identity, state, and behavior. Each object contains data
and code to manipulate the data. Objects can interact without having to know details of each other’s data or code, it
is sufficient to know the type of message accepted and type of response returned by the objects.
For example “Dog” is a real-life Object, which has some characteristics like color, Breed, Bark, Sleep, and Eats.
The example for object of car class can be:
obj = maruti()
Here, obj is an object of class car.
11. What is constructor?
The constructor is a method that is called when an object is created. This method is defined in the class and can be
used to initialize basic variables. If you create four objects, the class constructor is called four times. Every class has
a constructor, but its not required to explicitly define it.
12. Write short notes on python init .
The function init(self) builds your object. Its not just variables you can set here, you can call class methods too.
Everything you need to initialize the object(s). Lets say you have a class Plane, which upon creation should start
flying. There are many steps involved in taking off: accelerating, changing flaps, closing the wheels and so on.
classPlane:
def init (self):
[Link] = 2
13. Define [Link] are its types?
The inheritance is the process of acquiring the properties of one class(parent class) to another class(child class). In
inheritance, we use the terms like parent class, child class, base class, derived class, superclass, and subclass. The
Parent class is the class which provides features to another class. The parent class is also known as Base class or
Superclass. The Child class is the class which receives features from another class. The child class is also known as
the Derived Class or Subclass.
There are five types of inheritances, and they are as follows.
Simple Inheritance (or) Single Inheritance
Multiple Inheritance
Multi-Level Inheritance
Hierarchical Inheritance
Hybrid Inheritance
14. What is namespace?
A namespace is a declarative region that provides a scope to the identifiers (the names of types, functions,
variables, etc) inside it. Namespaces are used to organize code into logical groups and to prevent name collisions
that can occur especially when your code base includes multiple libraries.
15. What is divide an conquer?
A divide and conquer algorithm is a strategy of solving a large problem by breaking the problem into smaller sub-
problems solving the sub-problems, and combining them to get the desired output.
To use the divide and conquer algorithm, recursion is used
3
16. Define recursion.
A recursion is a process of function calling itself.
num = 3
print("The factorial of", num, "is", factorial(num))
if x == 1:
return 1 else:
return (x * factorial(x-1))
def factorial(x):
"""This is a recursive function
to find the factorial of an integer"""
17. Differentiate is shallow and deep copying?
[Link] are asymptotic notations.
Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends
towards a particular value or a limiting value.
For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is linear i.e. the best case
There are mainly three asymptotic notations:
Big-O notation
Omega notation
Theta notation
19. What is OOP?
Object-Oriented Programming or OOPs refers to languages that use objects in programming. Object-oriented
programming aims to implement real-world entities like inheritance, hiding, polymorphism, etc in programming.
4
The main aim of OOP is to bind together the data and the functions that operate on them so that no other part of the
code can access this data except that function.
OOPs Concepts:
Class
Objects
Data Abstraction
Encapsulation
Inheritance
Polymorphism
Dynamic Binding
Message Passing
20. Define Encapsulation
Encapsulation is defined as the wrapping up of data under a single unit. It is the mechanism that binds together code
and the data it manipulates. In Encapsulation, the variables or data of a class are hidden from any other class and can
be accessed only through any member function of their class in which they are declared. As in encapsulation, the
data in a class is hidden from other classes, so it is also known as data-hiding.
PART-B
1. Explain about Inheritance in detail.
Types of inheritances:
The inheritance is a very useful and powerful concept of object-oriented programming. Using the inheritance
concept, we can use the existing features of one class in another class.
In inheritance, we use the terms like parent class, child class, base class, derived class, superclass, and subclass.
The Parent class is the class which provides features to another class. The parent class is also known as Base class
or Superclass
The Child class is the class which receives features from another class. The child class is also known as the Derived Class
or Subclass.
There are five types of inheritances, and they are as follows.
Simple Inheritance (or) Single Inheritance
Multiple Inheritance
Multi-Level Inheritance
Hierarchical Inheritance
Hybrid Inheritance
The following picture illustrates how various inheritances are implemented.
5
Creating a Child Class
In Python, we use the following general structure to create a child class from a parent class.
Syntax
classChildClassName(ParentClassName):
ChildClass implementation
6
.
.
Let's look at individual inheritance type with an example.
1. Explain in detail about classes and object with example programs.
OOPs in Python is a programming approach that focuses on using objects and classes as same as other general
programming languages. The objects can be any real-world entities. Python allows developers to develop
applications using the OOPs approach with the major focus on code reusability.
classParentClass:
deffeature_1(self):
print('feature_1 from ParentClass is running...')
deffeature_2(self):
print('feature_2 from ParentClass is running...')
classChildClass(ParentClass):
deffeature_3(self):
print('feature_3 from ChildClass is running...')
obj = ChildClass()
obj.feature_1()
obj.feature_2()
obj.feature_3()
Class
A class is a blueprint for the object.
We can think of class as a sketch of a parrot with labels. It contains all the details about the name, colors,
size etc. Based on these descriptions, we can study about the parrot. Here, a parrot is an object.
2. The example for class of parrot can be :
class Parrot:
pass ance) is an instantiation of a class. When
7 class is defined, only the description
fo refore, no memory or storage is allocated.
Here, we use the class keyword to define an empty class Parrot. From class, we construct instances.
Object
An object (inst r the object
is defined. The
The example f
instance is a sp
obj = Parrot()
Here, obj is an object of class Parrot.
Suppose we have details of parrots. Now, we are going to show how to build the class and objects of
parrots.
8
Example:
class Parrot:
# class attribute
species = "bird"
# instance attribute
def init (self, name, age):
[Link] = name [Link] = age
# instantiate the Parrot classblu
= Parrot("Blu", 10) woo =
Parrot("Woo",
# access the class attributes
print("Blu is a {}".format(blu. class .species))
print("Woo is also a {}".format(woo. cla ss .species))
# access the instance attributes
print("{} is {} years old".format( [Link], [Link]))
print("{} is {} years old".format( [Link], [Link]))
[Link] is Recursion. Elaborate about Binary Search and File systems.
A recursion is a process of function calling itself.
example:
def factorial(x):
"""This is a recursive function
to find the factorial of an
if x == 1:
return 1
else:
num = 3
print("The factorial of", num, "is",
A binary search is an algorithm to find a particular element in the list. Suppose we have a list of thousand
elements, and we need to get an index position of a particular element. We can find the element's index
position very fast using the binary search algorithm.
There are many searching algorithms but the binary search is most popular among them.
The elements in the list must be sorted to apply the binary search algorithm. If elements are not sorted then
sort them first.
9
CD3291-DATA STRUCTURES AND ALGORITHMS
Let's understand the concept of binary search.
Concept of Binary Search
The divide and conquer approach technique is followed by the recursive method. In this method,
a functionis called itself again and again until it found an element in the list.
A set of statements is repeated multiple times to find an element's index position in the
iterative [Link] while loop is used for accomplish this task.
Binary search is more effective than the linear search because we don't need to search each list
index. Thelist must be sorted to achieve the binary search algorithm.
Let's have a step by step implementation of binary search.
We have a sorted list of elements, and we are looking for the index position of 45.
[12, 24, 32, 39, 45, 50, 54]
So, we are setting two pointers in our list. One pointer is used to denote the smaller value called low
and thesecond pointer is used to denote the highest value called high.
Next, we calculate the value of the middle element in the array.
1. mid = (low+high)/2
2. Here, the low is 0
and the high is 7.3. mid =
(0+7)/2
4. mid = 3 (Integer)
[Link] the concept of shallow and deep copying.
11
[Link] about the various asymptotic notations.
Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing
of its run-time performance. Using asymptotic analysis, we can very well conclude the
best case, average case, and worst case scenario of an algorithm.
Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to
work in a constant time. Other than the "input" all other factors are considered constant.
Asymptotic analysis refers to computing the running time of any operation in mathematical
units of computation. For example, the running time of one operation is computed as f(n)
and may be for another operation it is computed as g(n2).
This means the first operation running time will increase linearly with the increase in n and
the running time of the second operation will increase exponentially when n increases.
Similarly, the running time of both operations will be nearly the same if n is significantly
The time required by an algorithm falls under three types −
Best Case − Minimum time required for program execution.
Average Case − Average time required for program execution.
Worst Case − Maximum time required for program execution.
Asymptotic Notations
Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.
Ο Notation
Ω Notation
θ Notation
Big Oh Notation, Ο
The notation Ο(n) is the formal way to express the upper bound of an algorithm's running
time. It measures the worst case time complexity or the longest amount of time an algorithm
can possibly take to complete.
For example, for a function f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's running
time. It measures the best case time complexity or the best amount of time an algorithm can
possibly take to complete.
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
13
Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the upper boundof
The time required by an algorithm falls under three types −
Best Case − Minimum time required for program execution.
Average Case − Average time required for program execution.
Worst Case − Maximum time required for program execution.
Asymptotic Notations
Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.
Ο Notation
Ω Notation
θ Notation
Big Oh Notation, Ο
The notation Ο(n) is the formal way to express the upper bound of an algorithm's running
time. It measures the worst case time complexity or the longest amount of time an algorithm
can possibly take to complete.
For example, for a function f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's running
time. It measures the best case time complexity or the best amount of time an algorithm can
possibly take to complete.
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
13
Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the upper boundof
CD3291-DATA STRUCTURES AND ALGORITHMS
an algorithm's running time. It is represented as follows −
14
CD3291-DATA STRUCTURES AND ALGORITHMS
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n
> n0. }