2018年云南师范大学信息学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。
【答案】算法如下:
建立有向图的十字链表存储结构
假定权值为整型
建立顶点向量
当输入i 、j 、v 之一为0时，结
束算法运行
申请结点
弧结点中权值域
算法结束
2． 编写算法，将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。
图
【答案】算法如下:
//将自然数
，按" 蛇形M 填入n 阶方阵A 中
//i，j 是矩阵元素的下标，k 是要填入的自然数
//从右上向左下填数
//副对角线及以上部分的新i ，j 坐标
//副对角线以下的新的i ，j 坐标
//从左下向右上
//最外层
while
3． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。
图
【答案】算法如下:
递增序输出二叉排序树中结点的值，滤去重复元素
中序遍历左子树
是当前访问结点的前驱，调用本算法时初值为
null
记重复元素，调用
本算法时初值为
前驱后移
中序遍历右子树
结束
算法
4． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。
顺序存储结构的线性表描述为:
线性表可能达到的最大长度}；
【答案】算法如下:
//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值
//当査找失败时，low ＝high ＋
1
//结束对分査找函数
//本过程生成顺序表
L
//顺序表L 初始化
//设x ＝9999时退出输入
//去查找x 元素
//不同元素才插入
//插入元素x ，线性表长度增
1
//结束过程creat
5． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。
【答案】算法如下:
求以双亲表示法作为存储结构的树的深度