Рубрики

Структуры данных и алгоритмы | Комплект 5

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

1. Рассмотрим следующую функцию C.

float f(float x, int y) 

  float p, s; int i; 

  for (s=1, p=1, i=1; i < y; i ++) 

  

    p*= x/i; 

    s+=p; 

  

  return s; 

}   

Для больших значений y возвращаемое значение функции f наилучшим образом приближается (GATE CS 2003)
а) х ^ у
б) е ^ х
c) ln (1 + x)
г) х ^ х

Ответ (б)
Функция f () является реализацией Серии Тейлора для вычисления e ^ x

   e^x = 1 + x + x^2/2! + x^3/3! + ---

Чем больше значение y, тем точнее значение e ^ x будет возвращено функцией f ()

Ссылки:
http://en.wikipedia.org/wiki/E_%28mathematical_constant%29

2. В худшем случае количество сравнений, необходимых для поиска односвязного списка длины n для данного элемента, равно (GATE CS 2002)
а) log 2 n
б) н / 2
в) log 2 n — 1
г) н

Ответ (г)
В худшем случае искомый элемент должен сравниваться со всеми элементами связанного списка.

3. Элементы 32, 15, 20, 30, 12, 25, 16 вставляются один за другим в указанном порядке в Max Heap. Результирующая Max Heap есть.

Ответ (а)

4. Рассмотрим следующие три утверждения
I (n + k) ^ m = Θ (n ^ m), где k и m — постоянные
II 2 ^ (n + 1) = 0 (2 ^ n)
III 2 ^ (2n + 1) = 0 (2 ^ n)
Какие из этих утверждений верны? (GATE CS 2003)

(а) I и II
(б) I и III
(с) II и III
(d) I, II и III

Ответ (а)

(I)  (n+m)^k = n^k + c1*n^(k-1) + ... k^m = Θ(n^k)
(II)  2^(n+1) = 2*2^n = O(2^n)

5. Единый массив A [1..MAXSIZE] используется для реализации двух стеков. Два стека растут с противоположных концов массива. Переменные top1 и top2 (topl
а) (top1 = MAXSIZE / 2) и (top2 = MAXSIZE / 2 + 1)
б) top1 + top2 = MAXSIZE
c) (top1 = MAXSIZE / 2) или (top2 = MAXSIZE)
г) top1 = top2 -1

Ответ (г)
Если мы хотим использовать пространство эффективно, то размер любого стека может быть больше, чем MAXSIZE / 2.
Оба стека будут расти с обоих концов, и если одна из вершин стека достигнет другой вершины, то стеки будут заполнены. Таким образом, условие будет top1 = top2 -1 (учитывая, что top1
Пожалуйста, напишите комментарии, если вы найдете какие-либо из приведенных выше ответов / объяснений неверными.

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

Структуры данных и алгоритмы | Комплект 5

0.00 (0%) 0 votes