2018年郑州大学联合培养单位安阳师范学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
【答案】(1)递归算法如下:
递减序输出二叉排序树t 中所有左子树为空右子树非空的结点数据域的值
(2)非递归算法如下:
递减序输出二叉排序树t 中所有左子树为空、右子树非空的结点的数据域的值
S 是二叉排序树结点指针的栈，容量足够大
沿右分支向下
去左分支
算法结束
2． 编写算法，将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。
图
【答案】算法如下:
//将自然数，按" 蛇形M 填入n 阶方阵A 中
//i，j 是矩阵元素的下标，k 是要填入的自然数
//从右上向左下填数
//副对角线及以上部分的新i ，j 坐标
//副对角线以下的新的i ，j 坐标
//从左下向右上
//最外层
while
3． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。
【答案】算法如下:
//本算法将无符号十进制整数m 转换为十六进制整数
本算法的递归描述如下:
//本算法将无符号十进制整数m 转换为十六进制整数
4． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
0 //选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
是马鞍点，
元素值是
是马鞍点
5． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
(1)下面所示的序列中哪些是合法的？
A.
B.
C.
D.
(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。
【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:
//判断字符数组A 中的输入输出序列是否是合法序列。
//i为下标
//j和k 分别为I 和字母O 的个数
//
相关内容
相关标签