Di Zad2012

Задачи и решения от изпита през 2012

Тази страница бе започната, защото от университета не пожелаха да дадат задачите от миналата година(2011), когато те бяха поискани. Задачите са плод на добрата памет на авторите, така че е възможно да има грешки и неточности. Ако някой забележи такива, моля да ги поправи.

Общият брой точки от задачите е 110 т., като за отличен е над 60 точки. Времето за работа - 3 астрономически часа.

1 Задача (10 т.)

Имаме масив от летища A[1…n]. За всяко летище A[i] имаме даден списък на съседите, чрез който се предоставя информация до кои летища A[i] има директна връзка, като всяко едно летище не може да има директно връзка със себе си. Да се напише възможно най-бърз алгоритъм (асимптотически), който извежда "Yes" в случай, че съществува летище, такова че ако тръгнем от него, то след няколко директни прехода ще стигнем отново до него, и "No" в противен случай.

Накратко: представяме схемата от летища като ориентиран граф, който дори може да не е свързан. Пита се: дали съществува цикъл (контур в ориентирания случай) в графа.

2 Задача (10 т.)

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

Пример: имаме 6 предмета с цени: 1 8 6 3 2 4
Възможно разбиване е {1, 6, 3, 2} и {8, 4}, тъй като 1 + 6 + 3 + 2 = 8 + 4.

Решение:

3 Задача (10 т.)

Даден е сортиран масив от цели числа. Имаме клас Node (Java вариант), предоставящ възел в двоично дърво:

class Node {
    public int Data;
    public Node Left;
    public Node Right;
}

Да се напише функция buildTree(int[] array), която построява двоично балансирано дърво за търсене, съдържащо елементите на масива.
Езикът за програмиране може да е C++/Java.
Припомняме какво е двоично балансирано дърво за търсене:
- всеки връх има най-много 2 наследника;
- всички възли, намиращи се вляво от конкретен възел, са по-малки или равни на него (относно полето Data), а всички вдясно - по-големи или равни на него;
- разликата между височината на лявото поддърво и тази на дясното е най-много едно.

Решение:

4 Задача (10 т.)

Да се напише на езика Scheme или на Haskell (по избор) процедурата countLists, която при подаден списък от списъци - връща броя на списъците, които съдържат поне по един елемент от другите списъци. Ето пример:
(countLists '((1 2 3) (3 4 5) (3 6 7) (4 1 8) (3 2 1))) -> 3

Забележка: С риск да объркам някого - хората искаха да покажем броя на тези елементи на фамилията от множества, които всъщност са трансверзали за фамилията (справка за трансверзала - логическо програмиране / теория на множествата)

Решение:

5 Задача (15 т.)

Да се дефинира абстрактен клас, представящ обекта превозно средство - информацията, която се съхранява, е годината на производство на превозното средство. Да се имплементират класове, представящи обектите кола и автобус (наследявайки базовия клас). Класът за кола съхранява параметър, определящ типа на колата - седан, кабрио или комби. Класът за автобус има параметър, съхраняващ информация за максималния брой пътници, които може да събере. И двата класа имат член, извличащ тяхната такса при престой на паркинг. При автомобил таксата се определя по следния начин: година на произвеждане се умножава по 2, в случай че типът на колата е седан или кабрио, или по 3, ако типът е комби. При автобусите: годината на произвеждане се умножава по броя пътници.
Да се предостави вътрешен начин за извличане на общия брой създадени превозни средства в цялата йерархия от класове.
Да се имплементира клас, представящ обекта паркинг. Паркингът има параметър, указващ максималния брой места. Да се дефинират методи за добавяне (в края на паркинга) и изтриване (от края на паркинга) на превозно средство. Да се дефинира метод, който изчислява таксата на всички превозни средства, стоящи на паркинга в момента.

Език за програмиране: Java/C++

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

6 Задача (10 т.)

Даден е двоичен файл и в него са записани обекти от тип:

struct Person {
    int Age;
    char[40] Name;
}

Да се напише програма, която приема файла като аргумент и сортира обектите вътре в лексикографски нарастващ ред спрямо тяхното име. Ако двама души имат еднакви имена - този, който е по млад, трябва да е на по - предна позиция.

Забележка: тъй като не бяхме учили C и такъв курс не присъства в нашия учебен план, комисията позволи да се ползва Java като обектът Person би трябвало да приеме вида:

class Person {
    public int Age;
    public String Name;
}

7 Задача (10 т.)

Нормална задача по бази от данни, както от миналите години. Задачата се състои от две подточки и се пита при всяка една от тях - коя заявка е правилна (отговаря на дадено условие), като има по 4 възможни отговора. Базата, която се използваше, беше известната SHIPS.

8 Задача (10 т.)

Нека $\mathcal{L}$ е език на предикатно смятане от 1ви ред с единствен триместен предикатен символ $p$. Нека $A_n$ е множество от структури за $\mathcal{L}$ с универсум $\{1, 2, \ldots, n\}$. Нека $B_n$ са онези от тях, в които е вярна формулата $\forall x p(x, x, x)$. Да се намери границата $\lim_{n \to \infty} \frac{A_n}{B_n}$
Решение:

9 Задача (15 т.)

Дадена е матрицата:

(1)
\begin{align} A = \begin{pmatrix} 0 & 1 & -1 & 1 \\ 1 & 0 & 1 & -1 \\ -1 & 1 & 0 & 1 \\ 1 & -1 & 1 & 0 \end{pmatrix} \end{align}

Да се намерят диагонална матрица $D$ и ортогонална матрица $T$, такива че $D= TAT^{-1}$.
Решение:

10 Задача (10 т.)

Да се реши неопределения интеграл:

$\int \frac{dx}{x(ln^2x + 1)^2}$
Решение:

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License