131304 Data Structure and Algorithms 2mark Questions with Answers for all units

CLICK HERE TO DOWNLOAD

UNIT I

2MARKS Q&A

1. What is meant by an Abstract data type (ADT)?
An Abstract data type (ADT) is a set of operations. Abstract data types are
Mathematical abstractions.
Example:
Object such as set, list, and graphs along their operations can be viewed as
ADT.
Union, intersection, size, complement and find are the various operations of ADT.

2.What does List ADT mean?
General list: A1, A2, A3,…………..An
• A1-> first element
• An-> last element
• In general Ai is an element in a list I
• Ai-> current element position
• Ai+1-> predecessor

3. What are the various operations done under list ADT?
• Insert –element insertion
Ex: Insert (x, 3)
Insert the element X in 3rd position
• Delete-Element deletion
Ex: Delete (52)
Deletes the element
• Find-searching an element in the list
Ex: find (34)
Finds the element
* Next             -Successor
* Previous       -predecessor
* Print list       -Print all the elements in the list
*Make empty  - Emptying the list

4.What is the basic idea behind ADT?
The various operation of ADT such as union, intersection, sizes etc. are
Written once in the program and any other part of the program that needs to
Perform an operation on ADT can do so by calling the appropriate function.

5. What are advantages in the array implementation of list?
The advantages in the array implementation of list are,
1.        Print – list operation can be carried out at the linear time.
2.        Find – Kth operation takes a constant time.
6.What are the disadvantages in array implementation of stacks?
Disadvantages in array implementation of stacks are,
a. Array implementation requires the maximum size of the list in prior, which sometimes becomes an overestimate and which wastages considerable space when we use lists of unknown size.
b .bisection and deletion operation are expensive
1.        To insert a element at position 0, we need to push the entire array down one spot to make room.
2.        To delete a element requires shifting all the elements in the list up one.
3.        Hence the process is very slow.
7. What is a linked list?
Linked list is a kind of series of data structure, which are not necessarily
adjacent in memory. Each structure contains the element and a pointer to a
record containing its successor.
 A3

 A4

 A1

 A2

Next pointer
8. How do you insert an element in the array?
 A1 A2 A3 A4 A5
A (0)     A (1)      A (2)      A (3)      A (4)………………………………………….A (50)

To insert the element x in the array at position ‘0’.

Step 1: Create a place at position zero by pushing all other data.
 A1 A2 A3 A4 A5
A (0)   A (1)      A (2)      A (3)      A (4)       A (5)………………………………. A (50)

Step 2: Insert the element x,
 x A1 A2 A3 A4 A5
A (0)    A (1)       A (2)      A (3)       A (4)      A (5)………………………………..A (50)

9. How do you delete an element from the array?
Consider the list
 W E L C O M E
A (0) A (1) A (2) A (3) A (4) A (5) A (6)………………………………..A (50)
To delete ‘L’
Step 1: Find the position of the element.
Step 2: Delete the data and push all other data up

 W E C O M E
A (0) A (1) A (2) A (3) A (4) A (5)……………………………………….A (50)

10.What is doubly liked list?
In a simple linked list , there will be one pointer named as ‘NEXT POINTER’ to point the next element /data location, where as in a doubly linked list, there will be two pointers one to point the next and other to point the previous element location
Example:

11.Define double circularly linked list.
In doubly circular linked list, if the last node or pointer of the list, points to the first element of the list, then it is a circularly linked list
12. List three examples that use linked list.
Linked list are used by,
1.        Polynomial ADT
2.        Radix sort
3.        Multi lists.

13. What is the cursor implementation of linked list?
1.        Data is stored in a collection of objects; each object contains the data and a pointer to the next object.
2.        A new object that can be obtained from the system is global memory by a call to new and released by a call to delete

14. What are the applications of stack?
Stack can be applied in different situations. Some of the examples where is applied are explained below.
1.        Infix, Prefix & Postfix expression.
2.        Conversion of infix to postfix expression.
3.        Evaluating postfix expression.
4.        Balancing symbols.
5.        Tower of Hanoi.

