A two-dimensional array A[1..n][1..n] of pairwise distinct integers, where n ≥…
PYQ GATE 1996Modified — slightly modified from the official paper; see the solution
A two-dimensional array A[1..n][1..n] of pairwise distinct integers, where n ≥ 2, is partially sorted if every row and every column is strictly increasing:
A[i][j] < A[i][j+1] for 1 ≤ i ≤ n, 1 ≤ j < n;
A[i][j] < A[i+1][j] for 1 ≤ i < n, 1 ≤ j ≤ n.Fill in the blanks:
(a) The smallest item in the array is at A[i][j], where i = ____ and j = ____.
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x, which is distinct from every remaining item and smaller than every item in the last row or column, while keeping A partially sorted.
procedure insert(x: integer);
var i, j: integer;
begin
i := 1; j := 1; A[i][j] := x;
while (x > ____ or x > ____) do
if A[i+1][j] < A[i][j] ____ then begin
A[i][j] := A[i+1][j]; i := i+1;
end
else begin
____
end;
A[i][j] := ____;
end;Attempted by 2 students.
Sign up free to check your answer
Sign up freeLoading lesson…

