Unit 1

Chapter -1
Introduction
To
Data
Structures
 Unit 1
Chapter -1
Introduction To Data Structures
Question & Answer: -

Ques1: Difference between data and information.

Ans:

Ques2: Define Data structures.

Ans:
The Organized collection of data is known as data structure.
OR
In Other words, the possible way in which the data values such as
integers, floats, chars are logically related among themselves are
defined by data structures.
OR
The data structures deal with the study of how the data is organized in
the memory. So, the data structure can also be defined as the logical
(or)mathematical model of a particular organization of data.
Data Structure = Organized data + Operations
Ques3: Why data structures are required?
Ans:
Data structures are essential for organizing and manipulating data in a
systematic and efficient way.
1. Efficient Data Organization: Data structures provide efficient
ways to organize and store data. Different structures are designed to
optimize specific operations like searching, insertion, deletion and
retrieval.
2. Algorithm Design: Efficient algorithm often relies on appropriate
data structures. Choosing the right data structure can significantly
impact the performance of algorithms. For example, a well-designed
data structure can lead to faster sorting or searching algorithms.
3. Resource Management: Data structures help in managing and
optimizing the use of resources such as memory. They enable
efficient storage and retrieval of information, reducing the overall
resource requirements of a program.
4. Abstraction: Data structures allow programmers to abstract
complex details and focus on high-level problem-solving. They
provide a way to represent and manipulate data in a more
understandable and modular manner.
5. Flexibility and Adaptability: Different data structures are suited
for different tasks. By understanding the characteristics and
behaviours of various data structures, programmers can choose the
most appropriate one for a specific problem or scenario.
Ques4: Mention the application of data structure.
Ans:
Designing and using data structure is good programming skill, the
data structure skills are not provided in general purpose programming
languages. The programmer who wants to use this structure has to
build them. The data structure is necessary for following reasons:

[Link] provides a function that can be used to retrieve the individual data
elements.
2. The data structure enables to solve the relationships between the
data elements that are relevant to the solution of the problem.
3. Data structure helps to describe the operation that must be
performed on the logically related data elements, the operations such
as creating, displaying, inserting, deleting, retrieving, etc.
4. Data structure enables to devise the methods of representing the
data elements in the memory of the computers, that will reduce the
loss of fragmentation and also allows to select the memory
configuration or storage structures.
5. Data structures give the freedom to the programmer to decide any
type of language that best suits for a particular problem. 6. The
algorithm can be improved by structuring the data in such a way that
the resulting operations can be efficiently carried out.
7. The data structure describes the physical and logical relationship
between the data items. It also provides a mode of access to each
element in the data structure.
8. Data structure helps in selection of an appropriate mathematical
model for writing a program.

Ques5: Explain the classification of data structures.

Ans:
The data structures are classified into two categories as shown below:

1. Primitive Data Structures:

The data structures which can be directly operated by machine
level instruction are called primitive data structures. In C
language the following are the primitive data structures
1. int
2. char
3. float
4. double
2. Non-Primitive Data Structures
The data structures which are not primitive are called non
primitive data structures, which means these are the data
structures that cannot be manipulated directly by machine
instructions
 Non-Primitive data structures are classified into two categories
1. Linear data structure
2. Non-Linear data structure

Linear Data Structures

A linear data structure is one which establishes the relationship of

adjacency between the elements in which all the elements are
stored in memory linearly or sequentially (one after the other).

Example:
1. Arrays
2. Linked List
3. Stack
4. Queues

Non-Linear Data Structures

Any data structure which establishes the relationships other than the
adjacency relationship is called Non-Linear data structures.

Example:

1. Trees
2. Graphs

Ques6: Write operations on primitive data structures.

Ans: Operations on Primitive Data Structures:-

1. Creation: The operation creates a data structure.
Example: int;
It results in creation of memory space for ‘i’ during the complication
of declaration statement.

2. Deletion: It provides complimentary effect of creation operation. It

leads to the efficient use of memory. It is used to destroy the data
structure. This operation is not supported in many programming
languages. In C language, we can use function free () for destroying
the data structure.
3. Selection: It is for accessing of data within a data structure. It
depends on type of data structure being used. Method of accessing is
one of the important operations in data structure.

4. Update: This operation is used to change data in the structure. An

assignment operation is a good example of an update operation.
eg: int i = 0;

i=5; //update operation.

Ques7: Explain the classification non-primitive data structures.

Ans:
The data structures which are not primitive are called non-primitive
data structures, which means these are the data structures that cannot
be manipulated directly by machine instructions.
Non-primitive data structures are classified into two categories: -
1. Linear data structure
2. Non-Linear data structure

Linear Data Structures:

A linear data structure is one which establishes the relationship of
adjacency between the elements in which all the elements are stored
in memory linearly or sequentially (one after the other).

Example:

1. Arrays
2. Linked List
3. Stack
4. Queues

Non-Linear Data Structures:

Any data structure which establishes the relationships other than the
adjacency relationship is called Non-Linear data structures.

Example:

1. Trees 2. Graphs
In trees, children, parent, grandparent relationship can be established.
The possible way in which the data items or atoms are logically
related define different data structures, some of the data structures are
as follows:

(i)Arrays: Array is a finite ordered set of homogeneous elements,

which are stored in adjacent cells in memory. The data are
represented by a single name identified by a subscript.

Linear arrays are called one-dimensional arrays because each element

in an array is referred by one subscript.

A Two-dimensional array is a collection of similar data types where

an element is referred by two subscripts.
Array can be multi-dimensional that can be
2 dimensional, 3-dimensional, 4-dimensional, N-dimensional.

(ii)Stacks: It is a linear data

structure in which data is inserted
and deleted at one end called as top
Top Of the Stack
of stack, i.e., data is stored and
retrieved in last in first out (LIFO)
order.

(iii)Linked Lists: A list is a linear

sequence of data objects of the same
type. The list may be such as singly, doubly and circular linked list.
The linked list is a linear collection of data items called as nodes,
node is divided into two parts
(1) Information field (2) Link field.

The linked list structure i.e., each of its nodes have

-data/information field.
-a pointer pointing to next node of the list / link field.
(iv) Trees: A tree is a finite set of
vertices that has a vertex called as
root and remaining vertices are
collection of sub-trees.

Ques8: What are linear data structures?

Ans:
Linear Data Structures:
A linear data structure is one which establishes the relationship of
adjacency between the elements in which all the elements are stored
in memory linearly or sequentially (one after the other).

Example:
1. Arrays 2. Linked List
3. Stack 4. Queues

Ques9: What are non-linear data structures?

Ans:
Non-Linear Data Structures:
Any data structure which establishes the relationships other than the
adjacency relationship is called Non-Linear data structures.
Example:
1. Trees 2. Graphs
Ques10: Explain non-linear data structures in detail.

Ans:
Non-Linear Data Structures:
Any data structure which establishes the relationships other than the
adjacency relationship is called Non-Linear data structures.

There are two types of non-linear data structures: -

1. Trees
-Hierarchy of nodes.
-Root node at the top.
- Nodes have parent-child relationships.
- Binary trees have at most two children per node.
- AVL trees and B-trees are specific types.

2. Graphs
-Nodes connected by edges.
-Edges can be directed or undirected.
-Can be cyclic or acyclic.
-Directed Acyclic Graphs (DAGs) have no cycles.
-Weighted graphs assign values to edges.

Ques11: What are the operations on data structures?

Ans:
The data appearing in the data structures are processed by the
operations, the operations on data structures are classified as follows:
1. Inserting: Adding the new element to the existing data structure.
2. Deleting: Deleting the element from a data structure.
3. Traversing: Accessing each element exactly once is called
traversing.
4. Searching: Searches a particular element in the list of elements.
5. Sorting: Arranging the elements in ascending or descending order.
6. Merging: Combining the two different lists into single list.
Ques12: What are fixed length records & variable length records?

Ans:
The records are classified according to their lengths:
(1) Fixed length records
(ii) Variable length records

(1) Fixed Length Records: In this type of records, all records

will contain equal number of fields with similar data items
and the same amount of space allocated for each record.
(2) Variable Length Records: In this type of records, each
record will have equal number of fields with same data items
but available in different lengths in size i.e., amount of space
is varied for each record.

Ques13: Define Abstract Data Type.

Ans.
An abstract data type is a type with associated operations, but whose
representation is hidden.

OR

An abstract data type (ADT) is a specification of a set of data and the

set of operations that can be performed on the data; and this is
organized in such a way that the specification of values and
operations on those values are separated from the representation of
the values and the implementation of the operations.

OR

An abstract data type (ADT) is an object (or type) with a generic

description but independent of implementation details. This
description includes a specification of the
components from which the object is made
and also the behavioural details of the object.
Ques14: Explain Abstract Data Type Model
Ans:
An ADT model contains both public functions and private functions.
The private function is accessible only to public functions and public
functions are accessible to the application program (or) user by an
interface call. The functions defined in an interface are implemented
by the data structures like stack, queue, linked list, arrays etc

Data are entered, accessed, modified and deleted through the external
call using application programming interface. This interface can
access only public functions.
Ques15: Explain Abstract Data Type with example
Ans:
An abstract data type (ADT) is a specification of a set of data and the
set of operations that can be performed on the data; and this is
organized in such a way that the specification of values and
operations on those values are separated from the representation of
the values and the implementation of the operations.
Examples Of Abstract Data Type (ADT): -
Stack ADT: We can define ADT stack as a collection of elements
together with operations push, pop, isFull, isEmpty, top, etc., that
have the usual properties.

Queue ADT: We can define ADT queue as a collection of elements

together with operations insert, delete, isFull, isEmpty, etc., that have
the usual properties.
Ques16: Why ADTs are important?
Ans:
To manage the complexity of problems and the problem-solving
process, computer scientists use abstractions to allow them to focus
on the "big picture" without getting lost in the details. By creating
models of the problem domain, we are able to utilize a better and
more efficient problem-solving process. These models allow us to
describe the data that our algorithms will manipulate in a much more
consistent way with respect to the problem itself.
Ques17: What is the relationship between ADT and data structures?
Ans:
Abstract data type is an interface and data structure is an
implementation. An ADT gives the specification and data structure
implements that specification. So, we can say that data structure is an
implementation of ADT.
Ques18: Define Algorithm and Algorithm Complexity
Ans:
ALGORITHM: -
Informally, an algorithm is any well-defined computational procedure
that takes some values as "input" and produces some value, or set of
values, as "output". An algorithm is thus "a sequence of
computational steps that transform the input into the output."
We can also view an algorithm as a tool for solving a well specified
"computational problem". The statement of the problem specifies in
general terms the desired input/output relationship. The algorithm
describes a specific computational procedure for achieving that
input/output relationship.
OR
In simple terms we can say that "An algorithm is a step-by-step
procedure for performing some tasks in a finite amount of time".
ALGORITHM COMPLEXITY: -
Algorithmic complexity is concerned about how fast or slow
particular algorithm performs and how much memory it requires.
Complexity of algorithm is a function of size of input of a given
problem instance which determines how much running time/memory
space is needed by the algorithm in order to run to completion.
OR
In simple terms we can say that “Complexity of an algorithm is a
measure of the amount of time and/or space required by an algorithm
for an input of a given size (n)”.
Ques19: Define Space and Time Complexity.
Ans:
In order to find the complexity of algorithm, two kinds of efficiencies
are to be kept in mind.
1. Space Complexity: It indicates the amount of storage required for
running the algorithm. i.e. "the amount of memory needed by the
algorithm to run to completion".
2. Time Complexity: Time complexity of an algorithm is the amount
of time it needs in order to run the program for completion.
Ques20: Explain Time-Space Trade off.
Ans:
Time-Space tradeoff is a way of solving a problem or calculation in
less time by using more storage space (or memory), or by solving a
problem in very little space by spending a long time.

Created By: - Assigned By: -

Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit 1
Chapter - 2
Preliminaries
 Unit 1
Chapter- 2
Preliminaries
Question & Answer: -

Ques1: Explain different mathematical functions and notations.

Ans:
Mathematical Notations and functions:
• Floor and Ceiling Functions
If x is a real number, then floor and ceiling of x is defined as follows:
1.)Floor(x): returns the largest integer that is smaller then or equal to x (i.e.:
rounds down the nearest integer).
2.)Ceil(x): Returns the smallest integer that is greater than or equal to x (i.e.:
rounds up the nearest integer).
Example:
floor (2.5) =2, floor(2.9)=2, floor(-7.2)= -8,
ceil(2.5)=3, ceil(2.9)= 3, ceil(-7.2)= -7
• Remainder Function(Modular Arithmetic)
If k is any integer and M is a positive integer, then: k(mod M) gives
the integer remainder when k is divided by M.
Example: 26(mod 7)=5, 30(mod 5)=0

• Integer and Absolute Value Functions

If k is a real number, then integer function INT(x) will convert x into
integer and the fractional part is removed.
Example: int(5.34)=5, INT(-7.5)= -7

The absolute function ABS(x) or |x| gives the absolute value of x i.e. it
gives the positive value of x even if x is negative.

Example:
ABS (-99) =99 or ABS [-99] =99
ABS (-3.33) =3.33 or ABS [-3.33]=3.33
 • Summation symbol
Here we introduce the summation symbol ∑(sigma). Consider a
sequence of n-terms a1 + a2………an, then the sums a1 + a2 + … + an will
be denoted as
∑ai
1≤i≤n

Examples are sum of n natural numbers, square of n positive integers and many
more. We can write an expression as a sum of series or sequence. We can also
call summation of summation.
Consider that a function f(n) denotes the summation of n positive integers. Here
function f(n) computes the order of magnitude of an algorithm.
f(n)= ∑ ai =1+2+….+ n= n(n+1)/2, and the order of complexity is 0(n2)
1≤i≤n

• Factorial Function
n! denotes the product of the positive integers from 1 to n. n! is read
as ‘n factorial’, i.e. n! = 1*2*3*….*(n-2)*(n-1)*n

Example: 4! = 1*2*3*4 = 24 5! = 5*4*3*2*1 = 120

• Permutations
Let us consider a set of n elements. A permutation of this set means
the arrangement of the elements of the set in some order.

Example: Suppose the set contains a, b and c. the various

permutations of these elements can be: abc, acb, bac, bca, cab, cba.

If there are n elements in the set then there will be n! permutations of

those elements. It means if the set has 3 elements, then there will be
3! = 1*2*3 = 6 permutations of the elements.

• Exponents and Logarithms

Exponent means how many times a number is multiplied by itself. If
m is a positive integer, then: am= a* a* a*…. a(m times)
and am = 1/am

Example: 25= 2*2*2*2*2 = 32, 2-5= 1/25= 1/32

The concept of logarithms is related to exponents. If b is a positive number, then
the logarithm of any positive number x to the base b is written as logbx. it
represents the exponent to which b should be raised to get x
i.e. y=logbx and by= x
Ques2: Explain Algorithmic notations with an example.
Ans:
An algorithm can be described in many ways. A natural language such as English
can be used to write an algorithm but generally algorithms are written in English-
like pseudo code that resembles with high level languages such as ‘C’ and ‘C++’.
The following algorithmic notations are used to write an algorithm.
Algorithmic Notations Description
Name of algorithm Every algorithm is given an identifying name.
Example: Algorithm LINEARSEARCH
Every algorithm can have brief description of the
tasks the algorithm performs and any assumptions
Comments that have been made. The description gives the
name and types of the variables used in the
algorithm. Comment begins with // and continues
until the end of line. Comments are included only
for clarity.
Example: Algorithm: LINEARSEARCH
//This algorithm is used to find the element in an
array
//by accessing elements sequentially.
Data Type Data types such as integer, char, real, Boolean and
other data structures such as array, pointer, structure
are used. Array ith element can be described as A[i]
and (i,j) element can be described as A[i,j]
Example: Integer MAX, MIN, SUM
Real SALARY, AVG
Integer ARRAY[N]

Variable Names The variable names are generally be in capital

letters such as MAX, MIN, NAME, AGE etc.
 Each algorithm is made of a sequence of numbered
Steps steps and each step has an ordered sequence of
statements, which steps describe the tasks to be
performed.
The statements in each step are executed in a left-
to-right order.
Example: Set A = 1, MAX=0; MIN:= 0
The assignment statement is indicated by placing
Assignment statement equal (=) between the variable (in left hand side)
and expression or value(s) (in right hand side). For
example, addition of a and b is assigned in variable
a. a= a+b
There are three expressions: arithmetic, relational
and logical. The arithmetic expression used
Expression arithmetic operator such as /,*,+,-, relational
expression used relational operator such as
<,<=,>,>=,<>,= and logical expression used logical
operator such as not, or, and. There are two Boolean
values, true or false.
Example: if(A>B)
For input of data READ statement and for output of
Input and output data WRITE statement are used. If more than one
output data then we can use comma as separator
among the variable names.
Example: READ: X
READ:X, Y
WRITE:X,Y
The goto statement causes unconditional transfer of
Goto statement control to the step referenced. Thus statement goto
step N will cause transfer of control to step N.
Example: GOTO step 4;
End statement The end statement is used to terminate an
algorithm. It is usually the last step and algorithm
name is written after the end.
Example: END LINEARSEARCH
Functions or procedures A function is used to return single value to the
calling function. Transfer of control and returning
of the value are accomplished by return(value)
statement. A function begins as follows:
Example: function name(parameters list).
Ques3: Explain different control structures with an example.
Ans:
Control Structures
One of the most important concepts of programming is the ability to control a
program so that different lines of code are executed or that some lines of code are
executed many times. The mechanism that allows us to control the flow of
execution are called control structures. There are four main categories:
1. Sequence
Simply do one instruction then the next and the next. It just executes them
in a given sequence or in order listed. Most lines of code in any program
belongs to this category.

In this figure, statement 1 is executed first, Statement 1

followed by statement 2, then finally

statement 3. Statement 2

Statement 3

Sequence control structures

2. Selection
This is where we select or choose between two [or] more flows. The choice
is decided by asking some sort of questions. The questions are nothing but
conditions. The answer determines the path (or which lines of code) will be
executed.
Example: if-then-else True
condition S1
If condition then
Statement 1;
else
Statement 2;

False
S1

Here the condition is a Boolean expression which evaluates to either true [or]
false. If condition evaluates to true, then statement 1 will be executed, otherwise
statement 2 will be executed S1 and S2 may single statement or group of
statements.

3. Iteration
• It is also known as repetition; it allows some code to be executed
several times.
• It executes the statements repeatedly for a certain number of times as
long as the condition is true.
• If the value of condition is true, then it executes all the statements in
the body of the loop after which the control is transferred to the while
statements for evaluation of condition again.
• The execution of loop is terminated, when the condition is evaluated
to FALSE. Then the control statement is transferred to the first
statement of the while loop.

Example:
 4. Branching
A control structure that allows the flow of execution to jump to a different
part of program. This category is rarely used in modular structured
programming.
Example: Go To statement
Ques4: Explain time complexity of an algorithm.
Ans:
The amount of time needed to run the program is termed as time efficiency or
time complexity. The total time taken by a program is the sum of the compile
time and runtime. The compile time does not depend on the instance
characteristics and it can be assumed as a constant factor so we concentrate on
runtime of the program.
Let this runtime is denoted by tp (instance characteristics).
Then
tp (n) = ta ADD(n) + ts SUB(n) + tm MUL(M) +-----
where n indicates the instance characteristics and ta, ts, tm ---denote the time
needed for an addition, subtraction, multiplication, and so on. ADD, SUB, MUL -
-- represent the functions and they are performed when the code for the program
is used on an instance characteristic ‘n’.
Ques5: Explain space complexity of an algorithm.
Ans:
The total amount of time of computer memory required by an algorithm
to complete its execution is called as space complexity of that
algorithm.
For any algorithm, memory is required for the following purposes:
1. Memory required to store program instructions.
2. Memory required to store constant variables.
3. Memory required to variable values.
4. And for few other things.
Generally, when a program is under execution it uses the computer
memory for three reasons. This are as follows:
1. Instruction Space: It is the amount of memory used to store
compiled version of instructions.
 2. Environmental Stack: It is the amount of memory used to store
information of partial executed functions at the same time of
function call.
3. Data Space: It is the amount of memory used to store all the
variables and constants.

Ques6: Write a note on operation count and step count.

Ans:
Operations counts
Consider an algorithm ‘A’ with ‘n’ size of that input data. The time and
space are the two main measures for the efficiency of the algorithm. In
operation counts, the time is measured by counting the number of basic
operations [or] key operations.
The ‘basic operations’ are defined that time for the other operations is
much less than [or] almost proportional to the time for the basic
operations.

The operation count method concentrates on certain important basic operations

like multiplications, for loop where it takes considerably more time than any
other operations in an algorithm.
Step counts
In step counts method, we attempt to find the time spent in all the parts of the
program. A step is any computational unit that is independent of the selected
characteristics.

There is another method to determine the step count of an algorithm is to build a

table and list the total number of steps contributed by each statement. First
determine the number of steps per execution [s/e] of the statement and total the
number of times [frequency] each statement is executed.
Ques7: List out various asymptotic notations and their significance.
Ans:
1. Big-oh Notation (O)
The Big – oh – Notation gives an upper bound on function f(n). The upper
bound of f(n) indicates that the function f(n) will be the worst - case that it does
not consume more than this computing time.
2. Omega Notation (Ω)
This notation is used to find the lower bound behavior of f(n). The lower
bound implies that below this time the algorithm cannot perform bett er i.e., the
algorithm will take at least this much of time (this indicates lower bound). It is
represented mathematically by notation Ω for a given function g(n), we denote
by Ω(g(n). The function g(n) is only a lower bound of f(n). For the statement
f(n) = Ω(g(n) to be informative, g(n) should be as large as function of n as
possible for which the statement f(n) = Ω(g(n) is true.
3. Theta Notation
The theta notation can be used when the function f(n) can be bounded both
from above and below by the same function g(n). For some functions, the lower
bound and upper bound may be same. In finding the maximum and minimum
element in an array, the computing time is O(n) and Ω(n). There exists a special
notation to denote for functions having the same time complexity for lower
bound and upper bound and this notation is called the theta – notation and which
is denoted by ϴ.
Ques8: Arrange the following complexities in ascending sequence. Give reasons.
O(n log n) O(n3) O(n) O(n2) O(1)
Ans:
O(1) < O(n) < O(n log n) < O(n2) < O(n3)
Reason: let us assume that algorithm P has complexity O(n) and algorithm Q
has complexity O(n2). We can asset that algorithm P is faster than algorithm Q
for sufficiently large n. Since here (n < n2) and we can say that algorithm p is
faster than algorithm Q.

Ques9: Derive space complexity for finding sum of array elements.

Ans: Finding the sum of array elements.
int square (int a)
{
return a*a;
}
In this program it requires 4 bytes of memory to store variable ‘a’ and
another 4 bytes of memory is used to return value.
That means, totally it requires 4 bytes of memory to complete its execution.
If any algorithm requires a fixed amount of space for all input values then that
space complexity is said to be Constant space Complexity.
Therefore, S(P) = CP + SP
S(P) = 8 + 0
S(P) = 4
Ques10: Explain the active areas of study of algorithm.
Ans:
Algorithm Definition:
A step- by- step set of rules to solve a specific problem.
1. Time complexity:
Measure of how runtime grows with input size (Big – O notation).
[Link] complexity:
Measure of how memory usage grows with input size (Big – O notation).
4. Efficiency and Optimization
Minimizing resource usage for better performance.
5. Algorithmic Paradigms:
General approaches like Divide and Conquer, Dynamic programming, Greedy
algorithms, Backtracking, and Randomized algorithms.
Ques11: Briefly explain best case, average case and worst case time complexity
of an algorithm.
Ans:
Let’s find the complexity function T(n) for certain cases.
• Worst case
The worst-case efficiency of an algorithm is its efficiency for the
worst-case input of size n, for which the algorithm runs the longest
among all possible inputs of that size. Basically, it gives the maximum
value of T(n) for any possible input.
Let us denote the worst-case efficiency of an algorithm by Tworst(n).

The worst-case occurs when the element to be searched is found at the

last position or element to be searched is not found. In both cases, the
algorithm makes n comparison.
Therefore, the number of comparisons = n Tworst(n) = n

• Best case
The best-case efficiency of an algorithm is its efficiency for the
best-case inputs of size n, for which the algorithm runs the fastest
among all the possible inputs of that size. Eventually, it gives the
minimum value of T(n) for any possible input.
Let us denote the best -case efficiency of an algorithm by Tbest(n).

The best-case occurs when the element to be searched is found at the

first location. In that case, the algorithm makes only one comparison.

Therefore, number of comparisons = 1

Tbest(n) = 1

• Average case
It’s noticed that neither the worst-case nor the best-case yields the
necessary information about the algorithm’s behaviour on random
input. The average-case efficiency provides that information.

To find the average-case efficiency. The following assumptions are

made.
1. The probability of successful search is equal to P(0 ≤ P ≤ 1)
2. The probability of the first match occurring in the ith position of the
array is P/n or every I, and in the case of unsuccessful search, the
 number of comparisons is n with the probability of such a search
being (1-p). therefore

Ques12: What do you mean by Orders of Growth?

Ans:
The time complexity of an algorithm is generally some function of the instance
characteristics. This function is very useful in determining how the time
requirements vary as the instance characteristics change. Let T(n) be the
complexity function with input size ‘n’. the values of T(n) increases when ‘n’
value increases and t(n) value decreases when ‘n’ value decreases. Therefore, the
complexity function is directly proportional to the instance characteristics ‘n’.
Ques13: What are the units for measuring running time?
Ans:
The units for measuring running time are:
➢ Operation Counts
➢ Step Counts
➢ Asymptotic notations (mathematical analysis)

Ques14: Given f(n) = 120n + 20, prove that f(n) = o(n2).

Ans:
Given, f(n) = 120n + 20, prove that f(n) = o(n 2)
|120 + 20| ≤ c. |n2| Ɐ n ≥ n0
120n + 20 ≤ 121.n2 Ɐn≥1
The above inequality can be satisfied by setting C = 121 and n0 = 1
Therefore, f(n) = o(n2) is proved.

Ques15: Given f(n) = 20n2 + 10n + 5, prove that f(n) = Ω(n).

Ans:
Given f(n) = 20n2 + 10n + 5 prove that f(n) = Ω(n)
20n2 + 10n + 5 ≥ c.n Ɐ n ≥ n0
Choose c=1 and n0 =1, we get
20n2 +10n + 5 ≥ 1.n
The above inequality can be satisfied by setting c = 1 and n 0 = 1
Therefore, f(n) = Ω(n) is proved.

Ques16: Given that f(n) = 30n3 -2, prove that f(n) = O(n3) using limits of the ratio
of two functions.
Ans:
Ques17: Let f(n) = 100n +5. Express f(n) using Big – Omega and Big – Oh.
Ans:
1. To express f(n) in terms of Big – Oh, we need to find a function h(n) such that
0 ≤ f(n) ≤ h(n) Ɐ n ≥ n0
Where n0 is some positive constant.
In that case we can choose h(n) = 200n Ɐn≥1
0 ≤ 100n + 5 ≤ 200n
Therefore, f(n) as O(n) with h(n) = 200n.
2. To express f(n) in terms of Big – Omega, we need to find function g(n) such
that,
0 ≤ g(n) ≤ f(n) Ɐ n ≥ n0
g(n) = n Ɐn≥1
0 ≤ n ≤ 100n + 5
Therefore, f(n) as Ω(n) with g(n) = n.

Ques18: Prove that 3n3 + 4n2 = O(n3).

Ans:
|0 ≤ 3n3 + 4n2| ≤ c |n3| Ɐ n ≥ n0
3n3 + 4n2 ≤ 3n3 + 4n3 Ɐn≥1
Common factor = n3
3n3 + 4n3 = 7n3
We have, 3n3 + 4n3 ≤ 7n3 Ɐn≥1
Choose c = 7 and n0 = 1
0 ≤ 3n3 + 4n2 ≤ 7n3
Therefore, 3n3 + 4n2 = O(n3) is proved.

Ques19: Let f(n) = 100n + 5. Express f(n) using Big – Theta.

Ans:
c1 | g(n) | ≤ | f(n) | ≤ c2 | h(n) | Ɐ n ≥ n0
We can choose g(n) = n, h(n) = n
1. For lower bound:
c1 . g(n) = c1 . n where c1 = 1 and n0 = 1.
0 ≤ 1.n ≤ 100n + 5

2. For upper bound:

c2 . h(n) = c2 . n where c2 = 101 (any constant greater than 100) and n0 = 1.
0 ≤ 100n + 5 ≤ 101. n
Therefore, f(n) = ϴ(n)
Ques20: Explain time and space complexity with an example.
Ans:
• Time complexity
The amount of time needed to run the program is termed as time
efficiency or time complexity. The total time taken by a program is the
sum of the compile time and runtime.
Example:
#include <stdio.h>
1. int main() {
2. int n, sum = 0;
3. scanf("%d", &n);
4. for (int i = 1; i <= n; i++) {
5. sum += i;
6. }
7. printf("Sum of first %d natural numbers = %d\n", n, sum);
8. return 0;
 9. }

The number of operations in the for loop is n, and each operation takes constant
time. That's why the Time Complexity of the above example is considered as O(n).

• Space complexity
It indicates the amount of temporary storage required for running the
algorithm.

Example
Ques21: Find out the time required to run matrix multiplication using
a) Operation counts b) Step counts
Ans:
a) Operation counts
let us consider two matrices A and B. AB requires dot product of row ‘i’ in
A and column ‘j’ in B. computing the dot product requires n multiplications and

