Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 76

GATE

В матрице M'N такая, что все ненулевые записи покрыты строками и столбцами b. Тогда максимальное количество ненулевых записей, таких, что нет двух одинаковых строк или столбцов, равно
(A) ≤ a + b
(B) ≤ max {a, b}
(C) ≤ min {Ma, Nb}
(D) ≤ min {a, b}

Ответ: (D)
Объяснение: Предположим, что a <b, например, пусть a = 3, b = 5, тогда мы можем поместить ненулевые записи только в 3 строки и 5 столбцов. Итак, предположим, что мы поместили ненулевые записи в любые 3 строки в 3 разных столбцах. Теперь мы не можем поместить любую другую ненулевую запись где-нибудь в матрице, потому что, если мы поместим ее в какую-то другую строку, то у нас будет 4 строки, содержащие ненулевые значения, если мы поместим ее в одну из этих 3 строк, то мы будет иметь более одной ненулевой записи в одной строке, что недопустимо.

Таким образом, мы можем заполнить только «a» ненулевые записи, если a <b, аналогично, если b <a, мы можем поместить только «b» ненулевые записи. Таким образом, ответ ≤min (a, b), потому что, если между a и b меньше, мы можем поместить не больше нуля.

Таким образом, вариант (D) является правильным.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2004 | Вопрос 76

0.00 (0%) 0 votes