1、图、查找模拟试卷 1 及答案与解析一、单项选择题1 设无向图的顶点个数为 n，则该图最多有( )条边。（A）n-1（B） n(n-1) 2（C） n(n+1)2（D）02 一个 n 个顶点的连通无向图，其边的个数至少为( )。（A）n 一 1（B） n（C） n+l（D）nlog 2n3 用有向无环图描述表达式(A+B)(A+BA)，至少需要顶点的数目为( )。（A）5（B） 6（C） 8（D）94 用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( ) 。（A）逆拓扑有序（B）拓扑有序（C）无序的（D）不确定5 用邻接矩阵 A 表示图，判定任意两
2、个顶点 Vi 和 Vj 之间是否有长度为 m 的路径相连，则只要检查( ) 的第 i 行第 j 列的元素是否为零即可。（A）mA（B） A（C） Am（D）Am 一 16 当各边上的权值( ) 时，BFS 算法可用来解决单源最短路径问题。（A）均相等（B）均互不相等（C）不一定相等（D）不确定7 在有向图 G 的拓扑序列中，若顶点 vi 在顶点 vj 之前，则下列情形不可能出现的是( )。（A）G 中有弧口 i，v j（B） G 中有一条从 vi 到 vj 的路径（C） G 中没有弧 i，v j（D）G 中有一条从 vj 到 vi 的路径8 下列关于 AOE 网的叙述中，不正确的是( )。（A
3、）关键活动不按期完成就会影响整个工程的完成时间（B）任何一个关键活动提前完成，那么整个工程将会提前完成（C）所有的关键活动提前完成，那么整个工程将会提前完成（D）某些关键活动提前完成，那么整个工程将会提前完成9 一个二部图的邻接矩阵 A 是一个( )类型的矩阵。（A）nn 矩阵（B）分块对称矩阵（C）上三角矩阵（D）下三角矩阵10 若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。（A）(n 一 1)2（B） n2（C） (n+1)2（D）n11 适用于折半查找的表的存储方式及元素排列要求为( )。（A）链接方式存储，元
4、素无序（B）链接方式存储，元素有序（C）顺序方式存储，元素无序（D）顺序方式存储，元素有序12 具有 12 个关键字的有序表，折半查找的平均查找长度为( )。（A）31（B） 4（C） 25（D）513 折半查找的时间复杂性为( )。（A）O(n 2)（B） D(n)（C） D(nlog2n)（D） D(log 2n)14 既希望较快地查找又便于线性表动态变化的查找方法是( )。（A）顺序查找（B）折半查找（C）索引顺序查找（D）哈希法查找15 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 O，右孩子的平衡因子为 1，则应作( )型调整以
5、使其平衡。（A）LL（B） LR（C） RL（D）RR16 下列关于 m 阶 B-树的说法错误的是( )。（A）根结点至多有 m 棵子树（B）所有叶子都在同一层次上（C）非叶结点至少有 m2(m 为偶数)或 m2+l(m 为奇数)棵子树（D）根结点中的数据是有序的17 下面关于 B 和 B+树的叙述中，不正确的是 ( )。（A）B 树和 B+树都是平衡的多叉树（B） B 树和 B+树都可用于文件的索引结构（C） B 树和 B+树都能有效地支持顺序检索（D）B 树和 B+树都能有效地支持随机检索18 m 阶 B-树是一棵( )。（A）m 叉排序树（B） m 叉平衡排序树（C） m 一 1 叉平衡
6、排序树（D）m+1 叉平衡排序树19 在一棵含有 n 个关键字的 m 阶 B-树中进行查找，至多读盘( )次。（A）log 2n（B） 1+log2n（C）（D）20 设哈希表长为 14，哈希函数是 H(key)=key11，表中已有数据的关键字为15、38、61、84 共 4 个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )。（A）8（B） 3（C） 5（D）921 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。（A）最大概率（B）最小概率（C）平均概率（D）同等概率21 散列表的地址区间为 017，散列函数为 H(K)=K mod
7、 17。采用线性探测法处理冲突，并将关键字序列 26，25，72，38，8，18，59 依次存储到散列表中。22 元素 59 存放在散列表中的地址是( )。（A）8（B） 9（C） 10（D）1123 存放元素 59 需要搜索的次数是( )。（A）2（B） 3（C） 4（D）524 将 10 个元素散列到 100 000 个单元的哈希表中，则( )产生冲突。（A）一定会（B）一定不会（C）仍可能会（D）不确定二、综合题25 证明：具有 n 个顶点和多于 n 一 1 条边的无向连通图 G 一定不是树。26 证明：对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全 O 的充要条件是该
8、图为无环图。27 关于图(Graph) 的一些问题：(1)有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?(2)表示有 1 000 个顶点、1 000 条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?(3)对于一个有向图，不用拓扑排序，如何判断图中是否存在环?28 如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的 1 都集中到对角线以上?29 假定图 G=(V，E)是有向图，V=1 ，2，N ，N1，G 以邻接矩阵方式存储，G 的邻接矩阵为 A，即 A 是一个二维数组，如果 i 到 j 有边，则 Ai，j=1 ，否则Ai，j=0，请给出一个算法思想，该算法能判断
9、G 是否是非循环图(即 G 中是否存在回路)，要求算法的时间复杂性为 O(nn)。30 对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?31 G=(V，E)是一个带有权的连通图，如图所示。 (1)什么是 G的最小生成树? (2)G 如图所示，请找出 G 的所有最小生成树。32 (1)对于有向无环图，叙述求拓扑有序序列的步骤。(2)对于以下的图，写出它的4 个不同的拓扑有序序列。33 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点 Vi 到顶点 Vj 的路径(ij) 。注意：算法中涉及的图的基本操作必须在存储结构上实现。34 假设以邻接矩阵作为图的存储
10、结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注：图中不存在顶点到自己的弧)35 已有邻接表表示的有向图，请编程判断从第 u 顶点至第 v 顶点是否有简单路径，若有则印出该路径上的顶点。36 “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“ 破圈法 ”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注：圈就是回路)37 自由树(即无环连通图)T=(V，E)的直径是树中所有点对间最短路径长度的最大值，即 T 的直径定义为 MAX D(u，v)，这里
11、 D(u， v)(u，vV)表示顶点 u 到顶点 v的最短路径长度(路径长度为路径中所包含的边数)。写一算法求自由树 T 的直径，并分析算法的时间复杂度。38 对于一个使用邻接表存储的有向图 G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为 O 的邻接到的顶点进行递归。(1)给出完成上述功能的图的邻接表定义。(2)定义在算法中使用的全局辅助数组。(3)写出在遍历图的同时进行拓扑排序的算法。39 HASH 方法的平均查找路长决定于什么?是否与结点个数 N 有关?处理冲突的方法主要有哪些?40
12、对下面的关键字集30，15，2l，40，25，26，36，37若查找表的装填因子为08，采用线性探测再散列方法解决冲突，完成下列内容：(1)设计哈希函数；(2)画出哈希表；(3)计算查找成功和查找失败的平均查找长度。41 在一棵表示有序集 S 的二叉搜索树 (binary searCh tree)中，任意一条从根到叶结点的路径将 S 分为三部分：在该路径左边结点中的元素组成的集合 S1；在该路径上的结点中的元素组成的集合 S2；在该路径右边结点中的元素组成的集合S3。S=S 1S2S3。若对于任意的 aS1，b S2，CS 3 是否总有 abC?为什么?42 试画出从空树开始，由字符序列(t，
13、d，e，s，u，g，b，j，a，k，r，i) 构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。43 在数轴上有 N 个彼此相临不交的区间，每个区间下界上界都是整数。 N 个区间顺序为 1N。要查找给定的 x 落入的区间号，你认为应怎样组织数据结构 ?选择什么方法最快? 并简述其原因。43 设有 5 个数据 do，for，if，repeat ，while，它们排在一个有序表中，其查找概率分别为 p1=0 2，p 3=015 ，p 3=01，p 4=003， p5=001。而查找它们之间不存在数据的概率分别为q0=0 2，q 1=015，q 2=01，q 3=003，q 4=002，q 5=0
14、01。44 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。45 分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。46 判定是顺序查找好，还是折半查找好。47 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用左右链法存储。48 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针 p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结点的右孩子。用高级语言将上述算法写为过程形式。49 写出从哈希表中删除关键字为 K 的一个记录的算法，设哈希函数为 H，解决冲突的方法为链地址法。50
15、 假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。50 设从键盘输入一个整数的序列：n，a 1，a 2， an，其中 n 表示连续输入整数的个数。51 试编写一程序按整数值建立一个二叉排序树。52 在题(1)的基础上将此二叉树上的各整数按降序写入一磁盘文件中。53 编写对有序表进行顺序查找的算法。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。54 已知顺序表中有 m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在
16、顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到 D(m)。图、查找模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 B【试题解析】 此题考查的知识点是完全无向图的定义。具有 n 个结点的无向图边最多的图是无向完全图，设 n 阶无向完全图的边数为 m，则图中所有点的度数和为 2m。而 n 阶无向完全图的每个顶点都与其他顶点相邻，故图中每个点度数都为n 一 1，进而所有点的度数和为 n(n 一 1)。因此 2m=n(n 一 1)，故 m=n(n 一 1)2。所以选 B。【知识模块】 图2 【正确答案】 A【试题解析】 此题考查的知识点是无向图的性质。根据无向图的性质可知，对于一个有
17、 n 个顶点的连通无向图，只需要 n 一 1 条边即可成为连通无向图。【知识模块】 图3 【正确答案】 A【试题解析】 此题考查的知识点是有向无环图的定义。有向无环图是一个无环的有向图，可以用来表示公共子表达式，本题中出现的 5 个字符作为 5 个顶点，其中A+B 和 A 可共用，所以至少 5 个即可，选 A。【知识模块】 图4 【正确答案】 A【试题解析】 此题考查的知识点是图 DFS 的遍历及拓扑分类。在 DFS 算法退栈返回时，输出的是出度为 O 的顶点，所以为逆拓扑有序，应选 A。【知识模块】 图5 【正确答案】 C【试题解析】 此题考查的知识点是图的邻接矩阵存储。在图的邻接矩阵中，两
18、点之间有边，则值为 1，否则为 0。本题只要考虑 Am=AAA(m 个 A 矩阵相乘后的乘积矩阵)中(i ，j) 的元素值是否为 0 就行了。【知识模块】 图6 【正确答案】 A【试题解析】 此题考查的知识点是图的 BFS 算法。BFS 是从根结点开始，沿着树的宽度遍历树的结点，如果所有结点均被访问，则算法中止。当各边上的权值相等时，计算边数即可，所以选 A。【知识模块】 图7 【正确答案】 D【试题解析】 此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点vi 与顶点 vj 有一条弧，则拓扑序列中顶点 vi 必在顶点 vj 之前。若有一条从 vi 到 vj的路径，则顶点 vi 不可能
19、在顶点 vj 之前。所以应选 D。【知识模块】 图8 【正确答案】 D【试题解析】 此题考查的知识点是图的关键路径。在 AOE 网中，从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并且不只一条。关键路径上的活动称为关键活动。A 、B 、C 的说法都正确。但任何一个关键活动提前完成，不一定会影响关键路径，所以 B 不正确。根据题意，应选 B。【知识模块】 图9 【正确答案】 B【试题解析】 此题考查的知识点是二部图的定义与存储。二部图定义为：若能将无向图 G= 的顶点集 V 划分成两个子集 V1 和 V2(V1V2=)，使得 G 中任何一条边的两个端点一个
20、属于 Vl，另一个属于 V2，则称 G 为二部图。由于其特点，其存储矩阵必为分块对称的，所以选 B。【知识模块】 图10 【正确答案】 C【知识模块】 查找11 【正确答案】 D【试题解析】 此题考查的知识点是折半查找的特点。折半查找要求顺序存储且元素有序，所以应选 D。【知识模块】 查找12 【正确答案】 A【试题解析】 此题考查的知识点是折半查找的思想。把关键字按完全二叉树的形式画出查找树，按结点高度计算比较次数。12 个结点可以画出高度为 4 的完全二叉树，1 层 1 个结点比较 1 次，2 层 2 个结点比较 2 次，3 层 4 个结点比较 3 次，4层 5 个结点比较 4 次，351
21、2=31，应选 A。【知识模块】 查找13 【正确答案】 D【试题解析】 此题考查的知识点是折半查找的效率。其查找效率与比较次数有关，折半查找成功时，关键字比较次数最多不超过log 2n+1，所以其效率为 O(log2n)，应选 D。【知识模块】 查找14 【正确答案】 C【试题解析】 此题考查的知识点是各类查找的特点。顺序查找，算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用，但查找效率低。折半查找要求线性表中结点按关键字有序，并且要用数组作为表的存储结构，其不适合动态变化。索引顺序查找分为两部分，由“分块有序”的线性表和索引表
22、组成，查找效率较高，又便于线性表动态变化。哈希法查找以结点的关键字 K 为自变量，通过一个确定的函数 (即映射)关系 H，计算出对应的函数值 H(K)，然后把这个值解释为结点的存储地址，将结点存人H(K)所指的存储位置上。在查找时，根据要查找的关键字用同一函数日计算出地址，再到相应的单元里去取要找的结点。根据题意，应选 C。【知识模块】 查找15 【正确答案】 C【试题解析】 此题考查的知识点是平衡二叉树的旋转。因为不平衡点 A 的左子树平衡因子为 0，若插入到左子树上不会影响 A 的平衡因子，所以只能插入到 A 的右子树上，而右子树的因子为 1，所以只能是插在其左子树上，应该是 RL 型，所
23、以选择 C。【知识模块】 查找16 【正确答案】 D【试题解析】 此题考查的知识点是 m 阶 B-树的定义。一棵 m 阶的 B-树或为空，或满足下列条件：(1)树中每个结点至多有 m 个孩子；(2)除根结点和叶子结点外，其他每个结点至少有 m2 个孩子(3)若根结点不是叶子结点，则至少有 2 个孩子；(4)所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；(5)所有的非叶结点都包含下列数据： (n，A 0，K 1，A 1，K 2， ，K n，A n)，且 KiK i+l。综上所述，只有 D 不全面，所以应选 D。【知识模块】 查找17 【正确答案】 C【知识模块】 查找18 【正确答案
24、】 B【试题解析】 此题考查的知识点是 m 阶 B 一树的定义。B 一树是一种平衡的多路排序树，m 阶即 m 叉。应选 B。【知识模块】 查找19 【正确答案】 C【试题解析】 此题考查的知识点是 B-树的查找。在 B-树上进行查找需比较的结点数最多为 B-树的高度，B -树的高度与 B-树的阶 m 和键值总数 n 有关。 (1) 设 B-树某结点的子树数为 Ci，则该结点的关键字数 Ni=Ci1。对于有 k 个结点的 B-树，有 N i=(Ci 一 1)=Ci 一 k (1ik) (1) 因为 B 树上的关键字数，即 Ni=n (1ik) (2) 而 B-树上的子树数可这样计算：每个结点(除
25、根结点)都是一棵子树，设叶子(子树)数为 s；则 C i=(k 一 1)+s (1ik) (3) 综合式(1) 、式(2) 、式(3)，有 h=n+1。 (2)根据 B-树的定义，B -树的第一层(即根结点)的结点数至少为 1 个，第二层的结点数至少为 2，第三层的结点数至少为 2m2，第四层的结点数至少为 2(m2)2 ，以此类推，第 h+1 层的结点数至少为 2(m2)h 一 1。综上所述，可得到如下不等式： h1+log m/2(n+1)2，所以选 C。【知识模块】 查找20 【正确答案】 D【试题解析】 此题考查的知识点是散列法查找。地址计算公式为 H i(key)=(H(key)+d
26、i)B，其中 di=12，2 2，k 2，称为二次探测再散列。先计算加，后计算减，计算后选 D。【知识模块】 查找21 【正确答案】 D【试题解析】 此题考查的知识点是散列函数性质。为保证其地址的随机性，函数值应当以同等概率取其值域的每个值。所以应选 D。【知识模块】 查找【知识模块】 查找22 【正确答案】 D【知识模块】 查找23 【正确答案】 C【试题解析】 此题考查的知识点是线性探测法。通过计算知 h(26)=9，h(25)=8， h(72)=4，h(38)=4 ，h(8)=8，h(18)=1，h(59)=8。因为有冲突，所以根据线性探测法 59 应存放在 11 中，(1)应选 D。当
27、搜索元素 59 时，先计算地址为 8，发现不是，按存放原则向后继续，比较 4 次后即可。所以(2)应选 C。【知识模块】 查找24 【正确答案】 C【试题解析】 此题考查的知识点是散列法查找特点。由于散列函数的选取，仍然有可能产生地址冲突，所以应选 C。【知识模块】 查找二、综合题25 【正确答案】 具有 n 个顶点 n 一 1 条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于 n 一 1 条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。【知识模块】 图26 【正确答案】
28、 据题意该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为 0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(Aij=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为 0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)【知识模块】 图27 【正确答案】 (1)n(n 一 1)，n (2)10 6 ，不一定是稀疏矩阵 (3) 使用深度优先遍历，按退出 DFS 过程的先后顺序记录下的顶点是逆向拓扑有
29、序序列。若在执行 DFS (v)未退出前，出现顶点 u 到 v 的回边，则说明存在包含顶点 v 和顶点 u 的环。【试题解析】 此问题考查的知识点是图的相关术语。(1)在有向图 G 中，如果对于每一对 vi，v j 属于 V，v i 不等于 vj，从 vi 到 vj 和从 vj 到 i 都存在路径，则称 G 是强连通图。最多边是所有的顶点每对之间都有边，边数为 n(n 一 1)，最少只有一个方向有边为 n。(2)元素个数为矩阵的大小，即 106 ，稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律，不一定稀疏。(3)使用深度优先遍历，按退出 DFS 过程的先后顺序记录下的顶点是逆向拓扑
30、有序序列。若在执行 DFS (v)未退出前，出现顶点 u 到 v 的回边，则说明存在包含顶点 v 和顶点 u 的环。【知识模块】 图28 【正确答案】 可以按各顶点的出度进行排序。n 个顶点的有向图，其顶点最大出度是 n 一 1，最小出度为 O。这样排序后，出度最大的顶点编号为 1，出度最小的顶点编号为 n。之后，进行调整，即若存在弧 ，而顶点 j 的出度大于顶点 i的出度，则将把 j 编号在顶点 i 的编号之前。【知识模块】 图29 【正确答案】 采用深度优先遍历算法，在执行 DFS(v)时，若在退出 DFS(v)前，碰到某顶点 u，其邻接点是已经访问的顶点 v，则说明 v 的子孙 u 有到
31、 v 的回边，即说明有环；否则，无环。【知识模块】 图30 【正确答案】 遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。【知识模块】 图31 【正确答案】 (1)无向连通图的生成树包含图中全部 n 个顶点，以及足以使图连通的 n 一 1 条边。而最小生成树则是各边权值之和最小的生成树。 (2)最小生成树有两棵。下面给出顶点集合和边集合，边以三元组(V i，V j，W) 形式，其中 W 代表权值。 V(G)=1 ，2，3， 4，5 E1(G)=(4，5，2)，(2，5，4)，(2，3，5)，(1，2， 7)； E2(G)=(4，5，2) ，(2，4，4)，
32、(2，3，5)，(1，2，7)【试题解析】 此问题考查的知识点是最小生成树的定义。该题说明图的最小生成树不唯一，但权值和唯一，出现两个或以上的情况是因为有权值相同的边。牢记Prim(选图的顶点) ，Kruscal(选图的边，边上权值排序)两种算法的区别及算法步骤。【知识模块】 图32 【正确答案】 (1)对有向图，求拓扑序列步骤为：在有向图中选一个没有前驱(即人度为零) 的顶点并输出。在图中删除该顶点及所有以它为尾的弧。重复和步，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。(2)从入度为 0 的顶点开始，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑
33、序列。从顶点 1 开始的所有可能的拓扑序列为12345678，12354678，1345627813546278。【知识模块】 图33 【正确答案】 int vsited =0 ；全局变量，访问数组初始化int dfs(AdjList g，vi)以邻接表为存储的有向图 g，判断 vi 到 vj 是否有通路，返回 1 或无 0vsitedvi=1；vis ted 是访问数组，设顶点的信息就是顶点编号p=gviifirstarc ；第一个邻接点while(P!=null)j=p-adjvex；if(vj=j)flag=1；return(1)；vi 和 vj 有通路if(visitedj=0)dfS
34、(g，j) ；P=P 一 next：whileif(!flag)return(0)；结束【试题解析】 此问题考查的知识点是图的遍历。在有向图中，判断顶点 vi 和顶点vj 间是否有路径，可采用搜索的方法，从顶点 vi 出发，不论是深度优先搜索(DFS)还是宽度优先搜索(BFS)，在未退出 DFS 函数或 BFS 函数前，若访问到 vj，则说明有通路，否则无通路。设一全程变量 flag。初始化为 0，若有通路，则 flag=1。【知识模块】 图34 【正确答案】 用邻接矩阵存储void Print(int v，int start)输出从顶点 start 开始的回路for(i=1；i0 II P)
35、P=gStopfirstarc；第一个邻接点 while(P!： null&visitedp-adjvex=1)P：p-next；下一个访问邻接点表if(P=null)top-；退栈elsei=p-adjvex；取邻接点(编号)if(i=v)找到从 u 到 v 的一条简单路径，输出for(k=1；k=n)破圈，直到边数 e=n 一 1if(connect(k)删除第 k 条边若仍连通edgekW=0；eg 一一；测试下一条边 edgek，权值置 0 表示该边被删除k+；下条边 while算法结束connect()是测试图是否连通的函数，可用 DFS 函数或 BFS 函数实现，若是连通图，一次进
36、入 DFS 函数或 BFS 函数就可遍历完全部顶点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。“破圈” 结束后，可输出 edge 中 w 不为 0 的 n 一 1 条边。【试题解析】 此问题考查的知识点是最小生成树的定义。连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n 一 1 条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩 n-1 条边为止。【知识模块】 图37 【正确答案】 int dfs(Graph
37、 g，vertype parent， vertype child，int len)深度优先遍历，返回从根到结点 child 所在的子树的叶结点的最大距离currentlen：len；maxlen=len；v=GraphFirstAdj(g，child)；while(v!=0)邻接点存在if(v!=parent)len=len+length(g，child，c)；dfs(g ，child，V， len)；if(1enmaxlen)maxlen=len；v=GraphNextAdj(g，child，v) ；len=current_len；iflen=maxlen；return(len)；结束 df
38、sint Find_Diamenter(Graph g)求无向连通图的直径，图的顶点信息为图的编号maxlenl=0；maxlen2=0；存放目前找到的根到叶结点路径的最大值和次大值len=0；深度优先生成树根到某叶结点间的距离W=GraphFirstAdj(g，1)；顶点 l 为生成树的根while(W!=0)邻接点存在len=length(g，1，w) ；if(1enmaxlenl)maxlen2=maxlenl；maxlenl=len；else if(1enmaxlen2)maxlen2=len；w=GraphNextAdj(g，1，w)；找顶点 1 的下一邻接点 whileprintf
39、(”无向连通图 g 的最大直径是dn”，maxlenl+maxlen2)；return(maxlenl+maxlen2)；结束 finddiamenter算法主要过程是对图进行深度优先遍历。若以邻接表为存储结构，则时间复杂度为 O(n+e)。【知识模块】 图38 【正确答案】 (1)邻接表定义：typedef struct ArcNodeint adjvex；struct ArcNode*next；ArcNode； Typedef struct VNodevertype data；ArcNode*firstarc；VNode，AdjListMAX；(2)全局数组定义：int visited=0
40、；finished=0 ；flag：=1；flag 测试拓扑排序是否成功ArcNode*final=null；final 是指向顶点链表的指针，初始化为 0(3)算法void dfs(AdjList g，vertype V)以顶点 v 开始深度优先遍历有向图 g，顶点信息就是顶点编号ArcNode* t；指向边结点的临时变量printf(“d”，v)；visitedv=1；P=gvfirstarc；while(P!=null)j=p-adjvex；if(visitedj=1&finishedJ=0)flag=0dfs 结束前出现回边else if(visitedJ=0)dfS(g，j)；fin
41、ishedj=1；ifP=P 一next； whilet=(ArcNode*)malloc(sizeof(ArcNode)；申请边结点t 一adjvex=v ；t 一next=final；final=t；将该顶点插入链表 dfs 结束int dfs-Topsort(Adjlist g)对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回 1，否则返回0i=1；while(flag&ilchild，flag)；中序遍历左子树if(pre=null)pre=t；中序遍历的第一个结点不必判断else if(pre 一datadata)pre=t；前驱指针指向当前结点elseflag=flase；不
42、是二叉排序树Judgebst(t-rchild，flag)；中序遍历右子树 JudgeBST 算法结束本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：int JudgeBST(BTree t)判断二叉树 t 是否是二叉排序树if(t=null)return true；if(Judgebst(t 一lchild)&Judgebst(t-rchild)若左右子树均为二叉排序树m=max(t 一lchild)；n=min(t 一rchild)；左子树中最大值和右子树中最小值retu
43、rn(t-datam&t-datarchild!=null)P=p-rchild；return p 一data；int min(BTree p)求二叉树右子树的最小值if(P=null)return maxint；返回机器最大整数elsewhile(p-lchild!=null)P：p-lchild；return p-data；【试题解析】 此题考查的知识点是二叉排序树的特点及遍历算法。根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量 pre(初值为 null)和全局变量 flag，初值为 true。若非二叉排序树，则置
44、flag 为 false。【知识模块】 查找48 【正确答案】 void Delete(BSTree t，P)在二叉排序树 t 中，删除 f 所指结点的右孩子 (由 P 所指向)的算法if(p-lchild=null)f-rchild=p-rchild；free(P) ；p 无左子女else用 P 左子树中的最大值代替 P 结点的值q=p-lehild；s=q ；while(q 一rchild)S=q；q=q 一rchild； 查 P 左子树中序序列最右结点if(S=p 一lchild)p 左子树的根结点无右子女p-data=s-data；p-lchild=s-lchild；free(S)；e
45、lsep-data=q-data； s-rchild=q-lchild；free(q)； Delete【知识模块】 查找49 【正确答案】 typedef struct nodekeytype key；strnct node，* next ：HSNode；， lc HSListtypedef struct node，lc HLK；void Delete(HLK HT，keytype K)用链地址法解决冲突，从哈希表中删去关键字为 K 的记录i=H(K)；用哈希函数确定关键字 K 的哈希地址if(HTi=null)printf(”无被删除记录n”)；exit(0)；HLK P，q；P=Hi；q=
46、P；p 指向当前记录(关键字)，q 是 P 的前驱while(P&p-key!=k)q=P；P-p-next；if(P=null)printf(”无被删除记录 ”)；exit(0)；if(q=Hi)被删除关键字是链表中第一个结点HTi=HTinext；free(P)；elseq-next=p-next；free(P) ；结束 Delete【试题解析】 此题考查的知识点是 HASH 表基本算法。用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，(第 i 个)单链表结点有两个域，一个是哈希地址为 i 的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。【知
47、识模块】 查找50 【正确答案】 int Height(BSTree t)求平衡二叉树 t 的高度level=0；P=t；while(P)level+；树的高度增 1if(p 一bfrchild；bf=-1 沿右分枝向下else P=p-lchild；bf=0 沿左分枝向下 while return(level)；平衡二叉树的高度算法结束【试题解析】 此题考查的知识点是平衡二叉树的算法。因为二叉树各结点已标明了平衡因子 b，故从根结点开始记树的层次。根结点的层次为 1，每下一层，层次加 1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子 b为 0 时，任选左右一分支向下查找，
48、若 b 不为 0，则沿左(当 b=1 时)或右(当 b=一1 时)向下查找。【知识模块】 查找【知识模块】 查找51 【正确答案】 非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。void CreatBST(BiTree bst，datatypeK，int n)以存储在数组 K 中的 n 个关键字，建立一棵初始为空的二叉排序树for(i=1；in；i+)P=bst；f=null；在调用 Creat_BST 时，bst=nullwhile(P!=null)if(p 一dataRLINK；f 是 P 的双亲elseif(p 一dataKi)f=P；P=p-LLINK ；s=(BiTree)malloc(sizeof(BiNode)；申请结点空间s 一data=Ki；s 一LLINK=null；s-RLINK=null；if(f=null)bst=s；根结点elseif