n -1 additions. Since there are n2 elements, the dot product must be computed n2

times.
Thus, the total number of operations is
n2 (n + (n – 1)) = 2n3 – n2 = O(n3).
b) Step counts
Consider that for each [Link](column) you have to do the same thing,
and you have to do this for each [Link] pair - so it seems like each
dimension would give you 21/7=3 steps, since you have 7 [Link] pairs
needing a total of 21 steps.
Ques22: Explain worst – case, best – case and average – case efficiencies?
Explain with an example.
Ans:
1. Worst – case
The worst case occurs when the element to be searched is found at the last
position or element to be searched is not found at any location.
Example
2. Best- case
The best case occurs when the element to be searched is found at the first
location.
Example

3. Average- case
This gives expected value when the element is searched.
Example
Ques23: Explain what are the basic steps that are required to be followed to
analyze recursive and non – recursive algorithms. Explain with an example.
Ans:
Ques24: Explain asymptotic notations and give an example for each.
Ans:
1. Big- oh notation (O)
Big- Oh notation gives an upper bound on function f(n). The upper bound
of f(n) indicates that the function f(n) will be the worst- case that it does not
consume more than this computing time.

[Link] notation (Ω)

This notation is used to find the lower bound behaviour of f(n). The lower
bound implies that the algorithm will take at least this much of time. It is
represented by Ω.
3. Theta- notation (ϴ)
This notation can be used when the function f(n) can be bounded both from
above and below by the same function g(n). for some functions, the lower and
upper bound may be same. This will the average case which the computing time
is O(n) and Ω(n). It is denoted by ϴ.
Ques25: Design an algorithm to obtain maximum of N elements and obtain the
time complexity.
Ans:
Algorithm:
start
arr[]
for (int i=1; i<n; ++i)
if (arr[0] < arr[i])
{
arr[0] = arr[i];
}
}
if the first element will be the largest element, then also loop will run till end of
the array to verify.
and if the last element is the largest then also for loop will be executed till the
end of the for loop.
So, the worst and best case both will be same that is O(n).

Ques26: Calculate the time complexity for the following recursive algorithms.
a. Factorial b. GCD c. Fibonacci Series
Ans:
a) Factorial
factorial(n):
if n is 0
return 1
return n * factorial(n-1)

From the above analysis we can write:

T(n) = T(n — 1) + 3
T(0) = 1
T(n) = T(n-1) + 3
= T(n-2) + 6
= T(n-3) + 9
= T(n-4) + 12
= …….
= T(n-k) + 3k
as we know T(0) = 1
we need to find the value of k for which n - k = 0, k = n T(n) = T(0) + 3n , k = n
= 1 + 3n
that gives us a time complexity of O(n)
b) GCD
Algorithm:
GCD(x,y)
{
// x >= y where x & y are integers
if(y==0)
return x
else
return (GCD(y,x%y))
}
Time Complexity:
1. Best Case: O(1)
if y is divisible of x, then Euclid GCD terminates in one call.
[Link] Case: O(log n)
when x, y are two consecutive Fibonacci numbers.
c) Fibonacci Series

Ques27: Write an algorithm to add two matrices and explain how its time
complexity is obtained by introducing count statements.
Ans:
In this example, the total count of basic operations is 3*m*n* + 2, where ‘m’ is
the number of rows and ‘n’ is the number of columns in the matrices.
The time complexity is O(m * n), where ‘m’ and ‘n’ are the dimensions of the
matrices.

Ques28: Write an algorithm for bubble sort and prove that T(n) = n 2.
Ans:
Ques29: Write an algorithm for sequential search and explain best - case, worst –
case, average – case efficiencies.
Ans:

Created By: - Assigned By: -

Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit 1
Chapter-3
Single
Dimensional
Array
 Unit 1
Chapter-3
Single Dimensional Array
Questions & Answers: -
Ques1: Define an Array
Ans:
An array is a collection of elements of the same type of data or an array
is a sequence of data items of homogeneous value (same type)
Ques2: What are the operations on Array?
Ans:
1. Traversal: Processing each element in the array.
2. Search: Finding the location of the element with a given
value in the array.
3. Insertion: Adding a new element into an array.
4. Deletion: Removing an element from an array.
5. Sorting: Arranging the elements in some type of order.
6. Merging: Combining two arrays into single array
Ques3: Explain Array as Abstract data type.
Ans:
An array is a fixed-size sequence of elements of the same type. An array
is a fundamental abstract data type (ADT). The basic operations include
direct access to each element in the array by specifying its position so
that values can be retrieved from or stored in that position.
 Ques4: How arrays are represented in memory? Explain with
diagram.
Ans:
In memory, all the data items are stored in contiguous memory locations
one after the other. For example: -
Int value [5] = {85,98,79,88,90};
Array name→ VALUE [0] VALUE [1] VALUE [2] VALUE [3] VALUE [4]

Data→ 85 98 79 88 90
Address→ 1200-1203 1204-1207 1212-1215 1208-1211 1216-1219

Ques5: Write an algorithm to traverse an array.

Ans:
Here A is a linear array with lower bound LB and upper bound UB. This
algorithm traverses array A and applies the operation PROCESS to each
element of the array
1. Repeat for I =LB to UB
Apply PROCESS to A[I]
[End of For Loop]
2. Exit
Explanation
Here A is a linear array stored in memory with lower bound LB and
upper bound UB. The for loop iterates from LB to UB and visits each
element of the array. During this visit, it applies the operation PROCESS
to the elements of the array A. the PROCESS operation could be any
operation like adding a number to A[I], Modifying the value of A[I] etc.,
Ques6: Write an algorithm to insert an element into an array
Ans:
Algorithm to insert an element into an array
Here A is a linear array with N elements, LOC is the location where
ITEM is to be inserted
1. Set I=N [initialize counter]
2. Repeat While (I>=LOC)
3. Set A[I+1] =A[I] [Move elements to next location]
4. Set I=I-1 [Decrease counter by 1]
[End of while loop]
5. Set A[LOC] = ITEM [Insert element at LOC position]
6. Set N=N+1 [Increment N by 1]
7. Exit
Ques7: Write an element to delete an element from an array
Ans:
Algorithm to delete an element from an array
Here A is a linear array with N [Link] is the location where
ITEM is to be deleted
1. Set ITEM=A[LOC] [Assign the element to be deleted to ITEM]
2. Repeat for I=LOC to N
3. Set A[I]=A[I+1] [Move the Ith element to previous locations
[End of for loop]
4. Set N=N-1 [Decrement N by 1]
5. Exit
Ques8: Write a program to demonstrate traverse, insert, and delete
operations on array.
Ans:
Created By: - Assigned By: -
Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit 1
Chapter -4
Multi
Dimensional
Arrays
 Unit 1
Chapter -4
Multi-Dimensional Arrays
Question & Answer: -
Ques1: - Define Multi-Dimensional Arrays
Ans: A multi-dimensional array is an array with more than one level
or dimension. For example, a 2D array, or two-dimensional array, is
an array of arrays (meaning it is a matrix of rows and columns). A 3D
array adds another dimension, turning it into an array of arrays of
arrays.

Ques2: - Explain the different memory representation of

two-dimensional arrays with an example.
Ans:
ROW MAJOR REPRESENTATION
In this representation the arrays are stored in the memory in terms of
the row design, i.e. first the first row of the array is stored in the
memory then second and so on. Suppose we have an array named arr
having 3 rows and 3 columns then it can be stored in the memory in
the following manner:
int arr[3][3];

In this representation 1st row is stored from the base address then 2nd
row is stored then 3rd row is stored and so on. Location of A[i,f]with
Size=RowSize(m) x ColSize(n) can be calculated using following
mapping function.
Case 1: Index started from 0,0
Location[i,j]= Base Address(A)+{(i*ColSize)+j}*Word Size)
Case 2: Index started from 1,1
Location[i,j]= Base Address(A)+[{(I-1)*ColSize}+ (j-1)]*Word Size)
Where WordSize is the size of the data type. For example, for integer
it would be either 2 or 4
COLUMN MAJOR REPRESENTATION
In this representation the arrays are stored in the memory in the term
of the column design, i.e. the first column of the array is stored in the
memory then the second and so on. By taking above eg. we can show
it as follows:
Assume that the matrix is collection of columns. In this mapping
scheme 1st column is stored from the base address then 2 nd column is
stored then 3rd column is stored and so on. Location of A[i,j] with
Size = RowSize(m) x ColSize(n) can be calculated using following
mapping functions.
Case 1: Index started from 0,0
Location[i,j]= Base Address(A)+{i+(j*RowSize)}*Word Size)
Case 2: Index started from 1,1
Location[i,j]= Base Address(A)+[(i-1)+{(j-1)*RowSize}]*WordSize)

