UNIT - 1

ABSTRACT DATA TYPES

Abstract Data Types (ADTs) – ADTs and classes – introduction to OOP – classes in
Python – inheritance – namespaces – shallow and deep copying Introduction to
analysis of algorithms – asymptotic notations – divide & conquer – recursion –
analyzing recursive algorithms

1.1 Abstract Data Types (ADTs)

Abstraction is the process of providing only the essential information and hiding the
other background information.

Data types such as int, float, double, long, etc. are considered to be in-built data types
and we can perform basic operations with them such as addition, subtraction,
division, and multiplication

An abstract data type (ADT) is a high-level description of a data structure that

defines the behavior of the data and the operations that can be performed on it,
without specifying the implementation details. It focuses on what the data structure
can do rather than how it is implemented.

Example:
Some of the commonly used Abstract data types are
i)List ADT, ii) Stack ADT and iii)Queue ADT

1.1 Abstract Data Type (ADT):

Definition:

· Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a
set of values and a set of operations.

· It mentions what operations are to be performed but not how these operations will be
implemented.
 · It is called “abstract” because it gives an implementation-independent view.

The process of providing only the essentials and hiding the details is known as abstraction.

Types of Abstract Data Types:

Some of the important types of ADT are

i) List
ii) Stack
iii) Queue
iv) Tree
v) Graph
vi) Hash Table
1. List ADT:

The data is generally stored in key sequence in a list.

· Linked list are the linear data structures which are not stored
consequently, but they are linked with each other using Pointers.
· The node of a linked list is composed of data and a pointer called next.
· Application: Image viewing app, Music player app, etc…
2. Stack ADT:

Stacks are the linear Data Structure which are based on the principle of LIFO(Last In First Out)
where data which is entered last will be the first to get accessed.
It is built using array structure and has operations namely
· Push() – add elements
· Pop() – delete elements
· Top() – Access the elements only from the top of the stack, top is the pointer
indicate current position of the stack.
3. Queue

Queue is also a linear data structure which is based on the principle of FIFO (First In First Out)
where the data entered first will be accessed first.
It is built using the array data structure and has the following operations
· Enqueue() – add elements to the queue
· Dequeue() – Delete elements from the queue
4. Trees:

Trees are the non-linear Data Structure which have root and nodes. The root is the node from where
the data originates, and it is the parent node for its following node. The preceding nodes are called
the parent and the following nodes are called child. The levels of a tree have shown the depth of
information. The last node is called as leaves which does not have any child node.
5. Graphs:

Graph is a data structure that store the data as collection of vertices that are connected by
edges.

· Graph mostly used to find the various cost to distance between various points called as
nodes and find the least path.

Application: Google Maps, Uber.

6. Hash Maps:

This data structure is same as what dictionaries are in python.

Application: Phonebooks, databases, compiler.

Apart from this commonly used datatype, Python provides built-in ADTs like lists, tuples, and
dictionaries, and you can also create custom ADTs using classes.

i) List in Python:

Lists are used to store multiple items in a single variable. Lists are created using square brackets.

List is a collection which is ordered and changeable. Allows duplicate members.

Example:

Fruit= ["apple", "banana", "cherry"]

print(Fruit)

Output:

['apple', 'banana', 'cherry']

ii) Tuple in Python:

Tuples are used to store multiple items in a single variable. A tuple is a collection which is ordered
and unchangeable Tuples are written with round brackets.

Example:

Fruit= ("apple", "banana", "cherry")

print(Fruit)

Output:

('apple', 'banana', 'cherry')

 iii) Set in Python:

Python, a "set" is a built-in data type that represents an unordered collection of unique elements.
It is defined by enclosing elements inside curly braces {} or by using the set() constructor.

One of the main characteristics of sets is that they automatically remove duplicates, so each
element can appear only once in the set. Additionally, sets do not support indexing or slicing, as
they are unordered collections.

Example:

student_id = {112, 114, 116, 118, 115}

print('Student ID:', student_id)
Output:

Student ID: {112, 114, 115, 116, 118}

iv) Dictionary in Python:

