UNIT-I

PROBLEM SOLVING
PART-A
1.Write down the definition of data structures?
A data structure is a mathematical or logical way of organizing data in the
memory that consider not only the items stored but also the relationship to each
other and also it is characterized by accessing functions.

2.What is meant by problem solving?

Problem solving is a creative process, which needs systemization and
mechanization.

3. Give few examples for data structures?

Stacks, Queue, Linked list, Trees, graphs

4. What is problem definition phase?

The first step in solving a problem is to understand problem clearly. Hence,
the first phase is the problem definition phase. That is, to extract the task from the
problem statement. If the problem is not understood, then the solution will not be
correct and it may result in wastage of time and effort.

5. Define Algorithm?
Algorithm is a solution to a problem independent of programming
language. It consist 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.

6. 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.

7. 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 adopt a similar method in solving the problem. The contribution of
experience in the previous problem with help and enhance the method of problem
for the current problem.
8. What is working backward from the solution?
When we have a solution to the problem then we have to work backward to
find the starting condition. Even a guess can take us to the starting of the problem.
This is very important to sytematize the investigation to avoid duplication of our
effort.

9. Mention some of the problem solving strategies?

The most widely strategies are listed below
Divide and conquer
Binary doubling strategy
Dynamic programming

10. What is divide and conquer method?

The basic idea is to divide the problem into several sub problems beyond
which cannot be further subdivided. Then solve the sub problems efficiently and
join then together to get the solution for the main problem.

11. What are the features of an efficient algorithm?

Free of ambiguity
Efficient in execution time
Concise and compact
Completeness
Definiteness
Finiteness

12. List down any four applications of data structures?

Compiler design
Operating System
Database Management system
Network analysis

13. What is binary doubling strategy?

The reverse of binary doubling strategy, i.e. combining small problems in to
one is known as binary doubling strategy. This strategy is used to avoid the
generation of intermediate results.

14. 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.
15. 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.

16. Mention the types of bugs that may arise in a program?

The different types of bugs that can arise in a program are
Syntactic error
Semantic error
Logical error

17. What is program testing?

Program testing is process to ensure that a program solves the smallest
possible problem, when all the variables have the same value, the biggest possible
problem, unusual cases etc.

18. 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 defined output Specifications.

19. How will you verify branches with segments?

To handle the branches that appear in the program segments, it is necessary
to set-up and proves verification conditions individually.

20.What is proof of termination?

To prove that a program accomplishes its stated objective in a finite number
of steps is called program termini nation. The prooft of termination is obtained
directly from the properties of the interactive constructs.

PART-B
1.Explain top-down design in detail?
• Definition
• Breaking a problem in to subproblems
• Choice of a suitable data structure
• Constructions of loops
• Establishing initial conditions for loops
• Finding the iterative construct
• Terminations of loops
2. What are the steps taken to improve the efficiency of an algorithm?
• Definition
• Redundant computations
• Referencing array elements
• Inefficiency due to late termination
• Early detection of desired output conditions
• Trading storage for efficiency gains

3. Design an algorithm fro sine function computation. Explain it with an example?

• Algorithm development
• Algorithm description
• Pascal implementation
• Application

4. Design an algorithm for reversing the digit of an integer. Explain it with an

example?
• Algorithm development
• Algorithm description
• Pascal implementation
• Application

5. Design an algorithm for base conversion. Explain it with an example?

• Algorithm development
• Algorithm description
• Pascal implementation
• Application
 UNIT –II
PART-A
1.What is meant by an abstract data type?
An ADT is a set of operation. Abstract data types are mathematical
abstractions.Eg.Objects such as list, set and graph along their operations can be
viewed as ADT's.

2. What are the operations of ADT?

Union, Intersection, size, complement and find are the various operations of
ADT.

3. 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 the successor of ai and ai-1 is the predecessor of ai.

4. What are the various operations done under list ADT?

• Print list
• Insert
• Make empty
• Remove
• Next
• Previous
• Find kth

5. What are the different ways to implement list?

• Simple array implementation of list
• Linked list implementation of list

6. What are the advantages in the array implementation of list?