15. Assuming S as an array representing the stack, Top is the pointer to
top of the stack and N is the maximum capacity of the stack, write
an algorithm for pushing an element in to the stack.
Algorithm for pushing an element into the stack
Step 1: If Top >= N
Then write (“stack overflow”)
Return
Step 2: Top¬ Top +1
Step 3: S [Top]¬ X
Step 4: Return.

16.Assuming S as an array representing the stack, Top is the pointer to
top of the stack and N is the maximum capacity of the stack, write
an algorithm for popping an element from the stack.
Algorithm for popping an element from the stack
Step 1: [Check for underflow on stack]
If Top = 0
Then write (“Stack overflow on pop”)
Exit
Step 2: [Decrement pointer]
Top ¬ Top –1
Step 3: [Return former top element of stack]
Return (S [Top +1])

17.Assuming S as an array representing the stack, Top is the pointer to
top of the stack  and N is the maximum capacity of the stack, write
an algorithm to find  out or display the content of the stack at a
particular index.
Algorithm for popping into the stack at an Index I:
Step 1: [Check for stack underflow]
If Top – I + 1 £ 0
Then write (“Stack underflow on peep”]
Exit.
Step 2: [Return the element from top of stack]
Return (S [Top – I + 1])

18. Assuming S as an array representing the stack, Top is the pointer to
top of the stack and N is the maximum capacity of the stack, write
an algorithm to change the content of the stack at location I.
Algorithm to change the content of the stack at location I.
Step 1: [Check for Stack underflow]
If Top – I + 1 £ 0
Then write (“Stack underflow on change”)
Return.
Step 2: [Check the I th element from the top of the stack]
S [Top – I + 1] ¬ X
Step 3: [Finished]
Return

19. What is the solution for the Towers of Hanoi problem?
The solution for the Tower of Hanoi problem is,
1.        Move N-1 disk from A to B.
2.        Move disc N from A to C.
3.        Move N-1 disk from B to C.

20. What is meant by list ADT?
List ADT is a sequential storage structure, general list of the form a1, a2, a3…an and the size of the list is ‘n’. any element in the list at the position  ‘i’ is defined to be ai.ai+1 is the successor of ai and ai-1 is the predecessor of ai.

21. What are the different ways to implement the list?
Ways to implement the lists are,
1.        Simple array implementation of list
2.        Linked list implementation of list

22. What is a pointer?
Pointer is a variable, which stores the address of the next element in the list. Pointer is basically a number.
Example

23. Why do we convert the infix expression into suffix expression?
We find it more convenient, to evaluate an infix arithmetical expression by first converting it to a suffix expression and then evaluating the latter. This approach will eliminate the repeated scanning of an infix expression, in order to obtain its value.

24. What is meant by degree of an operator?
The degree of an operator is a number of operands, which that operator has, example: Degree of the addition operator is two.

25. Define suffix expression.
Suffix expression is given by,
1.        A single symbol is an expression
2.        If x1,x2,…………xn are expressions and oi is of degree n, then x1,x2,………..xn oi is an expression
3.        The only valid expressions are those obtained by steps a and b.

UNIT II

2markS q&a

1.      Define Tree
A tree is a data structure, which represents hierarchical relationship Between individual data item.
A tree is a finite set of one or more nodes such that
Ã¼  There is a specially designated node called root.
Ã¼  The remaining nodes are partitioned into n>= 0 disjoint sets a, b, c, d…. n
Where a, b, c, d are called the sub trees of the root
A tree is shown in the following fig.

2.Define Non-linear data structure. (OR)
Give two examples of non-linear data structures, which are widely used. (Apr/May2004)
Data structure, which is capable of expressing more complex relationship than that of physical adjacent, is called non-linear data structure.
Example: Trees, graph, lists

3.What is meant by Binary tree? (Apr/May2004)
A binary tree is a finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left sub-tree and right sub-tree.(OR)In an m-ary tree, if m=2, then it is a binary tre  Each node has not more than 2 child nodes, each of which may be a Leaf node.
Application:
Binary tree is used in data processing.
Ã¼       File index schemes
Ã¼       Hierarchical database management systems.

