2018年西藏大学藏文信息技术研究中心840计算机专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
在后半部分继续进行划分
在前半部分继续进行划分
2． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下:
在中序线索树t 上，求结点p 的双亲结点q
暂存
找P 的中序最右下的结点
顺右线索找到q 的后继(P的袓先结点
)
若后继是头结点，则转到根结点
根结点无双亲
找最右结点的过程中回找到P
第 2 页，共 32 页
) 小元素。
准备到左子树中找
P
结束FFA
3． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。
【答案】算法如下:
将满二叉树的后序序列转为前序序列，
标。
根结点
左子树或右子树的结点数
将左子树前序序列转
为后序序列
将右子树前序序列转为
后序序列
4． 起泡排序算法是把大的元素向上移(气泡的上浮) ，也可以把小的元素向下移(气泡的下沉；请给出上浮和下沉过程交替的起泡排序算法。
【答案】算法如下:
相邻两趟向相反方向起泡的起泡排序算法，
起泡的上下界
设不发生交换
以上向下起泡
有交换，修改标志
change
修改界
气泡下沉，小元素上浮(向左
)
修改下界
5． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
第 3 页，共 32 页
是序列初始和最后结点的下
n 为偶数时
r 最小值
("最大值
) ；
二、应用题
6． 如果输入序列为123456，试问能否通过栈结构得到以下两个序列:435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素(4356)得到后，栈中元素剩12，且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下:1入栈并出栈，得到部分输出序列1; 然后2和3入栈，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
7． 在堆排序、快速排序和合并排序中:
(1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？
(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 【答案】(1)应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 (2)应选取归并排序方法 (3)应选取快速排序方法 (4)应选取堆排序方法
8． 画出对算术表达式表所示。
表 操作数栈和运算符栈的变化过程
F 求值时操作数栈和运算符栈的变化过程。
F 求值，过程如
【答案】设操作数栈是opnd ，运算符栈是optt ，对算术表达式
第 4 页，共 32 页
相关内容
相关标签