Ques3: Explain the difference between Row major Vs Column major

memory representation.
Ans:
Row-Major Representation:
Storage Pattern:
• In row-major order, the elements of each row are stored together
in contiguous memory locations.
• Rows are stored one after another, and elements within the same
row are stored consecutively.
[Link] Access Formula: The formula to calculate the memory
location of an element at position (i, j) in row-major order is
calculated using the formula:
address = base_address + (i * number_of_columns + j) *
size_of_each_element
Usage: Commonly used in languages like C and C++ for representing
multi-dimensional arrays.
Example: For a 3x4 matrix:
1 2 3 4
5 6 7 8
9 10 11 12
The elements would be stored in memory as ‘1 2 3 4 5 6 7 8 9 10 11’.
Column-Major Representation:
Storage Pattern:
• In column-major order, the elements of each column are stored
consecutively in memory.
• Columns are stored one after another in contiguous memory
locations.
Memory Access Formula: The memory location of an element at
position (i, j) in column-major order is calculated using the formula:
address = base_address + (j * number_of_rows + i) *
size_of_each_element
Usage: Commonly used in languages like Fortran and in some
mathematical and scientific computing environments.
Example: For the same 3x4 matrix:
1 5 9
2 6 10
3 7 11
4 8 12
The elements would be stored in memory as ‘1 5 9 2 6 10 3 7 11 4 8
12’.
Ques4: - Write an algorithm to find the addition of two matrices.
Ans:
Algorithm Matrix Addition (A, B, M, N, X, Y)
Here A is a two-dimensional array with M rows and N columns and B
is a two-dimensional array with X rows and Y columns. This
algorithm adds these two arrays.
1. If (M ≠ X) or (N ≠ Y) Then
2. Print: Addition is not possible.
3. Exit
[End of If]
4. Repeat For I = 1 to M
5. Repeat For J = 1 to N
6. Set C[I][J] = A[I][J] + B[I][J]
[End of Step 5 For Loop]
[End of Step 6 For Loop]
7. Exit
Ques5: - Write an algorithm to find the subtraction of two matrices.
Ans:
Matrix Subtraction (A, B, M, N, X, Y)
Here A is a two-dimensional array with M rows and N columns and B
is a two-dimensional array with X rows and Y columns. This
algorithm adds these two arrays.
1. If (M ≠ X) or (N ≠ Y) Then
2. Print: Subtraction is not possible.
3. Exit
[End of If]
4. Repeat For I = 1 to M
5. Repeat For J = 1 to N
6. Set C[I][J] = A[I][J] - 8[I][J]
[End of Step 5 For Loop]
[End of Step 6 For Loop]
7. Exit
Ques6: - Write an algorithm to find the multiplication of two matrices.
Ans:
Matrix Multiplication (A, B, M, N, X, Y)
1. If (M ≠ Y) or (N ≠ X) Then
2. Print: Multiplication is not possible.
3. Else
4. Repeat For I = 1 to N
5. Repeat For J = 1 to X
6. Set C[I][J] = 0
7. Repeat For K = 1 to Y
8. Set C[I][J] = C[I][J] + A[I][J] ≠ B[I][J]
[End of Step 7 For Loop]
[End of Step 5 For Loop]
[End of Step 4 For Loop]
[End of If]
[Link]
Ques7: - Write a C Program to find the addition and subtraction of
matrices.
Ans:
Ques8: - Write a C Program to find the multiplication of two matrices.
Ans:
Ques9: - What is sparse matrix? What is transpose of sparse matrix?
Explain with an example.
Ans:
SPARSE MATRIX
Matrices which contain high numbers of zero entries are called sparse
matrices. In simple terms, matrix which contain more zero elements
than non-zero elements are referred as sparse matrix.
TRANSPOSE OF A MATRIX
The transpose of a matrix is a new matrix that is obtained by
exchanging the rows and columns.
Transposing a Sparse Matrix:
To transpose a sparse matrix, for each row of the sparse
matrix<I,j,value> and store it in the element <j,I,value> of the
transpose as shown below.
Ques10: - Write a program to check whether matrix is sparse matrix
or not.
Ans:
Ques11: - Write a program to find the transpose of sparse matrix.
Ans:

Created By: - Assigned By: -

Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit 2
Chapter- 5
Linked Lists
 Unit 2
Chapter- 5
Linked Lists

Question and Answers: -

Ques1: What do you understand by a Linked list?

Ans:
A linked List, in simple terms, is a linear collection of data elements. These data
elements are called nodes.

Ques2: what are the advantages and disadvantages of linked lists over arrays.
Ans:
➢ Advantages of Linked Lists over Arrays
• Efficient Memory Utilization.
• Insertion and Deletion operations are Easier and Efficient.
• Extensive Manipulations.
• No Memory Wastage.
• Arbitrary Memory Locations.

➢ Disadvantages of Linked List Over Arrays

• Extra Memory Space.
• Random Access.
• Traversal and Search Time.

Ques3: How Linked list is represented using an array? Explain with example.
Ans:
Ques4: Explain the dynamic representation of linked list.
Ans:
• The process of allocating memory at runtime is known as dynamic
memory allocation.
• The functions malloc() and calloc() are used to allocate memory and free()
is used to deallocate memory.
• In dynamic representation of linked list, a node is created dynamically
whenever it is required. Any number of nodes can be created depending
upon the requirement.
• The link member field contained in that structure node, which is used to
point to the same structure type is called self-referential structure.
• There is no need to setup any actual storage space at this stage as space will
be allocated for each node as needed when the program is running.

Struct node
{
Int info:
struct node * link;
};

In order to create a linked list structure is to declare that defines all the list
entries. The above structure is capable of holding the data plus the address of the
memory space holding the next structure in this list.

Struct node
{
Int info1, info2, info3,………info6;
Struct node * link;
};

A node may contain any number of information fields. The general syntax for
this is:
Node
 Info1 Info2 Info3 Info4 Info5 Info6 Link

Ques5: write a C- function to create a singly linked list with an example.

Ans:

Ques6: write a note on getnode() and freenode() operations.

Ans:
➢ Getnode()
• The first area where the allocation of dynamic memory space to the node
during the program execution is done by means an operation called
getnode.
• Getnode is used only for building a node. It never breaks down the node.
• if we go on creating the nodes using getnode, the number of nodes that can
be possibly used will reduce.
• Whenever a getnode is invoked, a newnode is created different from all the
nodes previously in use.
 p.t.o

➢ Freenode()
• to reuse an operation is used known as freenode.
• This operation makes it possible to make a node that is no longer being
used in its current context available fore reusing it in different context.
• The freenode() operation adds a node to the front of availability list.

Ques7: Explain Garbage Collection.

Ans:
Garbage is a block of heap memory that cannot be accessed by the program.
OR
Garbage collection [GC] is an automatic management of dynamically allocated
storage. It reclaims unused heap bocks for later use by program.
• Garbage collection is a form of automatic memory management.
• The garbage collector attempts to reclaim garbage or memory occupied by
the objects or pointers that are no longer in use by a program.
• Garbage collection is opposite of manual memory management, which
requires the programmer to specify which object to deallocate and return to
the memory system.
• Garbage collection may take a significant proportion of total processing
time in a program and can thus have significant influence on performance.
• Resources other than memory, such as network sockets, database handles,
user interaction windows etc. are not handled by garbage collection.
• The basic principles of garbage collection are:
• Finds data objects in a program that cannot be accessed in the future.
• Reclaim the resources used by those objects.
Ques8: What is List as ADT?
Ans:
A list is a sequence of zero or more elements of a given type.
Consider the list A1, A2, A3,…. An.
The ADT list is a linear sequence of an arbitrary number of items, together with
the following properties and operations.

Let us assume that the list has the following properties.

• The size of the list is N.
• Ai-1 precedes of Ai.
• The position of Ai is i.
• The items in the list must have of the same type.
• The empty list has size 0.
• Ai follows Ai-1.
Operations on list:
1. createList() : creates an empty list.
2. add(index, item) : insert item at position index of a list.
3. isEmpty() : Determine if a list is empty.
4. size() : Returns number of items in a list.
5. remove(index) : Remove item at position index of a list.
6. traverse() : Traverse all the elements in the list.
7. sort() : Sort the elements in the list.
8. search() : Searching an element in the list.

Ques9: How memory is allocated for a node in Linked List? Explain with an
example.
Ans:
There are two ways to allocate memory for a node.
1. Static representation using array.
2. Dynamic representation using free pool of storage.

• Static representation
Static representation of single linked list maintains two arrays: one
array for information and the other for the Links or pointers as
INFO[] and LINK[]. These two arrays should be of equal size and
 parallel to each other. The memory size of these arrays should be
sufficient to store the entire linked list.

• Dynamic representation of linked list

The process of allocating memory at runtime is known as dynamic

memory allocation. The functions malloc() and calloc() are used to
allocate memory and free is used to deallocate memory.

Info1 Info2 Info3 Info4 Info5 Info6 Info7 Link

Ques10: Mention the types of linked list.

Ans:
Types of linked list:
• Singly linked list.
• Doubly linked list.
• Circular linked list.
• Header linked list.

Ques11: Mention the operations on linked list.

Ans:
Operations on linked list
1. Creation. 4. Searching. 7. Sorting.
2. Traversing/ Display. 5. Inserting. 8. Merging
3. Length. 6. Deletion. 9. Reversing.
Ques12: Write C-function or algorithm to find the length of singly linked list.
Ans:
C- function:
int length()
{
int len = 0;
NODE *CURRPTR;

if (start == NULL)
{
Printf(“The linked list is empty \n”);
Return(len);
}
CURRPTR = start;
while (CURRPTR != NULL)
{
len++ ;
CURRPTR = CURRPTR -> LINK;
}
return(len);
}
Ques13: Write a C- function or algorithm to search an item X in a linked list.
Ans:
Algorithm:
Step 1: set CURRPTR = start, LOC = NULL
Step 2: Repeat step 3 while CURRPTR ≠ NULL
Step 3: if (ITEM == INFO [CURRPTR] )
then LOC = CURRPTR
and display “search successful”
EXIT
else
CURRPTR = LINK[CURRPTR]
[so CURRPTR, now points to the next node]
Step 4: if LOC = NULL
display “search unsuccessful”
Step 5: EXIT
Ques14: Write a C function or algorithm to
i. Insert an item at the beginning of the singly linked list (S.L.L)
ii. Insert an item at the end of the S.L.L
iii. Insert an item at the specified position.
iv. Insert an item into the sorted linked list.
Ans:
i. Insert an item at the beginning of the singly linked list (S.L.L)

Function:
ii. Insert an item at the end of the S.L.L
iii. Insert an item at the specified position

iv. Inserted an item into a sorted linked list

Step 1: If the list is empty, then make the new node as head.

Step 2: If the new node value is lesser than the head node, then insert it at the
start, make it the head.

Step 3: Traverse through the list until the data of the next of current is less
than the data of the new node. By doing this, we are looking for an appropriate
position to insert the new node.

Step 4: When the loop breaks, insert the new node just after the current node:
1) New_node – > next = current – > next
2) current – > next = New_node
Ques15: Write a C-function or algorithm to
1. Delete an item from the beginning of S.L.L

C-function:

P.T.O
2. Delete an item from the end of S.L.L.

C-function:
 3. Delete an item from the specified position of S.L.L.

C-function:
Ques16: What is linked list? With the aid of algorithms discuss how a node can
be inserted and deleted from such a list.
Ans:
A linked list is a sequence of nodes in which each node contains on or more
data fields and a pointer to the next node.
A node can be inserted in many ways
A node can be deleted in many ways:
Ques17: Write a C- program to implement insert and delete operations on S.L.L.
Ans:
C- Program to implement insert operations on S.L.L.
 P.T.O

C-Program to implement delete operations on S.L.L.

P.T.O
Ques18: Write a C- function or algorithm to display the contents of singly linked
list.
Ans:
Algorithm:

C- Program:
Ques19: What is circular list? What are the advantages of circular linked lists
over singly linked list.
Ans:
A circular linked list is a type of linked list in which the last node of the list
points back to the first node, forming a circle or loop. In other words, the last
next pointer of the last node in the list is not NULL; instead, it points to the first
node. This arrangement creates a closed loop, allowing traversal though the
entire list from any starting point.

Advantages of Circular List:

• The circular list can be traversed to any node from any node.
• All the nodes link address will have valid addresses, instead of NULL
pointer.
• A node can be inserted at or deleted from any position of the linked list.
• One can start at any node in the list and traverse the whole list.

