2018年广西民族大学软件学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。
(1)编写用前序遍历树中每个结点的非递归算法；
(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:
全局变量
递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为
1)
是桟s 的栈顶指针，栈容量足够大
访问根结点，设虚结点
以0表示
右子女的下标位置入
栈
沿左子女向下
取出栈顶元素
结束
(2)算法如下:
打印最大序号叶结点的全部袓先
找最大序号叶结点，该结点存储时在最后
的双亲结点
f
从结点c 的双亲结点直到根结点，
路径上所有结点均为祖先结点
逆序输出，最老的祖先最后输出
结束
2． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
第 2 页，共 39 页
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
3． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？
(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。
【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下:
图中顶点的最大个数
弧(边) 结点
是邻接点在顶点向量中的下标，num 是边的编号
指向下一邻接点的指针
与弧(或边) 相关的信息指针
顶点结点
顶点信息及指向第一邻接点
的指针
邻接表
修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。
第 3 页，共 39 页
用邻接表作为存储结构的深度优先遍历算法
第一邻接点
结束dfs （ ）
求顶点的度
若顶点度为0, 或顶点的度不是偶
数，无解
无解
4． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 第 4 页，共 39 页