3/4
6. 约定多边形的顶点按逆时针序列表示，即 P={v0, v1, …, vn-1} 表示一个多边形 有 n 条边：v0v1, v1v2, …, vn-1vn。其中，v0=vn。如果 vi 和 vj 是多边形上不相邻的 两个顶点，则线段 vivj 称为该多边形的一条弦。下面图 5 中的(a)和(b)是一个凸 7 边形的两种不同的三角剖分（各弦互不相交） 。在一个有 n 个顶点的凸多边 形的三角剖分中，恰好有 n-3 条弦和 n-2 个三角形。 给定一凸边形 P={v0, v1, …, vn-1}以及定义在由凸边形的边和弦组成的三角 形上的权值函数 w。请设计算法：确定该凸边形的一个三角剖分，使得该三角 剖分中所有三角形上权值之和为最小，并给出三条边权值之和最小的三角形。 （本题满分 1二叉树，请给出按后序周游该树的结点序列，并画出该二叉树 的中序穿线二叉树存储表示。 （本小题满分 7 分）
1/4
(5) 以下算法实现从二叉排序树中删除结点，并重新连接它的左右子树。请在 4 个空缺处填上适当的内容，使该算法完整。请把答案写在答卷纸上，注 明空缺处的编号和其对应的内容。另外，下面的图 3 为一二叉排序树，请 画出删除结点 P 之后的情况。 Status Delete(BiTree &p) { if (!p -> rchild) { q = p; p = p-> lchild; } else if(!p -> lchild) { q = p; p = p-> rchild; } else{ q = p; s = p -> lchild; while (s -> rchild) { p -> data = s-> data; if (q != p) ③ else ④ delete s; } return TRUE; // Delete
请用表达式描述该多项式的广义表表示， 并设计该多项式的广义表存储结构。 (本小题满分 7 分) (3) 图 1 是一个有向图。请分别画出从顶点 V1 出发其深度优先搜索和广度优 先搜索的生成森林。
V1 V2 V3 V5 V6 V7 V8 B V4 D E F C
（本小题满分 6 分）
A
G
H
I
图 1. 有向图
中国科学院自动化研究所 2015 年招收攻读博士学位研究生入学考试题
考试科目： 算法设计与分析
（共 4 页，6 个大题，满分 100 分，时间为 3 个小时） 说明：算法设计可以用类程序语言描述。 1. 完成下列各题 （本题包括 6 个小题，满分 40 分） ： (1) 希尔排序（Shell’s Sort）又称缩小增量排序。现有如下 10 个关键字： 49，38，65，97，76，13，27，49，55，4 请写出每一趟希尔排序的结果，并说明希尔排序算法的时间复杂度。 （本小题满分 7 分） (2) 有如下三元多项式：
C L W
……
……
A H
……
I
O
A
E O $
$
$
$
N G $
N $
图 4. 姓氏“CAI, CAO, CHANG, CHAO, CHEN” 的键树示意图 5. 请设计一个模式匹配算法， 其中模板 Pattern 含有通配符“？”和“*”。字符 “?”可以和任意字符匹配，而字符“*”可以和任意长度的字串匹配。该算 法可搜索字符串 AnyString，找出 AnyString 中匹配模板 Pattern 的一个子串。 例如， 模板 Pattern 为: I?C*S 可以搜索出字符串 AnyString 中的 ISCAS, IECAS, ILCASS 等子串。 （本题满分 13 分）
v0 v1 v2 v6 v2 v5 v3 v4 v3 v4 v0 v1 v6
v5
(a)
(b)
图 5. 一个凸 7 边形的两种不同的三角剖分
4/4
2/4
①
;
③
;
2. 请写出非递归的归并排序算法。要求：不用堆栈，也不用队列。 （本题满分 10 分） 3. 请设计一个算法，对于输入的任意一个图（有向图或者无向图）G=(V, E)以及 一对顶点 Vi, VjV，可输出如下结果：如果从 Vi 到 Vj 存在简单路径，则输出 从 Vi 到 Vj 的所有简单路径，否则，输出为空。 （本题满分 10 分） 4. 键树又称为数字查找树（Digital Search Trees） 。为了查找和插入方便，我们约 定键树是有序树，即同一层中兄弟结点之间所含符号自左向右有序，并约定 结束符$小于任何字符，如图 4 所示。假设采用双链树存储结构，用于存储 N (N2)个人名，请写出该键树的构造算法。假设这些人名都可以用 26 个英文 字母和空格表示。 （本题满分 12 分）
free(q);
free(q);
F
① ② ; ;
; }
C
P
PR
Q
CL QL
S
}
SL
(本小题满分 7 分)
图 3. 二叉排序树
(6) 下面是对顺序表 L 做折半插入排序的算法。 请在 4 个空缺处填上适当的内 容，使该算法完整。请把答案写在答卷纸上，注明空缺处的编号和其对应 的内容。另外请写出折半插入排序算法的时间复杂度。 void BInsertSort (SqList &L) { for (i =2; i<= L.length; ++i) { L.r[0] = L.r[i]; lx = 1; hx = i -1; while (lx <= hx) { m = (lx + hx)/2; if (LT(L.r[0].key, L.r[m].key)) else ② ； } // while for ( j = i – 1; j >= hx + 1; --j) ④ ; } // for } // BInsertSort (本小题满分 6 分)