2018年西安科技大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的
(以其中之一为0标志结束) ，对于每条这样的
边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。
提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:
建立有向图的邻接表存储结构
题目要求两顶点之一为0表示结束
2． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。
【答案】算法如下:
//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前
//用类C 语言编写，数组下标从0开始
//交换A[i]与
A[j]
//算法Arrange 结束
输入顶点信息
3． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(
) 改造为(
【答案】算法如下:
//本算法将线性表
//q指向a 1结点
//r记住a l 结点的指
针
//先将a 1结点放到正确位置
//从a 2结点开始
//暂存后继
//对称放置
//恢复待处理结点
4． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。
改造为
) 。
图
【答案】算法如下:
递增序输出二叉排序树中结点的值，滤去重复元素
中序遍历左子树
是当前访问结点的前驱，调用本算法时初值为
null
记重复元素，调用
本算法时初值为
前驱后移
中序遍历右子树
结束
算法
5． 假设K1，... ，Kn 是n 个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树。
(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立如图所示的二叉查找树。
图
该二叉查找树的嵌套括号表示结构为:B(A，D(C，E)) 。 【答案】(1)算法如下:
在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针
f
以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树
不再插入相同值结点
.
申请结点空间
根结点
左子女
右子女