1. Да се реализира функция, която слива два едносвързани списъка от числа, подредени в нарастващ ред, така че резултатът да съдържа всички числа отново в нарастващ ред.
  2. Кое от следните твърдения за алгоритми над графи е вярно (с n е означен броят на върховете):
    1. Обхождането на граф в дълбочина винаги е по-бързо от обхождането му в ширина.
    2. Обхождането на граф в ширина винаги е по-бързо от обхождането на граф в дълбочина.
    3. Обхождането на граф в ширина заема в най-лошия случай памет O(n)
    4. Обхождането на граф в дълбочина отнема в най-лошия случай време O(n)
  3. Да се посочат едно предимство и един недостатък на представянето на граф чрез матрица на съседство
  4. Да се открият и поправят грешките в следната реализация на търсене на елемент в двоично наредено дърво:
    void search(T const& x) {
      I it = iterator();
      while (*it != x) {
        if (it < x) it = ++it;
        if (it >= x) it = it++;
      }
      return *it;
    }  
  5. Кой от следните оператори правилно отваря текстовия файл students.txt за четене
    1. istream("students.txt", ios::open);
    2. ifstream if("students.txt");
    3. ifstream fi("students.txt", ios::in);
    4. ifstream::open("students.txt", ios::text);
  6. Да се даде пример за физическо представяне на структурата от данни стек.
  7. Да се опише в какъв ред ще бъдат изведени елементите на следното дървото при обхождане дясно-ляво-корен.Пример за двоично дърво
  8. Кое от следните твърдения за балансирани двоични дървета е вярно?
    1.   Ако в дадено двоично дърво броят на елементите в лявото и дясното му поддърво се различава с най-много 1, то е идеално балансирано.
    2.   Има идеално балансирани дървета, които не са балансирани.
    3.   Не всяко двоично дърво е балансирано, но всяко двоично наредено дърво е балансирано.
    4.   За всяко балансирано дърво височината на лявото и дясното поддърво се различават с не повече от 1.
  9.  Да се предложи примерна йерархия от класове, която позволява реализацията на хетерогенен списък от речници, всеки от които може да е с различна реализация: сортиран масив, AVL дърво или хеш таблица.

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

    1. \(O(1.01^n)\)
    2. \(O(n^3)\)
    3. \(O(n \log^4 n)\)
    4. \(O(1000000)\)
  11. Да се предефинират операторите >> и << за вход от и изход към поток за следния клас:
    class Taxi {
    private:
      char company[50];
      double rate;
    };
Последно модифициране: сряда, 10 февруари 2016, 13:51