Поправителен писмен изпит ПЪРВИ поток - вариант А
Моля, предайте всички файлове с код в ZIP архив със следното име:
groupX_varY_FN.zip
където X е номерът на групата, с която посещавате упражнения, Y е номерът на варианта, а FN е факултетния Ви номер.
Не включвайте в ZIP архива компилирани, изпълними, обектни, дебъг, проектни или всякакви други файлове!
Задача 1. Разглеждаме вариант на структурата опашка, наречен „опашка с пререждане“, в който има допълнителна операция, която позволява в началото на опашката да се наредят подаден масив от n елемента, „пререждайки“ останалите.
а) (0,50) Да се реализира шаблон SkipQueue, която прави динамична реализация на „опашка с пререждане“. Позволено е използването на структурите от данни, взимани на лекции, както и стандартните шаблони от STL, но дефинираният шаблон трябва да поддържа само стандартните за опашка операции и допълнителната операция “пререждане”, както и селектор за брой елементи в опашката.
б) (0,50) Работното време на гише в център за обслужване на клиенти е от 9 до 17 часа. Да се реализира хетерогенен списък, който съдържа два вида клиенти:
-
обикновен клиент, за който се пазят име (низ с произволна дължина), точен час на нареждане на гишето (час и минути в рамките на работното време), и време, необходимо за обслужване (цяло число минути);
-
клиент с връзки, за който освен данните за обикновен клиент съдържа и положително цяло число n, указващо колко от следващите клиенти освен него „пререждат“ опашката.
в) (0,25) За списъка да се реализира метод, който добавя клиент на подходящо място в списъка, така че клиентите в него да са подредени във възходящ ред по час на нареждане на гишето.
г) (1,00) Да се реализира функция, която приема хетерогенен списък от горния вид и с помощта на шаблона SkipQueue прави симулация на работата на гишето, като при всяко едно от следните събития се извежда информация за името на съответния клиент, текущ час и дължина на опашката след събитието:
-
нареждане на опашката на клиент
-
„пререждане“
-
начало на обслужване на клиент (при това събитие клиентът остава на опашката)
-
край на обслужване на клиент
Когато клиент с връзки се нарежда на гишето той винаги прережда опашката, като със себе си взема и следващите n клиента от списъка, без да се взима под внимание точния час, в който те са щели да се наредят на гишето при нормални обстоятелства. Упътване: не е нужно и опашката да е хетерогенна.
Примерен вход:
|
Име |
Час |
Време за обслужване |
С връзки? |
|
Ivan |
9:05 |
10 мин. |
не |
|
Stefan |
9:07 |
8 мин. |
не |
|
Mihail |
9:10 |
15 мин. |
да, взима 2 клиента |
|
Albena |
9:15 |
5 мин. |
не |
|
Boris |
9:20 |
10 мин. |
не |
Примерен изход:
Ivan се нарежда на опашката в 9:05. Дължина на опашката: 1.
Ivan започва да бъде обслужван в 9:05. Дължина на опашката: 1.
Stefan се нарежда на опашката в 9:07. Дължина на опашката: 2.
Mihail, като клиент с връзки, прережда опашката в 9:10, като взема Albena, Boris със себе си. Дължина на опашката: 5.
Обслужването на Ivan завършва в 9:15. Дължина на опашката: 4.
Mihail започва да бъде обслужван в 9:15. Дължина на опашката: 4.
Обслужването на Mihail завършва в 9:30. Дължина на опашката: 3.
Albena започва да бъде обслужвана в 9:30. Дължина на опашката: 3.
Обслужването на Albena завършва в 9:35. Дължина на опашката: 2.
Boris започва да бъде обслужван в 9:35. Дължина на опашката: 2.
Обслужването на Boris завършва в 9:45. Дължина на опашката: 1.
Stefan започва да бъде обслужван в 9:45. Дължина на опашката: 1.
Обслужването на Stefan завършва в 9:53. Дължина на опашката: 0.
Задача 2. Свойствата на даден предмет се описват с речник, съпоставящ на имената на свойствата (низове с произволна дължина) техните стойностите дробни числа.
а) (0,50) Да се реализира клас Object, който представя предмет с име (низ с произволна дължина) и речник от свойства.
б) (0,50) Разглеждаме йерархия от предмети, представена с дърво от предмети, в който всеки възел има произволен брой наследници. Всеки предмет наследява свойствата и стойностите им от предшествениците си в йерархията, като стойностите на свойствата, зададени в речника на предмета, са с по-висок приоритет от наследените стойности на свойства и ги презаписват. Да се реализира дърво, представящо такава йерархия, като управлява коректно паметта.
в) (0,75) Да се реализира метод на дървото, който по име на предмет извежда свойствата на предмета и техните стойности, като за всяко свойство указва дали стойността е собствена или ако е наследена, от кой негов предшественик е наследена.
Примерно дърво: Примерен изход
за Car:
maxSpeed: 150 (own)
weight: 100 (from Vehicle)
numDoors: 4 (own)
за SportsCar:
maxSpeed: 200 (own)
weight: 900 (own)
numDoors: 4 (from Car)
turboBoost: 50 (own)