a) Print list operation can be carried out at the linear time
b) Fint Kth operation takes a constant time

7. What is a linked list?

Linked list is a kind of series of data structures, which are not necessarily
adjacent in memory. Each structure contain the element and a pointer to a record
containing its successor.
8. What is a pointer?
Pointer is a variable, which stores the address of the next element in the list.
Pointer is basically a number.

9. What is a doubly linked list?

In a simple linked list, there will be one pointer named as 'NEXT
POINTER' to point the next element, where as in a doubly linked list, there will be
two pointers one to point the next element and the other to point the previous
element location.

10. Define double circularly linked list?

In a doubly linked list, if the last node or pointer of the list, point to the first
element of the list, then it is a circularly linked list.

11. What is the need for the header?

Header of the linked list is the first element in the list and it stores the
number of elements in the list. It points to the first data element of the list.

12. List three examples that uses linked list?

• Polynomial ADT
• Radix sort
• Multi lists

13. Give some examples for linear data structures?

• Stack
• Queue

14. What is a stack?

Stack is a data structure in which both insertion and deletion occur at one
end only. Stack is maintained with a single pointer to the top of the list of
elements. The other name of stack is Last-in -First-out list.

15. Write postfix from of the expression –A+B-C+D?

A-B+C-D+

16. How do you test for an empty queue?

