信管软件11级数据结构课程设计(5)

请实现求M(x)= Am(x)+Bn(x) 要求：

1) 结果M(x)中无重复阶项和无零系数项； 2) 要求输出结果的升幂和降幂两种排列情况

17. 利用栈求表达式的值，可供小学生作业，并能给出分数。（难度*） 要求：（1）判断表达式是否正确，主要是括号问题

（2）题目涉及加减乘除，带括弧的混合运算

18. 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实

现，应包含建树的实现。（难度*） 要求：遍历的内容应是千姿百态的。

19. 敢死队问题（难度**）

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

20. 猴子吃桃子问题（难度**）

有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求：

1) 采用数组数据结构实现上述求解 2) 采用链数据结构实现上述求解 3) 采用递归实现上述求解

21. 数制转换问题（难度**）

将一个十进制数转换为二、八、十六进制数

22. 排序综合（难度**）

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求：

1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、

起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。

2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出

其中两种较快的方法。

23. 最小生成树求解实现（难度**） 要求：