4. What are the various operations performed on binary tree using linked  representation?
The operation of binary tree that use linked list representation are,
Ã¼       Insertion – Insert a given item into a tree.
Ã¼       Traversal – Processing the nodes of the tree one by one.
Ã¼       Search – Search for the specified item.
Ã¼       Copying – To obtain the exact copy of the given tree.
Ã¼       Deletion – Delete an item from the tree.

5. What are the two methods of binary tree implementation?
Two methods to implement binary tree are,
Ã¼       Linear representation.
Ã¼       Linked representation.

6. What are the different types of tree traversal technique? (Apr/May2004)
The different types of tree traversal technique are,
Ã¼       Pre-order traversal – yields prefix form of expression.
Ã¼       In-order traversal - yields Infix form of expression.
Ã¼       Post- order traversal - yields Postfix form of expression.

7. Define Pre-order traversal.
Pre-order traversal entains the following steps:
• Process the root node.
• Process the left sub tree.
• Process the right sub tree.
E.g.

 O/P: +AB

8.Define Post- order traversal.
Post- order traversal entrains the following steps:
• Process the left sub tree.
• Process the right sub tree.
• Process the root node.
E.g.

 O/P: AB+

9. Define In-order traversal.
In-order traversal entains the following steps:
• Process the left sub tree.
• Process the root node.
• Process the right sub tree.
E.g.

 O/P: A+B

10.Define complete binary tree.
A binary tree is said to be a complete binary tree, if all its level, except   possibly the last level, have the maximum number of possible nodes, all the nodes at the last level appear as far left as possible.

11.Define Full binary tree.
A binary tree is a full binary tree, if it contains maximum possible number of
nodes in all level.

12. What is meant by height balanced trees or AVL trees?
A tree is said to be height balanced if all its nodes have a balance factor of
1, 0 or –1.Height balancing, attempts to maintain trees that posses the ordering
property in a form close to fullness. AVL – Adulation VelsKii and Landis.

13. What is a balance factor in AVL trees?
Balance factor of a node is defined to be the difference between the heights of
the node’s left sub tree and the height of the node’s right sub tree.

14. Define AVL rotation.
Manipulation of tree pointers is centered at the pivot node to bring the
tree into height balance. The visual effect of this pointer manipulation is to
‘rotate’ the sub tree whose root is the pivot node. This operation is referred as
AVL rotation.
15. What are the four-different cases of pointer manipulations done in
AVL rotation?
The four-different cases of pointer manipulations are,
• Insertion occurred in the left sub tree of the left child of the pivot node.
• Insertion occurred in the right sub tree of the right child of the pivot node.
• Insertion occurred in the right sub tree of the left child of the pivot node.
• Insertion occurred in the left sub tree of the right child of the pivot nod
16. Define Binary Search tree.
A Binary Search tree ‘t’ is a binary tree; either it is empty or each node in the
tree contains an identifier and
• All identifier in the left sub tree of ‘t’ are less (numerically or
alphanumerically) than the identifier in the root Node +.
• All identifier in the right sub tree of ‘t’ are greater than the identifier in the root Node +.
• The left and right sub trees of ‘t’ are also binary search trees.

17.  What are the applications of trees?
Applications of trees are,
• Trees are used in the representation of sets.
• Decision-making. E.g.: Eight coins problem.
• Computer-games such as chess, tic-tac-toe, checkers etc., are created and executed using trees.
• Manipulation of arithmetic expression.
• Symbol table construction.
• Syntax-analysis.

UNIT III

2markS q&a

1.Define Hash function.
Hash function takes an identifier and computes the address of that   identifier in the hash table using some function. Hash function is used to perform insertions, deletions and finds in constant average time.

2. Define Hashing.
The address or location of an identifier x is obtained by computing some arithmetic function ‘f’ of ‘x’ i.e., f (x) gives the address of x in the table.

