1. Да се реализира функция, която слива два едносвързани списъка от числа, подредени в нарастващ ред, така че резултатът да съдържа всички числа отново в нарастващ ред.
  2. Кое от следните твърдения за алгоритми над графи е вярно (с n е означен броят на върховете):
    1. Обхождането на граф в дълбочина винаги е по-бързо от обхождането му в ширина.
    2. Обхождането на граф в ширина винаги е по-бързо от обхождането на граф в дълбочина.
    3. Обхождането на граф в ширина заема в най-лошия случай памет, линейна по n
    4. Обхождането на граф в дълбочина отнема в най-лошия случай памет, линейна по n
  3. Да се посочат едно предимство и един недостатък на представянето на граф чрез матрица на съседство
  4. Да се открият и поправят грешките в следната реализация на търсене на елемент в двоично дърво за търсене:
    void search(T const& x) {
      P pos = rootPosition();
      while (*pos != x) {
        if (pos < x) pos = pos.left();
        if (pos >= x) pos = pos.right();
      }
      return *pos;
    }  
  5. Да се даде пример за физическо представяне на структурата от данни стек.
  6. Да се опише в какъв ред ще бъдат изведени елементите на следното дървото при обхождане дясно-ляво-корен.Пример за двоично дърво
  7. Кое от следните твърдения за балансирани двоични дървета е вярно?
    1.   Ако в дадено двоично дърво броят на елементите в лявото и дясното му поддърво се различава с най-много 1, то е идеално балансирано.
    2.   Има идеално балансирани дървета, които не са балансирани.
    3.   Не всяко двоично дърво е балансирано, но всяко двоично наредено дърво е балансирано.
    4.   За всяко балансирано дърво височината на лявото и дясното поддърво се различават с не повече от 1.

  8.  Да се предложи примерна йерархия от класове, която позволява реализацията на хетерогенен списък от речници, всеки от които може да е с различна реализация: сортиран масив, AVL дърво или хеш таблица.

  9. Коя от следните сложности е най-висока?

    1. Експоненциална
    2. Кубична
    3. Логаритмична
    4. Константна
Last modified: Saturday, 11 February 2023, 9:45 PM