Data Structures

DATA STRUCTURES

297. DATA STRUCTURES:
1. What is an algorithm?
The process of providing solution to a problem in a sequence of steps is called an algorithm.
2. What are the properties of an algorithm?
An algorithm must possess the following properties:
a. It should get input data.
b. It should produce output.
c. The algorithm should terminate.
d. Algorithm should be clear to understand.
e. It should be easy to perform.
3. What are the types of algorithms?
Algorithms are of two types: repetitive and recursive algorithms.
4. Define iterative algorithms.
Algorithms which use loops and conditions to solve the problem are called iterative algorithms.
5. Define recursive algorithms.
Algorithms which perform the recursive steps in a divide and conquer method are called recursive algorithms.
6. What is an array?
An array is a sequential collection of same kind of data elements.
7. What is a data structure?
A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.
8. Name the areas of application of data structures.
The following are the areas of application of data structures:
a. Compiler design
b. Operating system
c. Statistical analysis package
d. DBMS
e. Numerical analysis
f. Simulation
g. Artificial Intelligence
h. Graphics
9. What are the major data structures used in the following areas: Network data model, Hierarchical data model, and RDBMS?
The major data structures used in the above areas are:
Network data model – Graph
Hierarchical data model – Trees
RDBMS – Array
10. What are the types of data structures?
Data structures are of two types: Linear and non linear data structures.
11. What is a linear data structure?
If the elements of a data structure are stored sequentially, then it is a linear data structure.
12. What is non linear data structure?
If the elements of a data structure are not stored in sequential order, then it is a non linear data structure.
13. What are the types of array operations?
The following are the operations which can be performed on an array:
Insertion, Deletion, Search, Sorting, Merging, Reversing and Traversal.
14. What is a matrix?
An array of two dimensions is called a matrix.
15. What are the types of matrix operations?
The following are the types of matrix operations:
Addition, multiplication, transposition, finding determinant of square matrix, subtraction, checking whether it is singular matrix or not etc..
16. What is the condition to be checked for the multiplication of two matrices?
If matrices are to be multiplied, the number of columns of first matrix should be equal to the number of rows of second matrix.
17. Write the syntax for multiplication of matrices?
Syntax:
for (=0; < value;++)
{
for (=0; < value;++)
{
for (=0; < value;++)
{
arr[var1][var2] += arr[var1][var3] * arr[var3][arr2];
}
}
}
18. What is a string?
A sequential array of characters is called a string.
19. What is use terminating null character?
Null character is used to check the end of string.
20. What is an empty string?
A string with zero character is called an empty string.
21. What are the operations that can be performed on a string?
The following are the operations that can be performed on a string:
finding the length of string, copying string, string comparison, string concatenation, finding substrings etc.
22. What is Brute Force algorithm?
Algorithm used to search the contents by comparing each element of array is called Brute Force algorithm.
23. What are the limitations of arrays?
The following are the limitations of arrays:
Arrays are of fixed size.
Data elements are stored in continuous memory locations which may not be available always.
Adding and removing of elements is problematic because of shifting the locations.
24. How can you overcome the limitations of arrays?
Limitations of arrays can be solved by using the linked list.
25. What is a linked list?
Linked list is a data structure which store same kind of data elements but not in continuous memory locations and size is not fixed. The linked lists are related logically.
26. What is the difference between an array and a linked list?
The size of an array is fixed whereas size of linked list is variable.
In array the data elements are stored in continuous memory locations but in linked list it is non continuous memory locations.
Addition, removal of data is easy in linked list whereas in arrays it is complicated.
27. What is a node?
The data element of a linked list is called a node.
28. What does node consist of?
Node consists of two fields:
data field to store the element and link field to store the address of the next node.
29. Write the syntax of node creation?
Syntax:
struct node
{
data type ;
struct node *ptr; //pointer for link node
}temp;
30. Write the syntax for pointing to next node?
Syntax:
node->link=node1;
31. What are self referential structures?
The structures which contain a member field which point to the same structure type are called self referential structures.
32. How can you identify the end of a linked list?
In a linked list the link field of the last node stores the NULL value using which the end of the linked list is identified.
33. Write the syntax to identify the end of the linked list?
Syntax:
while (temp!=NULL)
{
……
}
34. How can you access the elements of a linked list?
The elements of a linked list can be accessed using the head pointer which points to the first node of the list and then by using the link field the next elements are accessed one by one until the last node is reached which is identified using the null pointer.
35. Write the algorithm for displaying the nodes of a linked list.
Algorithm:
i. Start with head node.
ii. While nodes are present or last node is not reached:
a. display the current data element.
b. move to next node.
36. What are the operations that can be performed on a linked list?
Addition, deletion, traversal, append, merge, sort, reverse, copy, search.
37. What are the situations in inserting a node?
When you want to insert a node, there are 3 situations encountered:
Insert at beginning of list, insert in the middle of list, insert at the end of list.
38. Write the algorithm for insertion of a node?
Algorithm:
Start
If the list is empty or new node should be added at beginning then,
insert the new node as head node,
else
if the new node should be inserted at the end then,
insert the new node at the end of list,
else
insert the new node in the middle of the list.
End
39. Write the algorithm for inserting node at the beginning of the linked list.
Algorithm:
a. Create space for new node.
b. Assign the value to the data field of new node.
c. Set the next field of the new node to the start of list.
d. Change the value of head pointer to point to new node.
40. Write the algorithm for inserting a new node in the middle of the list between specified values.
Algorithm:
a. Create space for new node.
b. Assign the value to the data field of new node.
c. Set the next field of new node to point to the value before which node should be inserted.
d. Set the next field of the value after which new node should be inserted to point to the new node.
41. Write the algorithm for inserting a node at the end of the list.
Algorithm:
a. Create space for new node.
b. Assign the value to the data field of new node.
c. Set the next field of the last node to the new node.
d. Set the next field of new node to null.
42. What are the situations in deleting a node?
Deletion of a node encounter the following situations:
Deletion of first item, deletion of the last item, deletion of a node between the specified nodes.
43. Write the syntax for deletion of a node.
Algorithm:
Start
If the list is empty then,
node cannot be deleted,
else
if the node to be deleted is the first node then,
make the head point to the second node,
else
delete the node from the list body
End
44. Write the algorithm for deleting the first node of the linked list.
Algorithm:
a. Check if the list is empty.
b. If the list is not empty make the head node point the next node.
45. Write the algorithm for deleting the last node.
Algorithm:
a. check if the list is empty.
b. If the list is not empty, traverse to the last but one node and set its next field to null.
46. Write the algorithm for deleting a specified node.
Algorithm:
a. Check if the list is empty.
b. If the list is not empty, traverse to the node after which the node to be deleted is present using the first loop.
c. And traverse to the node before which the node to be deleted is present using second loop.
d. Set the next field of first node to the node after the node to be deleted.
47. What are the advantages of a linked list?
As the linked list is dynamic data structure it can grow and shrink during program execution.
It doesn’t waste memory.
Flexibility in arranging data elements.
48. What are the applications of linked lists?
Linked lists are used to model different abstract data types like stacks, queues, trees etc.
49. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
Void pointer, because the heterogeneous linked list contains different data types in its nodes and we need a pointer to connect them, and we ordinary pointers cannot be used for this. So, we use void pointer which is capable of storing pointer to any type as it is a generic pointer type.
50. Is a linked list linear or non linear data structure?
According to access linked list is linear data structure, but according to storage it is non linear.
51. What are the types of linked lists?
Circular linked list, doubly linked list, circular doubly linked list are the types of linked lists.
52. What is the limitation of linked list?
The limitation of linked list is that we can traverse the list in only one direction, i.e., forward direction only. We cannot traverse the list back.
53. How can you overcome the limitation of linked list?
The limitation of linked list can be overcome by using the circular linked list.
54. What is a circular linked list?
Circular linked list is the list in which the last node points back to the first node instead of storing a null value.
55. How can you traverse a circular linked list?
The elements of a circular linked list can be accessed using the head pointer which points to the first node of the list and using the link field, next elements can be accessed. As there is no null pointer indicating the end of the list, a condition that last node is not equal to first node should be used to identify the end of the list.
56. What is recursion?
Recursion is the process of a function calling itself to complete a task.
57. What is the limitation of circular linked list?
The limitation of circular linked list is that if we want to access the previous node, the entire list has to be traversed again continuing from that node till that node.
58. How can you overcome the limitation of circular linked list?
The limitation of circular linked list can be overcome by using doubly linked list.
59. What is a doubly linked list?
The linked list in which each node has 3 fields, one data field, second pointing to the previous node and the third pointing to the next node, for the easy traversal in both the directions is called doubly linked list.
60. What are the operations that can be performed on doubly linked list?
Traversal of the list, add at beginning, add at end, add after n node, delete nth node, merge, sort, reverse, copy etc.
61. Using which data structure are the stacks and queues maintained?
Using linked list.
62. What is the disadvantage of doubly linked list in comparison to single linked list?
The disadvantage of doubly linked list in comparison to single linked list is that it occupies more memory than single linked list.
63. What is a circular doubly linked list?
The linked list in which there are both forward pointer and backward pointer in circular form is called circular doubly linked list.
64. What is a sparse matrix?
If a matrix has many zero elements then it is a sparse matrix.
65. Name few applications of multilinked data structure.
In index generation, sparse matrix etc.
66. What is a stack?
Stack is a data structure in which addition or deletion of the elements is done at the top.
67. What is the other name for stack?
Stack is also called Last in First out (LIFO) list.
68. What are the operations done on a stack?
Push and pop are the two operations which can be done on stack.
69. Define push.
The process of adding data element to the stack is called push.
70. Define pop.
The process of deleting a data element from the stack is called pop.
71. What are the ways of representing a stack?
A stack can be represented either as an array or as an linked list.
72. Write the algorithm of adding an element to a stack represented as an array.
Algorithm:
a. Check whether stack is full or not.
b. Increment the pointer pointing to the top of the stack.
c. Assign the value to the top index of the array.
73. Write the algorithm for removing an element from a stack represented as an array.
Algorithm:
a. Check whether stack is empty.
b. If stack is not empty, decrement the top pointer.
74. What is the limitation in representing a stack as an array?
An array has a fixed size whereas a stack doesn’t have any fixed size because of push and pop operations. So, fixed size becomes a limitation in representing a stack as an array.
75. Write the algorithm for push operation on stack represented as a linked list.
Algorithm:
a. Create space for new node.
b. Assign the value to the data field of new node.
c. Set the link field of new node to top;
d. Set the top to the new node.
76. Write the algorithm for pop operation on stack represented as a linked list.
Algorithm:
a. Check whether stack is empty.
b. If not empty traverse to the node below the top.
c. Set the top to the second node.
77. What are the applications of stacks?
The following are the applications of stacks:
In evaluation of expressions, unfolding systems recursive jobs, to find the traversals of graphs, non recursive traversal of binary trees, implementation of function calls, translating from one computer language to another etc.
78. Which data structure is used in recursion? Why?
Stack is the data structure used in recursion. Because stack follows the rule Last in first out (LIFO), and remembers its caller to return the value.
79. Where are the return values stored while using recursion?
Return addresses or return values of function calls are stored in system stack while using recursion.
80. What is stack overflow?
When you try to add an element to a stack which is already full, it results in stack overflow.
81. What is stack underflow?
When you try to remove an element from a stack which is empty, it results in stack underflow.
82. What is polish notation?
The notation which is used to represent an arithmetic expression is called polish notation and is named after a polish mathematician Jan Lukasiewicz.
83. What are the types of polish notations?
Polish notations are represents as prefix notation and postfix notation.
84. Which notations are used in evaluating arithmetic expressions using prefix and postfix forms?
Polish and Reverse Polish notations.
85. What is a queue?
Queue is a data structure in which insertion of element is done at one end and removal of element is done at the other end.
86. What is other name for queue?
Queue is also called as First in First out (FIFO) list.
87. What are the ways of representing a queue?
Queue can be represented either as an array or as a linked list.
88. What is front end?
The end of the queue at which insertion of data elements takes place is called front end.
89. What is rear end?
The end of the queue at which removal of data elements takes place is called rear end.
90. Write the algorithm of adding an element to a queue represented as an array.
Algorithm:
a. Check whether queue is full or not.
b. If the queue is empty then increment the front pointer and the rear pointer.
c. If the queue is not empty and not full then increment the rear pointer.
c. Assign the value to the rear index of the array.
91. Write the algorithm for removing an element from a queue represented as an array.
Algorithm:
a. Check whether queue is empty.
b. If queue is not empty, increment the front pointer.
c. If front and rear point to the same value then make both the pointers negative.
92. What are the applications of queues?
The following are the applications of queues:
Queues are used in a network with shared printers, fax etc and the jobs accumulate in a queue.
Queues are using in Operating system with GUI, windows and applications communication messages are placed in queue.
In messaging systems, event schedulers, in radix sort algorithm etc.
93. What is the limitation in representing a queue as an array?
An array has a fixed size whereas a queue doesn’t have any fixed size because of addition and deletion operations. So, fixed size becomes a limitation in representing a queue as an array.
94. Write the syntax of node creation for queue?
Syntax:
struct node
{
data type ;
node *link; //field where next node address is stored
}*front, *rear; // front and rear end pointers
95. Write the algorithm for adding a data element to a queue represented as a linked list.
Algorithm:
a. Create space for new node.
b. Assign the value to the data field of new node.
c. Set the link field of new node to rear;
d. Set the rear to the new node.
96. Write the algorithm for removing a data element from a queue represented as a linked list.
Algorithm:
a. Check whether queue is empty.
b. If not empty then increment the front pointer.
c. If both front and rear point to same value then make them both negative.
97. What is queue overflow?
When you try to add an element to a queue which is already full, it results in queue overflow.
98. What is queue underflow?
When you try to remove an element from a queue which is empty, it results in queue underflow.
99. What is circular queue?
Circular queue is the one in which elements are added to the rear end till is full, then keeps adding data elements to the front end if it is free.
100. What do we need circular queue?
We need circular queue because when normal queue is represented as an array, when the rear has reached maximum array size it shows as full. But as the removal of elements is done from the front end even though the queue is empty it doesn’t show.
101. Write the algorithm of adding an element to a circular queue represented as an array.
Algorithm:
a. Check whether queue is full or not.
b. If the queue is empty then increment the front pointer and the rear pointer.
c. If the queue is not empty and not full then increment the rear pointer.
d. Assign the value to the rear index of the array.
e. If the queue is full check whether the front is free or not.
f. If the front is free then increment the front pointer.
g. Assign the value to the front index of the array.
102. What is a dequeue?
Dequeue is a double ended queue in which data elements can be added or deleted from both the ends.
103. What is a priority queue?
A priority queue is an abstract data type in which elements are stored according to their levels of priority.
104. What are the operations performed on a priority queue?
The following are the operations performed on a priority queue:
Adding an element with a particular priority.
Remove the element with the highest priority and return.
Peek at the highest priority element.
105. What are the rules followed in using a priority queue?
Data of higher priority is processed first.
If the same priority data is found, then the data first added to the queue is processed first.
106. Write the syntax of node creation for priority queue?
Syntax:
struct node
{
data type ;
int priority, order;
};
107. What is the minimum number of queues required to implement priority queue?
Two queues are required to implement priority queue. One for actual storing of data and other for storing priorities.
108. What are the applications of priority queues?
The following are the applications of priority queues:
Managing of limited resources like bandwidth, printers (in a network), in A* search algorithm, in discrete event simulation, scheduling jobs in OS etc.
109. What is a bounded queue?
A queue limited to a fixed number of items is called bounded queue.
110. What is a tree?
Tree is a non linear data structure in which each node may point to many nodes.
111. Name the applications of tree data structure.
The following are the applications of tree data structure:
a. In manipulation of arithmetic expression.
b. Symbol table construction.
c. Syntax analysis.
112. What is a binary tree?
The non linear data structure which has at the most two pointers to the other tree nodes is called binary tree.
113. What does a binary tree consist of ?
A binary tree consists of a root, the left sub tree and the right sub tree.
114. What is an empty binary tree?
A binary tree with no elements is called an empty binary tree.
115. What is a node?
The individual element of a tree is called a node.
116. What is a root?
The base node of a tree is called the root.
117. What is a leaf node?
A node that does not have any further nodes is called a leaf node.
118. What is a father node?
If A is root node of B, and B is the left or right sub node of it, then A is called father of B, and B is called left or right son of A.
119. What is an ancestor?
If a node A is father of some node C, or may be father of C’s father and further more, then A is said to be ancestor of C.
120. What is a left descendant?
If a node A is father of some node C, or may be father of C’s father and further more, then C is said to be descendant of A.
121. What is climbing of tree?
The traversal of tree from leaf node to root node is called climbing of tree.
122. What is descending of tree?
The traversal of tree from root node to leaf node is called descending of tree.
123. What is a strictly binary tree?
If every non leaf node in a binary tree has non empty left and right sub trees then it is called a strictly binary tree.
124. What is a degree of a node?
Degree of a node is the number of nodes connected to that node.
125. What is a level of tree?
The level of a tree is determined in terms of its distance from the root node where a root node has a level 0; a child node is one level more than the root node and so on.
126. What is depth of a tree?
Depth of a tree is the maximum level of any leaf node.
127. What is a complete binary tree?
Complete binary tree is a strict binary tree in which all the leaf nodes are at same level.
128. What is traversal of tree?
The process of visiting each node of a tree exactly once in a particular method is called traversal of a tree.
129. What is the efficient data structure used to implement tree?
Linked list.
130. What are the different methods of traversal of a tree?
The following are the different methods of traversal of a tree:
In-order , Pre-order and Post-order traversal.
131. What is the primary difference in the different methods of traversal?
The difference is only in the order in which the root node, nodes in the right sub tree, and the nodes in the right sub tree are visited.
132. Write the algorithm for in-order traversal.
Algorithm:
a. Traverse the left sub tree in in-order.
b. Visit the root.
c. Traverse the right sub tree in in-order.
133. Write the algorithm for pre-order traversal.
Algorithm:
a. Visit the root.
b. Traverse the left sub tree in pre-order.
c. Traverse the right sub tree in pre-order.
134. Write the algorithm for post-order traversal.
Algorithm:
a. Traverse the left sub tree in post-order.
b. Traverse the right sub tree in post-order.
c. Visit the root.
135. What are the elements of each node of a binary tree?
Node of a binary tree consists of a data field, a pointer to the right child, and a pointer to the left child.
136. Write the syntax for structure of a binary tree.
Syntax:
struct tree
{
tree *left;
int data;
tree *right;
};
137. What are the different ways in which a binary tree can be represented?
A binary tree can either be represented using links or by using arrays.
138. What is a binary search tree?
A tree in which all the elements in the right sub tree of a node n are greater than or equal to the contents of n and the elements in the left sub tree are less than the contents of n, then it is called a binary search tree.
139. What are the different operations that can be performed on a binary search tree?
Insertion, deletion and searching.
140. Write the algorithm for searching a node in a binary search tree?
Algorithm:
a. Data is compared with root node.
b. If it is not equal, then check if it is less than the root node, then follow the same steps for left sub tree.
c. If the value is greater than root node, then follow the same steps for right sub tree.
141. Write the algorithm for inserting a node in a binary search tree?
Algorithm:
a. First the data is compared with root node.
b. If it is greater than or equal to the root node, then follow the same steps to insert the data in right sub tree.
c. If the value is lesser than the root node, then follow the same steps to insert it in the left sub tree.
d. Steps a and (b or c) are repeated until an empty node is found where the data is to be inserted.
142. What are the possible conditions encountered in deleting data from a binary tree?
The following are the possible conditions:
a. Node with data has no children.
b. Node with data has only one child.
c. Node with data has two children.
143. What are the applications of binary tree?
The binary tree is used in situations where we want to make two way decisions, in using binary search trees, in representing expressions etc.
144. What are expression trees?
Expression trees are the arithmetic expression represented as binary trees.
145. If you traverse the expression tree in pre-order which type of expression is obtained?
Prefix expression.
146. If you traverse the expression tree in post-order which type of expression is obtained?
Postfix expression.
147. If you traverse the expression tree in in-order which type of expression is obtained?
Infix expression.
148. How do you convert a binary tree into an extended tree?
By adding new nodes to the leaf nodes of a binary tree and to the nodes that have only one child we can convert a binary tree into an extended tree.
149. What is the other name for extended tree?
2-tree.
150. What are internal nodes?
When a binary tree is converted to an extended tree, the nodes of the original tree are called internal nodes.
151. What are external nodes?
When a binary tree is converted to an extended tree, the nodded that are added to the binary tree are called external nodes.
152. How do you calculate the external nodes if the number of internal nodes are given?
The number of external nodes of a binary tree is always one more than the number of internal nodes. For example, if N is the number of internal nodes, then the external nodes are N+1.
153. How do you calculate the number of nodes of a binary tree, if the height of it is given?
If the height of a binary tree is given, the number of nodes is calculated by using 2h+1-1.
154. How do you calculate the number of branches of a tree if the number of nodes is given?
If the number of nodes is given, the number of branches of a tree is always less then it by 1.
155. What are right threads?
Right threads are the pointers that point in-order successor of a node.
156. What are left threads?
Left threads are the pointers that point to in-order predecessor of a node.
157. What is the limitation of threads in using binary tree?
The limitation of thread in using binary tree is in finding out whether a pointer is normal pointer to child or a thread that points back to in-order predecessor node or in-order successor node.
158. What are the elements of a node in threaded binary tree?
The following are the elements of a node in threaded binary tree:
Data, left pointer, right pointer, a true or false value for left thread, and a true or false value for right thread.
159. Write the syntax of threaded binary tree node?
Syntax:
struct tbtree
{
int data;
tbtree *leftchild;
tbtree *rightchild;
enum Boolean left;
enum Boolean right;
};
160. What are the conditions to be checked when deleting a node in threaded binary tree?
The following conditions are to be checked when deleting a node in threaded binary tree:
a. No node in tree should contain the specified data.
b. Node should have no children.
c. Node should have exactly one child.
d. Node should have two children.
161. What is a general tree?
A tree with n number of nodes is called a general tree.
162. What are siblings?
Siblings are the children of a node.
163. Name the pointers which are to be maintained in converting a general tree to a binary tree.
The pointers which are to be maintained in converting a general tree to a binary tree are:
i) A pointer pointing to first child of node.
ii) A pointer pointing to siblings of node.
164. Write the syntax of node of a general tree represented as a binary tree.
Syntax:
struct gtree
{
int data;
gtree *firstchild;
gtree *siblings;
};
165. What is a forest?
A set of trees which are not linked together is called a forest.
166. What is a balanced binary tree?
Balanced binary tree is the binary search tree in which the difference between the heights of left and right sub trees of all nodes is at most one.
167. What is the other name for balanced binary tree?
Balanced binary trees are also called AVL trees.
168. Why are balanced binary trees called AVL trees?
The balanced binary trees also called AVL trees are named after the Russian mathematicians G.M. Adelson-Velskii and E.M. Landis who invented them.
169. What are the elements of an AVL tree?
The AVL tree consists of data field, two fields for storing the left and right child address, and one field to hold balance factor.
170. How do you calculate the balance factor a node?
If you subtract the height of the right sub tree of node from the height of left sub tree we get the balance factor.
171. Write the syntax of AVL tree node?
Syntax:
struct AVL_tree
{
int data;
int bal_factor;
AVL_tree *left;
AVL_tree *right;
};
172. How do you check whether a tree is AVL tree or not, provided the balance factor is known?
If the balance factor of any node is -1, 0 or 1 then only it is an AVL tree otherwise not.
173. How can you represent balance factor apart from using -1, 0 or 1?
Apart from using -1, 0, or 1 we can also represent balance factor using \, -, /.
174. How can you determine whether right sub tree has more height or left sub tree has more height?
It can be done using the balance factor value:
If it is -1, right sub tree has more height than the left sub tree.
If it is 1, left sub tree has more height than the right sub tree.
If it 0, both are of equal height.
175. At what condition the balancing has to be done in AVL tree?
When the height factor is greater than 1 or less than -1.
176. What is the disadvantage of AVL trees?
The disadvantage of AVL trees is that insertion and deletion needs rotation which is complicated.
177. How can you overcome the disadvantage of AVL tree?
The disadvantage of AVL trees can be overcome using 2-3 trees data structure.
178. What are the conditions to be followed to build 2-3trees?
The following are the conditions to be followed to build 2-3trees:
a. The leaf nodes should have two or three non-empty child nodes which are in turn 2-3trees.
b. One single node can contain either one or two values.
c. All the leaf nodes should be at same level.
d. If a node has two children, then it contains single data, and data value of left sub tree should be less than the node, and data value of right sub tree should be greater than the node.
e. If a node has three children, then node contains two data values. And the data of left sub tree nodes should be less than first data value, and data of middle sub tree should be greater than first data value and less than second data value, and data of right sub tree should be greater than first data value and second data value.
179. Write the syntax of 2-3tree node?
Syntax:
struct two_three
{
int count;
int data[3];
two_three *child[4];
};
180. What is a multiway tree?
A tree of order n is a multiway tree if any node contains maximum n-1 values and has maximum n children.
181. What is a B-tree?
If a multi way search tree of order n meet the following criteria then it a B-tree.
a. All non-leaf nodes have atleast n/2 children and at most n children.
b. A non-leaf node may have at most n non-empty child.
c. A root node with no child is possible.
d. If there are n children of a node, then it must have n-1 data values.
e. All values of left child are less than first value of node, and all values of right node are greater than last value of node.
f. All leaf nodes should appear on same level.
182. Write the syntax of B-tree node?
Syntax:
struct btree
{
int count;
int value[max + 1];
btree *child[max + 1];
};
Where
count – number of children of a node
value – values of node
child – stores addresses of child node
max – maximum number of node values
183. What is the data structure used in internal storage representation in RDBMS?
B+ tree in which all the data is stored only in leaf nodes.
184. Using which structure is the priority queue implemented?
Using heap.
185. What is a heap?
A complete binary tree is called a heap.
186. What are the types of heaps?
Max heap and min heap are the types of heaps.
187. What is max heap?
A tree in which the value at any node is greater than all its children then it is called max heap.
188. What is min heap?
A tree in which the value at any node is less than all its children then it is called min heap.
189. What is the other name for max heap?
Descending heap.
190. What is the other name for min heap?
Ascending heap.
191. Name the operations that can be performed on a heap.
Insertion, deletion, and replacement of a node are the operations of a heap.
192. What is searching?
The process of finding out the position of a given value in a list is called searching.
193. What is linear search?
Linear search is the process of the searching for an element right from the 0th element of a list till the end of the list or until the element is found.
194. What is the condition to use binary search?
To use a binary search the list should be in a sorted order.
195. Write the algorithm for binary search?
Algorithm:
a. Compare the value with the mid value of list.
b. If not equal, then divide the list into two halves; one half from 0th element to mid element -1 and other element from mid element + 1 to the last element.
c. Steps a and b are repeated individually with each halves until the element is found.
196. What is the advantage of binary search compared to linear search?
Binary search executes very fast compared to linear search because of less number of comparisons.
197. What is the disadvantage of binary search?
The disadvantage is that the list should be sorted, if not linear search is to be used.
198. What is sorting?
Sorting is arranging of data in a particular order.
199. What are the types of sorting?
Sorting is of two types: Internal and external sorting.
200. When should we use internal sorting?
Internal sorting can be used when all the data can be kept at a time in memory.
201. When should we use external sorting?
External sorting should be used when the data is huge and cannot be kept in memory at a time and has to use auxiliary memory.
202. What are the types of internal sorting?
Bubble sort, Selection sort, Insertion sort, Heap sort, Merge sort, Shell sort are the types of internal sorting.
203. Write the algorithm for bubble sort.
Algorithm (ascending order):
a. Start with first element and compare with next element.
b. If first element is greater than next, then they are interchanged.
c. All the elements are compared in the same way with their next element except the last element, which results in large element.
d. Repeat the steps a, b, and c excluding the last element bubbled out in that iteration.
204. Why is the term bubble used in bubble sort?
The bubble sort in its iterations causes larger values to "bubble" to the end of the list and smaller values "sink" towards the beginning of the list, thus the name bubble sort.
205. What is the complexity of bubble sort?
O (n2).
206. Why the complexity of bubble sort is same in all the scenarios (worst, average, and best)?
The reason is that the code has no way of determining whether the list is already in order.
207. How can you solve the limitation of bubble sort?
The limitation of bubble sort can be solved using modified bubble sort which uses a flag to check whether list is sorted or not.
208. What is the use of modified bubble sort?
Modified bubble sort has a flag which is set to check if a swap is done after an entire pass over the array. If no swap is done, then it is clear that the list is already in order because no two elements need to be switched. In that case, the sort should end.
209. What is the best case complexity for modified bubble sort?
The complexity for best case for modified bubble sort is O (n).
210. Write the algorithm for selection sort.
Algorithm:
a. Start with the first element and compare with all the other elements in the list.
b. If the next element is less than the first element, then they are swapped.
c. At the end of iteration smallest element is placed in the beginning of list.
d. Steps a, b are repeated with 2nd, 3rd, and so on elements until the last but one element.
211. What is the complexity of selection sort?
O (n2).
212. Write the algorithm for insertion sort.
Algorithm:
a. In first iteration, 1st element is compared with 0th element.
b. Likewise in the nth iteration, nth element is compared with the elements below it starting from 0th element.
c. In this iterations, if it is found that to be inserted element can be inserted anywhere space is created by shifting the other elements one position to right.
213. What is the complexity of insertion sort?
For worst and average cases it is O (n2) and for best case it is n-1.
214. What is logic of quick sort?
Quick sort uses the divide and conquer recursive algorithm.
215. Write the algorithm for quick sort?
Algorithm:
a. Pick an element in the array to use as a pivot element.
b. Split the array into two parts: one with elements greater than pivot element and the other with elements less than the pivot element.
c. Repeat the above steps for both halves of the original array.
216. What is the other name for quick sort?
Partition exchange sort.
217. What is the complexity of quick sort?
Worst case - O (n2), average case – log2n, best case – log2n.
218. Write the algorithm for heap sort?
Algorithm:
a. First step is building a heap out of the data set.
b. Then remove the largest item and place it at the end of the sorted array.
c. Next reconstruct the heap and remove the largest remaining item and place it in the next open position from the end of the sorted array.
d. This is repeated until there are no items left in the heap and the sorted array is full.
219. How many arrays are used in heap sort?
Heap sort uses two arrays - one to hold the heap and the other to hold the sorted elements.
220. Out of the following which is the slower sort: merge, quick and heap?
Heap.
221. What do you mean by “In place”?
Sorting methods that do not require additional space are called “In place”.
222. What is the complexity of heap sort?
Worst case - O (n log n), average case – O (n log n), best case – O (n log n).
223. Write the algorithm for merge sort.
Merge sort either merges 2 already sorted lists or to sort huge data, divides the list into smaller lists using divide and conquer method.
Algorithm:
a. First split the list into two equal halves and place them in separate arrays.
b. Each array is recursively sorted.
c. Then the elements from both the sorted arrays are compared and smaller of both the elements is placed in third array.
d. Sorting is done when all the elements from both the elements are placed in third array.
224. What is the complexity of merge sort?
O (n log n) for all the cases.
225. How many arrays are required for merge sort?
Three arrays (one for each half of data set and the other for the sorted list).
226. What are the other names for shell sort?
Shell sort is also called diminishing increment sort or comb sort.
227. What is logic followed by shell sort?
The shell sort makes multiple passes through the list, and each time it sorts equal sized sets using insertion sort. The size of the set to be sorted becomes larger with each pass through the list, until it consist the entire list.
228. Which of the following algorithms is slower: merge, heap, shell, quick?
Shell sort.
229. What are the methods available to store sequential files?
The following are the methods used to store sequential files:
a. Straight merge
b. Polyphase sort
c. Natural merge
d. Distribution of initial runs.
230. List the hashing functions based on the methods used to find key value.
The following are the hashing functions based on the methods to find key value:
direct method, mid-square method, folding method, subtraction method, modulo-division method, pseudo-random method, digit-extraction method.
231. What are the types of collision resolution techniques and the methods used?
The following are the types of collision resolution techniques and their methods:
a. Open addressing (closed hashing) – method is overflow block
Closed addressing (Open hashing) – methods are linked list and binary tree.
232. What is a graph?
A graph is a collection of set of vertices and edges.
233. What are the types of graphs?
Directed graph and the undirected graph are the two types of graphs.
234. What is the difference between directed and undirected graph?
The difference is that in directed graph order of vertices representing edge is important whereas in undirected graph order of vertices is not important.
235. What is the other name for directed graph?
Digraph.
236. What are the commonly used representations for graphs?
The most commonly used representation of graphs are: Adjacency matrices and Adjacency lists.
237. What are the different ways of visiting all the vertices in a graph from a given vertex?
Using Depth first search and breadth first search algorithms.
238. Write the algorithm for depth first search.
Algorithm:
a. Visit a vertex and mark it as visited.
b. select an unvisited vertex w adjacent to v.
c. Repeat steps a and b till are adjacent vertices of w are visited.
d. Then go back to the last vertex visited which has an unvisited adjacent vertex and repeat step (a).
e. Stop the search when no unvisited vertex is left.
239. Write the algorithm for breadth first search.
Algorithm:
a. Visit a vertex and mark it as visited.
b. Visit all unvisited vertices adjacent to v.
c. Then visit unvisited vertices adjacent to these vertices until all the vertices are finished.
240. What is a spanning tree?
An undirected tree consisting of only those edges that are necessary to connect all the vertices in the original graph is called spanning tree of a graph.
241. What are the properties of a spanning tree?
A spanning tree has the following properties:
a. Between any pair of vertices there exists only one path.
b. Insertion of any edge to a spanning tree form a unique cycle.
242. What is depth first spanning tree?
Depth first spanning tree is the one resulting from a call to depth first tree.
243. What is breadth first spanning tree?
Breadth first spanning tree is the one resulting from a call to breadth first tree.
244. What is the use of spanning tree?
In analysis of electrical circuits, shortest route problems etc.
245. How do you determine the cost of a spanning tree?
By adding the costs of edges of that tree.
246. What is the condition to be satisfied by an edge to be included in spanning tree of Kruskal’s algorithm?
In order to be included in spanning tree of Kruskal’s algorithm, the edge should not form a cycle with already present edges.
247. What is the use of Dijkstra’s algorithm?
It is used to find shortest path between two nodes.
248. What is the type of the algorithm used in solving the 8 Queens problem?
Backtracking algorithm.
249. Does the minimum spanning tree of a graph give the shortest distance between any 2 specified nodes?
No. Minimal spanning tree assures only that the total weight of the tree is kept at its minimum. But it doesn’t mean that it provides the shortest distance between any two nodes.