3.Define Hash table.
The memory available to maintain a table of identifier is said to be a hash  table, which is assumed to be sequential.
Hash table (ht) is partitioned into ‘b’ buckets ht [0]………ht [b-1]
Example: Hash table
1-26 buckets with 2 slots Slots slot1 & slot2    Slot 1           Slot 2
0-indicates empty

4. List out the different types of Hashing functions.
The different types of Hashing functions are,
Ã¼       The division’s method.
Ã¼       The mid square method
Ã¼       The folding method.
Ã¼       Digit analysis.
Ã¼       The length dependent method.
Ã¼       Algebraic coding.
Ã¼       Multiplication hashing.

5. What are problems in hashing?
The problems in hashing are,
v  Collision.
v  Overflow.

6. Define collision in hashing.
When two different keys or identifiers compute into the same location or  address in the hash table through any of the hashing functions, then it is termed Collision.

7.Define Double Hashing.
Double Hashing is a collision-resolution technique used in open addressing category. In double hashing, we apply a second hash function to x and probe at a   distance of hash2 (x), 2hash2 (x)…………, and so on.

8. What are applications of hashing?
The applications of hashing are,
v  Compliers use hash table to keep track of declared variables on source code.
v  Hash table is useful for any graph theory problem, where the nodes have real names instead of numbers.
v  Hash tables are used in programs that play games.
v  Online spelling checkers use hashing.

9.What does sorting mean?
Ordering the data in an increasing or decreasing fashion, according to some linear relationship among the data items is called sorting.

10.What are the two main classification of sorting based on the source of data?
According to the source of data sorting is classified into,
1.
1.        External sorting
2.        Internal sorting

11.What does external sorting mean?
External sorting is a process of sorting in which large blocks of data stored in storage device are moved to the main memory and then sorted.

12.What does internal sorting mean?
Internal sorting is a process of sorting the data in the main memory

13.What are the various factors to be considered in deciding a sorting algorithm?
Factors to be considered in deciding a sorting algorithm are,
1.
1.        Programming time
2.        Executing time for program
3.        Memory or auxiliary space needed for the programs environment.

14.How does the bubble sort get its name?
The bubble sort derives its name from the fact that the smallest data item bubbles up to the top of the sorted array.

15.What is the main idea behind the selection sort?
The main idea behind the selection sort is to find the smallest entry among in a(j),a(j+1),……..a(n) and than interchange it with a(j). this process is then repeated for each value of j.

16.What is the basis of shell sort?
Instead of sorting the entire array at once, it first divides the array into smaller segments, which are then separately sorted using the insertion sort.

17.What is the purpose of quick sort?
The purpose of quick sort is to move a data item in the correct direction, just enough for it to reach its final place in the array.

18.What is the advantage of quick sort?
Quick sort reduces unnecessary swaps and to moves an item to a greater distance in one move.

19.Is the heap sort always better than the quick sort?
No, the heap sort does not perform better than the quick sort. Only when array is nearly sorted to begin with the heap sort algorithm gains an advantage. In such a case, the quick deteriorates to its worst performance of O (n2).

20.Name some of the external sorting methods.
Some of the external sorting methods are,
1.
1.        Polyphase sorting
2.         Oscillation sorting
3.        Merge sorting

UNIT IV
2markS q&a

1.Define a graph.
A graph G consists of a nonempty set v which is a set of node
s of the graph a set E which is the set of edges of the graph and a mapping from the set of edges e to a set of pairs of elements of v. It can also be represented as G= (V, E)

2. Define adjacent nodes.
Any two nodes which are connected by an edge in a graph are called adjacent nodes. For example if an edge x e E is associated with a pair of nodes (u.v) where u, v e V then we say that the edge x connects the nodes u and v.

3. what is a directed edge?
In a graph G=(V,E) an edge which is directed from one node to another is called a directed edge.

4. what is an undirected edge?
In a graph G=(V,E) an edge which  has no specific  direction is called an undirected edge.

5. What is a directed graph & undirected graph?

A graph in which every edge is directed is called a directed graph

A graph in which every edge is undirected is called a directed graph.