A dictionary is a built-in data type that represents an unordered collection of key-value pairs. It is
also known as an associative array, map, or hash table in other programming languages.
Dictionaries are enclosed in curly braces {} and consist of key-value pairs separated by colons.

Example:

my_dict = { "name": "John", "age": 30, "city": "New York"}

print(my_dict)

Output:

{'name': 'John', 'age': 30, 'city': 'New York'}

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 EnggTree.com

Downloaded from EnggTree.com

 Department of Information Technology
Academic Year: 2024- 2025 (Odd Semester)

Degree, Semester & Branch: III Semester, B.Tech, & IT

Regulation: Anna University R 2021
Course Code & Title: CD3291 DATA STRUCTURES AND ALGORITHMS
Name of the Faculty: Mrs. G. Mareeswari, AP/IT
QUESTION BANK – UNIT I
ABSTRACT DATATYPES
PART –A
TWO MARKS
1. What is Abstract Data type? (or) Define ADT. [Nov/Dec 2022, Apr/May 2025]
Abstract Data type (ADT) is a type (or class) for objects whose behaviour defined by
a set of value and a set of operations.
The ADT only mentions what operations are to be performed but not how the
operations will be implemented.
2. What is advantage of an ADT ?
The advantages of ADT are -
1. Change: The implementation of the ADT can be changed without making changes
in the client program that uses the ADT.
2. Understandability: ADT specifies what is to be done and does not specify the
implementation details. Hence code becomes easy to understand due to ADT.
3. Reusability: The ADT can be reused by some program in future.
4. Flexibility: Different implementations are possible for the same ADT.
3. Mention the features of ADT. [Nov/Dec 2022]
Data abstraction, information hiding, Data structure independence, encapsulation,
Modularity, Robustness
4. Define Data structures
• Its a way organizing data in such a way so that data can be easier to use.
• A data structure is a particular way of organizing data in a computer so that it can be
used efficiently.
A scheme for organizing related pieces of information
5. Explain about the classification of data structures.

1
6. What do you mean by linear data structure? Give examples
(or)
Give some examples of linear structure. [Apr/May 2022]
In Linear Data structure, data’s are arranged in linear order.
Ex: Arrays, Linked list, Stack and Queue.
7. What do you mean by linear data structure? Give example.
In non-linear Data structure, data’s are arranged in hierarchical order.
Ex: Trees, Graphs.
8. Enlist the various operations that can be performed on data structure.
1. Create
2. Insertion of element
3. Deletion of element
4. Searching for the desired element
5. Sorting the elements in the data structure
6. Reversing the list of elements.
9. What is the difference between ADT and data structure? [Apr/May 2022]
ADT
ADT is a logical description Data structure is concrete.
ADT is the logical picture of the data and Data structure is the actual representation of
the operations to manipulate the component the data during the implementation and the
elements of the data. algorithms to manipulate the data elements.
10. Define data structures and how the data types are classified at the higher level.
[Nov/Dec 2023]
Data structures are a specific way of organizing data in a specialized format on a computer so
that the information can be organized, processed, stored, and retrieved quickly and
effectively. In data structures, data types are classified at a higher level into two main
categories: Primitive Data Types and Non-Primitive Data Types.
11. List out the areas in which data structures are applied extensively.
Following are the areas in which the data structures are applied extensively.
1. Operating system - The data structures like priority queues are used for scheduling the
jobs in the operating system.
2. Compiler design -The tree data structure is used in parsing the source program.
Stack data structure is used in handling the recursive calls.
3. Database management system -The file data structure is used in database management
systems. Sorting and searching techniques can be applied on these data in the file..
4. Numerical analysis package -The array is used to perform the numerical
analysis on the given set of data.
5. Graphics -The array and linked list are useful in graphics application
6.Artificial intelligence - The graph and trees are used for the applications like building
expression trees, game playing.
7. Networking - The graph is used for finding the shortest path length between any two
computers that are connected in a LAN
8. Simulation - The queue is used for simulation and modeling.
12. What is oops in python?
In Python, object-oriented Programming (OOP) is a programming paradigm that uses
objects and classes in prograniming. It aims to implement real-world entities like inheritance,
polymorphisms, encapsulation, etc. in the programming The main concept of OOPs is to bind
the data and the functions that work on that together as a single unit so that no other part of
the code can access this data.

