DATASTRUCTURE TWO MARK QUESTIONS

 

DATA STRUCTURE

1. Define Algorithm

It is a set of explicit and unambiguous finite step which, when carried out for a given set of initial conditions, produce the corresponding output and terminate in finite time.

2. What are the steps involved in problem solving aspects

1. 
   
   
   Problem definition phase
2. 
   
   
   Getting started on a problem
3. 
   
   
   Use of specific examples
4. 
   
   
   Similarities among problems
5. 
   
   
   Working backwards from the solution
6. 
   
   
   General problem solving strategies

3. Define top down design or step (or) step wise refinement

A technique for algorithm design that tries to accommodate a very limited span of logic or instruction, It builds solutions to a problem in a step wise fashion.

4. What are the steps involved in top-down design

1. 
   
   
   Breaking a problem into sub problem
2. 
   
   
   Choice of a suitable data structure
3. 
   
   
   Construction of loops
4. 
   
   
   Establishing initial condition for loops
5. 
   
   
   Find the iterative construct
6. 
   
   
   Termination of loops

5. What are the points to be considered during implementation of algorithms

1. 
   
   
   use of procedure to emphasize modularity
2. 
   
   
   Choice of variable names
3. 
   
   
   Documentation of programs
4. 
   
   
   Program testing

   
   

   6. What types of strategy is used in binary search? Give its analysis
   
   Divide and conquer strategy. Analysis is n/2-O(log n)

   
   

   
   

   7. What types of strategy is used in linear search? Give its analysis.

   Brute force approach ie., Finds the solution directly without considering the time and memory consumption. Analysis is n- O(n)
   
   8. Define program verification

   It refers to application of mathematical proof technique to establish that the results obtained by the execution of a program with arbitray inputs are in accord with formally defined output specification.

   9. What are the steps involved in program verification

   1. 
      
      
      Computer model for program execution
   2. 
      
      
      Input and Output assertion
   3. 
      
      
      Implications and symbolic executions
   4. 
      
      
      Verification of straight-line program segments
   5. 
      
      
      Verification of program segments with branches
   6. 
      
      
      Verification of program segments with loops
   7. 
      
      
      Verification of program segments that employ array
   8. 
      
      
      Proof of termination.

   
   

   10. What are the steps involved in efficiency of algorithm

   1. 
      
      
      Avoiding redundant computation
   2. 
      
      
      Inefficiency due to late terminations
   3. 
      
      
      Referencing array elements
   4. 
      
      
      Early diction of desired output conditions
   5. 
      
      
      Trading storage for efficiency gain

   
   

   11. What are the steps involved in analysis of algorithm

   1. 
      
      Computational complexity
   2. 
      
      
      The order notation
   3. 
      
      
      Worst and average case behaviour
   4. 
      
      
      Probabilistic average case analysis

   
   

   12. How will you swap two values A,B

   T=A;

   A=B;

   B=T; Here T is a temporary storage variable

   
   

   13. Write an algorithm to find the total number of students passed in a subject

   1. 
      
      
      Read the number of marks
   2. 
      
      
      Initialize count=0
   3. 
      
      
      While there are still marks do
      1. 
         
         
         Read next mark
      2. 
         
         
         If it is a pass(>=50) then add one to count
   4. 
      
      
      Write the total number of passes=count

   
   

   14. Design an algorithm to compute the average of n numbers

   1. 
      
      
      Read the number
   2. 
      
      
      Initialize sum=0
   3. 
      
      
      While less than n numbers have been summed do

   a. Read next number

   b. Compute sum=sum +number

   4. Write out the sum n numbers

   
   

   15. Design an algorithm for e=1/0! + 1/1! + ½! +…….

   Long int factorial(int n)

   {

   If(n<=1)

   Return 1;

   else

   Return n*factorial (n-1)

   }

   Long int series (int n)

   {

   Sum=0;

   For(i=0;i

   Sum=sum+1/factorial(i);

   print sum;

   }

   
   

   
   

   16. Design an algorithm for sin(x)=x/1! – x^3/3! + x^5/5!-…….

   1. 
      
      
      Function sin(float x)
   2. 
      
      
      Term=x;
   3. 
      
      
      Tsin=x;
   4. 
      
      
      I=1;
   5. 
      
      
      X2=x*x;
   6. 
      
      
      While abs(term)>error do
      1. 
         
         
         i=i+2
      2. 
         
         
         term=term*x2/(j*(j-1));
      3. 
         
         
         tsin=tsin+term;
   7. 
      
      
      Print sine series as t sin

   
   

   17. Design an algorithm for Fibonacci sequence

   1. 
      
      
      Get the n value
   2. 
      
      
      Initialise=0,b=1;
   3. 
      
      
      While i

   1. 
      
      
      Print the value of a&b
   2. 
      
      
      a=a+b;
   3. 
      
      
      b=a+b;
   4. 
      
      
      i=i+2;

   4. 
      
      
      Print the value of a and b

   18. Design an algorithm to find the reverse the digits of an integer

   1. 
      
      
      Function findreverse(int n)
   2. 
      
      
      Initalise reverse=0
   3. 
      
      
      While n>0 do
      1. 
         
         
         reverse=reverse*10+n mod 10;
      2. 
         
         
         n=n div 10;
   4. 
      
      
      Print the reverse value

   
   

   19. Design an algorithm to convert a decimal integer to octal representation

   1. 
      
      
      Establish the new base and initialize the quotient to the decimal number to be converted
   2. 
      
      
      Set the new digit count n digit to zero
   3. 
      
      
      Repeatedly

   1. 
      
      
      Compute the next most significant digit (octal) form the current quotient q as the reminder r after division by new base
   2. 
      
      
      Covert r to appropriate ASCII value
   3. 
      
      
      Increment new digit count n digit and store r in output array newrep
   4. 
      
      
      Compute the next quotient q from its predecessor using integer division by new base

   4. 
      
      
      Until the quotient is zero

   
   

   20. Design an algorithm to convert integer to decimal format

   1. 
      
      
      Establish the character string for conversion to decimal and its length initialize decimal value to zero
   2. 
      
      
      Set base 0 value to ASCII or ordinal value of 0
   3. 
      
      
      While less than n characters have been examined do
      1. 
         
         
         Convert next character to corresponding decimal digit
      2. 
         
         
         Shift current decimal value to the left one digit and add in digit for current character
   4. 
      
      
      Return decimal integer corresponding to input character representation

   
   

   21. Design an algorithm for factorial using recursion

   Long int factorial(int n)

   {

   If(n<=1)

   Return 1;

   else

   return n*factorial(n-1)

   }

   
   

   22. Define computational complexity or time and space complexity

   It is a quantitative measure (time & memory consumption) of an algorithm performance, which is necessary to step up a computational model that reflects its behaviour under specific input conditions.

   
   

   23. Define worse case complexity

   It is a quantitative measure of an algorithms performance for a given problem of size n corresponds to maximum complexity encountered among all problems of size n.

   
   

   24. Give the analysis of nested for loops

   Analysis O (n^2)

   
   

   25. Define Big Oh

   T(N)=O(f(N)) if there are positive constants c and n_o such that

   T(N)>=cf(N) where N>=n₀