Data Structure and Algorithms
UNIT – I PART- A Questions & Answers 1. What is an algorithm? An algorithm is a finite set of instructions that , if followed, accomplishes a particular task. 2. What are the characteristics of an algorithm?  Input – Zero or more quantities  Output – At least one quantity  Definiteness – each instruction is clear and unambiguous  Finiteness – terminate after a finite number of steps  Efficiency – easily understandable 3. Define Space Complexity The Space complexity of an algorithm is the amount of memory it needs to run to completion 4. Define Time Complexity Time complexity of an algorithm is the amount of computer time it needs to run to completion 5. What are asymptotic notations? The notations that enables us to make meaningful statements about the time and space complexity of a program is called asymptotic notations. 6. What are the various asymptotic notations used to define the efficiency of an algorithm?  Big ‘Oh’ (O)  Omega (Ω)  Theta (θ)  Little ‘oh’ (o)  Little Omega 7. What is information? Information is a recorded or communicated material that has some meaning associated with symbolic representation. 8. What are the aspects to be considered to ensure information transfer between source and destination?  Syntactic – Physical form of information  Semantic – Meaning



Pragmatic – Action taken as a result of interpretation of information

9. State the Markov algorithm It takes the input string X and through a number of steps in the algorithm, transform X to an output string Y 10. Differentiate function & procedure A function is a sub algorithm which is used when one wants a single value returned to the calling routine. A procedure is a sub algorithm which does not return any value explicitly 11. How the character information is represented in memory? A character is represented in memory as a sequence of bits where a distinctive bit sequence is assigned to each character in the character set. Character sets are encoded in fixed length bit sequences. 12. What is a pointer? A pointer is a reference to a data structure. Important property of pointer is that, as a single fixed size data item, it provides a homogeneous method of referencing any data structure, regardless of the structures type or complexity. 13. What are the primitive functions associated with string?  Create a string of text  Concatenating two strings to form another string  Search and replace a given string  Test for the identity of a string  Compute the length of a string  14. What is a language? A language L to be a set of strings over some finite alphabet V, such that L