一、假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
答：
分析题目我们可以知道我们可以通过一个栈进行实现。首先，我们规定运算优先级：乘除法优先级大于加减法优先级。其中，对于同一运算符号，前面出现符号优先级大于后面出现的优先级。我们构建一个栈，然后依次读入，如果读入的数字，就把数字送入到数组中。如果读入的的是运算符，如果是空栈就push这个运算符，如果非空，开始循环，取出栈顶元素。将栈顶元素与读入的该运算符进行比较，如果栈顶的运算符优先级高，弹出栈顶运算符，就把该运算符送入数组。循环执行，遇到此时栈顶运算符优先级比判断运算符优先级低时，结束循环。最后返回得到的char*类型的字符数组便是逆波兰式。
该算法实现的伪代码如下：
/*
函数名称：将一般运算表达式转换为逆波兰表达式
函数传入参数：需要转换的表达式
函数返回值：char*类型 转换后得到的逆波兰表达式
*/
char * InversePolandExpression(char term[]) {
Stack S; //声明一个用于存放运算符的栈
char e; //用于获取栈顶元素;
char *ans; //用于返回答案
int i = 0, j = 0; //循环变量
while(term[i] != ' ') {
if(term[i] <= '9' && term[i] >= '0') { //如果读到的是数字
ans[j++] = term[i];
}
else {
while(!Empty(S)) { //如果栈S不为空
GetTop(S, &e); //获取栈顶元素
if(Priority(e, term[i])) //如果栈顶元素优先级更高
{
Pop(&S, &e); //弹出栈顶元素
ans[j++] = e; //送入数组
}
else{
break;
}
Push(&S, term[i]);
}
}
i++;
}
S.clear(); //清空栈
ans[j] = ' ';
return ans; //返回逆波兰表达式
}
算法分析：本算法时间复杂度为nlogn。空间占用一个栈的一个字符类型数组的空间。总的来说是用栈实现的较为高效的算法。
二、假设称正读和反读都相同的字符序列为“回文”，例如，’abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。试写一个算法算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。
答：
分析题目我们容易知道我们可以用一个栈实现回文串的判定。我们把输入字符的一半压入栈中（假设是奇数个字符我们压入(n-1)/2个）。然后如果是奇数个字符，我们从压入之后的第二个开始判断，偶数个直接开始判断。将栈顶元素与此时遍历到的元素进行比较。如果相等，弹出栈顶元素，继续进行比较。如果不相等，直接返回false代表不是“回文”。当遍历完成之后，最后的栈为空，返回true代表它是“回文”。
该算法实现的伪代码如下：
/*
函数名称：判断字符串是否是回文串
传入参数：str需要判断的字符串
返回值：布尔型 返回true代表是回文串 返回false代表不是回文串
*/
bool IsPalindromeString(char *str) {
Stack S;
int i = 0;
for(int i = 0; i < (str.size())/ 2; ++i) {
S.Push(str[i]);
//将字符串的一半压入栈中
}
if(str.size() & 1) { //如果字符串的长度为奇数
i++;
}
char e; //获得栈顶元素
for(; i < str.size(); ++i) {
GetTop(&S, &e); //获得栈顶元素
if(str[i] == e) { //判断栈顶元素与此时遍历的元素是否相等
Pop(&S, &e);
continue; //继续执行循环
}
return false;
}
return true;
}
算法分析：本算法的时间复杂度为O(n)。空间占用一个栈的空间。总的来说，是一个很高效的算法。
三、试利用循环队列编写求k阶斐波那契序列中前n+1项(f0，f1，...，fn)的算法，要求满足：fn≤max而fn+1>max，其中max为某个约定的常数。（注意：本题所用的循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项fn-k+1，...，fn）。
答：
由题目分析可知，我们可以通过一个循环链表实现该算法。传入的参数是k，最终得到的数组f以及数组元素的个数n和约定的常数max。首先当k小于2或者max<0时，出现错误输入，应当返回error。然后由k阶斐波拉契数列相关知识，我们需要把队列中前k-1项置为0，第k项置为1。然后，将f数组初始化为上述情况。然后执行循环，我们设置临时变量进行判断，temp为此时循环队列中的元素之和。循环的终止条件为temp>max。通过不断改变尾指针进行循环。最后留在循环队列中的元素便是最后k项。
该算法实现的伪代码如下：
Status GetKFibolacciSequence(int f[], int k, int max, int &n) {
if(max < 0 || k < 2) {
return error;
}
int n;
Queue Q;
initQueue(&Q); //创建一个空队列
//初始化
for(int i = 0; i < k - 1; ++i) {
EnQueue(&Q, 0);
}
EnQueue(&Q, 1);
for(int i = 0; i < k; ++i) {
f[i] = Q.base[i];
}
n = k - 2;
do{
n++;
int temp = 0;
//求和
for(int i = 0; i < Q.length; ++i) {
temp += Q.base[i];
}
fib[n + 1] = temp;
Q.base[Q.rear] = temp; //插入尾部
Q.rear = (Q.rear + 1) % MAXQSIZE;
//更新尾部
}while(temp<=max);
return ok;
}
算法分析：该算法使用了二重循环。在do...while语句中进行循环队列求和。然后实现了队列的不断更新，当运行结束后，便得到所求结果。该算法占用了一个队列的空间。对于这个问题来说，这是一个高效的算法。