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 3^{rd} position
Ex: Delete (52)
Deletes the element
 Findsearching 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.




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 N1 disk from A to
B.
2.
Move disc N from A to C.
3.
Move N1 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 ai1 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 Nonlinear data structure. (OR)
Give two examples of
nonlinear 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 nonlinear 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
subtree and right subtree.(OR)In an mary 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,
Ã¼
Preorder traversal – yields prefix form of expression.
Ã¼
Inorder traversal  yields Infix form of expression.
Ã¼
Post order traversal  yields Postfix form of expression.
7. Define Preorder traversal.
Preorder traversal entains the following steps:
 Process the root node.
 Process the left sub tree.
 Process the right sub tree.
E.g.

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.

9. Define Inorder traversal.
Inorder traversal
entains the following steps:
 Process the left sub tree.
 Process the root node.
 Process the right sub tree.
E.g.

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 fourdifferent cases of pointer manipulations
done in
AVL rotation?
The fourdifferent 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.
 Decisionmaking. E.g.: Eight coins problem.
 Computergames such as chess, tictactoe, checkers
etc., are created and executed using trees.
 Manipulation of arithmetic expression.
 Symbol table construction.
 Syntaxanalysis.
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 [b1]
Example: Hash table
126 buckets with 2
slots Slots slot1 & slot2 Slot 1
Slot
2
0indicates 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 collisionresolution technique used in open addressing
category. In double hashing, we apply a second hash function to x and probe at
a distance of hash_{2 }(x), 2hash_{2 }(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 P_{1} and P_{2
}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 topdown 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 topdown design.
The steps involved in solving a problem using topdown 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 topdown design and explain?
Topdown 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.