Algorithm & Data
Structures Q Bank:
Concepts &
Applications.
, UNIT-I SHORT ANSWER QUESTIONS
1.Define algorithm and state the criteria the algorithm should satisfy?
Ans:
Definition: An Algorithm is a method of representing the step-by-step procedure for solving a
problem. It is a method of finding the right answer to a problem or to a different problem by
breaking the problem into simple cases.
It must possess the following properties:
• Finiteness: An algorithm should terminate in a finite number of steps.
• Definiteness: Each step of the algorithm must be precisely (clearly) stated.
• Effectiveness: Each step must be effective.i.e; it should be easily convertible into
program statement and can be performed exactly in a finite amount of time.
• Generality: Algorithm should be complete in itself, so that it can be used to solve all
problems of given type for any input data.
• Input/Output: Each algorithm must take zero, one or more quantities as input data and
gives one of more output values.
2. Define asymptotic notations: big ‘oh’,omega, theta ?
Ans:
Big Oh Notation
Big Oh notation denoted by „O‟ is a method of representing the upper bound of algorithm‟s
running time. Using big oh notation we can give longest amount of time taken by the algorithm
to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0 and constant
C such that C > 0 and for all integers n > n0, f(n) ≤ c*g(n), then f(n) = Og(n).
Omega Notation
Omega notation denoted „Ω‟ is a method of representing the lower bound of algorithm‟s
running time. Using omega notation we can denote shortest amount of time taken by algorithm
to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0 and constant C
such that C > 0 and for all integers n > n0, f(n) >c*g(n), then f(n) = Ω g(n).
,Theta Notation
Theta notation denoted as „θ‟ is a method of representing running time between upper bound and
lower bound.
Definition:
Let, f(n) and g(n) are two non-negative functions. There exists positive constants C1 and C2 such
that C1 g(n) ≤ f(n) ≤ C2 g(n) and f(n) = θ g(n)
3.Define data abstraction
Ans:
Data abstraction is the reduction of a particular body of datato a simplified representation of
the whole. Abstraction, in general, is the process of taking away or removing characteristics
from something in order to reduce it to a set of essential characteristics.
4.Define data structures? List the types of data structures.
Ans: Data structure is a method of organizing large amount of data more efficiently so that any
operation on that data becomes easy
5. Define single, double, circular linked lists.
Ans:
Singly Linked List:
A singly linked list, or simply a linked list, is a linear collection of data items. The linear
order is given by means of POINTERS. These types of lists are often referred to as linear
linked list.
* Each item in the list is called a node.
Types of Data Structure:
Data Structure
Data structures are divided into two types:
• Primitive data structures.
Primitive Data
Non-Primitive Data
• Non-primitive data structures. Structures
Structures
Non-Linear Data
Structure
, * Each node of the list has two fields:
1. Information- contains the item being stored in the list.
2. Next address- contains the address ti the next item in the list.
* The last node in the list contains NULL pointer to indicate that it is the end of the list.
Double Linked List:
A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node (previous node)
from any arbitrary node within the list. Therefore each node in a double linked list has two
link fields (pointers) to point to the left node (previous) and the right node (next). This helps
to traverse in forward direction and backward direction.
Circular Linked List:
A circular linked list is one, which has no beginning and no end. A single linked list can be
made a circular linked list by simply storing address of the very first node in the link field of
the last node.
6. List out any four applications of data structures.
Ans: As applications are getting complex and data rich, there are three common problems
that applications face now-a-days.
Data Search − Consider an inventory of 1 million(106 ) items of a store. If the application is
to search an item, it has to search an item in 1 million(106 ) items every time slowing down
the search. As data grows, search will become slower.
Processor Speed − Processor speed although being very high, falls limited if the data grows
to billion records.
Multiple Requests − As thousands of users can search data simultaneously on a web server,
even the fast server fails while searching the data.
To solve the above-mentioned problems, data structures come to rescue. Data can be
organized in a data structure in such a way that all items may not be required to be searched,
and the required data can be searched almost instantly.
7.List linear and non linear data structures.
Ans: Linear Data Structures
If a data structure is organizing the data in sequential order, then that data structure is called as
Linear Data Structure.
Structures Q Bank:
Concepts &
Applications.
, UNIT-I SHORT ANSWER QUESTIONS
1.Define algorithm and state the criteria the algorithm should satisfy?
Ans:
Definition: An Algorithm is a method of representing the step-by-step procedure for solving a
problem. It is a method of finding the right answer to a problem or to a different problem by
breaking the problem into simple cases.
It must possess the following properties:
• Finiteness: An algorithm should terminate in a finite number of steps.
• Definiteness: Each step of the algorithm must be precisely (clearly) stated.
• Effectiveness: Each step must be effective.i.e; it should be easily convertible into
program statement and can be performed exactly in a finite amount of time.
• Generality: Algorithm should be complete in itself, so that it can be used to solve all
problems of given type for any input data.
• Input/Output: Each algorithm must take zero, one or more quantities as input data and
gives one of more output values.
2. Define asymptotic notations: big ‘oh’,omega, theta ?
Ans:
Big Oh Notation
Big Oh notation denoted by „O‟ is a method of representing the upper bound of algorithm‟s
running time. Using big oh notation we can give longest amount of time taken by the algorithm
to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0 and constant
C such that C > 0 and for all integers n > n0, f(n) ≤ c*g(n), then f(n) = Og(n).
Omega Notation
Omega notation denoted „Ω‟ is a method of representing the lower bound of algorithm‟s
running time. Using omega notation we can denote shortest amount of time taken by algorithm
to complete.
Definition:
Let, f(n) and g(n) are two non-negative functions. And if there exists an integer n0 and constant C
such that C > 0 and for all integers n > n0, f(n) >c*g(n), then f(n) = Ω g(n).
,Theta Notation
Theta notation denoted as „θ‟ is a method of representing running time between upper bound and
lower bound.
Definition:
Let, f(n) and g(n) are two non-negative functions. There exists positive constants C1 and C2 such
that C1 g(n) ≤ f(n) ≤ C2 g(n) and f(n) = θ g(n)
3.Define data abstraction
Ans:
Data abstraction is the reduction of a particular body of datato a simplified representation of
the whole. Abstraction, in general, is the process of taking away or removing characteristics
from something in order to reduce it to a set of essential characteristics.
4.Define data structures? List the types of data structures.
Ans: Data structure is a method of organizing large amount of data more efficiently so that any
operation on that data becomes easy
5. Define single, double, circular linked lists.
Ans:
Singly Linked List:
A singly linked list, or simply a linked list, is a linear collection of data items. The linear
order is given by means of POINTERS. These types of lists are often referred to as linear
linked list.
* Each item in the list is called a node.
Types of Data Structure:
Data Structure
Data structures are divided into two types:
• Primitive data structures.
Primitive Data
Non-Primitive Data
• Non-primitive data structures. Structures
Structures
Non-Linear Data
Structure
, * Each node of the list has two fields:
1. Information- contains the item being stored in the list.
2. Next address- contains the address ti the next item in the list.
* The last node in the list contains NULL pointer to indicate that it is the end of the list.
Double Linked List:
A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node (previous node)
from any arbitrary node within the list. Therefore each node in a double linked list has two
link fields (pointers) to point to the left node (previous) and the right node (next). This helps
to traverse in forward direction and backward direction.
Circular Linked List:
A circular linked list is one, which has no beginning and no end. A single linked list can be
made a circular linked list by simply storing address of the very first node in the link field of
the last node.
6. List out any four applications of data structures.
Ans: As applications are getting complex and data rich, there are three common problems
that applications face now-a-days.
Data Search − Consider an inventory of 1 million(106 ) items of a store. If the application is
to search an item, it has to search an item in 1 million(106 ) items every time slowing down
the search. As data grows, search will become slower.
Processor Speed − Processor speed although being very high, falls limited if the data grows
to billion records.
Multiple Requests − As thousands of users can search data simultaneously on a web server,
even the fast server fails while searching the data.
To solve the above-mentioned problems, data structures come to rescue. Data can be
organized in a data structure in such a way that all items may not be required to be searched,
and the required data can be searched almost instantly.
7.List linear and non linear data structures.
Ans: Linear Data Structures
If a data structure is organizing the data in sequential order, then that data structure is called as
Linear Data Structure.