Ques20: What do you mean by header node? Explain the types of header linked
list.
Ans:
A header linked list is a linked list which always a info contains a special node
called header node at the beginning of the list. The info field of such a header
node generally contains the global information of the entire list.

There are two kinds of widely used header linked list:

• Grounded header linked list
1. The grounded header linked list is also referred as ‘singly header linked
list’. In this the last node LINK field contains the NULL pointer.
 2. Here, the info field of header node contains the number of nodes in a linked
list (excluding header list).
3. The number of nodes in the list may be obtained directly from the header
node without traversing the entire list.
4. The info field of header node contains the address of last node.

• Circular header linked list

1. A linked list in which last node points to the header node is called
circular header linked list.
2. Here, the info field of header node is containing the number of nodes in a
linked list(excluding header node).
3. The length of a linked list can be obtained from the info of the header
node.
4. The info value of header node should be incremented and whenever we
delete a node from the linked list, the info value of header node should be
decremented.

Ques21: Mention the advantages and disadvantages of header linked list.

Ans:
• Advantages
1. Simplified Operations.
2. Improved list management.
3. Facilities empty list handling.
 4. Simplifies algorithms.

• Disadvantages
1. Wasted memory.
2. Complex initialization.
3. Potential for confusion.
4. Increased code complexity.

Ques22: What do you mean by doubly linked list? What are the advantages and
disadvantages of doubly linked list?
Ans:
A doubly linked list is a data structure in which each nodes holds a data
element and had two pointers- one pointing to the previous node and another
pointing to the next node in the sequence.

• Advantages
1. The doubly linked list can be traversed in forward or backward direction.
2. If any particular node address is known, one can have both successor
node address and predecessor node address that makes inserting and
deleting much easier.
3. The doubly linked list is used to represent the trees effectively.
4. This simplifies list management.

• Disadvantages
1. Extra memory is required to store the back pointer.

Ques23: Write a C- function to search an item in singly linked list. If the item is
found, then return true, else add the item at the beginning of the list and return
false.
Ans:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Define the Node structure

struct Node {
int data;
struct Node* next;
};

P.T.O
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to search for an item in a singly linked list

bool searchAndInsert(struct Node** head, int item) {

struct Node* current = *head;
struct Node* newNode;

// Search for the item in the list

while (current != NULL) {
if (current->data == item) {
// Item found, return true
return true;
}
current = current->next;
}

// Item not found, insert at the beginning

newNode = createNode(item);
newNode->next = *head;
*head = newNode;

// Return false
return false;
}

// Function to display a singly linked list

void displayList(struct Node* head) {

struct Node* current = head;

while (current != NULL) {

printf("%d -> ", current->data);
current = current->next;
}

printf("NULL\n");
}
 int main() {
struct Node* head = NULL;

// Example: Search for item 3, then display the list

if (searchAndInsert(&head, 3)) {
printf("Item 3 found in the list.\n");
} else {
printf("Item 3 not found. Added at the beginning.\n");
}

// Display the list after the operation

displayList(head);

return 0;
}

Ques24: Write a program to add two polynomials using linked list.

Ans:

P.T.O
Ques25: Write a program to add elements into ordered linked list and perform
delete operations on ordered linked list.
Ans:

P.T.O
Ques26: What is Dynamic Memory Allocation?
Ans:
Dynamic memory allocation refers to the process of allocating memory for
variable or data structures during the runtime of a program. It allows a program
to request memory from the system while the program is running, rather than
relying on fixed, static memory allocations defined at compile-time.

Ques27: What is Dynamic Data Structure?

Ans:
A dynamic data structure is a way of organizing and storing data in a program
that allows for flexibility in size and structure during the execution of the
program. Unlike static data structures, which have fixed sizes determined at
compile-time, dynamic data structures can change in size and shape as needed
while the programming is running.

Ques28: Explain Dynamic Memory Allocations Functions in C with an example.

Ans:
1. malloc()
malloc is used for dynamic memory allocation and is useful when you
don’t know the amount of memory needed during compile time. Allocating
memory allows objects to exist beyond the scope of the current block.
2. calloc()
It is used to allocate a specified amount of memory and then initialize it to
zero. The function returns a void pointer to this memory location, which
can then be cast to the desired type. The function takes in two parameters
that collectively specify the amount of memory to be allocated.
3. Free()
The free() function is used to deallocate memory that was allocated using
the malloc() or calloc() functions. It takes pointer to the memory block to
be freed as its only argument. The memory block is then returned to the
system and can be reused by other programs.

Created By: - Assigned By: -

Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 UNIT-2
CHAPTER-5
Stacks
 UNIT-2
CHAPTER-5
Stacks
Questions & Answers: -
Ques1: Define a stack. Explain the working of a stack with a suitable
example.
Ans:
A stack is a collection of homogeneous data items where the insertion
and deletion take place at one end in a LIFO (Last in First out)
fashion. This end is termed as TOP of the stack
The insertion and deletion operations that can be performed on the
stacks are technically termed as PUSH and POP respectively

Ques2: Write Push and Pop algorithm

Ans:
Algorithm to push an element in a stack
1: [overflow check]
If TOP = MAXSTK-1
Then write (‘Stack overflow’)
2: [Increment TOP value]
TOP = TOP+1
3: [Insert the item at the TOP]
S[TOP] = item
4: return
Explanation
Overflow occurs whenever an extra item is attempted to push in to
stack even after TOP reached MAXSTK-1. So, Top should always be
less than MAXSTK in order to prevent overflow problems.
If TOP is equal to MAXSTK-1, then ‘stack overflow’ is to be
displayed else TOP should be incremented by ‘1’ and the item is
pushed into the stack. So, S[TOP] now becomes the new item.
Algorithm to pop an element from a stack
1: [Underflow check]
If TOP = -1
Then write (‘Stack underflow on POP’)
And exit ()
2: [Delete the item]
Item = S[TOP]
3: [Decrement TOP value]
TOP = TOP-1
4: exit ()
Explanation
We know that underflow occurs whenever an item is tried to pop from
the empty stacks. So, TOP should not be equal to -1. If TOP is equal
to -1, then ‘Stack Underflow on POP’ is to be displayed else the item
is to be popped (deleted) from the stack. Step2 indicates the deletion
of an item from the top of the stack. After deleting an item TOP
should be decremented by 1.
Ques3: Write C program for PUSH and POP operations of a stack
implemented using arrays. The functions should check overflow and
underflow conditions.
Ans:
Ques4: How a stack can be represented using Arrays?
Ans:
Since stack is also a collection of same type of items, we can take
array for implementing a stack. It is easy to implement but the
problem here is we have to allocate the memory block of sufficient
size prior to the operation. It is usually suggested to declare the array
to be large enough without wasting too much memory space.
Associated with each stack there is a top item of the stack, on which
the PUSH and POP operations are to be performed. For this we need
to consider a variable TOP which keeps the position of the top item in
the stack. This variable TOP is set to ‘-1’ for an empty stack.
As the Array size is already declared, it may be possible that
sometimes there can not be the place for an item to be pushed
(added). This condition is termed as ‘stack overflow’. For this, we
need to check the value of TOP with the size of the array prior to the
operation.
Sometimes it may be possible that there is no item in the stack to POP
(delete). If there is no element in the stack, the TOP value will be ‘-1’.
This condition of popping from an Empty stack is termed as ‘stack
underflow’. For this, we need to always check the value of TOP
before deleting the item.
Ques5: How a stack can be represented using Linked List?
Ans:
In a linked stack, every node has two parts- one that stores data and
another that stores the address of the next node. The START pointer
of the linked list is used as TOP. All the insertions and deletions are
done at the node pointed by TOP. If TOP=NULL, then it indicates that
the stack is empty
Ques6: Explain Stack as ADT
Ans:
A stack is a first in last out (FILO) structure, or a last in first out
(LIFO) structure. A stack is sometimes generalized with
insertion(push) and removal(pop) all at same end.
A stack is either empty or consists of two parts, a top element and
stack (the remaining elements). The elements in a stack may be of any
type, but all the elements in a given stack must be the same type.

A good example of stack is a stack of dishes in the dining hall. We

cannot get the one on bottom unless we pick up all the ones on top of
it.
Ques7: Mention the operations on stack
Ans:
Push (): - Insert an element at the TOP of the stack
Pop (): - Deleting an element from the TOP of the stack
Isempty (): - Checks whether the stack contains any item and displays
true if it is empty
Stacktop (): - To determine what the TOP item on a stack list is,
without removing it.
Display (): - Used to display the elements of the stack
Ques8: Write C-functions for Isempty () and Stacktop () operations.
Ans:
Isempty ()

Stacktop ()

Ques9: Write C program to implement stack using linked list.

Perform, PUSH, POP and Display operations.
Ans:
Ques10: Assume that S1 and S2 are two stacks. Combine these two
stacks by placing all elements of the second stack on top of the first
stack (maintain the same order as it was).
Ans:
To combine two stacks (S1 and S2) by placing all elements of the
second stack on top of the first stack while maintaining the same
order, The following steps can be followed: -
• Empty S1 into a temporary stack (TempStack).
• Combine S2 and TempStack into S1.
Here’s a simple algorithm for it
CombineStacks(S1, S2):
// Step 1: Empty S1 into a temporary stack
while S1 is not empty:
TempItem = pop(S1)
push(TempStack, TempItem)

// Step 2: Combine S2 and TempStack into S1

while TempStack is not empty:
TempItem = pop(TempStack)
push(S1, TempItem)

while S2 is not empty:

Item = pop(S2)
push(S1, Item)
• We use a temporary stack (TempStack) to temporarily hold the
elements of S1.
• We empty S1 into TempStack by popping elements from S1 and
pushing them onto TempStack.
• Then, we combine S2 and TempStack into S1 by popping
elements from both stacks and pushing them onto S1.
• After executing this algorithm, S1 will contain all the elements
from both S1 and S2, with the order maintained.
Ques11: Discuss the applications of stacks.
Ans:
There are several applications of stack like: -
• Recursion
• Reversal of a string
• Checking the parenthesis matching
• Postfix expression evaluation
• Infinix to Postfix conversion
• Infinix to prefix conversion
Ques12: Write the prefix and postfix form of the following Infinix
expressions
i. ((A+B)*C-(D-E))$(F+G)
ii. (A+B)*(C+D-E)*F
iii. (A+B)*(C+D)$(A+B)
iv. A+B*C-D/E*H
v. (A+B^C^D)*(E+F/D)
Ans:
((A+B)*C-(D-E))$(F+G)
Prefix: $ - * + A B C - D E + F G
Postfix: A B + C * D E - - F G + $
(A+B)*(C+D-E)*F
Prefix: * + A B * + C - D E F
Postfix: A B + C D E - + * F *
(A+B)*(C+D)$(A+B)
Prefix: $ * + A B + C D + A B
Postfix: A B + C D + * A B + $
A+B*C-D/E*H
Prefix: - + A * B C / D * E H
Postfix: A B C * + D E / H * -
(A+B^C^D)*(E+F/D)
Prefix: * + A ^ B ^ C D + E / F D
Postfix: A B C ^ D ^ + E F D / + *
Ques13: Write a C-program to evaluate postfix expression
Ans:
Ques14: Write a C-program to convert given Infinix expression into
postfix expression
Ans:
1. 2.

3.
Ques15: Show the stack contents after each operation for the
following sequence of PUSH and POP operations, assuming that
MAXSTK = 5;
a. PUSH(10)
b. PUSH(20)
c. POP()
d. PUSH(30)
e. PUSH(40)
f. POP()
g. POP()
h. PUSH(50)
i. POP()
j. PUSH(60)
Ans:
Initial Stack: (Empty)
a. PUSH(10):
Stack Contents: [10]
b. PUSH(20):
Stack Contents: [10, 20]
c. POP():
Stack Contents: [10]
d. PUSH(30):
Stack Contents: [10, 30]
e. PUSH(40):
Stack Contents: [10, 30, 40]
f. POP():
Stack Contents: [10, 30]
g. POP():
Stack Contents: [10]
h. PUSH(50):
Stack Contents: [10, 50]
i. POP():
Stack Contents: [10]
j. PUSH(60):
Stack Contents: [10, 60]
Ques16: What is Recursion?
Ans:
Recursion is a process of calling the function repeatedly in terms of
itself until a specified condition is reached so that it reduces the
complexity of the program.
In Recursion, stack is used to store the current value and return
address of the function call. At each recursive procedure call, the
stack is pushed to save necessary values; upon exit from that level the
stack is “popped” to restore the saved values of the preceding level.
Ques17: Write a recursive program for Tower of Hanoi Problem.
Ans:
Ques18: Write a recursive program to find GCD of three numbers.
Ans:

Ques19: Write a program to find the factorial of a number using

recursion.
Ans:
Ques20: Write a program to generate Fibonacci series using recursion.
Ans:

Created By: - Assigned By: -

Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit 2
Chapter -7
Queues
 Unit 2
Chapter -7
Queues
Question & Answer: -

Ques1: What is a queue? How queues are represented in memory?

Ans: -
Queue is defined as an ordered collection of items from which, the item from
which, the item may be deleted at one end called FRONT end and into which the
items may be inserted at the other end called REAR end.

Ques2: What are the different types of queues?

Ans: -

Ques3: What are the operations performed on queues?

And: -
Ques4: Explain linear/ordinary queue and write a C-program to implement the
same.
Ans:
Explanation
A linear queue is a data structure that follows the FIFO (first in, first out)
principle. This means that the element that is added to the queue first is also the
element that is removed first. Queues are often used to buffer data or to
implement tasks that need to be completed in a specific order.

Program to Implement Linear/Ordinary Queue

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int data;
} element;

typedef struct {
element *items;
int front;
int rear;
int size;
} queue;

queue *createQueue(int size) {

queue *q = (queue *)malloc(sizeof(queue));
q->items = (element *)malloc(size * sizeof(element));
q->front = -1;
q->rear = -1;
q->size = size;
 return q;
}

void enqueue(queue *q, element item) {

if (q->rear == q->size - 1) {
printf("Queue is full\n");
return;
}
q->rear++;
q->items[q->rear] = item;
}

element dequeue(queue *q) {

if (q->front == q->rear) {
printf("Queue is empty\n");
return;
}
q->front++;
return q->items[q->front];
}

int main() {
queue *q = createQueue(5);
enqueue(q, (element){1});
enqueue(q, (element){2});
enqueue(q, (element){3});
enqueue(q, (element){4});
 enqueue(q, (element){5});

printf("The elements of the queue are:\n");

while (q->front != q->rear) {
element item = dequeue(q);
printf("%d ", [Link]);
}

printf("\n");

return 0;
}
Ques5: Distinguish between linear queue and circular queues
Ans:
Ques6: Write a C function to insert an element in linear queue.
Ans:

Ques7: Write an algorithm for queue insert and delete.

Ans:
Ques8: Explain Queue as ADT.
Ans:

Ques9: What is underflow and overflow in queue?

Ans:
Underflow & Overflow: We know that the deletion or removal of item from the
queue requires at least one item in the 'front.i.e., deletion is possible only if the
queue is non- empty. It does not make sense to delete the item which is not
present. So, the illegal attempt made to remove the element from an empty queue
is called 'Underflow'.
We know that if an array is used for a queue, then there is a limit for the insert
operations to be performed. The possibility of a condition called 'Overflow' arises
when the queue size reaches the maximum array size. In the above example
when R=4, it has reached the maximum array size. Hence the insertions can not
take place and there by Overflow occurs.
Ques10: Write a C program to perform the following operation on linear queue.
1. Insert 2. Delete 3. Display
Ans:
1. Insert
 2. Delete

3. Display

Ques11: Write a C program to perform the following operation on linear queue.

1. Insert 2. Delete 3. Display
Ans:
1. Insert

2. Delete
3. Display
Ques12: Write a short note on priority queues.
Ans:
A priority queue is a queue such that each element of the queue has been
assigned with a priority & such that the order in which elements are processed
(deletion and insertion) comes from the following rules:
1. An element of higher priority is processed before any element of lower
priority.
2. if 2 elements have same priority, then the element which come first will be
processed first.

Ques13: What are the different types of priority queue?

Ans:

Ascending Priority Queue: It is a collection of elements into which items can

be inserted arbitrarily, but deletion is possible only for the smallest element, it
means that elements can be inserted in any order, but only the smallest element
can be removed first from the queue.

Descending Priority Queue: It is a collection of elements into which items can

be inserted arbitrarily, but deletion is possible only for the largest elements can
be inserted in any order, but only the largest element can be removed first from
the queue.
Ques14: What are the different types of representing priority queues in memory?
Ans:
There are various ways of implementing a priority queue. They are:
1. Circular Queue.
2. Array.
3. Trees.
4. Heap.
5. Multi- Queue.

Ques15: Write a C-program to implement ascending priority queue using arrays.

Ans:
Ques16: How queues are represented using Linked List? Explain with an
example.
Ans:
Each node of a linked queue consists of two fields: data and next(storing of
next node). The data field of each node contains the assigned value, and the next
points to the node containing the next item in the queue. A linked queue consists
of two pointers, i.e., the front pointer and the rear pointer.
Ques17: Write a C-program to perform Insert and Delete Operations on Queue
using Linked List.
Ans:
#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node *next;
};

struct node *front = NULL;

struct node *rear = NULL;

void enqueue(int data) {

struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;

if (front == NULL) {
front = new_node;
rear = new_node;
} else {
rear->next = new_node;
rear = new_node;
}
}
void dequeue() {
if (front == NULL) {
printf("Queue is empty\n");
return;
}

struct node *temp = front;

front = front->next;

if (front == NULL) {
rear = NULL;
}

free(temp);
}

void printQueue() {
struct node *temp = front;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

int main() {
enqueue(1);
 enqueue(2);
enqueue(3);

printQueue();

dequeue();

printQueue();

return 0;
}

Ques18: Write a C-program to implement priority queue by using 3 priority

levels and 3 queues sequentially.
Ans:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
int priority;
struct Node *next;
};
struct Queue {
struct Node *front;
struct Node *rear;
};
struct Queue queues[3];

void initQueue(struct Queue *queue) {

 queue->front = queue->rear = NULL;
}

void enqueue(struct Queue *queue, int data, int priority) {

struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;

if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}
int dequeue(struct Queue *queue) {
if (queue->front == NULL) {
return -1;
}
int data = queue->front->data;
struct Node *temp = queue->front;
queue->front = queue->front->next;

if (queue->front == NULL) {
queue->rear = NULL;
}
 free(temp);
return data;
}

int main() {
// Initialize the queues
for (int i = 0; i < 3; i++) {
initQueue(&queues[i]);
}
// Enqueue some data
enqueue(&queues[0], 10, 1);
enqueue(&queues[1], 20, 2);
enqueue(&queues[2], 30, 3);

// Dequeue the data in priority order

while (1) {
int data = dequeue(&queues[0]);
if (data == -1) {
break;
}

printf("%d\n", data);
}

return 0;
}
Ques19: What is double ended queue or deque? What are the operations that can
be performed on double ended queue?
Ans:
Deque (pronounced as “Deck”), in deque, both insertion and deletion can be
made at either end but not in the middle. The term deque is a contraction of the
name Double- ended Queue.
Deque is maintained by a circular array; DEQUE with pointers FRONT and
REAR, which points to the two ends of the deque.

Operations performed on double- ended queue:

1. Insertion at Front.
2. Insertion at Rear.
3. Deletion at Front.
4. Deletion at Rear.
Ques20: Write a C- program to implement deque both input- restricted and
output- restricted queue.
Ans:
Ques21: Explain how elements can be arranged in ascending order in priority
queue while inserting? After arranging them in ascending order, how insert and
delete operations are performed?
Ans:
In a priority queue, elements are arranged based on their priorities.
one way is that we can first sort the inserted elements in ascending order so that
the FRONT element of the queue will be the smallest element.

let’s consider a linear array of size = 5,

0 1 2 3 4

20 30 10 5 40

FRONT REAR

Fig. a. Unsorted array

0 1 2 3 4

5 10 20 30 40

FRONT REAR

Fig. b. Sorted array

Now, we can see in Fig. b. that after sorting, ‘5’ element has come to FRONT
from 3rd index position.
Now, we can directly delete the element from the queue. This will save a lot time
because there is no need to search the entire array elements.
So, when we delete the front element of the queue, the highest priority element
(smallest one) is deleted.
Ques22: If priority queue is not sorted, then how insert and delete operations are
performed on priority queue.
Ans:
Starting from the FRONT, traversing the array for an element of the highest
priority (the smallest element) and then deleting this element from the queue. If
this is not the front most element, then shift all its trailing elements to left side,
after the deleted element, one stroke each to fill up the vacant position.
let’s consider a linear array of size = 5,
0 1 2 3 4

20 30 10 5 40

FRONT REAR

Starting from ‘20’ all the remaining elements are said to be compared and the
smallest item is to be found out. The smallest element is ‘5’. So, ‘5’ is to be
deleted at 3rd position of the array and now 4th positions are to be shifted one
stroke to the left side.

0 1 2 3 4

20 30 10 40

FRONT REAR

Ques23: Explain the applications of queues.

Ans:
Applications of Queues:
1. Queues are widely used as waiting lists for a single shared resource like
printer, disk, CPU.
2. Queues are used in playlists for jukebox to add songs to the end, play from
the front of the list.
3. Queues are used as buffers in most of the applications like MP3 media
player, CD player, etc.
4. Used in call center systems for handling incoming calls in sequence.
5. To process orders in E-commerce in sequence.
Ques24: Write a C- program to perform Insert and Delete Operations in Circular
Queue using Linked List.
Ans:
Created By: - Assigned By: -
Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit- 3
Chapter- 8
Binary Trees
 Unit- 3
Chapter- 8
Binary Trees

Question and Answers: -

Ques1: Define a tree?
Ans:
Tree is a non- linear data structure, used to represent a relationship between
elements such as records, nodes and table of contents.
Ques2: Define a binary tree? Distinguish between tree and binary tree.
Ans:
A binary tree is a hierarchical data structure in which each node has at most
two children, referred to as left child and the right child. The arrangement of
nodes in a binary tree forms a tree- like structure where each node can have, at
most, two subtrees.
Distinguish between tree and binary tree:

Ques3: Define the following:

Ans:
1. Degree
The maximum number of children that is possible for a node is known as
degree.
[or]
The number of sub- trees of a node is called degree.

Indegree: The number of edges entering into the node is known as indegree.
outdegree: The number of edges coming out from the node is known as
outdegree.

2. Leaf
A node with no successors [nodes after it] is called a leaf node.
 in simple words, the node which is at the end and having no children or a node
whose degree is zero is called a leaf node. It is also known as terminal node or
external node.

3. Level
Level is the rank of hierarchy and root node is termed as in level 0. Similarly,
each node in a tree has a level. If a node is at level p, then their children are at
level [p+1] and parent is at level [p-1].
4. Depth or height
The depth or height of the tree is the maximum number of nodes that is
possible in a path starting from root node to a leaf node. So, the maximum level
of any leaf in the tree can be considered as the height.
5. Siblings
the nodes which have the same parent are said to be siblings [or] children of
the same parent are said to be siblings or brothers.
6. Forest
A forest is a collection of disjoint binary trees. Each binary trees within the
forest consists of nodes connected by edges, where each node has at most two
children. The term ‘disjoint’ implies that there are no common nodes among the
different trees in the forest.
7. Ancestor
An ancestor of a node is any node that lies on the path from the root to that
node. Specifically, it includes the node itself and all the nodes encountered while
moving upward from the node toward the root of the tree.
8. Descendant
A descendant of a node is any node that lies on the path from that node to any
of its leaves. More precisely, it includes the node itself and all the nodes
encountered while moving downward from that node toward the leaves of the
tree. Each node in binary tree has zero, one or two descendants, depending on the
structure of the tree.
Ques4: Explain the properties of Binary tree with suitable diagrams.
Ans:
Ques5: Write a C- program to create a binary tree using sequential
representation.
Ans:
Ques6: Explain linked list representation of binary tree.
Ans:
Linked list representation of binary trees of each node is divided into three
parts:
1. Info field.
2. Left link.
3. Right link.
The info field is use to store the information of the node [element]. The left link
is a link field which contains the address of its left node and the right link is a
link field which contains the address of its right node.
Representation:

Ques7: Explain the different methods of representation of binary trees in C.

Ans:
a) Contiguous or Sequential representation
1. Elements are stored in a linear, continuous block of memory.
2. For a binary tree, you must use an array to represent the tree in a
contiguous manner. Such that, each node is assigned an index, and the
relationship between parent and child nodes can be determined by simple
arithmetic calculation
3. This method is efficient in terms of memory usage, but it may require more
space than actually needed if the tree is not fully populated.
 b) Linked list representation
Linked list representation of binary trees of each node is divided into three
parts:
1. Info field.
2. Left link.
3. Right link.
The info field is use to store the information of the node [element]. The left link
is a link field which contains the address of its left node and the right link is a
link field which contains the address of its right node.
Ques8: What is Binary Search Tree?
Ans:
A Binary Search Tree [BST] is a binary tree where each node has at most two
children: a left child with values less than the node and a right child with the
values greater than the node. No duplicate values are allowed. This structure
allows for efficient search, insertion, and deletion operations with an average
time complexity of O(log n), where ‘n’ is the number of nodes. Maintaining
balance in the tree is crucial for optimal performance.
A Binary Search Tree is also known as Ordered Binary Tree.
Ques9: Write an algorithm for constructing a binary search tree.
Ans:
If node == NULL
return createNode(data)
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;