2
13. What is class?
A class is a collection of objects. A class contains the blueprints or the prototype from which
the objects are being created. It is a logical entity that contains some attributes and methods.
14. What is objects?
The object is an entity that has a state and behavior associated with it. It may be any real-
world object like a mouse, keyboard, chair, table, pen, etc. Integers, strings, floating-point
numbers, even arrays, and dictionaries, are all objects. More specifically, any single integer
or any single string is an object.
15. What is __init__ method?
The init method is similar to constructors in C++ and Java. It is run as soon as an object of a
class is instantiated. The method is useful to do any initialization you want to do with your
object.
16. What is Python inheritance?
Inheritance is a mechanism through which we create a class or object based on another class
or object. In other words, the new objects will have all the features or attributes of the class or
object on which they are based. We refer to the created class as the derived or child class, and
the class from which it inherits is the base or parent class
17. Is inheritance possible in Python?
An object-oriented programming language like Python, not only supports inheritance but
multiple inheritance as well. The mechanism of inheritance allows programmers to create a
new class from a pre-existing class, which supports code reusability. We
Can also say that the methods defined in the parent class are reused to the child class.
list the advantages of using classes in python.
1. classes provide an easy way of keeping the data members and methods together in one
place which helps in keeping the program more organized.
2. using classes also provides another functionality of this object-oriented programming
paradigm, that is inheritance.
3. classes also help in overriding any standard operation.
4. using classes provides the ability to reuse the code which makes the program more
efficient.
5. grouping related functions and keeping them in one place provides a clean structure to
the code which increases the readability of the program.
18. What is self-parameter?
The self-parameter is a reference to the current instance of the clam, and is used to access
variables that belongs to the class.
19. What is class attributes?
Class attributes are attributes that have the same value for all class instance.
20. List the benefits of using the super() function.
We are not required to remember or specify the parent class name to access its methods.
We can use the super() function in both single and multiple inheritances.
The super() function support code reusability as there is no need to write the entire
function.
21. What is namespace.
A namespace is a system that has a unique name for each and every object in Python. An
object might be a variable or a method. A name or identifier is the name given to objects
when we create objects in python.
22. What is shallow copy?
A shallow copy is a copy of an object that stores the reference of the original elements. It
creates the new collection object and then occupying it with reference to the child objects
found in the original.

3
23. What is deep copy?
A deep copy is a process where we create a new object and add copy element recursively.
24. List the difference between shallow copy and deep copy. [Nov/Dec 2024]
SHALLOW COPY DEEP COPY
A shallow copy constructs a new compound A deep copy constructs new compound
object and then (to the extent possible) object and then, recursively, inserts into it of
inserts references into it to the objects found the objects found in the original.
in the original.
A shallow copy stores references which are Deep copy stores copies of an absolute
absolute to the original memory address in object's values.
the runtime code.

Shallow copy does the same in run time Deep copy does not reflect any change
code. made to the new/copied object in the orginal
object.
If the orginal do not have any nested Deep copy is necessary when the original
objects, shallow copy is the same as deep objects should not be modified.
copy.
25. Define Asymptotic notations.
Asymptotic notations are used to represent the complexities of algorithms for asymptotic
analysis. These notations are mathematical tools to represent the complexities. Asymptotic
analysis refers to computing the running time of any operation in mathematical units of
computation.
26. List the commonly used asymptotic notations to calculate the running time complexity
of an algorithm.
1. Big O notation
2. Big theta notation
3. Big omega notation
27. What is an Algorithm? How to compute its time complexity? [Apr/May 2023]
An algorithm is a step-by-step procedure or formula for solving a problem. It is a finite
sequence of well-defined instructions, typically to solve a class of problems or perform a
computation.
Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run
as a function of the length of the input. It is usually expressed using Big O notation
28. What is Recursion? (or) What is recursion in data structure? [ Nov/Dec 2023]
The process in which a function calls itself directly or indirectly is called recursion and the
corresponding function is called as recursive function.
29. List the advantages of Recursion.
Advantages of recursion
A complicated functions can be split down into smaller sub-problems utilizing
recursion.
Sequence creation is simpler through recursion than utilizing any nested iteration.
Recursion functions rounder the code look simple and effective.
30. List the disadvantages of Recursion
A lot of memory and time is taken though recursive calls which makes it expensive
for use.
Recursive functions are challenging to debug
The reasoning behind recursions can sometimes be tough to think through

