Skip to content
GATETECH
Official PYQ · 2013Q50Arrays, Stacks and QueuesMCQ1 mark

GATE CS 2013 Q50 — Arrays, Stacks and Queues

Explain with AI

The procedure given below is required to find and replace certain characters inside an input character string supplied in array AA. The characters to be replaced are supplied in array oldcoldc, while their respective replacement characters are supplied in array newcnewc. Array AA has a fixed length of five characters, while arrays oldcoldc and newcnewc contain three characters each. However, the procedure is flawed.

void find_and_replace (char *A, char *oldc, char *newc) {
    for (int i=0; i<5; i++)
        for (int j=0; j<3; j++)
            if (A[i] == oldc[j])
                A[i] = newc[j];
}

The procedure is tested with the following four test cases.

  1. oldc=“abc”,newc=“dab”oldc = “abc”, newc = “dab”   
  2. oldc=“cde”,newc=“bcd”oldc = “cde”, newc = “bcd”
  3. oldc=“bca”,newc=“cda”oldc = “bca”, newc = “cda”    
  4. oldc=“abc”,newc=“bac”oldc = “abc”, newc = “bac”

The tester now tests the program on all input strings of length five consisting of characters ‘aa’, ‘bb’, ‘cc’, ‘dd’ and ‘ee’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

Choose one option
View worked solution

Answer: B

The flaw in the find_and_replace procedure lies in the inner loop. When a character A[i]A[i] matches oldc[j]oldc[j], it is immediately replaced by newc[j]newc[j]. However, the inner loop continues to run for subsequent indices k>jk > j. If the newly replaced character newc[j]newc[j] matches any oldc[k]oldc[k] (where k>jk > j), it undergoes a second replacement in the same iteration of the outer loop (cascading replacement).

For a test case to capture this flaw, there must exist some indices jj and kk such that k>jk > j and newc[j]=oldc[k]newc[j] = oldc[k]. Let us analyze the four test cases:

  1. oldc=“abc”,newc=“dab”oldc = \text{“abc”}, newc = \text{“dab”}
    • newc[0]=’d’newc[0] = \text{'d'} does not match oldc[1]=’b’oldc[1]=\text{'b'} or oldc[2]=’c’oldc[2]=\text{'c'}.
    • newc[1]=’a’newc[1] = \text{'a'} does not match oldc[2]=’c’oldc[2]=\text{'c'}.
    • No cascading occurs. (Flaw not captured)
  2. oldc=“cde”,newc=“bcd”oldc = \text{“cde”}, newc = \text{“bcd”}
    • newc[0]=’b’newc[0] = \text{'b'} does not match oldc[1]=’d’oldc[1]=\text{'d'} or oldc[2]=’e’oldc[2]=\text{'e'}.
    • newc[1]=’c’newc[1] = \text{'c'} does not match oldc[2]=’e’oldc[2]=\text{'e'}.
    • No cascading occurs. (Flaw not captured)
  3. oldc=“bca”,newc=“cda”oldc = \text{“bca”}, newc = \text{“cda”}
    • newc[0]=’c’newc[0] = \text{'c'} matches oldc[1]=’c’oldc[1] = \text{'c'}.
    • If A[i]=’b’A[i] = \text{'b'}, it first becomes ’c’\text{'c'} (at j=0j=0) and then immediately becomes ’d’\text{'d'} (at j=1j=1). The correct output should have been ’c’\text{'c'}. (Flaw captured)
  4. oldc=“abc”,newc=“bac”oldc = \text{“abc”}, newc = \text{“bac”}
    • newc[0]=’b’newc[0] = \text{'b'} matches oldc[1]=’b’oldc[1] = \text{'b'}.
    • If A[i]=’a’A[i] = \text{'a'}, it first becomes ’b’\text{'b'} (at j=0j=0) and then immediately becomes ’a’\text{'a'} (at j=1j=1). The correct output should have been ’b’\text{'b'}. (Flaw captured)

Thus, only test cases 3 and 4 are able to capture the flaw.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Arrays, Stacks and Queues questions