Ques10: What is Tree sort? Write a program to sort elements in BST.

Ans:
Tree sort is a sorting algorithm that organizes elements into a binary search
tree and then retrieves them in sorted order through an in- order traversal of the
of the tree
C-program: P.T.O
Ques11: Write a Program to create and search an element in BST.
Ans:
Ques12: Write a program to construct BST and perform preorder, inorder, and
postorder traversals.
Ans:
 Ques13: What is AVL Tree? Give an example.
Ans:
An AVL tree is a binary search tree in which the heights of the left and right
subtrees of the root differ by at most 1 and in which the left and right subtrees are
again AVL trees.
Example:

Ques14: What is Balance Factor in AVL trees? Give an example.

Ans:
The Balance Factor is a numerical value that represents the difference in
heights between the left and right subtrees of a node. The balance factor helps
maintain the balance property of AVL trees, ensuring that the tree remains
balanced and maintains its logarithmic height.
Balance factor = Height [left sub-tree] – Height [right sub-tree]
Ques15: Explain AVL Rotations with an example.
Ans:
1. Left to Left Rotations
When the pivot node is left heavy [balance factor is 1] and the new node is
inserted in left subtree of the left child of pivot node then the rotation performed
is left to left rotation
Example:
 2. Right to Right Rotation
When the pivot node is right heavy and the new node is inserted in right
subtree of the right child of pivot node then the rotation performed is right to
right rotation. This is mirror image to left to left rotation.
Example:

3. Left to Right Rotation

When the pivot node is left heavy and the new node is inserted in right sub
tree of the left child of pivot node then the rotation performed is left to right
rotation.
Example:

4. Right to Left Rotation

When the pivot node is right
heavy and the new node is inserted
in left subtree of the right child of
pivot node then the rotation is right
to left rotation.
Example:
Ques16: Create an AVL tree by inserting the following elements:
60,10,20,30,19,120,100,80,19
Ans:

Ques17: What is Heap Tree?

Ans:
A heap tree is a binary tree with a specific order property: in a max heap, each
node is greater than or equal to its children, and in a min heap, each node is less
than or equal to its children. It’s commonly used for priority queues.

Ques18: How heaps are represented in memory? Give the memory

representation.
Ans:
Heaps are typically represented in memory using arrays. In a heap, the
elements are stored in an array such that the relationship between parent and
child nodes can be easily determined using index calculations.
For a binary heap, if a node is at index i, its left child is at index 2i + 1, and its
right child is at index 2i + 2. Conversely, if a node is at index j, its parent is at
index (j -1)/2.
0 1 2 3 4 5 6 7 8

90 85 80 75 70 60 55 50 40

Heap representation using Array

Ques19: Build a max heap H from the given set of numbers:

45,36,54,27,63,72,61 and 18. Also draw the memory representation of the heap.
Ans:
Ques20: Build a max heap H from the given set of numbers:
45,36,54,27,63,72,61 and 18. Then insert 15,29,90,55 and delete 27,36,61.
Ans:
Ques21: Give an example for Trie data structure.
Ans:

Ques22: Define B-Tree.

Ans:
A B-Tree is a self- balancing m-way tree data structure that allows searches,
accesses, insertions and deletions in a logarithmic time. Each node in a B-Tree of
order m can have, at most, m children and m-1 keys.

Ques23: Define Multi Way Search Trees?

Ans:
A multi way search tree is a generalized version of a binary search tree that
allows for efficient data searching and sorting. This can have multiple children
per node. This allows for faster search and sort operations, especially on large
datasets.
Ques24: Write the procedure of inserting a new element into B- Tree.
Ans:
Ques25: Write the procedure of deleting an element from B-Tree.
Ans:
Step 1: Search for the element to be deleted.
Step 2: If the element is found, delete it from the node.
Step 3: If the node has fewer than the minimum number of keys, rebalance the
tree.

Created By: - Assigned By: -

Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 UNIT 3
Chapter-9
Graphs
 UNIT 3
Chapter-9
Graphs
Question & Answer: -
Ques1: Define the below graphs and give example.
(a) Directed Graphs
Ans: A directed graph is defined as a type of graph where the
edges have a direction associated with them.

Example of Directed Graphs

(b) Undirected Graphs

Ans: An undirected graph is a type of graph where the edges have
no specified direction assigned to them.

Example of Undirected Graphs

Ques2: Define subgraph with an example.
Ans:
A graph whose vertices and edges are subset of another graph is called
subgraph.

Example of subgraph

Ques3: Write a note on following.

(a) Adjacent and incident vertices
Ans:
Adjacent Vertices: Two vertices in a graph are said to be adjacent if
there exists an edge that connects them.
Incident Vertices: For an edge in a graph, the vertices connected by
that edge are called incident vertices. In other words, the endpoints of
an edge are incident vertices.
 (b) Indegree and Outdegree
Ans:
Indegree: The indegree of a vertex in a directed graph is the count
of incoming edges to that vertex. In other words, it is the number of
edges pointing towards the vertex.
Outdegree: The outdegree of a vertex in a directed graph is the
count of outgoing edges from that vertex. It is the number of edges
leaving the vertex.
Ques4: Explain complete graph with a example
Ans:
A complete graph is an undirected graph in which every pair of
distinct vertices is connected by a unique edge. In other words, every
vertex in a complete graph is adjacent to all other vertices. A
complete graph is denoted by the symbol K_n, where n is the number
of vertices in the graph.

Example of complete graph

Ques5: Explain connected and strongly connected graph.
Ans:
Connected graph: A connected graph is a graph in which there is a
path (a sequence of edges) between every pair of vertices.
Strongly connected graph:
A strongly connected graph is a concept associated with directed
graphs. In a strongly connected graph, there is a directed path from
every vertex to every other vertex in the graph.

Ques6: Define Weighted graph. Give an example.

Ans:
A weighted graph is a type of graph in which each edge (connection
between vertices) is assigned a numerical value called a "weight."
These weights typically represent some measure of distance, cost,
time, or any other relevant metric associated with the connection
between the vertices.

Example of weighted graph

Ques7: Explain the following terms:
(a) Path
A path refers to a sequence of connected vertices in a graph,
where each connection is established by an edge. It represents a
route or a way to move from one vertex to another within the
graph structure.

(b) Simple path

Simple path is a sequence of distinct vertices connected by
edges in such a way that no vertex is visited more than once,
except for the first and last vertices in the path.

(c) Cycle
Cycle is a path that forms a loop, allowing for traversal through
a series of distinct vertices and edges, ultimately returning to the
starting point.

(d) Simple cycle

Simple cycle is a cycle without any self-intersections or revisits
to the same vertex or edge, except for the initial and final
vertices.

Ques8: How graph can be represented using adjacency matrix?

Ans: A graph can be represented using an adjacency matrix, which is a
2D array (matrix) where each cell at position i , j represents whether
there is an edge between i and j. The size of the matrix is determined
by the number of vertices in the graph. If the graph is undirected, the
matrix is symmetric because the relationship between vertex i and j is
the same as the relationship between j and i. If the graph is directed, the
matrix may not be symmetric.
Ques9: How graph can be represented using adjacency list?
Ans: An adjacency list represents a graph as an array of linked lists. The
index of the array represents a vertex and each element in its linked list
represents the other vertices that form an edge with the vertex.

Linked list representation of the graph

Ques10: Explain the different ways of representing graphs.
Ans: Different ways of representing graphs are:
1. Adjacency List:
In an adjacency list, each vertex is associated with a list of its
neighboring vertices.
It is a more memory-efficient representation for sparse graphs.
Space complexity is O(V + E), where V is the number of vertices and E
is the number of edges.
2. Edge List:
An edge list represents a graph as a list of edges, where each edge is a
pair of vertices.
Simple and easy to understand, but not efficient for certain operations.
Space complexity is O(E), where E is the number of edges.
3. Incidence Matrix:
An incidence matrix is used for directed graphs and bipartite graphs.
Rows represent vertices, columns represent edges, and entries indicate
whether a vertex is incident on an edge.
Space complexity is O(V * E), where V is the number of vertices and E
is the number of edges.
4. Compact Sparse Matrix:
This is a hybrid representation that combines features of adjacency
matrix and adjacency list.
Suitable for graphs with a moderate number of vertices and edges.
Can be more memory-efficient than an adjacency matrix for certain
cases.
Ques11: What is Depth first search? Explain with an example.
Ans:
Depth- first search [DFS] is a recursive
algorithm that searches tree or graph data
structure. The algorithm starts at the root node
and explores as far as possible along each
branch. If it can’t go any further, it backtracks
until it finds an explored path.

Example:
Ques12: What is Breadth- first search? Explain
with an example.
Ans:
Breadth-first search [BFS] is an algorithm that searches a tree or
graph data structure for a node that meets a given property. It starts at
the root of the tree or graph and explores all nodes at the current depth
level before moving on to nodes at the next depth level.
Example:
Ques13: Write an algorithm for depth-first search.
Ans:
//Let G(V,E) is a set of vertices and edges.
//Let v be the starting vertex.
// Visited [i] = false initially for all vertices
//For any node I, visited [i] = true if I has already been visited, else it
contains false.
//stack is represented as s.
{
For (all V in G)
Visited [v] = false;
Add source vertex ‘v’ to stack ‘s’
While (stack is not empty)
{
pop top element N from stack s;
if (visited [N] = = false) then
{
Visited[N] = true;
}
For all vertices W adjacent from N do
{
Push w into stack s;
}
}
}
Ques14: Write an algorithm for breath-first search.
Ans:
// let G(V, E) is a set of vertices and edges.
// let v be the starting vertex.
// visited [i] = false initially for i = 1 to n
//For any node i, visited [i] = true if I has already been visited, else
it contains false
// queue is represented as q.
{
For(all v in G)
Visited [v] = true;
While(q is not empty)
{
Delete from element N from q;
For all vertices w adjacent from N do
{
If(visited [w] = = false) then
 {
Add w to q;
Visited[w] = true;
}
}
}
}
far as possible before backtracking.

Ques15: What is topological sorting? Give an example.

Ans:
Topological sorting is a linear ordering of the vertices of a Directed
Acyclic Graph [DAG] such that for every directed edge [u,v] vertex ‘u’
comes before vertex ‘v’ in the ordering. In simple terms, it arranges the
vertices in a way that respects the partial order defined by the directed
edges, ensuring that if there is a directed edge from vertex u to vertex v,
then u comes before v in the ordering.

Example:
Ques16: Consider a graph shown below. Starting at vertex ‘5’ traverse
the graph by depth first search.

P.T.O
Ans:
Ques17: Consider the graph shown below. Starting at vertex ‘1’, traverse
the graph by DFS and BFS. Draw the BFS and DFS spanning trees.

Ans:

+
Ques18: Find the topological sort for the below a directed acyclic graph.

Ans:

t
Created By: - Assigned By: -
Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit-4
Chapter-10
Searching
&
Sorting
 UNIT-4
CHAPTER-10
Searching and Sorting
Question & Answers: -
Ques1: What is Searching technique?
Ans:
Searching techniques refer to methods and strategies used to locate
specific information or items within a given context.
Ques2: Explain Linear search method.
Ans:
It is the simplest of all searching techniques which does not expect
specific ordering of the data. Linear searching is nothing but
searching an element/record in a linear way. This can be in arrays or
in linked lists or in some other list.
We need to start the search from the beginning by comparing the
‘key’ in each case and by scanning all the elements one by one until
the end of array or linked list.
If search is successful/retrieval, the entire record of that particular
‘key’ or the index of that record or the pointer to that record is
returned. If the search is unsuccessful, it gives a failure notification
(‘-1’ is returned)
Ques3: Explain Binary search method.
Ans:
In Binary search, if the array is of large size, all the entries are first
arranged in either ascending or descending order and then made in
two halves.
The required entry is first compared with middle element. If they are
equal, the search has been completed successfully.
If the middle element is greater than the item being searched for, the
search process is repeated for the first half of the array; otherwise the
process is repeated for the second half/last half.
Note, that each time a comparison is made, the number of elements to
be searched is cut into half. That is why, this method is very useful for
large arrays.
Ques4: Write an algorithm to implement Linear search.
Ans:

Ques5: Write a C-program to demonstrate linear search.

Ans:
Ques6: Write a C-Program to implement binary search.
Ans:
Ques7: Write a C-Program to implement Binary search using
recursion.
Ans:

Ques8: Compare Linear and Binary search techniques.