4
31. What is recurrence relation?
A recurrence relation is an equation that defines a sequence where any termin defined in
terms of its previous terms.
32. What do you understand by the term algorithmic strategy?
Algorithmic strategies is a general approach by which many problems can be solved
algorithmically. These problems may belong to different areas of computing. Algorithmic
strategies are also called as algorithmic techniques or algorithmic paradigm.
33. Enlist few algorithmic strategies
1. Brute Force 2. Divide and Conquer 3. Greedy Method
4. Dynamic Programming 5. Backtracking 6. Branch and Bound
34. What are the drawbacks in using the standard unit of time, to measure the runtime of
an algorithm?
Ans. The runtime of an algorithm can not be measured in standard unit of time because in
multiuser system running time depends on many factors such as –
1) System load 2) Number of other programs running
3) Instruction set used 4) Speed of underlying hardware
If we use standard unit of time such as seconds, milliseconds, minutes and so on for
measuring the runtime of algorithm then we get varied result for same set of input data.
Hence the time complexity given in terms of frequency count
35. What are the types of Analysis of Algorithms? [Apr/May 2022]
There are five types of Algorithm Analysis
They are
i) Best Case Analysis
ii) Worst Case Analysis
iii) Average Case Analysis
iv) Amortized Analysis
v) Asymptotic Analysis
36. Identify how you will measure input size of an algorithm. [Nov/Dec 2023]
The input size is typically denoted by n and depends on the nature of the problem and the
type of input the algorithm processes.
Some common ways to measure the input size of an algorithm:
1. Number of Elements – Ex Sorting problem
2. Length of Input – Ex Searching in string input
3. Number of Vertices and Edges – Ex Graph
4. Dimensions of Input – Ex Matrix dimension rows and columns
5. Total Bits – In cryptarithmetic algorithms
37. Define Accessors method in python. [Nov/Dec 2023]
This method is used to access the state of the object i.e, the data hidden in the object can be
accessed from this method. However, this method cannot change the state of the object, it can
only access the data hidden. We can name these methods with the word get.
38. Differentiate time complexity from space complexity.
Ans. : Time complexity is amount of time required by a program to execute.
The space complexity is amount of space required by a program to execute.
39. Write the concept of time and space complexity. How do you measure the efficiency of
an algorithm? [Nov/Dec 2024]
Ans. : Time complexity is the amount of time required by an algorithm to execute. Fr
computing the time complexity the frequency count of the basic operation in the algorithm is
computed. This frequency count is then denoted in terms o asymptotic notations to express
the time complexity of an algorithm. The space complexity is an amount of space required by
an algorithm. The space complexity is denoted in terms of asymptotic notations.

5
40. Establish the relation between 0 and omega.
Ans.: The notation O represents the upper bound of algorithm's running time. The omega
notation omega represents the lower bound of algorithm's running time.
The theta notion represents the running time-between upper and lower bound. If f(n)
and g(n) are two functions then, f(n) = O(n) if and only if f(n) = 0 (g(n)) and f(n) =omega
g(n)).
41. What is the best, worst and average case time complexities of linear search algorithm?
Ans. The O(n) is the best,worst and average case time complexity of linear search algorithm
42. Define Big oh notation.
Ans. f(n) and g(n) be two non-negative functions.
Let no and constant c are two integers such that no denotes some value of input and n> no.
Similarly c is some constant such that c>0. We can write
f(n) <= c *g(n)
then f(n) is big oh of g(n). It is also denoted as f(n) e O (g(n)). In other words f(n) k less than
g(n) if g(n) is multiple of some constant c.

43. Define Big omega notation.

Ans. A function f(n) is said to be in 2 (g(n)) if f(n) is bounded below by some positive
constant multiple of g(n) such that
f(n) ≥ c* g(n) For all n ≥ no
It is denoted as f(n) belongs to omega (g(n)). Following graph illustrates the curve for omega
notation.

