Рубрики

Структуры данных и алгоритмы | Набор 31

На экзамене GATE CS 2013 были заданы следующие вопросы.

1) Что является возвращаемым значением f (p, p), если значение p инициализируется до 5 перед вызовом? Обратите внимание, что первый параметр передается по ссылке, тогда как второй параметр передается по значению.

int f(int &x, int c) {
   c  = c - 1;
   if (c == 0) return 1;
   x = x + 1;
   return f(x, c) * x;
} 

(А) 3024
(В) 6561
(С) 55440
(D) 161051

Ответ (Б)
Поскольку c передается по значению, а x передается по ссылке, все функции будут иметь одинаковую копию x, но разные копии c.

f (5, 5) = f (x, 4) * x = f (x, 3) * x * x = f (x, 2) * x * x * x = f (x, 1) * x * x * х * х = 1 * х * х * х * х = х ^ 4

Поскольку x увеличивается при каждом вызове функции, он становится 9 после вызова f (x, 2). Таким образом, значение выражения x ^ 4 становится 9 ^ 4, что составляет 6561.

#include <stdio.h>

  

int f(int &x, int c)

{

    c  = c - 1;

    if (c == 0) return 1;

    x = x + 1;

    return f(x, c) * x;

}

int main()

{

    int p = 5;

    printf("%d", f(p, p));

}

1) Последовательность обхода предзаказа дерева двоичного поиска составляет 30, 20, 10, 15, 25, 23, 39, 35, 42. Что из следующего является последовательностью обхода после заказа того же дерева?
(А) 10, 20, 15, 23, 25, 35, 42, 39, 30
(В) 15, 10, 25, 23, 20, 42, 35, 39, 30
(С) 15, 20, 10, 23, 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30

Ответ (D)
Ниже построено дерево

            30
         /      \
        20       39 
       /  \     /  \
     10    25  35  42  
      \   /
      15 23

3) Рассмотрим следующую функцию

 int unknown(int n) {
    int i, j, k = 0;
    for (i  = n/2; i 

What is the returned value of the above function?
(A) Θ(n^2)
(B) Θ(n^2Logn)
(C) Θ(n^3)
(D) Θ(n^3Logn)

Answer (B)
The outer loop runs n/2 or Θ(n) times. The inner loop runs Θ(Logn) times (Note that j is divide by 2 in every iteration). So the statement "k = k + n/2;" runs Θ(nLogn) times. The statement increases value of k by n/2. So the value of k becomes n/2*Θ(nLogn) which is Θ(n^2Logn)


4) The number of elements that can be sorted in Θ(logn) time using heap sort is
(A) Θ(1)
(B) Θ(sqrt(logn))
(C) Θ(Log n/(Log Log n))
(d) Θ(Log n)

Answer (C)
Time complexity of Heap Sort is Θ(mLogm) for m input elements. For m = Θ(Log n/(Log Log n)), the value of Θ(m * Logm) will be Θ( [Log n/(Log Log n)] * [Log (Log n/(Log Log n))] ) which will be Θ( [Log n/(Log Log n)] * [ Log Log n - Log Log Log n] ) which is Θ(Log n)



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

void find_and_replace(char *A, char *oldc, char *newc) {
    for (int i = 0; i 

The procedure is tested with the following four test cases
(1) oldc = "abc", newc = "dab"
(2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda"
(4) oldc = "abc", newc = "bac"
The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ 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?

(A) Only one
(B) Only two
(C) Only three
(D) All four

Answer (B)
The test cases 3 and 4 are the only cases that capture the flaw. The code doesn't work properly when an old character is replaced by a new character and the new character is again replaced by another new character. This doesn't happen in test cases (1) and (2), it happens only in cases (3) and (4).

6) If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?
(A) None
(B) 2 only
(C) 3 and 4 only
(D) 4 only

Answer (C)




#include <stdio.h> #include <string.h>    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]; }    int main() {     char *oldc1 = "abc", *newc1 = "dab";     char *oldc2 = "cde", *newc2 = "bcd";     char *oldc3 = "bca", *newc3 = "cda";     char *oldc4 = "abc", *newc4 = "bac";        char test[] =  "abcde";        printf("Test 2\n");     printf("%s\n", test);     find_and_replace(test, oldc2, newc2);     printf ("%s\n", test);        printf("\nTest 3\n");     strcpy(test, "abcde");     printf("%s\n", test);     find_and_replace(test, oldc3, newc3);     printf ("%s\n", test);        printf("\nTest 4\n");     strcpy(test, "abcde");     printf("%s\n", test);     find_and_replace(test, oldc4, newc4);     printf ("%s\n", test); }

Output:

Test 2
abcde
abbcd

Test 3
abcde
addde

Test 4
abcde
aacde

Пожалуйста, смотрите GATE Corner для всех документов / решений / объяснений предыдущего года, учебных планов, важных дат, заметок и т. Д.

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

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

Структуры данных и алгоритмы | Набор 31

0.00 (0%) 0 votes