Category: Data Structures & Algorithms Objective Questions

Data Structure Multiple Choice Questions on “Binary Search Iterative”.

1. What is the advantage of recursive approach than an iterative approach?
a) Consumes less memory
b) Less code and easy to implement
c) Consumes more memory
d) More code has to be written

Answer: b
Clarification: A recursive approach is easier to understand and contains fewer lines of code.

2. Choose the appropriate code that does binary search using recursion.
a)

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + (high - low)/2;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid+1,high,key);
	}
	else
	{
		return recursive(arr,low,mid-1,key);
	}
}

b)

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + (high + low)/2;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid-1,high,key);
	}
	else
	{
		return recursive(arr,low,mid+1,key);
	}
}

c)

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + (high - low)/2;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid,high,key);
	}
	else
	{
		return recursive(arr,low,mid-1,key);
	}
}

d)

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + ((high - low)/2)+1;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid,high,key);
	}
	else
	{
		return recursive(arr,low,mid-1,key);
	}
}

Answer: a
Clarification: Calculate the ‘mid’ value, and check if that is the key, if not, call the function again with 2 sub arrays, one with till mid-1 and the other starting from mid+1.

3. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
a) 5
b) 2
c) 3
d) 4

Answer: c
Clarification: level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).

4. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?
a) 90 and 99
b) 90 and 94
c) 89 and 99
d) 89 and 94

Answer: a
Clarification: At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.

5. What is the worst case complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: b
Clarification: Using the divide and conquer master theorem.

6. What is the average case time complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
View Answer

Answer: b
Clarification: T(n) = T(n/2) + 1, Using the divide and conquer master theorem.

7. Which of the following is not an application of binary search?
a) To find the lower/upper bound in an ordered sequence
b) Union of intervals
c) Debugging
d) To search in unordered list
View Answer

Answer: d
Clarification: In Binary search, the elements in the list should be sorted. It is applicable only for ordered list. Hence Binary search in unordered list is not an application.

8. Choose among the following code for an iterative binary search.
a)

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high + low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid - 1;
		}
		else
		{
			high = mid + 1;
		}
	}
	return -1;
}

b)

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high - low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

c)

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high + low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

d)

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high - low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid - 1;
		}
		else
		{
			high = mid + 1;
		}
	}
	return -1;
}

Answer: b
Clarification: Find the ‘mid’, check if it equals the key, if not, continue the iterations until low <= high.

9. Binary Search can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming

Answer: b
Clarification: Since ‘mid’ is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.

10. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?
a) 1
b) 3
c) 4
d) 2

Answer: d
Clarification: Iteration1 : mid = 77; Iteration2 : mid = 88;

11. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding array elements) generated in the first and second iterations?
a) 90 and 99
b) 90 and 100
c) 89 and 94
d) 94 and 99

Answer: a
Clarification: Trace the input with the binary search iterative code.

12. What is the time complexity of binary search with iteration?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: b
Clarification: T(n) = T(n/2) + theta(1)
Using the divide and conquer master theorem, we get the time complexity as O(logn).

and Answers.

contest

Data Structure Multiple Choice Questions on “Quicksort – 3”.

1. QuickSort can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming

Answer: b
Clarification: First you divide(partition) the array based on the pivot element and sort accordingly.

2. Select the appropriate recursive call for QuickSort.(arr is the array, low is the starting index and high is the ending index of the array, partition returns the pivot element, we will see the code for partition very soon)
a)

public static void quickSort(int[] arr, int low, int high)
{
	int pivot;
	if(high>low)
	{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot-1);
		quickSort(arr, pivot+1, high);
	}
}

b)

public static void quickSort(int[] arr, int low, int high)
{
	int pivot;
	if(high<low)
	{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot-1);
		quickSort(arr, pivot+1, high);
	}
}

c)

public static void quickSort(int[] arr, int low, int high)
{
	int pivot;
	if(high>low)
	{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot);
		quickSort(arr, pivot, high);
	}
}

d)

public static void quickSort(int[] arr, int low, int high)
{
	int pivot;
	if(high>low)
	{
		pivot = partition(arr, low, high);
		quickSort(arr, low, pivot);
		quickSort(arr, pivot+2, high);
	}
}

Answer: a
Clarification: Based on the pivot returned by the call to partition, recursive calls to quickSort sort the given array.

3. What is the worst case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: d
Clarification: When the input array is already sorted.

4. What is a randomized QuickSort?
a) The leftmost element is chosen as the pivot
b) The rightmost element is chosen as the pivot
c) Any element in the array is chosen as the pivot
d) A random number is generated which is used as the pivot

Answer: c
Clarification: QuickSort is randomized by placing the input data in the randomized fashion in the array or by choosing a random element in the array as a pivot.

5. Which of the following code performs the partition operation in QuickSort?
a)

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left > right)
	{
		while(arr[left] <= pivot_item)
		{
			left++;
		}
		while(arr[right] > pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

b)

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left <= right)
	{
		while(arr[left] <= pivot_item)
		{
			left++;
		}
		while(arr[right] > pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

c)

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left <= right)
	{
		while(arr[left] > pivot_item)
		{
			left++;
		}
		while(arr[right] <= pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

d)

private static int partition(int[] arr, int low, int high)
{
	int left, right, pivot_item = arr[low];
	left = low;
	right = high;
	while(left > right)
	{
		while(arr[left] > pivot_item)
		{
			left++;
		}
		while(arr[right] <= pivot_item)
		{
			right--;
		}
		if(left < right)
		{
			swap(arr, left, right);
		}
	}
	arr[low] = arr[right];
	arr[right] = pivot_item;
	return right;
}

Answer: b
Clarification: The array is partitioned such that the elements left to the pivot are lesser than the pivot while the elements right of the pivot are greater than the pivot.

6. What is the best case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
Answer: a
Clarification: The array is partitioned into equal halves, using the Divide and Conquer master theorem, the complexity is found to be O(nlogn).

7. The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
a) 1 and 3
b) 3 and 1
c) 2 and 6
d) 6 and 2

Answer: a
Clarification: The call to partition returns 1 and 3 as the pivot elements.

8. What is the average case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: a
Clarification: The position of partition(split) is unknown, hence all(n) possibilities are considered, the average is found by adding all and dividing by n.

9. The given array is arr = {2,6,1}. What are the pivots that are returned as a result of subsequent partitioning?
a) 1 and 6
b) 6 and 1
c) 2 and 6
d) 1

Answer: d
Clarification: There is only one pivot with which the array will be sorted, the pivot is 1.

10. Which of the following is not true about QuickSort?
a) in-place algorithm
b) pivot position can be changed
c) adaptive sorting algorithm
d) can be implemented as a stable sort

Answer: b
Clarification: Once a pivot is chosen, its position is finalized in the sorted array, it cannot be modified.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Gnome Sort”.

1. Gnome sort is also called __________
a) Smart sort
b) Stupid sort
c) Bogo sort
d) Special sort
Answer: b
Clarification: Gnome sort was originally named as stupid sort but later on it got renamed as gnome sort.

2. How many loops are required to implement gnome sorting algorithm?
a) Single loop
b) 2 nested loops
c) 3 nested loops
d) It does not require any loop

Answer: a
Clarification: In this sorting algorithm the variable representing the index number is not incremented in case the adjacent pair of elements are out of place. In such a case its value is decremented instead. Thus it is able to implement sorting using a single loop.

3. Which of the following pair of sorting algorithms are stable?
a) gnome sort and quick sort
b) merge sort and selection sort
c) gnome sort and merge sort
d) heap sort and merge sort

Answer: c
Clarification: Gnome sort and merge sort are stable sorting algorithms as the elements with identical values appear in the same order in the output array as they were in the input array when any of these sorting algorithms are implemented.

4. Auxiliary space used by gnome sort is _________
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: Auxiliary space used by gnome sort is O(1) as it does not use any extra space for manipulating the input. Thus it also qualifies as an in place sorting algorithm.

5. The given array is arr = {1,2,4,3,5}.The number of iterations required to sort the array using gnome sort will be _________
a) 5
b) 6
c) 7
d) 8
View Answer

Answer: b
Clarification: 6 iterations will be required as one pair of elements i.e. {4,3} is out of place which causes the loop to take one step backward.

6. Gnome sort uses which of the following method to implement sorting?
a) Merging
b) Partitioning
c) Selection
d) Exchanging
View Answer

Answer: d
Clarification: Gnome sort implements sorting by exchanging the adjacent elements which are out of order. Thus its method of sorting is called exchanging.

7. What is the best case time complexity of gnome sort?
a) O(n)
b) O(n²)
c) O(n log n)
d) O(log n)

Answer: a
Clarification: When the input array is already sorted then in that case there will be no need to decrease the value of the index variable at any stage. So only O(n) time is required in this case as we keep on increasing its value after each iteration.

8. Select the appropriate code that performs gnome sort.
a)

while (index > n) 
{ 
        if (index == 0) 
            index++; 
        if (arr[index] <= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 
}

b)

while (index < n) 
{ 
        if (index == 0) 
            index++; 
        if (arr[index] <= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 
}

c)

while (index < n) 
{ 
        if (index == 0) 
            index++; 
        if (arr[index] >= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 
}

d)

while (index < n) 
{ 
        if (index == 0) 
            Index--; 
        if (arr[index] >= arr[index - 1]) 
            index++; 
        else 
        { 
            swap(arr[index], arr[index - 1]); 
            Index++; 
        } 
}

View Answer

Answer: c
Clarification: The first if statement increments the value of index if found to be 0 so that comparison can take place for this element. Second if statement checks whether the adjacent pair of elements are in order or not. If found out of order they are swapped under the else statement and index is decremented.

9. What is the worst case time complexity of gnome sort?
a) O(n)
b) O(n²)
c) O(n log n)
d) O(log n)

Answer: b
Clarification: Worst case occurs when the input array is reverse sorted as it will have the maximum number of decrements while sorting. This causes the algorithm to have a time complexity of O(n²) in this case.

10. What is the average case time complexity of gnome sort?
a) O(n)
b) O(n²)
c) O(n log n)
d) O(log n)

Answer: b
Clarification: In gnome sort the loop has to take one step backwards every time any adjacent pair of elements is out of place which causes it to have time complexity of O(n²) on an average.

& Algorithms.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Tree Sort”.

1. Which of the following data structure is required for the implementation of tree sort?
a) any ordinary tree
b) balanced tree
c) binary search tree
d) unbalanced tree

Answer: c
Clarification: Tree sort uses a binary search tree for sorting the given elements. Tree sort can also be performed by using an unbalanced binary search tree.

2. Tree sort is an online sorting algorithm.
a) True
b) False

Answer: a
Clarification: Tree sort does not require the entire input data at the beginning itself in order to sort the array. It rather creates a partial solution in every step, so future elements are not required to be considered. Hence it is an online sorting algorithm.

3. Which of the following traversal in a binary search tree results in a sorted output?
a) in order traversal
b) pre order traversal
c) post order traversal
d) breadth first traversal

Answer: a
Clarification: Tree sort uses a binary search tree for sorting the given elements. First a BST is formed by using the input data elements and then the BST is traversed in an in order fashion which gives a sorted output.

4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Tree sort
d) Heap sort

Answer: c
Clarification: Out of the given options Tree sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.

5. Which of the following sorting algorithm uses a binary search tree?
a) radix sort
b) tree sort
c) odd-even sort
d) bead sort

Answer: b
Clarification: Tree sort makes use of a binary search tree. It is because every time when a BST is traversed in an in order fashion it gives a sorted output.

6. Which of the following is a comparison based sort?
a) tree sort
b) radix sort
c) counting sort
d) pigeonhole sort

Answer: a
Clarification: In tree sort, we need to compare elements as we insert them in the binary search tree. Thus it qualifies as a comparison based sort.

7. What is the average case time complexity of tree sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: As on an average every element takes log n time for insertion in a binary search tree so for n elements O(n log n) time will be required on an average.

8. What is the best case time complexity of tree sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: The best case time complexity of tree sort is the same as its average case complexity. So best case time complexity is O(n log n).

9. What is the worst case time complexity of tree sort (when implemented with a balanced tree)?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: b
Clarification: The worst case time complexity of tree sort depends on whether the tree used in the implementation is balanced or not. If the tree is balanced then the worst case complexity is O(n log n).

10. What is the worst case time complexity of tree sort (when implemented with an unbalanced tree)?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: The worst case time complexity of tree sort depends on whether the tree used in the implementation is balanced or not. If the tree is unbalanced then the worst case complexity is O(n²).

11. What is the auxiliary space complexity of tree sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: b
Clarification: Tree sort requires auxiliary space for maintaining a binary search tree. So the auxiliary space complexity of tree sort is O(n).

12. In which of the following case does a tree sort become adaptive?
a) when implemented with an unbalanced tree
b) when implemented with a balanced tree
c) when implemented with a splay tree as BST
d) when implemented with AVL tree as BST
View Answer

Answer: c
Clarification: Tree sort becomes an adaptive sort when it is implemented with a splay tree as a BST. In such a case the best case time complexity is better than (n log n).

13. Which of the following is not true about tree sort?
a) it is not an in place sorting algorithm
b) its every implementation is adaptive
c) it requires in order traversal of BST for sorting input elements
d) it is a stable sort

Answer: b
Clarification: Every implementation of tree sort is not adaptive. It becomes adaptive only when implemented with a splay tree as BST.

14. Which of the following sorting algorithm is not in place?
a) insertion sort
b) quick sort
c) tree sort
d) gnome sort

Answer: c
Clarification: Out of the given options tree sort is the only algorithm which is not in place. It is because the auxiliary space required by tree sort is O(n).

15. The worst case time complexity of tree sort remains unaffected when implemented with an unbalanced tree or a balanced tree.
a) True
b) False

Answer: b
Clarification: The time complexity of tree sort is affected when implemented with an unbalanced tree or a balanced tree. In case of a balanced tree it is O(n log n) and in case of unbalanced tree it is O(n²).

16. Which of the following is not an advantage of tree sort?
a) it has a low space complexity
b) it has good time complexity for balanced BST
c) it is an online sorting algorithm
d) it is stable sorting algorithm
Answer: a
Clarification: Tree sort has a linear time complexity O(n) which makes it inefficient. This the main reason why sorting algorithms like quick sort, heap sort etc. are preferred over it.

17. Which of the following version of tree sort will have the highest worst case time complexity?
a) using AVL tree as BST
b) using red black tree as BST
c) using splay tree as BST
d) using ordinary BST

Answer: d
Clarification: Out of the given options tree sort has the highest worst case time complexity with ordinary BST as it may not be balanced in every case. Whereas all other options have self balancing BST.

and Answers.

Data Structure Multiple Choice Questions on “Depth First Search”.

1. Depth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal
Answer: a
Clarification: In Depth First Search, we explore all the nodes aggressively to one path and then backtrack to the node. Hence, it is equivalent to the pre-order traversal of a Binary Tree.

2. Time Complexity of DFS is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: a
Clarification: The Depth First Search explores every node once and every edge once (in worst case), so it’s time complexity is O(V + E).

3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree
Answer: a
Clarification: The Depth First Search is implemented using recursion. So, stack can be used as data structure to implement depth first search.

4. The Depth First Search traversal of a graph will result into?
a) Linked List
b) Tree
c) Graph with back edges
d) Array

Answer: b
Clarification: The Depth First Search will make a graph which don’t have back edges (a tree) which is known as Depth First Tree.

5. A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s Algorithm

Answer: a
Clarification: This is the definition of the Depth First Search. Exploring a node, then aggressively finding nodes till it is not able to find any node.

6. Which of the following is not an application of Depth First Search?
a) For generating topological sort of a graph
b) For generating Strongly Connected Components of a directed graph
c) Detecting cycles in the graph
d) Peer to Peer Networks
Answer: d
Clarification: Depth First Search is used in the Generation of topological sorting, Strongly Connected Components of a directed graph and to detect cycles in the graph. Breadth First Search is used in peer to peer networks to find all neighbourhood nodes.

7. When the Depth First Search of a graph is unique?
a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d) When the graph is a ternary Tree

Answer: b
Clarification: When Every node will have one successor then the Depth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

8. Regarding implementation of Depth First Search using stacks, what is the maximum distance between two nodes present in the stack? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information

Answer: a
Clarification: In the stack, at a time, there can be nodes which can differ in many levels. So, it can be the maximum distance between two nodes in the graph.

9. In Depth First Search, how many times a node is visited?
a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) Thrice