44. Define Big theta notation.

Ans. Let F(n) and g(n) be two non negative functions. There are two positive constants
namely c, and c₂ such that
C1(n) ≤ c2 g(n)
Then we can say that
f(n) belongs to theta (g(n))
45. List the asymptotic classes in increasing order.
Ans. 1. Constant(1) 2. Logarithmic(log n) 3. Linear(n) 4. n log n
5. Quadratic (n) 6. cubic(n³) 7. Exponential((2) 8. Factorial (n!)
46. Compare the orders of growth of n(n-1)/2 and n².
Ans: For comparing the orders of growth of n(n-1)/2 and n² we consider some Sample value
of n.

6
 47. What kind of problems can be solved using divide and conquer method?
Ans.: The problems can be divided into sub-problems, and on solving all the sub-problems
the solution for the original problem can be obtained. This type of problems are usually
solved using divide and conquer method. For example.
1) Binary search 2) Merge sort 3) Quick sort 4)Finding maximum and minimum.
48. What is the necessary precondition for the binary search?
Ans : For the binary search the list should be sorted either in ascending or descending order.
49. What are the various object oriented principles? [Apr/May 2024]
OOP allows objects to interact with each other using four basic principles: encapsulation,
inheritance, polymorphism, and abstraction. These four OOP principles enable objects to
communicate and collaborate to create powerful applications.
50. What is Encapsulation? Give Example [Apr/May 2025]
The encapsulation refers to the bundling of data (attributes) and methods (functions) that
operate on the data into a single unit, typically a class.
Ex:
Encapsulation in Python is like having a bank account system where your account balance
(data) is kept private. You can't directly change your balance by accessing the account
database. Instead, the bank provides you with methods (functions) like deposit and withdraw
to modify your balance safely.
51. State the usage of namespace [Apr/May 2025]
Namespaces are used to organize code into logical groups, prevent naming conflicts, and
manage the scope of identifiers (like variables, functions, and classes). They provide a way to
group related code elements together, preventing naming collisions, especially in larger
projects or when using external libraries.
There are three types of namespace.
 Built in namespace
 Global namespace
 Local namespace
52. What is the upper bound of f(n) = 4n2 + 3 [Apr/May 2025]
Ans: Upper Bound O(n) = n2
53. Find the time complexity of the following recurrence relation: [Nov/Dec 2024]

Ans:
Here T(n)= n-1 = ϴ(n)

PART – B Questions
1. List out all Object-Oriented Programming (OOPs) Concepts and explain in detail.
[Apr/May 2022]
2. Explain about asymptotic notations and their role in algorithmic analysis. [Apr/May 2022]
3. Difference and explain in detail about the shallow and Deep copy of a class with suitable
example. [Nov/Dec 2022] [Apr/May 2024]
(or)
Explain the concepts of shallow and Deep copy of a class with an example. [Apr/May 2023]
(or)
Discuss the shallow and deep copying and differentiate its pros and cons. [Nov/Dec 2023]

