2018年西安科技大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
向右
访问根结点
找被访问结点的双亲
结束
2． 设记录
的关键字为
。，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
第 2 页，共 40 页
的双亲结点
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
3． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。
【答案】算法如下:
层次遍历二叉树，并统计度为1的结点的个数
统计度为1的结点的个数
是以二叉树结点指针为元素的队列
出队，访问结点
度为1的
结点
非空左子女入队
非空右子女入队
返回度为1的结点的个数
4． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的
(以其中之一为0标志结束) ，对于每条这样的
边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。
提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:
建立有向图的邻接表存储结构
题目要求两顶点之一为0表示结束
第 3 页，共 40 页
输入顶点信息
5． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。
顺序存储结构的线性表描述为:
线性表可能达到的最大长度}；
【答案】算法如下:
//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值
//当査找失败时，low ＝high ＋
1
//结束对分査找函数
//本过程生成顺序表
L
//顺序表L 初始化
//设x ＝9999时退出输入
//去查找x 元素
//不同元素才插入
//插入元素x ，线性表长度增
1
//结束过程creat
二、应用题
6． 对一个有
t 个非零元素的矩阵，用
第 4 页，共 40 页
的数组来表示，