1
NOORUL ISLAM COLLEGE OF ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
CS1151 DATA STRUCTURES
TWO MARKS QUESTIONS AND ANSWERS
UNIT I
1.What is an Algorithm?
An algorithm is clearly specified set of simple instructions to be followed to
solve a problem. The algorithm forms a base for program.
2.What are the properties of an Algorithm?
Takes zero or more inputs
Results in one or more outputs
All operations are carried out in a finite time
Efficient and flexible
Should be concise and compact to facilitate verification of their
correctness.
3.Define Program?
It is an instruction and it is written according to the instructions, which is given
in the algorithm.
4. What is Complexity analysis?
It is the analysis of the amount of memory and time an algorithm requires to
completion.
There are two types of Complexity
Space Complexity and Time Complexity
5. Explain the performance analysis of the algorithm?
The analysis of the performance of an algorithm based on specification is
called performance analysis. It is loosely divided into
a. Priori estimates
b. Posterior Testing
6. Explain Space complexity?
Space complexity of an algorithm is the amount of memory it needs to run to
completion.
7. Explain Time complexity?
Time complexity is the amount of computer time an algorithm requires to run
to completion.
8. List out the components that are used for space complexity?
a. Instruction Space
b. Environment Stack
c. Data Space.
9. What do asymptotic notation means?
Asymptotic notations are terminology that is introduced to enable us to make
meaningful statements about the time and space complexity of an algorithm.
The different notations are
Big – Oh notation
Omega notation
Theta notation.
10. Define Efficiency of an algorithm?
It denotes the rate at which an algorithm solves a problem of size n. It is
measured by the amount of resources it uses, the time and the space.
2
11. Define Worst case of an algorithm?
It is the longest time that an algorithm will use over all instances of size n for a
given problem to produce the result.
12. Define Best case of an algorithm?
It is the shortest time that an algorithm will use over all instances of size n for
a given problem to produce the result.
13. Define average case an algorithm?
It is the average time that an algorithm will use over all instances of size n for
a given problem to produce the result.
14. Define Divide and Conquer algorithm?
Divide and Conquer algorithm is based on dividing the problem to be solved
into several, smaller sub instances, solving them independently and then combining
the sub instances solutions so as to yield a solution for the original instance.
15. Mention some application of Divide and Conquer algorithm?
a. Quick Sort
b. Merge Sort
c. Binary search
16. Define dynamic programming algorithm?
Dynamic programming algorithm is a general class of algorithms which solve
problems by solving smaller versions of the problem, saving the solutions to the
small problems and then combining them to solve the larger problems.
17. Mention application of dynamic programming algorithm?
Efficient Fibonocci number computation
Chained matrix multiplication.
Longest common subsequence problem
18. State the various steps in algorithm?
Devising the algorithm
Validating the algorithm
Expressing the algorithm
Determination of complexity of the algorithm
19. Define algorithm paradigms space of an algorithm?
Algorithmic paradigms are defined as the general approach to design and
construct efficient solutions to problems.
20. Mention the various spaces utilized by a program?
a. A fixed amount of memory occupied by the space for the program code and
space occupied by the variables used in the program.
b. A variable amount of memory occupied by the variable whose size is
dependent on the problem being solved. This space increases or decreases
depending upon whether the program uses iterative or recursive procedures.
UNIT II
21. Define ADT (Abstract Data Type)?
An ADT is a mathematical model with a collection of operations defined
on that model.
22. Define Linear data structure?
Linear data structures are data structures having a linear relationship between
its adjacent elements. Eg. Linked List.
23. Define Non Linear data structure?
3
Non Linear data structures are data structures don’t have a linear relationship
between its adjacent elements, but had the hierarchical relationship. Ex. Graph,
Tree.
24. What are different types of Linked List?
Single linked list
Double linked list
Circular linked list
25 What are different types of Circular Linked List?
Circular Single linked list
Circular double linked list
26 List the basic operations carried out in a linked list?
a. Creation of list
b. Insertion of list
c. Deletion of list
d. Modification of list
e. Traversal of List
27 Define a stack?
Stack is an ordered collection of elements in which insertions and deletions
are restricted to one end. The end from which elements are added and /or removed
is referred to as top of the stack. Stacks are also referred as “piles” and “push-down
lists”.
28 Define a queue?
Queue is an ordered collection of elements in which insertions and deletions
are restricted to one end. The end from which elements are added and / or removed
is referred to as the rear end and the end from which deletions are made is referred
to as front end.
29 Difference between Arrays and Linked List?
Arrays Linked List
Size of any array is fixed Size of list is variable
It is necessary to specify the number of
elements during declaration
It is not necessary to specify the
number of elements during declaration
Insertion and deletions are difficult and
costly
Insertions and deletions are done in
less time
It occupies less memory than a linked
list
It occupies more memory
Coding is easy Careful coding is needed to avoid
memory errors.
30 What is single linked list?
It is a linear data structure which consists a pointer field that points to the
address of its next node(successor) and the data item.
31 Define HEAD pointer and NULL pointer?
HEAD It contains the address of the first node in that list.
NULL It indicates the end of the list structure.
32 What is meant by dummy header?
It is ahead node in the linked list before the actual data nodes.
39. Define double linked list?
It is linear data structure which consists of two links or pointer fields
Next pointer points to the address of the next(successor) node.
Previous pointer points to the address of the previous(predecessor) node.
4
33 Define Circular linked list?
It is a list structure in which last node points to the first node there is no
null value.
34 Write operations that can be done on stack?
PUSH and POP
35 Mention applications of stack?
a. Expression Parsing
b. Evaluation of Postfix
c. Balancing parenthesis
d. Tower of Hanoi
e. Reversing a string
36 Define Infix, prefix and postfix notations?
Infix operators are placed in between the operands
Prefix operators are placed before the operands
Postfix Operators are placed after the operands.
37 What are the conditions that followed in the array implementation of queue?
Condition Situation
REARltFRONT EMPTY QUEUE
FRONT==REAR ONE ENTRY QUEUE
REAR==ARRAY SIZE FULL QUEUE
38 What are the conditions that could be followed in a linked list implementations of
queue?
Condition Situation
REAR==HEAD EMPTY QUEUE
REAR==LINK(HEAD) ONE ENTRY QUEUE
NO FREE SPACE TO INSERT FULL QUEUE
39 What are the conditions that could be followed in a linked list implementations of
queue?
Condition Situation
(REAR MOD ARRAY SIZE +1
)==FRONT
EMPTY QUEUE
(REAR MOD ARRAY SIZE +2
)==FRONT
FULL QUEUE
FRONT==REAR ONE ENTRY QUEUE
40 Define Circular queue?
A circular queue allows the queue to wrap around upon reaching the end of
the array.
UNIT 3
41 Define tree?
Trees are non-liner data structure, which is used to store data items in a
shorted sequence. It represents any hierarchical relationship between any data
Item. It is a collection of nodes, which has a distinguish node called the root and zero
or more non-empty sub trees T1, T2,….Tk. each of which are connected by a
directed edge from the root.
42 Define Height of tree?
5
The height of n is the length of the longest path from root to a leaf. Thus
all leaves have height zero. The height of a tree is equal to a height of a root.
43 Define Depth of tree?
For any node n, the depth of n is the length of the unique path from the
root to node n. Thus for a root the depth is always zero.
44 Define Degree of a node?
It is the number of sub trees of a node in a given tree.
45 define Degree of a tree?
It is the maximum degree of a node in a given tree.
46.Define Terminal node or leaf?
Nodes with no children are known as leaves. A leaf will always have
degree zero and is also called as terminal node.
47. Define Non-terminal node?
Any node except the root node whose degree is a non-zero value is
called as a non-terminal node. Non-terminal nodes are the intermediate nodes in
traversing the given tree from its root node to the terminal node.
48.Define sibling?
Nodes with the same parent are called siblings.
49.Define binary tree?
A Binary tree is a finite set of data items which is either empty or
consists of a single item called root and two disjoin binary trees called left sub tree
max degree of any node is two.
50.Define expression tree?
Expression tree is also a binary tree in which the leafs terminal
nodes or operands and non-terminal intermediate nodes are operators used for
traversal.
51.Construction of expression trees?
1.convert the given infix expression into postfix notation
2. Create a stack and read each character of the expression and
push into the stack, if operands are encountered.
3.when an operator is encountered pop 2 values from the stack.
From a tree using the operator.
52.Define lazy deletion?
When an element is to be deleted it is left in the tree itself and
marked a s being deleted. This is called as lazy deletion and is an efficient
procedure if duplicate keys are present in the binary search tree, because the field
that keeps count of the frequency of appearance of the element can be
decremented of the element can be decremented.
53.Define AVL tree?
AVL tree also called as height balanced tree .It is a height
balanced tree in which every node will have a balancing factor of –1,0,1
Balancing factor
Balancing factor of a node is given by the difference between the
height of the left sub tree and the height of the right sub tree.
54.what are the various operation performed in the binary search tree ?
1.insertion
2.deletion
3.find
4.find min
5.find max
6
55. What are the various transformation performed in AVL tree?
1.single rotation
- single L rotation
- single R rotation
2.double rotation
-LR rotation
-RL rotation
56.General idea of hashing and what is the use of hashing function?
A hash table similar to an array of some fixes size-containing keys.
The keys specified here might be either integer or strings, the size of the table is
taken as table size or the keys are mapped on to some number on the hash table
from a range of 0 to table size
57.what is priority queue?
A priority queue is a data structure that allows at least the following
two operations: insert which does the obvious thing; and Deletemin, which finds,
returns, and removes the minimum element in the priority queue. The Insert
operation is the equivalent of Enqueue
58.Applecation of priority queues?
1.for scheduling purpose in operating system
2.used for external sorting
3.important for the implementation of greedy algorithm, which operate
by repeatedly finding a minimum.
59.what are the main properties of a binary heap?
1.structure property
2.heaporder property
60. Define tree traversal and mention the type of traversals?
Visiting of each and every node in the tree exactly is called as tree
traversal
Three types of tree traversal
1.inorder traversal
2.preoder traversal
3.postorder traversal.
UNIT- 4
61. what is insertion sort? How many passes are required for the elements to be sorted ?
one of the simplest sorting algorithms is the insertion sort. Insertion sort
consist of N-1 passes . For pass P=1 through N-1 , insertion sort ensures that the
elements in positions 0 through P-1 are in sorted order .It makes use of the fact that
elements in position 0 through P-1 are already known to be in sorted order .
62. Write the function in C for insertion sort ?
void
insertionsort(elementtype A[ ] , int N)
{
int j, p;
elementtype tmp;
for(p=1 ; p{
tmp = a[ p] ;
for ( j=p ; j>0 && a [ j -1 ] >tmp ;j--)
a [ j ]=a [j-1 ] ;
7
a [ j ] = tmp ;
}
}
63. Who invented shellsort ? define it ?
Shellsort was invented by Donald Shell . It works by comparing element that are
distant . The distance between the comparisons decreases as the algorithm runs
until the last phase in which adjacent elements are compared . Hence it is
referred as diminishing increment sort.
64. write the function in c for shellsort?
Void
Shellsort(Elementtype A[ ],int N)
{
int i , j , increment ;
elementtype tmp ;
for(elementtype=N / 2;increment > 0;increment / = 2)
For( i= increment ; i{
tmp=A[ ];
for( j=I; j>=increment; j - =increment)
if(tmp< A[ ]=A[j – increment];
A[ j ]=A[ j – increment];
Else
Break;
A[ j ]=tmp;
}
}
65. what is maxheap?
If we want the elements in the more typical increasing sorted
order,we can change the ordering property so that the parent has a larger key than the
child.it is called max heap
66. What are the two stages for heap sort?
Stage 1 : Construction of heap
Stage 2 : Root deletion N-1 times
67. What is divide and conquer strategy ?
In divide and conquer strategy the given problem is divided into smaller
Problems and solved recursively. The conquering phase consists of patching together
the answers . Divide – and – conquer is a very powerful use of recursion that we will see
many times.
68 . Differentiate between merge sort and quick sort ?
mergesort quicksort
1. Divide and conquer stategy Divide and conquer strategy
2. Partition by position Partition by value
69.Mention some methods for choosing the pivot element in quicksort ?
1. choosing first element
2. Generate random number
3. Median of three
70. What are the three cases that arise during the left to right scan in quicksort?
1. I and j cross each other
2. I and j do not cross each other
8
3. I and j points the same position
71. What is the need of external sorting?
External sorting is required where the input is too large to fit into
memory. So external sorting Is necessary where the program is too large
72. Define two way merge ?
It is a basic external sorting in which there are two inputs and two
outputs tapes .
73. Define multi way merge ?
If we have extra tapes then we can expect to reduce the number of
passes required to sort our input. We do this by extending two way merge to a k-way
merge.
74. Define polyphase merge ?
The k-way merging strategy requires the use of 2 k tapes. This could
be prohibitive for some applications . It is possible to get by with only k+1 tapes.
75. What is replacement selection ?
We read as many records as possible and sort them . writing the result
to some tapes. This seems like the best approach possible until one realizes that as
soon as the first record is written to a output tape the memory it used becomes available
for another record . if the next record on the input tape is larger than the record we have
just output then it can be included in the item . using this we can give algorithm. This is
called replacement selection.
76. What is sorting ?
Sorting is the process of arranging the given items in a logical order.
Sorting is an example where the analysis can be precisely performed.
77. What is mergesort?
The mergesort algorithm is a classic divide&conquer strategy.the
problem is divided into two arrays and merged into single array
78. What are the properties involved in heapsort?
1. structure property
2. heap order property
79. Define articulation points.
If a graph is not biconnected,the vertices whose removal would
disconnect the graph are known as articulation points.
80. Give some example of NP complete problems.
i. Hamiltonian circuit.
ii. Travelling salesmen problems
iii. Longest path problems
iv. Bin packing
v. Knapsack problem
vi. Graph colouring problem
UNIT V
81. What is a graph?
A graph consists of a set of vertices V and set of edges E which is
mathematically represented as G=(V,E).Each edge in a pair(V,W) where V,W,
belongs to E ,edges are sometimes referred to as arcs.
82. What are Directed graphs?
If a pair of vertices for any edge is ordered, then that graph is called as
Digraph or directed graph.
9
83. Define Path.
A path in a graph is a sequence of vertices w1,w2w,3,wN such that
Wi,Wi+1 belongs to E for a value 1<=I<=N. The length of such a path is the
number
Edges on the path,which is equal to n-1.
84. Define Cycle.
A cycle is a path in which the first and last vertices are the same.
85. Define Acyclic graph.
A graph with no cycles is called Acyclic graph.A directed graph with no
Edges is called as a directed Acyclic graph (or) DAG.DAGS are used for
compiler
Optimization process.
86. Define Connected 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 as strongly
connected
Connected graph.If a directed graph is not strongly connected but the underline
graph
Without direction is connected it is called as a weakly connected graph.
87. What are the conditions for a graph to become a tree?
A graph is a tree if it has two properties.
i. If it is a connected graph.
ii. There should not be any cycles in the graph.
88. Define a Weighted Graph.
A graph is said to be a weighted graph if every edge in the graph is
Assigned some weight or value.The weight of the edge is a positive value that
Represents the cost of moving the edge or the distance between two vertices.
89. Give the types of representation of graphs.
1.Adjacency matrix
2.Adjacency linked list
90. What is a minimum spanning tree?
A minimum spanning tree of an undirected graph G is a tree formed
from
Graph edges.that connect all the vertices of G at lowest total cost.
91. Explain about Adjacency Matrix
Adjacency matrix consists of a n*n matrix where n is the no. of vertices
present
In the graph,which consists of values either 0 or 1.
92. Explain about Adjacency linked list.
It consists of a table with the no. of entries for each vertex for each entry a
linked
List is inititated for the vertices adjacent to the corresponding table entry.
93. What is a single souce shortest path problem?
Given as an input,a weighted graph,G= and a distinguished vertex ‘S’
as the source vertex.Single source shortest path problem finds the shortest
weighted path from s to every other vertex in G.
94. Explain about Unweighted shortest path.
10
Single source shortest path finds the shortest path from the source to each
and every vertex present in a unweighted graph.Here no cost is associated
with the edges connecting the vertices.Always unit cost is associated with
each edge.
95. Explain about Weighted shortest path
Single source shortest path finds the shortest path from the source to each
and
Every vertex present In a weighted graph.In a weighted graph some cost is
always
Associated with the edges connecting the vertices.
96. What are the methods to solve minimum spanning tree?
a) Prim’s algorithm
b) Kruskal’s algorithm
97. Explain briefly about Prim’s algorithm
Prim’s algorithm creates the spanning tree in various stages.At each stage,a
node is picked as the root and an edge is added and thus the associated
vertex along with it.
98. Define a depth first spanning tree.
The tree that is formulated by depth first search on a graph is called as depth
first spanning tree.The depth first spanning tree consists of tree edges and
back edges.
99. What is a tree edge?
Traversal from one vertex to the next vertex in a graph is called as a tree
edge.
100. What is a back edge?
The possibility of reaching an already marked vertex is indicated by a dashed
line,in a graph is called as back edge.
KEYWORDS:DATA STRUCTURES,DATA STRUCTURES QUESTION PAPER,ANNA UNIVERSITY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS
NOORUL ISLAM COLLEGE OF ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
CS1151 DATA STRUCTURES
TWO MARKS QUESTIONS AND ANSWERS
UNIT I
1.What is an Algorithm?
An algorithm is clearly specified set of simple instructions to be followed to
solve a problem. The algorithm forms a base for program.
2.What are the properties of an Algorithm?
Takes zero or more inputs
Results in one or more outputs
All operations are carried out in a finite time
Efficient and flexible
Should be concise and compact to facilitate verification of their
correctness.
3.Define Program?
It is an instruction and it is written according to the instructions, which is given
in the algorithm.
4. What is Complexity analysis?
It is the analysis of the amount of memory and time an algorithm requires to
completion.
There are two types of Complexity
Space Complexity and Time Complexity
5. Explain the performance analysis of the algorithm?
The analysis of the performance of an algorithm based on specification is
called performance analysis. It is loosely divided into
a. Priori estimates
b. Posterior Testing
6. Explain Space complexity?
Space complexity of an algorithm is the amount of memory it needs to run to
completion.
7. Explain Time complexity?
Time complexity is the amount of computer time an algorithm requires to run
to completion.
8. List out the components that are used for space complexity?
a. Instruction Space
b. Environment Stack
c. Data Space.
9. What do asymptotic notation means?
Asymptotic notations are terminology that is introduced to enable us to make
meaningful statements about the time and space complexity of an algorithm.
The different notations are
Big – Oh notation
Omega notation
Theta notation.
10. Define Efficiency of an algorithm?
It denotes the rate at which an algorithm solves a problem of size n. It is
measured by the amount of resources it uses, the time and the space.
2
11. Define Worst case of an algorithm?
It is the longest time that an algorithm will use over all instances of size n for a
given problem to produce the result.
12. Define Best case of an algorithm?
It is the shortest time that an algorithm will use over all instances of size n for
a given problem to produce the result.
13. Define average case an algorithm?
It is the average time that an algorithm will use over all instances of size n for
a given problem to produce the result.
14. Define Divide and Conquer algorithm?
Divide and Conquer algorithm is based on dividing the problem to be solved
into several, smaller sub instances, solving them independently and then combining
the sub instances solutions so as to yield a solution for the original instance.
15. Mention some application of Divide and Conquer algorithm?
a. Quick Sort
b. Merge Sort
c. Binary search
16. Define dynamic programming algorithm?
Dynamic programming algorithm is a general class of algorithms which solve
problems by solving smaller versions of the problem, saving the solutions to the
small problems and then combining them to solve the larger problems.
17. Mention application of dynamic programming algorithm?
Efficient Fibonocci number computation
Chained matrix multiplication.
Longest common subsequence problem
18. State the various steps in algorithm?
Devising the algorithm
Validating the algorithm
Expressing the algorithm
Determination of complexity of the algorithm
19. Define algorithm paradigms space of an algorithm?
Algorithmic paradigms are defined as the general approach to design and
construct efficient solutions to problems.
20. Mention the various spaces utilized by a program?
a. A fixed amount of memory occupied by the space for the program code and
space occupied by the variables used in the program.
b. A variable amount of memory occupied by the variable whose size is
dependent on the problem being solved. This space increases or decreases
depending upon whether the program uses iterative or recursive procedures.
UNIT II
21. Define ADT (Abstract Data Type)?
An ADT is a mathematical model with a collection of operations defined
on that model.
22. Define Linear data structure?
Linear data structures are data structures having a linear relationship between
its adjacent elements. Eg. Linked List.
23. Define Non Linear data structure?
3
Non Linear data structures are data structures don’t have a linear relationship
between its adjacent elements, but had the hierarchical relationship. Ex. Graph,
Tree.
24. What are different types of Linked List?
Single linked list
Double linked list
Circular linked list
25 What are different types of Circular Linked List?
Circular Single linked list
Circular double linked list
26 List the basic operations carried out in a linked list?
a. Creation of list
b. Insertion of list
c. Deletion of list
d. Modification of list
e. Traversal of List
27 Define a stack?
Stack is an ordered collection of elements in which insertions and deletions
are restricted to one end. The end from which elements are added and /or removed
is referred to as top of the stack. Stacks are also referred as “piles” and “push-down
lists”.
28 Define a queue?
Queue is an ordered collection of elements in which insertions and deletions
are restricted to one end. The end from which elements are added and / or removed
is referred to as the rear end and the end from which deletions are made is referred
to as front end.
29 Difference between Arrays and Linked List?
Arrays Linked List
Size of any array is fixed Size of list is variable
It is necessary to specify the number of
elements during declaration
It is not necessary to specify the
number of elements during declaration
Insertion and deletions are difficult and
costly
Insertions and deletions are done in
less time
It occupies less memory than a linked
list
It occupies more memory
Coding is easy Careful coding is needed to avoid
memory errors.
30 What is single linked list?
It is a linear data structure which consists a pointer field that points to the
address of its next node(successor) and the data item.
31 Define HEAD pointer and NULL pointer?
HEAD It contains the address of the first node in that list.
NULL It indicates the end of the list structure.
32 What is meant by dummy header?
It is ahead node in the linked list before the actual data nodes.
39. Define double linked list?
It is linear data structure which consists of two links or pointer fields
Next pointer points to the address of the next(successor) node.
Previous pointer points to the address of the previous(predecessor) node.
4
33 Define Circular linked list?
It is a list structure in which last node points to the first node there is no
null value.
34 Write operations that can be done on stack?
PUSH and POP
35 Mention applications of stack?
a. Expression Parsing
b. Evaluation of Postfix
c. Balancing parenthesis
d. Tower of Hanoi
e. Reversing a string
36 Define Infix, prefix and postfix notations?
Infix operators are placed in between the operands
Prefix operators are placed before the operands
Postfix Operators are placed after the operands.
37 What are the conditions that followed in the array implementation of queue?
Condition Situation
REARltFRONT EMPTY QUEUE
FRONT==REAR ONE ENTRY QUEUE
REAR==ARRAY SIZE FULL QUEUE
38 What are the conditions that could be followed in a linked list implementations of
queue?
Condition Situation
REAR==HEAD EMPTY QUEUE
REAR==LINK(HEAD) ONE ENTRY QUEUE
NO FREE SPACE TO INSERT FULL QUEUE
39 What are the conditions that could be followed in a linked list implementations of
queue?
Condition Situation
(REAR MOD ARRAY SIZE +1
)==FRONT
EMPTY QUEUE
(REAR MOD ARRAY SIZE +2
)==FRONT
FULL QUEUE
FRONT==REAR ONE ENTRY QUEUE
40 Define Circular queue?
A circular queue allows the queue to wrap around upon reaching the end of
the array.
UNIT 3
41 Define tree?
Trees are non-liner data structure, which is used to store data items in a
shorted sequence. It represents any hierarchical relationship between any data
Item. It is a collection of nodes, which has a distinguish node called the root and zero
or more non-empty sub trees T1, T2,….Tk. each of which are connected by a
directed edge from the root.
42 Define Height of tree?
5
The height of n is the length of the longest path from root to a leaf. Thus
all leaves have height zero. The height of a tree is equal to a height of a root.
43 Define Depth of tree?
For any node n, the depth of n is the length of the unique path from the
root to node n. Thus for a root the depth is always zero.
44 Define Degree of a node?
It is the number of sub trees of a node in a given tree.
45 define Degree of a tree?
It is the maximum degree of a node in a given tree.
46.Define Terminal node or leaf?
Nodes with no children are known as leaves. A leaf will always have
degree zero and is also called as terminal node.
47. Define Non-terminal node?
Any node except the root node whose degree is a non-zero value is
called as a non-terminal node. Non-terminal nodes are the intermediate nodes in
traversing the given tree from its root node to the terminal node.
48.Define sibling?
Nodes with the same parent are called siblings.
49.Define binary tree?
A Binary tree is a finite set of data items which is either empty or
consists of a single item called root and two disjoin binary trees called left sub tree
max degree of any node is two.
50.Define expression tree?
Expression tree is also a binary tree in which the leafs terminal
nodes or operands and non-terminal intermediate nodes are operators used for
traversal.
51.Construction of expression trees?
1.convert the given infix expression into postfix notation
2. Create a stack and read each character of the expression and
push into the stack, if operands are encountered.
3.when an operator is encountered pop 2 values from the stack.
From a tree using the operator.
52.Define lazy deletion?
When an element is to be deleted it is left in the tree itself and
marked a s being deleted. This is called as lazy deletion and is an efficient
procedure if duplicate keys are present in the binary search tree, because the field
that keeps count of the frequency of appearance of the element can be
decremented of the element can be decremented.
53.Define AVL tree?
AVL tree also called as height balanced tree .It is a height
balanced tree in which every node will have a balancing factor of –1,0,1
Balancing factor
Balancing factor of a node is given by the difference between the
height of the left sub tree and the height of the right sub tree.
54.what are the various operation performed in the binary search tree ?
1.insertion
2.deletion
3.find
4.find min
5.find max
6
55. What are the various transformation performed in AVL tree?
1.single rotation
- single L rotation
- single R rotation
2.double rotation
-LR rotation
-RL rotation
56.General idea of hashing and what is the use of hashing function?
A hash table similar to an array of some fixes size-containing keys.
The keys specified here might be either integer or strings, the size of the table is
taken as table size or the keys are mapped on to some number on the hash table
from a range of 0 to table size
57.what is priority queue?
A priority queue is a data structure that allows at least the following
two operations: insert which does the obvious thing; and Deletemin, which finds,
returns, and removes the minimum element in the priority queue. The Insert
operation is the equivalent of Enqueue
58.Applecation of priority queues?
1.for scheduling purpose in operating system
2.used for external sorting
3.important for the implementation of greedy algorithm, which operate
by repeatedly finding a minimum.
59.what are the main properties of a binary heap?
1.structure property
2.heaporder property
60. Define tree traversal and mention the type of traversals?
Visiting of each and every node in the tree exactly is called as tree
traversal
Three types of tree traversal
1.inorder traversal
2.preoder traversal
3.postorder traversal.
UNIT- 4
61. what is insertion sort? How many passes are required for the elements to be sorted ?
one of the simplest sorting algorithms is the insertion sort. Insertion sort
consist of N-1 passes . For pass P=1 through N-1 , insertion sort ensures that the
elements in positions 0 through P-1 are in sorted order .It makes use of the fact that
elements in position 0 through P-1 are already known to be in sorted order .
62. Write the function in C for insertion sort ?
void
insertionsort(elementtype A[ ] , int N)
{
int j, p;
elementtype tmp;
for(p=1 ; p
tmp = a[ p] ;
for ( j=p ; j>0 && a [ j -1 ] >tmp ;j--)
a [ j ]=a [j-1 ] ;
7
a [ j ] = tmp ;
}
}
63. Who invented shellsort ? define it ?
Shellsort was invented by Donald Shell . It works by comparing element that are
distant . The distance between the comparisons decreases as the algorithm runs
until the last phase in which adjacent elements are compared . Hence it is
referred as diminishing increment sort.
64. write the function in c for shellsort?
Void
Shellsort(Elementtype A[ ],int N)
{
int i , j , increment ;
elementtype tmp ;
for(elementtype=N / 2;increment > 0;increment / = 2)
For( i= increment ; i
tmp=A[ ];
for( j=I; j>=increment; j - =increment)
if(tmp< A[ ]=A[j – increment];
A[ j ]=A[ j – increment];
Else
Break;
A[ j ]=tmp;
}
}
65. what is maxheap?
If we want the elements in the more typical increasing sorted
order,we can change the ordering property so that the parent has a larger key than the
child.it is called max heap
66. What are the two stages for heap sort?
Stage 1 : Construction of heap
Stage 2 : Root deletion N-1 times
67. What is divide and conquer strategy ?
In divide and conquer strategy the given problem is divided into smaller
Problems and solved recursively. The conquering phase consists of patching together
the answers . Divide – and – conquer is a very powerful use of recursion that we will see
many times.
68 . Differentiate between merge sort and quick sort ?
mergesort quicksort
1. Divide and conquer stategy Divide and conquer strategy
2. Partition by position Partition by value
69.Mention some methods for choosing the pivot element in quicksort ?
1. choosing first element
2. Generate random number
3. Median of three
70. What are the three cases that arise during the left to right scan in quicksort?
1. I and j cross each other
2. I and j do not cross each other
8
3. I and j points the same position
71. What is the need of external sorting?
External sorting is required where the input is too large to fit into
memory. So external sorting Is necessary where the program is too large
72. Define two way merge ?
It is a basic external sorting in which there are two inputs and two
outputs tapes .
73. Define multi way merge ?
If we have extra tapes then we can expect to reduce the number of
passes required to sort our input. We do this by extending two way merge to a k-way
merge.
74. Define polyphase merge ?
The k-way merging strategy requires the use of 2 k tapes. This could
be prohibitive for some applications . It is possible to get by with only k+1 tapes.
75. What is replacement selection ?
We read as many records as possible and sort them . writing the result
to some tapes. This seems like the best approach possible until one realizes that as
soon as the first record is written to a output tape the memory it used becomes available
for another record . if the next record on the input tape is larger than the record we have
just output then it can be included in the item . using this we can give algorithm. This is
called replacement selection.
76. What is sorting ?
Sorting is the process of arranging the given items in a logical order.
Sorting is an example where the analysis can be precisely performed.
77. What is mergesort?
The mergesort algorithm is a classic divide&conquer strategy.the
problem is divided into two arrays and merged into single array
78. What are the properties involved in heapsort?
1. structure property
2. heap order property
79. Define articulation points.
If a graph is not biconnected,the vertices whose removal would
disconnect the graph are known as articulation points.
80. Give some example of NP complete problems.
i. Hamiltonian circuit.
ii. Travelling salesmen problems
iii. Longest path problems
iv. Bin packing
v. Knapsack problem
vi. Graph colouring problem
UNIT V
81. What is a graph?
A graph consists of a set of vertices V and set of edges E which is
mathematically represented as G=(V,E).Each edge in a pair(V,W) where V,W,
belongs to E ,edges are sometimes referred to as arcs.
82. What are Directed graphs?
If a pair of vertices for any edge is ordered, then that graph is called as
Digraph or directed graph.
9
83. Define Path.
A path in a graph is a sequence of vertices w1,w2w,3,wN such that
Wi,Wi+1 belongs to E for a value 1<=I<=N. The length of such a path is the
number
Edges on the path,which is equal to n-1.
84. Define Cycle.
A cycle is a path in which the first and last vertices are the same.
85. Define Acyclic graph.
A graph with no cycles is called Acyclic graph.A directed graph with no
Edges is called as a directed Acyclic graph (or) DAG.DAGS are used for
compiler
Optimization process.
86. Define Connected 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 as strongly
connected
Connected graph.If a directed graph is not strongly connected but the underline
graph
Without direction is connected it is called as a weakly connected graph.
87. What are the conditions for a graph to become a tree?
A graph is a tree if it has two properties.
i. If it is a connected graph.
ii. There should not be any cycles in the graph.
88. Define a Weighted Graph.
A graph is said to be a weighted graph if every edge in the graph is
Assigned some weight or value.The weight of the edge is a positive value that
Represents the cost of moving the edge or the distance between two vertices.
89. Give the types of representation of graphs.
1.Adjacency matrix
2.Adjacency linked list
90. What is a minimum spanning tree?
A minimum spanning tree of an undirected graph G is a tree formed
from
Graph edges.that connect all the vertices of G at lowest total cost.
91. Explain about Adjacency Matrix
Adjacency matrix consists of a n*n matrix where n is the no. of vertices
present
In the graph,which consists of values either 0 or 1.
92. Explain about Adjacency linked list.
It consists of a table with the no. of entries for each vertex for each entry a
linked
List is inititated for the vertices adjacent to the corresponding table entry.
93. What is a single souce shortest path problem?
Given as an input,a weighted graph,G=
as the source vertex.Single source shortest path problem finds the shortest
weighted path from s to every other vertex in G.
94. Explain about Unweighted shortest path.
10
Single source shortest path finds the shortest path from the source to each
and every vertex present in a unweighted graph.Here no cost is associated
with the edges connecting the vertices.Always unit cost is associated with
each edge.
95. Explain about Weighted shortest path
Single source shortest path finds the shortest path from the source to each
and
Every vertex present In a weighted graph.In a weighted graph some cost is
always
Associated with the edges connecting the vertices.
96. What are the methods to solve minimum spanning tree?
a) Prim’s algorithm
b) Kruskal’s algorithm
97. Explain briefly about Prim’s algorithm
Prim’s algorithm creates the spanning tree in various stages.At each stage,a
node is picked as the root and an edge is added and thus the associated
vertex along with it.
98. Define a depth first spanning tree.
The tree that is formulated by depth first search on a graph is called as depth
first spanning tree.The depth first spanning tree consists of tree edges and
back edges.
99. What is a tree edge?
Traversal from one vertex to the next vertex in a graph is called as a tree
edge.
100. What is a back edge?
The possibility of reaching an already marked vertex is indicated by a dashed
line,in a graph is called as back edge.
KEYWORDS:DATA STRUCTURES,DATA STRUCTURES QUESTION PAPER,ANNA UNIVERSITY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS