1
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+1
-0.3
Let $$G$$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

$$P:$$ Minimum spanning tree of $$G$$ does not change
$$Q:$$ Shortest path between any pair of vertices does not change

A
$$P$$ only
B
$$Q$$ only
C
Neither $$P$$ nor $$Q$$
D
Both $$P$$ and $$Q$$
2
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+1
-0.3
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
A
$$\Theta \left( {n\,\log n} \right),\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {{n^2}} \right)$$
B
$$\Theta \left( {{n^2}} \right),\Theta \left( {{n^2}} \right),\,\,$$ and $$\,\,\Theta \left( {n\,\log n} \right)$$
C
$$\Theta \left( {{n^2}} \right),\,\,\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {n\,\log n} \right)$$
D
$$\Theta \left( {{n^2}} \right),\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {{n^2}} \right)$$
3
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+2
-0.6
An operator $$delete(i)$$ for a binary heap data structure is to be designed to delete the item in the $$i$$-th node. Assume that the heap is implemented in an array and i refers to the $$i$$-th index of the array. If the heap tree has depth $$d$$ (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
A
$$O\left( 1 \right)$$
B
$$O\left( d \right)$$ but not $$O\left( 1 \right)$$
C
$$O\left( {{2^d}} \right)$$ but not $$O\left( d \right)$$
D
$$O\left( {d{2^d}} \right)$$ but not $$O\left( {{2^d}} \right)$$
4
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+2
-0.6
$$G = (V,E)$$ is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees $$(MSTs)$$ of $$G$$ is/are TRUE?

$$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ If $$e$$ is the lightest edge of some cycle in $$G,$$ then every $$MST$$ of $$G$$
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$includes $$e$$
$$\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ If $$e$$ is the heaviest edge of some cycle in $$G,$$ then every $$MST$$ of $$G$$
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$excludes $$e$$

A
$${\rm I}$$ only
B
$${\rm I}$$$${\rm I}$$ only
C
both $${\rm I}$$ and $${\rm II}$$
D
neither $${\rm I}$$ nor $${\rm I}$$$${\rm I}$$
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12