6. What is a mixed graph?
A graph in which some of the edges are directed and some of the edges are undirected is called a mixed graph.
7. Define initial node.
Let (V,B) be a graph  and let x e E be a directed edge associated with the ordered  pair of nodes(u,v).Then the node ‘u’ is called the initiating node or initial node.

8. Define terminal node.
Let G=(V,E) be a graph and x e E is a directed edge connecting an ordered pair of nodes9u,v) then ‘v’ is called the terminating node or terminal node.

9.What is a simple graph?
A simple graph is a graph which has not more than one edge between a pair of nodes then such a graph is called a simple graph.

10.What is a weighted graph?
A graph in which weights are assigned to every edge is called a weighted graph.

11.Define out degree of a node.
In a directed graph for any node v,the number of edges which have v as their initial node called the out degree of the node v.
Example: Out degree of v=2.

12.Define in degree of a node.
In a directed graph for any node v, the number of edges which have v as their terminal node is called the indegree of a node.
Example: Out indegree of v=1.

13.Define total degree of a node.
The sum of the indegree and out degree of a node is called the total degree of the node (e.g.) In the graph given above,
Total degree of v = indegree of v + out degree of v
= 1+2
=3
14.Define a path in a graph.
The path in a graph is the route taken to reach the terminal node from a starting node.
Example:

15.what is meant by the length of the path?
The number of edges appearing in the sequence of a path is called the length of the path. E.g. in the above graph the length of the paths P1 and P2 and 3 respectively.

16.What is meant by strongly connected in a graph?
An undirected graph is connected if there is a path form every vertex to every other vertex. A directed graph with this property is called strongly connected.

17.When is a graph said to be weakly connected?
When a directed graph is not strongly connected but the underlying graph is connected then the graph is said to be weakly connected.

18.Name the different ways of representing a graph.
The different ways of representing a graph are,
1.        Venn diagram
2.        Nesting parentheses
3.        Table of contents method
4.        Adjacency matrix
5.        Level number format
6.        Adjacency list.

19.Where is topological sort used? Give the expansion of PERT.
Topological sort is used in network analysis with techniques such as PERT
PERT- Program Evaluation and Review technique.

20.What is the use of technological sort?
A topological sort is an ordering of vertices in a directed acyclic graph. Such that if there is a path from v1 to v2 then appears after v1 in the ordering.

21.What are the advantages of using lists for representing graphs?
The advantages of using lists for representing graphs are,
Unpredictable storage requirements
Extensive manipulation of the stored data is required.

22.When is a graph said to be maximal?
A graph is said to be maximal among a collection of graphs. If it is not proper sub graph of any graph in that collection. It need not have the most number of vertices or the most number of edges of any graph in that collection.

23.Define topological order for a graph.
A topological order fro G is an assignment of distinct integers 1,….. x to the vertices of V called their topological numbers, such that for every edge VWe E the topological number of V is less than the topological number of W.

24.Define depth first search forest.
When all the vertices cannot be reached from the starting vertex then a complete traversal of G partitions the vertices into several trees. The entire collection is called the depth first search forest. It is also called as depth first spanning forest.

UNIT V

2 MARKS Q& A

1. Define Data structures
The organization, representation and storage of data are called the data structure. Since all programs operate on data, a data structure plays an important role in deciding the final solution for the problem.
Ex: Stack, Queue, List, Array, etc…

2. Define program
Set of instructions to find the solution to a problem. It is expressed in a programming language in an explicit and unambiguous manner.

3. Define an algorithm (May/June 2005) OR
What is meant by algorithm? (April/May 2004)
Algorithm is a solution to problem independent of programming language. It consists of set of finite steps which, when carried out for a given set of inputs, produce the corresponding output and terminate in a finite time.

4. Mention how similarities among the problems are used in problem solving.
This method is used to find out if a problem of this sort has been already solved and to adapt a similar method in solving the problem. The contribution of experience in the previous problem will help and enhance the method of problem solving for the current problem.

5. Mention some of the problem solving strategies
The most widely strategies are listed below:
1.        Divide and conquer
2.        Binary doubling strategy.
3.        Dynamic programming.