7
4. Write a short note on the ADT and Objects. [Nov/Dec 2022]
5. Discuss the Analysis of recursive algorithm with factorial example. [Apr/May 2023]
6. Explain the concepts of Python Inheritance with an example. [Apr/May 2023]
7. Explain the Asymptotic Notations in detail and their types with a suitable example program.
[Nov/Dec 2023]
8. Write a short note on the namespace in python and its types. [Nov/Dec 2023]
9. Explain in short about python classes and objects. [Nov/Dec 2023]
10. Differentiate Data Types, Data Structures and Abstract Data Types. [Nov/Dec 2023]
11. List the four factors that are dependent by the running time of a program. [Nov/Dec 2023]
12. Assume an algorithm A, that solves problems by dividing them into 5 sub-problems of half
the size. Then, recursively solving each sub-problem and combining the solution in linear
time O(n). What is the recurrence relation of the algorithm A? [Nov/Dec 2023]
13. With an example describe the two types of looping constructs used in Python.
[Nov/Dec 2023]
14. Describe the three steps involved in divide-and-conquer paradigm and how it is applied in
merge sort algorithm. [Nov/Dec 2023]
15. What are the various criteria used to improve the effectiveness of the algorithm?
[Nov/Dec 2023]
16. Suppose you are on the design team for new e-book reader. What are the primary classes and
methods that the Python software for your reader will need? Draw an inheritance diagram for
this and implement it. Your software architecture should at least include ways for customers
to buy new books, view their list of purchased books, and read their purchased books.
[Apr/May 2024]
17. Given an unsorted sequence, S, of integers and an integer k, describe a recursive algorithm
for rearranging the elements in S so that all elements less than or equal to k come before any
elements larger than k. What is the running time of your algorithm on a sequence of n
values? [Apr/May 2024]
18. Write a short Python function that takes a positive integer n and returns the sum of the
squares of all the positive integers smaller than n. [Apr/May 2024]
19. What is objects? Explain the procedure of creating and using objects with example.
[Apr/May 2024]
20. Write a Python function that finds the minimum and maximum values in a sequence without
using any loops. [Apr/May 2024]
21. Write an algorithm to perform binary search and analyse its time complexity.
[Nov/Dec 2024]
22. Create a class Person with name and Id as data members. Define two classes Student and
Faculty. These classes inherit the properties of Person class. Student has semester number,
marks of five subjects and total as additional data. Define a member function display_result()
to display the result of a Student. Faculty class has salary_per_month as an additional data
member. Also define a member function display_salary() which prints the annual salary of an
faculty. Implement the inheritance relationship in Python. [Apr/May 2025]
23. Consider an n-element array A containing distinct integers that are listed in increasing order.
Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if
such a pair exists. What is the running time of your algorithm? [Apr/May 2025]
24. What is operator overloading? List any two operators that cannot be overloaded. Write a
program to overload '+’ operator to multiply two fractions. [Nov/Dec 2024]
25. ALGORITHM Q(n)
//Input: A positive integer n
if n = 1 return 1
else

8
 return Q(n - 1) +2^ * n-1
Identify the basic operation in the algorithm. Set up the recurrence relation for the number of
times the algorithm's basic operation is executed and solve it using back substitution.
[Nov/Dec 2024]
26. Find the time complexity of the recurrence: [Nov/Dec 2024]

27. Develop an inheritance hierarchy based upon a Polygon class that has abstract methods area()
and perimeter(). Implement classes Triangle, Quadrilateral, Pentagon that extend this base
class, with the obvious meanings for the area() and perimeter() methods. Also implement
classes, Isosceles Triangle and Rectangle that have the appropriate inheritance relationships.
Explain the inheritance relationship and write a simple program that allows users to create
polygons of the various types and input their geometric dimensions, and the program that
outputs their area and perimeter. [Nov/Dec 2024]
28. For each of the following, determine the asymptotic worst-case runtime in terms of n.
[Nov/Dec 2024]

29. Discuss about object-oriented design goals, object-oriented principles and object oriented
design patterns.
30. Write a python program to show implementation of a iterator class for any sequence type.
31. Write a python program to create an abstract class ‘Polygon’ and Derived classes are
Triangle, Rectangle and pentagon. Define as abstract method No of sides. Calculate and print
the circumference of the Shapes.
32. Describe the various operations of the list ADT with examples.
33. Write a program in Python to implement student details using class and object to demonstrate
ADT. Use appropriate data members and member functions for student class to get student
marks and to calculate the total marks.
34. Write a program in Python to implement library details using class and object to demonstrate
ADT. Use appropriate data members and member functions for student class to get book
details and to calculate fine for delayed submission of books.
35. Write a python program using class and object to display the car details. The implementation

9
 should have the class car with attributes Brand, prize, model and color. Create minimum 2
objects for the class and display the details.
36. Write a program in Python to implement Bank Account details using class and object to
demonstrate ADT. Use appropriate data members and member functions for Bank Account
class to get account details and to perform the following a. Withdraw b. Deposit c. Check
Balance
37. Describe the various asymptotic notations for analysis of algorithms.
38. Illustrate the ruler drawing using recursion traces. Implement a recursive function to draw an
English ruler using Python.
39. Write short notes on the following :
(i) Polymorphism
(ii) Operator overloading
(iii) Abstraction

10