Тест 3

Класът BinarySearchTree съдържа следната член-функция (Code Fragment 9.3):
 void setItem(const BTPosition& p,
                 const BSTItem& i) const
 {
    /*add*/
    p.element().setKey(i.key());
    p.element().setElement(i.element());
 }
Отбележете верни/неверни твърдения за тази функция.

(да) Функцията поставя Item от BST (речник) на позиция p в LinkedBinaryTree.
(РЅРµ)  Като заместим /*add*/ СЃ Element e = i.element(); получаваме синтактична грешка.


Отбележете верни/грешни твърдения за асимпотична оценка за следните функции:
 (РґР°) n2 e O(n3)
(РЅРµ) 3 + n2 e o(n)


Дадени са следните дефиниции:
int i = 4, j = 2, k = 1;
Определете дали дадената като коментар стойност е вярна/грешна стойност на израза.

(РґР°) i -= j // 2
(РЅРµ) j <<= j // 4


Посочете верни/неверни дефиниции и твърдения за търсещи дървета.

(да) Търсене в AVL дърво с n члена отнема време O(log n).
(не) Всеки вътрешен възел от многоканално търсещо дърво има най-много две деца.


Дадено е (2,4) дърво АТД: T = {12}({3,6,9},{15}). Външните възли не са включени в представянето. Определете дали даденото след операцията (2,4)-дърво е получено като резултат от прилагане на операцията.

(РґР°) insertItem(1) - T={6,12}({1,3}, {9},{15})
(РЅРµ) insertItem(1) - T={3,12}({1,6,9},{15})


Дадено е червено-черно дърво АТД, като черните възли са bold, а червените - italic. Външните възли не са включени
в представянето. Определете дали даденото след операцията червено-черно дърво е получено като резултат от прилагане на операцията.

(РґР°) 6(8) - insertItem(7) - 7(6,8)
- 5(7) - insertItem(6) - 5(6, 7)


Прост алгоритъм за разрешаване на колизии в хеш таблици e линейно пробване. Даден е клетъчен масив A = {35, 14, D, 21, E, 12, E} с капацитет N=7, където E означава "empty" и D означава "deattached" (или "available") елемент на масива. Хеш функцията e h(k) = k mod 7. Посочете верни/неверни съответствия, като след -> е дадено предполагаемото място на добавения елемент в масива.

(РґР°) insrtItem(7) -> A[2] = 7
(РЅРµ) insrtItem(10) -> A[3] = 10


Дадено е двоично дърво АТД: T = a(b(c(d,e),f),g(h,i(j(k,l),m)). Дали дадената редица е част от редицата от възли, получена чрез Ойлерово обхождане на двоичното дърво?

(РґР°) abcd
(РЅРµ) ecbc


Постройте двоично РґСЉСЂРІРѕ, представящо следния аритметичен израз:  (x + 2*(y - 2)) / 2. Дали дадената редица Рµ част РѕС‚ редицата РѕС‚ възли, получена чрез preorder обхождане РЅР° двоичното РґСЉСЂРІРѕ?

(РґР°) / + x
(РЅРµ) x + 2


Даден е стек АТД: S = (5,3,4,9). Върхът на стека е 5. Посочете вярно/невярно съответствие функция - върната стойност - стека S след изпълнението на функцията.

(РґР°) push(1) - NONE - S=(1,5,3,4,9)
(РЅРµ) push(10) - NONE - S=(5,3,4,9,10)


Дадена е опашка АТД: Q = (8,7,2). Начало на опашката е елементът 8. Посочете вярно/невярно съответствие функция - върната стойност - опашката Q след изпълнението на функцията.

(РґР°) enqueue(5) - NONE - Q=(8,7,2,5)
(РЅРµ) enqueue(7) - 7 - Q=(8,7,2,7)


Даден е дек АТД: D = (8,1,3). Начало на дека е елемантът 8. Посочете вярно/невярно съответствие функция - върната стойност - декът D след изпълнението на функцията.

(РґР°) insertFirst(5) - NONE - D =(5,8,1,3)
(РЅРµ) insertFirst(6) - NONE - D =(8,6,1,3)


Дадено е AVL дърво: 44(17(-,32),78(50(48,62),88)). Външните възли не са включени в представянето. Определете дали даденото след операцията AVL дърво е получено като резултат от прилагане на операцията.

(РґР°) insertItem(54)\\ 44(17(-,32),62(50(48,54),78(-,88)))
(РЅРµ) removeItem(32) 44(17,78(50(48,62),88))


Дадено е двоично дърво. Да се провери дали редицата след ; е част от inorder обхождане на дървото.

(РґР°) c(b(a,d),e);bdc
(РЅРµ) c(b(a,d),e(f,g));cfd


Постройте двоично дърво, представящо дадения аритметичен израз и проверете дали редицата x2y e част от postorder обхождане на полученото дърво.

(РґР°)  x+2*y
(РЅРµ) x/2-y


Класът Position e включен в дефиницията на класа BinarySearchTree (Code Fragment 9.2). Отбележете верни/неверни твърдения за член-функцията
 Element& element()             
 {
    return btPos.element().element();
 }
РѕС‚ class Position.

(да) Върнатата стойност е псевдоним на член-данна на класа Item.
(не) btPos e член-данна в класа BinarySearchTree.

 
Посочете верните и неверни дефиниции и твърдения за линейни структури от данни.

(да) Дек е контейнер от обекти, който поддържа добавяне и изваждане от двата края на редицата.
(не) Линейна редица, която поддържа достъп до елементите си чрез техните рангове се нарича списък.


Отбележете верни/грешни дефиниции за асимптотични нотации.

(да) f(n) e O(g(n)), ако има положителни константи c и N, такива, че f(n)<cg(n) за n>N.
(не) g(n) e O(f(n)), ако има положителни константи c и N, такива, че f(n)<cg(n) за всяко n>N.


Даден е следния код:
 void fun1()
 { throw runtime_error("ERR" ); }
 void fun2() throw(runtime_error)
 { ... }
 void fun3() throw(runtime_error)
 { fun2(); }
 int main()
 { try
   { fun3(); }
   catch (runtime_error e)
   {
    cout << e.what();
   }
   return 0;
 }
Като заместим ... с дадения оператор, дали ERR ще се отпечати на екрана?

(РґР°) fun1();
(РЅРµ) fun2();


Посочете верните/неверните дефиниции и твърдения за дървета.

(да) Ако възел u е родител на възел v, казваме, че v е дете на u.
(не) Един възел е вътрешен, ако няма деца и външен, ако има едно или повече деца.