Структури от данни, зимен семестър 2022/2023

Задача 1[25 т]. Да се дефинира функция most_common, която по линеен едносвързан списък намира стойността на този негов елемент, който се среща най-често (или един от тях, ако са няколко).

Задача 2[25 т]. Нека е даден следния тип на възел от кореново дърво:

template <typename T>

struct TNode { T data; std::vector<TNode*> children; };

Да се напише функция ordered_levels (t), която проверява дали елементите на всяко ниво в дървото, четени отляво надясно, са подредени относно ралацията “<=”.

Задача 3[35 т].  Да се напише функция create_tree, която по въведен от клавиатурата текст t с произволна големина, съставен само от думи с малки букви и интервали, създава двоично наредено дърво, чиито елементи са двойки от тип pair<string,int>. Дървото да съдържа по един възел за всяка различна дума w в текста, като вторият елемент на двойката, съдържаща дадено дума w, да съдържа броя на срещанията на w в t. Наредбата на елементите на дървото да е лексикографска относно думите във възлите му. На примера по-долу е изобразено едно възможно дърво, което се получава от текста “hello there hello again again again”.

Задача 4[35 т]. Да се дефинира шаблон на клас Spreadsheet, описваща правоъгълна матрица с елементи от някакъв тип T, чиито редове са индексирани с числата “0,...,4 294 967 295”, а колоните - с буквите ‘A’...’Z’. Класът да поддържа три операции:

• set(row,col,value) за записване на стойност в клетка от таблицата.
• get(row,col) за прочитане на стойност от клетка от таблицата. При прочитане на клетка, чиято стойност не е зададена, операцията може да върне произволна стойност. 
• max() намира най-голямата стойност (относно релацията <=) в таблицата