Рубрики

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

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

1. Задача подмножества суммы определяется следующим образом. Для заданного набора из n натуральных чисел S = {a1, a2, a3,…, an} и натурального W, есть ли подмножество S, элементы которого суммируются с W? Динамическая программа для решения этой проблемы использует 2-мерный логический массив X с n строками и W + 1 столбцами. X [i, j], 1
(A) X [i, j] = X [i — 1, j] VX [i, j -ai]
(B) X [i, j] = X [i — 1, j] VX [i — 1, j — ai]
(C) X [i, j] = X [i — 1, j] VX [i, j — ai]
(D) X [i, j] = X [i — 1, j] VX [i -1, j — ai]

Ответ (Б)

X [I, j] (2 2. В вопросе 1, какая запись массива X, если она ИСТИНА, подразумевает, что существует подмножество, элементы которого суммируются с W?
(A) X [1, W]
(B) X [n, 0]
(C) X [n, W]
(D) X [n -1, n]

Ответ (С)
Если мы получим запись X [n, W] как true, то есть подмножество {a1, a2, .. an}, которое имеет сумму как W.

Ссылка: http://en.wikipedia.org/wiki/Subset_sum_problem

3. Рассмотрим следующую программу на C, которая пытается найти элемент x в массиве Y [] с помощью бинарного поиска. Программа ошибочная.

1.   f(int Y[10], int x) {

2.     int i, j, k;

3.     i = 0; j = 9;

4.     do {

5.             k =  (i + j) /2;

6.             if( Y[k] < x)  i = k; else j = k;

7.         } while(Y[k] != x && i < j);

8.     if(Y[k] == x) printf ("x is in the array ") ;

9.     else printf (" x is not in the array ") ;

10. }

На каком из следующих содержаний Y и x происходит сбой программы?
(A) Y представляет собой [1 2 3 4 5 6 7 8 9 10] и x 2
(D) Y представляет собой [2 4 6 8 10 12 14 16 18 20] и 2
4. В вопросе 3 исправление, необходимое для правильной работы программы,
(A) Измените строку 6 на: if (Y [k]

f(int Y[10], int x) {

   int i, j, k;

   i = 0; j = 9;

   do {

           k =  (i + j) /2;

           if( Y[k] < x)  i = k + 1; else j = k - 1;

       } while(Y[k] != x && i < j);

   if(Y[k] == x) printf ("x is in the array ") ;

   else printf (" x is not in the array ") ;

}

Ссылка: http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementations

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

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

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

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

0.00 (0%) 0 votes