Data Structures and Algorithm-Unit 1

P. A. COLLEGE OF ENGINEERING AND TECHNOLOGY
POLLACHI, COIMBATORE – 642 002.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
ME – DEGREE COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES AND ALGORITHMS

Short Questions and Answers
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.

UNIT I – COMPLEXITY ANALYSIS & ELEMENTARY DATA STRUCTURES

1. What do asymptotic notation means?

Asymptotic notations are terminology that is introduced to enable us to

make meaningful statements about the time and space complexity of an

algorithm. The different notations are

Big – Oh notation

Omega notation

Theta notation.

2. What are the basic asymptotic efficiency classes?

The various basic efficiency classes are

Constant : 1

Logarithmic : log n

Logarithmic : log n

Linear : n

N-log-n : nlog n

Quadratic : n2

Cubic : n3

Exponential : 2n

Factorial : n!

3. Define O-notation?

A function t(n) is said to be in O(g(n)), denoted by t(n)

O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n,

i.e., if there exists some positive constant c and some nonnegative integer

n0 such that T(n) ” cg(n) for all n • n0

4. What are exponential growth functions?

The functions 2n and n! are exponential growth functions, because these

two functions grow so fast that their values become astronomically large even for

rather smaller values of n.

5. What is worst-case efficiency?

The worst-case efficiency of an algorithm is its efficiency for the worstcase

input of size n, which is an input or inputs of size n for which the algorithm

runs the longest among all possible inputs of that size.

6. What is best-case efficiency?

The best-case efficiency of an algorithm is its efficiency for the best-case

input of size n, which is an input or inputs for which the algorithm runs the fastest

among all possible inputs of that size.

7. What is average case efficiency?

The average case efficiency of an algorithm is its efficiency for an average

case input of size n. It provides information about an algorithm behavior on a

“typical” or “random” input.

8. What is amortized efficiency?

In some situations a single operation can be expensive, but the total time

for the entire sequence of n such operations is always significantly better that the

worst case efficiency of that single operation multiplied by n. this is called

amortized efficiency.

9. What is the formula used in Euclid’s algorithm for finding the greatest
common divisor of two numbers?

Euclid’s algorithm is based on repeatedly applying the equality

Gcd(m,n)=gcd(n,m mod n) until m mod n is equal to 0, since gcd(m,0)=m.

10. Define articulation points.

If a graph is not biconnected,the vertices whose removal would disconnect

the graph are known as articulation points.

11. Give some example of NP complete problems.

i. Hamiltonian circuit.

ii. Travelling salesmen problems

iii. Longest path problems

iv. Bin packing

v. Knapsack problem

vi. Graph colouring problem

12. What is the recurrence relation to find out the number of multiplications
and the initial condition for finding the n-th factorial number?

The recurrence relation and initial condition for the number of

multiplications is

M(n)=M(n-1)+1 for n>0 M(0)=0

13. What is the basic operation in the Tower of Hanoi problem and give the
recurrence relation for the number of moves?

The moving of disks is considered the basic operation in the Tower of

Hanoi problem and the recurrence relation for the number of moves is given as

M(n)=2M(n)+1 for n>1 M(1)=1

14. Who introduced the Fibonacci numbers and how can it be defined by a
simple recurrence?

Leonardo Fibonacci introduced the fibonacci numbers in 1202 as a

solution to a problem about the size of rabbit population. It can be defined by the

simple recurrence F(n)=F(n-1)+F(n-2) for n>1 And two initial conditions F(0)=0

and F(1)=1

15. What is the explicit formula for the nth Fibonacci number?

The formula for the nth Fibonacci number is given by

F(n)= 1/5(Φn - Φn)

Where

Φ =(1+5)/2

Φ =(1-5)/2

16. Define Data Structures

Data Structures is defined as the way of organizing all data items that

consider not only the elements stored but also stores the relationship between

the elements.

17. Define Linked Lists

Linked list consists of a series of structures, which are not necessarily

adjacent in memory. Each structure contains the element and a pointer to a

structure containing its successor. We call this theNext Pointer. The last

cell’sNext pointer points to NULL.

18. State the different types of linked lists

The different types of linked list include singly linked list, doubly linked list and

circular linked list.

19. List out the advantages of using a linked list

• It is not necessary to specify the number of elements in a linked list during its

declaration

• Linked list can grow and shrink in size depending upon the insertion and

deletion that occurs in the list

• Insertions and deletions at any place in a list can be handled easily and

efficiently

• A linked list does not waste any memory space

20. List out the applications of a linked list

Some of the important applications of linked lists are manipulation of

polynomials, sparse matrices, stacks and queues.

21. State the difference between arrays and linked lists

22. What do you mean by balanced trees?

Balanced trees have the structure of binary trees and obey binary search

tree properties. Apart from these properties, they have some special constraints,

which differ from one data structure to another. However, these constraints are

aimed only at reducing the height of the tree, because this factor determines the

time complexity.

Eg: AVL trees, Splay trees.

23. What is the use of threaded binary tree?

In threaded binary tree, the NULL pointers are replaced by some

addresses. The left pointer of the node points to its predecessor and the right

pointer of the node points to its successor.

24.Construction of expression trees?

1.convert the given infix expression into postfix notation

2. Create a stack and read each character of the expression and push into the

stack, if operands are encountered.

3.when an operator is encountered pop 2 values from the stack. From a tree

using the operator.

25. Why you need a data structure?

A data structure helps you to understand the relationship of one data

element with the other and organize it within the memory. Sometimes the

organization might be simple and can be very clearly visioned. Eg) List of names

of months in a year –Linear Data Structure, List of historical places in the world-

Non-Linear Data Structure. A data structure helps you to analyze the data, store

it and organize it in a logical and mathematical manner.

26. List the basic operations carried out in a linked list

The basic operations carried out in a linked list include:

• Creation of a list

• Insertion of a node

• Deletion of a node

• Modification of a node

• Traversal of the list