Answer: c
Clarification: In Depth First Search, we have to see whether the node is visited or not by it’s ancestor. If it is visited, we won’t let it enter it in the stack.

Multiple Choice Questions and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Chromatic Number”.

1. What is the definition of graph according to graph theory?
a) visual representation of data
b) collection of dots and lines
c) collection of edges
d) collection of vertices
Answer: b
Clarification: According to the graph theory a graph is the collection of dots and lines. Vertices are also called dots and lines are also called edges.

2. What is the condition for proper coloring of a graph?
a) two vertices having a common edge should not have same color
b) two vertices having a common edge should always have same color
c) all vertices should have a different color
d) all vertices should have same color

Answer: a
Clarification: The condition for proper coloring of graph is that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.

3. The number of colors used by a proper coloring graph is called?
a) k coloring graph
b) x coloring graph
c) m coloring graph
d) n coloring graph

Answer: a
Clarification: A proper graph ensures that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.

4. What is a chromatic number?
a) The maximum number of colors required for proper edge coloring of graph
b) The maximum number of colors required for proper vertex coloring of graph
c) The minimum number of colors required for proper vertex coloring of graph
d) The minimum number of colors required for proper edge coloring of graph

Answer: c
Clarification: The minimum number of colors required for proper vertex coloring of graph is called chromatic number whereas the minimum number of colors required for proper edge coloring of graph is called chromatic index of a graph.

5. What will be the chromatic number for an empty graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer

Answer: b
Clarification: An empty graph is a graph without any edges. So the chromatic number for such a graph will be 1.

6. What will be the chromatic number for an bipartite graph having n vertices?
a) 0
b) 1
c) 2
d) n

Answer: c
Clarification: A bipartite graph is graph such that no two vertices of the same set are adjacent to each other. So the chromatic number for such a graph will be 2.

7. Calculating the chromatic number of a graph is a
a) P problem
b) NP hard problem
c) NP complete problem
d) cannot be identified as any of the given problem types

Answer: c
Clarification: Chromatic number of an arbitrary graph cannot be determined by using any convenient method. So calculating the chromatic number of a graph is an NP complete problem.

8. What will be the chromatic number for a line graph having n vertices?
a) 0
b) 1
c) 2
d) n

Answer: d
Clarification: A line graph of a simple graph is obtained by connecting two vertices with an edge. A line graph has a chromatic number of n.

9. What will be the chromatic number for a complete graph having n vertices?
a) 0
b) 1
c) n
d) n!

Answer: c
Clarification: A complete graph is the one in which each vertex is directly connected with all other vertices with an edge. So in such a case each vertex should have a unique color. Thus the chromatic number will be n.

10. What will be the chromatic number for a tree having more than 1 vertex?
a) 0
b) 1
c) 2
d) Varies with the structure and number of vertices of the tree
View Answer

Answer: c
Clarification: The minimum number of colors required for proper vertex coloring of graph is called chromatic number. So every tree having more than 1 vertex is 2 chromatic.

11. A graph with chromatic number less than or equal to k is called?
a) K chromatic
b) K colorable
c) K chromatic colorable
d) K colorable chromatic

Answer: b
Clarification: Any graph that has a chromatic number less than or equal to k is called k colorable. Whereas a graph with chromatic number k is called k chromatic.

12. What will be the chromatic number of the following graph?

a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The given graph will only require 2 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 2.

13. What will be the chromatic number of the following graph?

a) 2
b) 3
c) 4
d) 5
View Answer

Answer: b
Clarification: The given graph will require 3 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 3.

14. What will be the chromatic number of the following graph?

a) 2
b) 3
c) 4
d) 5

Answer: b
Clarification: The given graph will require 3 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 3.

15. The chromatic number of star graph with 3 vertices is greater than that of a complete graph with 3 vertices.
a) True
b) False

Answer: b
Clarification: The chromatic number of a star graph is always 2 (for more than 1 vertex) whereas the chromatic number of complete graph with 3 vertices will be 3. So chromatic number of complete graph will be greater.

16. The chromatic number of star graph with 3 vertices is greater than that of a tree with same number of vertices.
a) True
b) False

Answer: b
Clarification: The chromatic number of a star graph and a tree is always 2 (for more than 1 vertex). So both have the same chromatic number.

and Answers.