04-16-2017, 07:36 AM

Data structure :questions

[22415]

PART - A

I. Say whether the following statements are true or false.

1) Definiteness is one of the properties of an algorithm.(true)

2) Graph is a linear data structure. (false)

3) A tree is a connected graph. (true)

4) The data structure used by recursion is stack. (true)

5) Queue works on the strategy First in First out . (true)

II. Using suitable word or phrase fill up the blanks in the following sentences:

1) __profiling or performance measurement__is the process of executing a correct program on data sets and

measuring the time and space.

2) Tree is a__non linear__data structure.

3) For a graph with n number of nodes the number of edges to form a tree is

__n-1__

4) Last in First out Data structure is referred to as __stack__

5) A binary tree of depth K has maximum of__2 ki power K -1__number of

nodes.

6) A __simple graph__is a graph without self loop and parallel edges.

7) The two methods of searching are__sequential__and__binary__

II. Write brief answers to the following questions:

1) Define algorithm. What are its properties?

2) Give atleast four real life examples where we use stack operations.

3) Differentiate full and complete binary trees. Pg59

4) What are the demerits of recursion? Pg 56

Part ii

Q1 1, a step-by-step method of solving a problem or making decisions, as in making a diagnosis.

2. an established mechanical procedure for solving certain mathematical problems.

Properities of the algorithm

) Finiteness: - an algorithm terminates after a finite numbers of steps.

2) Definiteness: - each step in algorithm is unambiguous. This means that the action specified by the step cannot be interpreted (explain the meaning of) in multiple ways & can be performed without any confusion.

3) Input:- an algorithm accepts zero or more inputs

4) Output:- it produces at least one output.

5) Effectiveness:- it consists of basic instructions that are realizable. This means that the instructions can be performed by using the given inputs in a finite amount of time.

Q2 Real life examples where stacks are used:-

a) Processing of procedure calls and their termination.

b) In a recursive call of a function.

c) When a person wear bangles the last bangle worn is the first one to be removed and the first bangle would be the last to be removed. This follows last in first out (LIFO) principle of stack.

d)In a stack of plates, once can take out the plate from top or can keep plate at the top. The plate that was placed first would be the last to take out. This follows the LIFO principle of stack.

e)Batteries in the flashlight :- You cant remove the second battery unless you remove the last in. So the battery that was put in first would be the last one to take out. This follows the LIFO principle of stack.

f) Cars in a garage :- In order to take out the car that was parked first you need to take out the car that was parked last. So the car that was parked first would be the last to take out. This follows the LIFO principle of stack.

g) Clothes in the trunk

h) CD's in the case