Ans:
[Link] Method:
Linear Search: Also known as sequential search, it involves checking
each element in the list one by one until the target element is found or
the end of the list is reached.
Binary Search: Requires a sorted list and works by repeatedly
dividing the search interval in half. It compares the target element
with the middle element of the sorted list and narrows down the
search range.
[Link]:
Linear Search: Typically has a time complexity of O(n), where n is
the number of elements in the list. It performs a constant-time
operation for each element in the worst case.
Binary Search: Has a time complexity of O(log n) in the average and
worst cases, where n is the number of elements. It efficiently reduces
the search space by half at each step.
[Link] vs. Unsorted Lists:
Linear Search: Can be used on both sorted and unsorted lists.
Binary Search: Requires a sorted list as it relies on dividing the
search space in half, which is only possible in a sorted order.
[Link] of Comparisons:
Linear Search: In the worst case, the number of comparisons is
proportional to the number of elements in the list.
Binary Search: The number of comparisons is logarithmic, making it
significantly more efficient than linear search for large data sets.
[Link] Usage:
Linear Search: Requires minimal additional memory beyond storing
the list itself.
Binary Search: Involves recursive calls or iterative steps, which may
require additional memory for function calls or loop variables.
Ques9: What is Sorting.
Ans:
Sorting refers to the operation of arranging the given data items either
in ascending order (numerically or lexicographically) or descending
order.
Let A be a list of a n elements A1,A2……..An in memory.
For ascending order the elements would be A1<A2<A3……<An
For descending order the elements would be A1>A2>A3……>An.
Ques10: Write C-Program to sort ‘n’ numbers using
a) Bubble sort
b) Selection Sort
c) Insertion Sort
d) Shell Sort
e) Quick Sort
f) Merge Sort
Ans:
Bubble Sort:
Selection Sort:

Insertion Sort:
Shell Sort:
Quick Sort:
Merge Sort:
Ques11: Write a C program to sort an array using of integers using
selection sort method. Show the steps to sort the elements.
25,57,48,37,12,92,86,33.
Ans:
Ques12: Explain Insertion Sort.
Ans:
The insertion sorts inserts each element in appropriate position. This
is same as playing cards, in which we insert a card in proper position.
If an array A contains n elements and we place each element of an
array at proper place in previously sorted element list.
The first pass starts with comparison of 1st element with 0th element.
i.e., A[1] with A[0]. In the second pass 2 nd element is compared with
0th and 1st element, i.e., A[2] with A[0] and A[1]. In general, in every
pass an element is compared with all elements before it.
Ques13: What are the factors to be considered during selection of a
sorting techniques?
Ans:
the following factors are to be considered during the selection of
sorting technique: -
• Execution Time: Execution time of program means how much
time is required for execution of program.
• Space: How much space is required for variables.
• Coding time: How much time is required to develop a sorting
technique for the given problem.
Ques14: Explain Divide and Conquer technique with an example
Ans:
The “divide and conquer” technique involves solving particular
problem by dividing it into one (or) more sub problems of smaller
size, recursively solving each sub problem and then “merging” the
solutions to the sub-problem to produce a solution to the original
problem.
The divide and conquer paradigm involve three steps at each level
of recursion.
1. Divide: Divide the problem into a number of sub problems.
 2. Conquer: Conquer the sub problems by solving them
recursively. If the sub problem sizes are small enough, then
solve the sub problem in a straightforward manner.
3. Combine: Combine the solutions to the sub problems in to the
solution for the original problem.
Ques15: Write a program to implement Merger Sort using Linked
List.
Ans:
Ques16: Why Linked list implementation is suitable for merge sort ?
Ans:
Merge sort is often preferred for sorting a linked list. The slow
random-access performance of a linked list makes some other
algorithms (such as quick sort) perform poorly, and others(such as
heap sort) completely impossible. Merge sort is a divide and conquer
algorithm in which need of random access to elements is less. Hence
making Linked list more suitable for merge sort.
Ques17: Explain the efficiencies of Linear and Binary search.
Ans:
Linear Search
• Suitable for small lists or unordered lists.
• It is easy to implement and doesn't require the data to be sorted.
• However, its time complexity is proportional to the size of the
list, which makes it less efficient for large datasets.
Binary Search
•
Highly efficient for large, sorted datasets.
 • The time complexity is logarithmic, which means the search
space is divided in half with each comparison.
• Binary search outperforms linear search for large datasets but
requires the data to be sorted, and additional sorting steps may
be needed.
Ques18: Explain the efficiencies of Quick sort and Merge sort.
Ans:
Quick Sort
• Quick sort is generally faster than many other sorting algorithms
in practice.
• It has good cache performance due to its partitioning nature.
• The worst-case time complexity is less likely to occur in
practice if a good pivot selection strategy is used.
Merge Sort
• Merge sort has a consistent and optimal time complexity of O(n
log n) in all cases, making it a reliable choice.
• It is a stable sort, meaning that the relative order of equal
elements is preserved.
• Merge sort performs well for linked lists as well as arrays.
Ques19: Write a C function for recursive Binary search
Ans:
Ques20: Write a menu driven program to sort the elements of an array
in descending order using selection sort and Insertion sort.
Ans:
Created By: - Assigned By: -
Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy
 Unit 4
Chapter 11
Hashing
 Unit 4
Chapter 11
Hashing

Question & Answers: -

Ques1: What is Hashing?

Ans:
Hashing is the process of mapping keys to their appropriate locations in the hash
table. It is the most effective technique of searching the values in an array or in a
hash table. Hashing allows to update and retrieve any data entry in a constant
time 0(1).

Ques2: what is the need of Hashing?

Ans:
• Ensures the integrity of data by generating fixed-size hash values that
uniquely represent the original data.
• hashing is an important data structure designed to solve the problem of
efficiently finding and storing data in an array.
• Hashing is an efficient method to store and retrieve elements.
• With hashing we can narrow down the search and find the number within
seconds.
Ques3: Define Hash function.
Ans:
the function of converting the key into the table/array index is called Hash
function. It is usually denoted by ‘H’.

Ques4: Define Hash table.

Ans:
Hash Table is a data structure which stores data in an associative manner. In a
hash table, data is stored in an array format, where each data value has its own
unique index value. Access of data becomes very fast if we know the index of the
desired data.
Ques5: Explain Hashing Mechanism with an example.
Ans:
Hashing is the process of transforming any given key or a string of characters
into another value. This is usually represented by a shorter, fixed-value or key
represents and makes it easier to find or employ the original string.

Hashing in a data structure is a two-step process.

1. The hash function converts the item into small integer or hash value.
This integer is used as an index to store the original data.
2. it stores the data in a hash table. We can use a hash key to locate the
data quickly.

Ques6: Explain the various methods of choosing a hashing function?

Ans:
1. Division Method
The division method is quite good for just about any value of M and since it
requires only a single division operation, the method works very fast. However,
extra care should be taken to select a suitable value for M.

As said early it is the simplest method of hashing an integer x. This method

divides x by M and then uses the remainder obtained. In this case, the hash
function can be given as
h(x) = x mod M
The number of collisions depend on the value of ‘M’. if it is a power of two then
is sure that we will get more collisions. So, we should take the ‘M’ as a prime
number for minimizing the collisions.
2. Midsquare Method
In this method, we square the key first. Then we take some digits from the
middle of this number as the generating address.
The hash function is H(K) = m
Where ‘m’ is obtained by removing some digits from both ends of “K2”. But it
should be noted that the digits taken from “K2” should be at the same positions.

3. Folding Method
This is the easiest way of computing that key where the key is broken into
pieces and then adding all of them to get the hash address. Each piece except
possibly the last, should have the same number of digits as the required address.
For this we ignore the last carry.

The hash function is:

H(K) = K1 + K2 + ….. + Kn

Where K1, K2 …… Kn are the broken pieces.

Sometimes, we can reverse some pieces (say even-numbered pieces K2, K4 …..)
and then add to get the hash address.
4. Mixed method
Sometimes, we can mix up other methods with the division method in order to
ensure that addresses are in the range of hash table.

So, by means of mixed method we get the addresses in the desired range once a
division method is performed. But one thing should be kept in mind that doing
one more and complete operation with the digits of the key will affect the first
criteria choosing the good hash function i.e. easy computation of the key.

Ques7: What is Hash Collision? Give one example.

Ans:
Hash collision is said to occur when two keys generate the same value. Whenever
there is one or more than one key that point/map to the same slot in the hash
table, the phenomenon is called a collision.
Ques8: What are the techniques of resolving Hash Collisions?
Ans:
1. Open Addressing
• Linear Probing.
• Quadratic Probing.
• Double Hashing.
• Rehashing.
2. Chaining
• Linear probing.
• Quadratic probing.
• Double probing.

Ques9: Explain Collision Resolution with Open Addressing.

Ans:

➢ once a collision takes place, open addressing or closed hashing computes

new positions using a probe sequence and the next record is stored in that
position.
➢ The hash table contains two types of values: sentinel values (e.g., -1) and
data values.
➢ The presence of sentinel values indicates the location contains no data
value at present but can be used to hold a value.
➢ When key is mapped to a particular memory location, then the value it
holds is checked.
➢ If it contains a sentinel value, then the location is free and data value can be
stored in it.
➢ If the location has some values in it, then other slots are checked
systematically in the forward direction to find a free slot.
 ➢ If a single free location is not found, then we have an OVERFLOW
condition.

Ques10: Explain Collision Resolution by Chaining.

Ans:
➢ Collision resolution by chaining combines linked representation with hash
table.
➢ When two or more records hash to the same location, these records are
constituted into a singly-linked list called a chain.
➢ In chaining, we store all the values with the same index with the help of
linked list.
➢ In this method, a chain of elements is maintained which have the same hash
address.
➢ The hash table here behaves like an array of pointers.
➢ Each location in the hash table stores a pointer to the linked list, which
contains all the key elements that were hashed to that location.
➢ The major drawback of chaining is that a linked list requires extra pointers.

Collision Resolution by Chaining

Ques11: Explain Linear Probing with an example.

Ans:
➢ This hashing technique find the hash key.
[or]
Generated address value through hash function and maps the key on
particular position in the hash table.
➢ In case if the key has same hash address, then it will find the next empty
position in the hash table.
➢ We take hash table as a circular array.
➢ So if the ‘table size’ is ‘N’, then after (N-1) position, it will search for 0th
position in the array.
 ➢ For searching the element, first we check the hash generated address
position in the table.
➢ If element is not available at that position, then we sequentially search the
element after the has address position.
➢ The main disadvantage of the linear probing technique is the records tend
to cluster i.e., when half of the table is full, then it is difficult to find the
empty position in the hash table in case of hash clash.
➢ Searching will also become slow because it will go for linear searching.

Ques12: Explain Quadratic Probing with an example.

Ans:
In order to minimize the clustering problem, quadratic probing can be used.
Suppose a hash generating address is ‘a’ then in the case of collision, linear
probing searches the location a, a+1, a+2…. So the location where the insertion
and searching takes place is (a+i) (for i = 0,1, 2,…). But in quadratic probing, the
location of insertion and searching takes place in (a+i2) (for i = 0,1,2,…) i.e., at
the locations a, a+1, a+4, a+9……. So it will decrease the problem of clustering
but the problem of this technique is it cannot search all the locations. If the
‘tablesize’ is prime number then it will search at least half of the locations of the
hash table.
Ques13: Explain Double Hashing with an example.
Ans:
Double hashing requires the hashing second time in case of collision.
Suppose the generated address of a hash function ‘H’ is ‘a’, then in case of
collision we will again do the hashing of this hash function. Let that hash
function is H1 and its address is a1. Now we will insert and search at the locations
a, a+a1, a+2a1, a+3a1…. But it requires two times the calculation of hash function
which creates it complex and searching will also be slower than linear and
quadratic probing.
Here, the next probing depends on the second hash function H1. So we should be
very careful in choosing H1.

Ques14: Explain Rehashing with an example.

Ans:
➢ Sometimes, there are chances of insertion failure when hash table is full. So
The solution for this particular case is to create a new table with the double
size of the previous hash table.
 ➢ Here we will use a new hash function and insert all the elements of the
previous hash table.
➢ We will scan the elements of the previous hash table one by one and
calculate the has key with the new has function and insert them into new
hash table. This technique is called rehashing.
➢ It ensures the insertion of element in hash table.

Ques15: What are the Characteristics of Good Hash Function?

Ans:
• Easy to Compute: it should be computed quickly and returns values within
the range of the Hash-Table.
• Uniform Distribution: it should provide a uniform distribution of hash
values. A non-uniform distribution increases the number of collisions and
the cost of resolving them.
• Less collisions: chose a hash function with a good collision resolution
algorithm which can be used to compute alternative index if the collision
occurs.
• High Load Factor: It should have a high load factor for a given set of
keys.
Load factor = Number of elements in hash Table / Hash Table size.

Ques16: What do you mean by Probing?

Ans: The process of examining memory locations in that hash table is called
Probing.

Created By: - Assigned By: -

Sumit Debbarma Mr. Aditya Diwan Sir
Deep Raj Gupta
Suman Das
Rohit Roy