Примерни задачи за изпит по Структури от данни и програмиране

Вариант А


Задача 1. Даден е двоичен файл products.dat, съдържащ структури от вида struct Product { char name[200]; int code; double price; }; описващи продукти с име, код и цена. Даден е и текстов файл codes.txt, съдържащ описанието на кодовете като редове с вида

<code> <description>

Да се напише функция, която създава текстов файл codeReport.txt, съдържащ редове от вида

<code> <name1> … <namek> <average_price> <description>

като на всеки ред са изброени имената на всички продукти отговарящи на дадения код, средната им цена и описанието на кода. Всички продукти, чиито код не се намира в codes.txt да се изброят под код 0 на последния ред на codeReport.txt и кодът им във файла products.dat да се промени на 0.

Задача 2. Дадени са два стека от числа, подредени в намаляващ ред от върха към дъното. Да се напише функция mergeStacks, която чрез операциите push и pop построява нов стек, който се състои от всички елементи на дадените два стека, подредени в нарастващ ред от върха към дъното.

Пример: ако първият стек съдържа 5, 3, 1, а вторият стек съдържа числата 6, 2, 1, полученият стек трябва да съдържа числата 1, 1, 2, 3, 5, 6.

Задача 3. Да се напише функция int sumNodes(tree<int> const& t), която по дадено двоично дърво от цели числа t намира сумата от тези от тях, които са по-малки от родителя си, но са по-големи от децата си.

Задача 4. а) Да се напише шаблон на функция bool singleChild(graph<T>& g, T const& a), която проверява дали е вярно, че върхът a е единствено дете на всичките си родители;

б) Път в ориентиран граф наричаме “ласо”, ако всички върхове в него са различни, с изключение на последния, който съвпада с някой друг връх от пътя. Пример: пътят 1, 2, 3, 4, 2 е ласо. Да се напише шаблон на функция LList<T> longestLasso(graph<T>& g), която намира най-дългото ласо в даден граф, или връща празен списък, ако такова няма. При наличие на няколко най-дълги ласа, да се върне някое от тях.





Вариант Б

Задача 1. Даден е  двоичен файл orders.dat, съдържащ структури от вида struct Order { char product[200]; int quantity; double pricePerUnit; }; описващи поръчки с име на продукт, количество и цена на единица количество. Даден е и текстов файл products.txt, съдържащ описанието на наличните продукти на склад като редове с вида

<product> <quantity_in_stock>

Да се напише функция, която създава текстов файл productsSale.txt, съдържащ редове от вида

<product> <newQuantity> <income>

като на всеки ред са изброени имената на всички продукти, новото количество в склада (останало след изпълнение на всички поръчки и общия приход за дадения продукт. Поръчките за продукти, които не са налични на склад (няма ги описани в products.txt или количеството в склада не е достатъчно, за да покрие поръчката) да бъдат анулирани, като във файла orders.dat в полето quantity бъде записано 0.


Задача 2. Дадени са двe опашки от числа, подредени в нараства ред от началото към края на опашката. Да се напише функция mergeQueues, която чрез операциите InsertElem и DeleteElem построява нова опашка, която се състои от всички елементи на дадените две опашки, подредени в нарастващ ред от началото към края.

Пример: ако първата опашка съдържа 1, 3, 5, а втората опашка съдържа числата 1, 2, 6, получената опашка трябва да съдържа числата 1, 1, 2, 3, 5, 6.


Задача 3. Да се напише функция bool readWord(tree<char> const& t, char const* w), която по дадено двоично дърво от символи t, проверява дали думата w може да бъде прочетена в дървото в посока от корена към листата. Не е задължително първата буква на думата да е корена, нито последната да е някое листо.

Задача 4.

а) Да се напише шаблон на функция int countNodes(graph<T>& g), която намира броя на върховете в графа g, които имат повече родители, отколкото деца;

б) Път в ориентиран граф с числа по върховете наричаме “стълба”, ако всеки връх е с единица по-голям от предходния, а последният връх е два пъти по-голям от първия. Пример: пътят 2, 3, 4 е стълба. Да се напише функция LList<int> shortestLadder(graph<int>& g), която намира най-късата стълба в даден граф, или връща празен списък, ако такава няма. При наличие на няколко най-къси стълби, да се върне някоя от тях.


Последно модифициране: вторник, 4 февруари 2014, 22:00