18-05-2012, 04:52 PM
Data structure :questions
Assignment TB.doc (Size: 29.5 KB / Downloads: 93)
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_________
III. 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 iii
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