To test for an empty queue, we have to check whether READ=HEAD
where REAR is a pointer pointing to the last node in a queue and HEAD is a
pointer that pointer to the dummy header. In the case of array implementation of
queue, the condition to be checked for an empty queue is READ<FRONT.
17.What are the postfix and prefix forms of the expression?
A+B*(C-D)/(P-R)
Postfix form: ABCD-*PR-/+
Prefix form: +A/*B-CD-PR

18. Explain the usage of stack in recursive algorithm implementation?

In recursive algorithms, stack data structures is used to store the return
address when a recursive call is
Encountered and also to store the values of all the parameters essential to the
current state of the procedure.

19. Write down the operations that can be done with queue data structure?
Queue is a first - in -first out list. The operations that can be done with
queue are addition and deletion.

20. What is a circular queue?

The queue, which wraps around upon reaching the end of the array is called
as circular queue.

PART-B
1.Explain the linked list implementation of list ADT in Detail?

Definition for linked list

Figure for linked list

Next pointer

Header or dummy node

Various operations
• Explanation
• Example figure
• Coding
2. Explain the cursor implementation of linked list?

Definition for linked list

Figure for linked list

Next pointer

Header or dummy node

Various operations
• Explanation
• Example figure
• Coding
3. Explain the various applications of linked list?

Polynomical ADT
• Operations
• Coding
• Figure

Radix Sort
• Explanation
• Example

Multilist
• Explanation
• Example figure

4. Explain the linked list implementation of stack ADT in detail?

Definition for stack

Stack model

Figure

Pointer-Top

Operations
• Coding
• Example figure

5. Explain the array implementation of queue ADT in detail?

Definition for stack

Stack model

Figure

Pointer-FRONT, REAR

Operations
• Coding
• Example figure
 UNIT-III
PART-A
1. Define non-linear data structure
Data structure which is capable of expressing more complex relationship
than that of physical adjacency is called non-linear data structure.

2. Define tree?
A tree is a data structure, which represents hierarchical relationship between
individual data items.

3. Define leaf?
In a directed tree any node which has out degree o is called a terminal node
or a leaf.

4. What is meant by directed tree?

Directed tree is an acyclic diagraph which has one node called its root with
indegree o whille all other nodes have indegree I.

5. What is a ordered tree?

In a directed tree if the ordering of the nodes at each level is prescribed then
such a tree is called ordered tree.

6. What are the applications of binary tree?

Binary tree is used in data processing.
a. File index schemes
b. Hierarchical database management system

7. What is meant by traversing?

Traversing a tree means processing it in such a way, that each node is
visited only once.

8. What are the different types of traversing?

The different types of traversing are
a. Pre-order traversal-yields prefix from of expression.
b. In-order traversal-yields infix form of expression.
c. Post-order traversal-yields postfix from of expression.

9. What are the two methods of binary tree implementation?

Two methods to implement a binary tree are,
a. Linear representation.
b. Linked representation
10. Define pre-order traversal?
Pre-order traversal entails the following steps;
a. Process the root node
b. Process the left subtree
c. Process the right subtree

11.Define post-order traversal?

Post order traversal entails the following steps;
a. Process the left subtree
b. Process the right subtree
c. Process the root node

12. Define in -order traversal?

In-order traversal entails the following steps;
a. Process the left subtree
b. Process the root node
c. Process the right subtree

13. What is a balance factor in AVL trees?

Balance factor of a node is defined to be the difference between the height
of the node's left subtree and the height of the node's right subtree.

14. What is meant by pivot node?

The node to be inserted travel down the appropriate branch track along the
way of the deepest level node on the branch that has a balance factor of +1 or -1 is
called pivot node.

15. What is the length of the path in a tree?

The length of the path is the number of edges on the path. In a tree there is
exactly one path form the root to each node.

16. Define expression trees?

The leaves of an expression tree are operands such as constants or variable
names and the other nodes contain operators.

17. What is the need for hashing?

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

19. List out the different types of hashing functions?

The different types of hashing functions are,
a. The division method
b. The mind square method
c. The folding method
d. Multiplicative hashing
e. Digit analysic

20. What are the problems in hashing?

a. Collision
b. Overflow

21. What are the problems in hashing?

When two keys compute in to the same location or address in the hash table
through any of the hashing function then it is termed collision.

PART-B
1. Explain the different tree traversals with an application?

In order
• Explanation with an example
• Figure

Preorder
• Explanation with an example
• Figure

Postorder
• Explanation with an example
• Figure

2. Define binary search tree? Explain the various operations with an example?

Definition

Figure for binary search tree

Operations
• Codings
• Explanation
• Example
3. Define AVL trees? Explain the LL, RR, RL, LR case with an example?

Definition

LL, RR, RL, LR case
• Figure
• Example
• Explanation

4. Define priority queue? Explain the basic heap operation with an example?

Definition

Basic operation
• Insert
• Delmin
• Delmax
 Coding
 Explanation
 Example

5. Explain any two techniques to overcome hash collision?

Separate chaining
• Example
• Explanation
• Coding

Open addressing
• Linear probing
• Quadratic probing
 UNIT-IV
PART-A
1.What is meant by sorting?
Ordering the data in an increasing or decreasing fashion according to some
relationship among the data item is called sorting.

2. What are the two main classifications of sorting based on the source of data?
a. Internal sorting
b. External sorting

3. What is meant by external sorting?

External sorting is a process of sorting in which large blocks of data stored
in storage devices are moved to the main memory and then sorted.

4. What is meant by internal sorting?

Internal sorting is a process of sorting the data in the main memory.

5. What are the various factors to be considered in deciding a sorting algorithm?

a. Programming time
b. Execution time of the program
c. Memory needed for program environment

6. What is the main idea behind insertion sort?

The main idea of insertion sort is to insert in the ith pass the ith element in
A (1) A (2)...A (i) in its rightful place.

7. What is the main idea behind insertion sort?

The main idea behind the selection sort is to find the smallest element
among in A (I) A (J+1)...A (n) and then interchange it with a (J). This process is
then repeated for each value of J.

8. What is the basic of shell sort?

Instead of sorting the entire array at once, it is first divide the array into
smaller segments, which are then separately sorted using the insertion sort.

9. What is the other name for shell sort?

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

11. What i the advantage of quick sort?

Quick sort reduces unnecessary swaps and moves an item to a greater
distance, in one move.

12. What is the average efficiency of heap sort?

The average efficiency of heap sort is 0 (n(log2 n)) where, n is the number
of elements sorted.

13. Define segment?

When large blocks of data are to be sorted, only a portion of the block or
file is loaded in the main memory of the computer since, it cannot hold the entire
block. This small portion of file is called a segment.

14. Name some of the external sorting methods?

a. Polyphase merging
b. Oscillation sorting
c. Merge sorting

15. When is a sorting method said to be stable?

A sorting method is said to be stable, it two data items of matching values
are guaranteed to be not rearranged with respect to each other as the algorithm
progresses.

16. Name some simple algorithms used in external sorting?

a. Multiway merge
b. Polyphase merge
c. Replacement selection

17. When can we use insertion sort?

Insertion sort is useful only for small files or very nearly sorted files.

18. How many passes are required fork-way merging?

The number of passes required using k-way merging is [log k (n/m)]
because the N H S get k times as large in each pass.
19. Define max heap?
A heap in which the parent has a larger key than the child's is called a max
heap.

20. Define min heap?

A heap in which the parent has a smaller key than the child's is called a min
heap.

PART-B
1.Explain heap sort with an example?
• Explanation
• Example
• Figure
• Coding

2. Explain quick sort with an example?

• Explanation
• Example
• Figure
• Coding

3. Explain quick sort with an example?

• Explanation
• Example
• Figure
• Coding

4. Explain any four external sorting techniques with example?

• Explanation
• Example
• Figure
• Coding

5. Explain shell sort with an example?

• Explanation
• Example
• Figure
• Coding
 PART-B

1.Explain heap sort with an example?

Explanation

Example

Figure

Coding

2. Explain quick sort with an example?

Explanation

Example

Figure

Coding

3. Explain merge sort with an example?

Explanation

Example

Figure

Coding

4. Explain any four external sorting techniques with example?

Explanation

Example

Figure

Coding

5. Explain shell sort with an example?

Explanation

Example

Figure

Coding
 UNIT-V
PART-A
1.Define Graph?
A graph G consist of a nonempty set V which is a set of nodes of the graph,
a set E which is the set of edges of the graph, and a mapping from the set for edge
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 and edge x∈E is associated with a pair of nodes
(u,v) where u, v ∈ V, then we say that the edge x connects the nodes u and v.

3. What is a directed graph?

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

4. What is a undirected graph?

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

5. What is a loop?
An edge of a graph which connects to itself is called a loop or sling.

6.What is a simple graph?

A simple graph is a graph, which has not more than one edge between a
pair of nodes than such a graph is called a simple graph.

7. What is a weighted graph?

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

8. Define out degree of a graph?

In a directed graph, for any node v, the number of edges which have v as
their initial node is called the out degree of the node v.

9. Define indegree of a graph?

In a directed graph, for any node v, the number of edges which have v as
their terminal node is called the indegree of the node v.

10. Define path in a graph?

The path in a graph is the route taken to reach terminal node from a starting
node.
11.What is a simple path?
A path in a diagram in which the edges are distinct is called a simple path.
It is also called as edge simple.

12. What is a cycle or a circuit?

A path which originates and ends in the same node is called a cycle or
circuit.

13. What is an acyclic graph?

A simple diagram which does not have any cycles is called an acyclic
graph.

14. What is meant by strongly connected in a graph?

An undirected graph is connected, if there is a path from every vertex to
every other vertex. A directed graph with this property is called strongly
connected.

15. 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.

16. Name the different ways of representing a graph?

a. Adjacency matrix
b. Adjacency list

17. What is an undirected acyclic graph?

When every edge in an acyclic graph is undirected, it is called an undirected
acyclic graph. It is also called as undirected forest.

18. What are the two traversal strategies used in traversing a graph?
a. Breadth first search
b. Depth first search

19. What is a minimum spanning tree?

A minimum spanning tree of an undirected graph G is a tree formed from
graph edges that connects all the vertices of G at the lowest total cost.

20. What is NP?

NP is the class of decision problems for which a given proposed solution
for a given input can be checked quickly to see if it is really a solution.
 PART-B
1.Explain the various representation of graph with example in detail?

Adjacency matrix
• Figure
• Explanation
• Table

Adjacency list
• Figure
• Explanation
• Table

2. Define topological sort? Explain with an example?

Definition

Explanation

Example

Table

Coding

3. Explain Dijkstra's algorithm with an example?

Explanation

Example

Graph

Table

Coding

4.Explain Prim's algorithm with an example?

Explanation

Example

Graph

Table

Coding

5. Explain Krushal's algorithm with an example?

Explanation

Example

Graph

Table

Coding