6. What is divide and conquer method?
What is divide and conquer algorithm? Give an example. (Nov/Dec2003)
The basic idea is a divide the problem into several sub problems beyond which cannot be further subdivided. Then solve the sub problems efficiently and join them together to get the solution for the main problem. E.g. Quick sort, Binary Search

7. Where is dynamic programming used?
Dynamic programming is used when the problem is to be solved in a sequence of intermediate steps. It is particularly relevant for many optimization problems. I.e., frequently encountered in operations research.

8. Define top-down design.
Top- down design is a strategy that can be applied to find a solution to a problem from a vague outline to precisely define the algorithm and program implementation by stepwise refinement.

9. Mention the steps involved in solving a problem using top-down design.
The steps involved in solving a problem using top-down design are,
1.        Divide the problem into a set of precisely define sub tasks.
2.        Decide the way of interaction between the sub tasks
3.        Prove the correctness of the solution.

10. What is loop statement?
A loop statement is an iterative construct that is conditionally executed which includes input, output statements, computable expressions and assignments. They improve the efficiency of coding.

11. Mention the parts of a loop.
The construction of a loop includes three points.
1.        Initial condition –to begin the loop to execute
2.        Invariant relation – that must apply after each iteration of the loop
3.        Terminal condition – to terminate the iterative process of the loop.

12. Write down the points to be considered in implementing an algorithm.
1.        Choice of variable names
2.        Use of procedures to emphasize modularity
3.        Debugging of programs
4.        Program verification
5.        Program testing
6.        Documentation of programs

13. Name some problem solving strategies, which are variations of dynamic programming.
Some of the problems solving strategies are,
1.        Greedy strategy
2.        Back tracking
3.        Branch and bound.

14. What is program testing?
Program testing is a process to ensure that a program solves the smallest possible problem, when all the variables have the small value, the biggest problem, unusual cases etc.
15. What is program verification?
Program verification refers to the application of mathematical proof techniques, to verify that the results obtained by the execution of the program with arbitrary inputs are in accord with formally define output specifications.

16. Why do we have to go for program verification?
The cost of software development is extremely high. Also it may cause serious changes on sensitive data if the program doesn’t work correctly. Therefore it is essential to verify whether the program works correctly or not.

17. How will you find the efficiency of an algorithm?
The efficiency consideration for algorithm is in inherently tied in with the design, implementation and analysis of algorithms. The resources used by the algorithms are central processing unit (CPU) time and internal memory. So, the efficiency of the algorithm lies with the economical usage of these resources.

18. How will you verify branches with segments?
To handle the branches that appear in the program segments, it is necessary to set –up and prove verification conditions individually.

19. How can you improve an efficiency of an algorithm in the design phase?
The following are the suggestions to improve the efficiency of an algorithm in designing.
1.        Redundant computations.
2.        Referencing array elements.
3.        Inefficiency due to late termination.
4.        Early detection of desired output conditions.
5.        Trading storage for efficiency gains.

20. What are measures to be considered in analyzing algorithm?
The measures to be considered in analyzing algorithm are,
a. Worst   case behavior       b. Average case behavior.
21. Where can we apply the average and worst case measures?
(April/May 2004)
Both the measures can be applied to the time complexity as well as to the space complexity of an algorithm.

22. Give some applications where the divide and conquer strategy is used
The divide and conquer strategy is much useful in application like sorting, selection and searching algorithms.

23. What is the other name given for top-down design and explain?
Top-down design is also called as stepwise refinement. A project is decomposed into subprojects, and this procedure is repeated until the subtasks have become so simple that an algorithm can formulated as a solution.

24. Why is the selection of data structures more important?
The choice of data structure leads to a simple, transparent and efficient implementation. Inappropriate data structure for a problem will lead to difficulty in solving a problem. Hence the selection of data structure is more important.

25. How do you correct the logical errors in a problem?
By adopting a sequence of steps debugging can be made easier. The best way to avoid logical error in the program is to manually work out the logic of the program before actually developing it.

Previous
Next Post »