SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 中序遍历左子树 访问根结点 中序遍历右子树。 (3)后序遍历(LRD)算法:若二叉树为空,则进行的是空操作,否则 后序遍历左子树 后序遍历右子树 访问根结点。 二叉排序树有如下特点:每个结点的左子树中所有结点的值都小于该结点的值,而右子树中 所有结点的值都大于该结点的值,可知由根结点P始,按结点字母的字典顺序构成的二叉 树如图2-3所示。 RI B分且,Q、点 X② H X 密中L R图示密 C ① R=4 X 奥合图231996年试题1解答 由图2-3可得出:L2指向 Null: L4指向C,即100C:R1指向Q,即1006;该二叉树排序 权前序遍历序列为 PBHCJQ,后序遍历序列为2 CJHBQP 【答案】A:⑨B:⑦C:⑤D:②E:④ 试题7(1996年试题14 从供选择的答案中,选出应填入下面叙述中内的最确切的解答,把相应编号写在答卷的 对应栏内。 下列图中,A是非简单图,B是完全图,C和D都是哈密尔顿图,其中C又是欧拉图 E是树。 供选择的答案 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn9816j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 16 页 中序遍历左子树； 访问根结点； 中序遍历右子树。 (3)后序遍历(LRD)算法：若二叉树为空，则进行的是空操作，否则 后序遍历左子树； 后序遍历右子树； 访问根结点。 二叉排序树有如下特点：每个结点的左子树中所有结点的值都小于该结点的值，而右子树中 所有结点的值都大于该结点的值，可知由根结点 P 始，按结点字母的字典顺序构成的二叉 树如图 2-3 所示。 由图 2-3 可得出：L2 指向 Null；L4 指向 C，即 100C；R1 指向 Q，即 1006；该二叉树排序 权前序遍历序列为 PBHCJQ，后序遍历序列为 2CJHBQP。 【答案】A：⑨ B：⑦ C：⑤ D：② E：④ 试题 7 (1996 年试题 14) 从供选择的答案中，选出应填入下面叙述中 内的最确切的解答，把相应编号写在答卷的 对应栏内。 下列图中，A 是非简单图，B 是完全图，C 和 D 都是哈密尔顿图，其中 C 又是欧拉图， E 是树。 供选择的答案：
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 非简单图:既无平先边也无环的无向图称为简单无向图,有平先边或有环的图是非简单图。 在6个图中只有②有环,其余的5个图都既无平先边也无环,因而A的答案应为② 完全图:每个顶点度数都等于(n-1)的n阶无向简单图称为n阶无向完全图,并记作kn。在 给定的6个图中,只有①图满足要求,它是k5,其余各图均不不完全图,所以B的答案为 ① 哈密尔顿图:通过图中所有结点一次且仅一次的回路称为该图的哈密尔顿回路,具有哈密尔 顿回路的图称为哈密顿图。图的连通性和图中不存在度数为1的顶点都是哈密尔顿图的必要 条件。⑤图是两分离的K3,即⑤是非连能图,而③、④、⑥已均有度数为1的顶点,所以 ③、④、⑤、⑥都不是哈密尔顿图。①、②中均存在哈密尔顿回路,因而①、②均为哈密尔 顿图。所以C、D的答案为①、② 欧拉图:给定无孤立结点的图G,若存在一条回路,经过图中每边一次且仅一次,该条路称 为欧拉回路。无向图G,当且仅当G是连通的,所有结点度数全为偶数,且有欧拉回路 该无向图称为无向欧拉图。在6个图中,只有①连通且无奇度顶点,因而①为欧拉图,其余 各图中,⑤无奇度顶点,但它不连通,所以不是欧拉图。而②、③、④、⑥中都有奇度顶点, 因而它们也不是欧拉图,所以C的答案为① 树:连通且无回路的无向图称为无向树。6个图中只有④满足要求,其余5个图中均有回路, 因而都不是树,E的答案为④ 【答案】A:②B:①C:①D:②E:④ 试题8(1995年试题3) 从下列有关树的叙述中,选出5条正确叙述,并按编号从小到大的次序写在答卷的A~E栏 内 ①一棵二叉树的层次遍历方法只有前序法和后序法两种; ②在哈夫曼树中,外部结点的个数比内部结点个数多1 ③完全二叉树一定是平衡二叉树; ④在二叉树的前序序列中,若结点u在结点ⅴ之前,则u一定是v的祖先 ⑤在查找树中插入一个新结点,总是插入到叶结点下面 ⑥树的后序序列和其对应的二叉树的后序序列的结果是一样的 ⑦对B树删除某一个关键字值时,可能会引起结点的分裂 ⑧在含有n个结点的树中,边数只能是n-1条: 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn9817j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 17 页 非简单图：既无平先边也无环的无向图称为简单无向图，有平先边或有环的图是非简单图。 在 6 个图中只有②有环，其余的 5 个图都既无平先边也无环，因而 A 的答案应为②。 完全图：每个顶点度数都等于(n-1)的 n 阶无向简单图称为 n 阶无向完全图，并记作 kn。在 给定的 6 个图中，只有①图满足要求，它是 k5，其余各图均不不完全图，所以 B 的答案为 ①。 哈密尔顿图：通过图中所有结点一次且仅一次的回路称为该图的哈密尔顿回路，具有哈密尔 顿回路的图称为哈密顿图。图的连通性和图中不存在度数为 1 的顶点都是哈密尔顿图的必要 条件。⑤图是两分离的 K3，即⑤是非连能图，而③、④、⑥已均有度数为 1 的顶点，所以 ③、④、⑤、⑥都不是哈密尔顿图。①、②中均存在哈密尔顿回路，因而①、②均为哈密尔 顿图。所以 C、D 的答案为①、②。 欧拉图：给定无孤立结点的图 G，若存在一条回路，经过图中每边一次且仅一次，该条路称 为欧拉回路。无向图 G，当且仅当 G 是连通的，所有结点度数全为偶数，且有欧拉回路， 该无向图称为无向欧拉图。在 6 个图中，只有①连通且无奇度顶点，因而①为欧拉图，其余 各图中，⑤无奇度顶点，但它不连通，所以不是欧拉图。而②、③、④、⑥中都有奇度顶点， 因而它们也不是欧拉图，所以 C 的答案为①。 树：连通且无回路的无向图称为无向树。6 个图中只有④满足要求，其余 5 个图中均有回路， 因而都不是树，E 的答案为④。 【答案】A：② B：① C：① D：② E：④ 试题 8(1995 年试题 3) 从下列有关树的叙述中，选出 5 条正确叙述，并按编号从小到大的次序写在答卷的 A～E 栏 内。 ①一棵二叉树的层次遍历方法只有前序法和后序法两种； ②在哈夫曼树中，外部结点的个数比内部结点个数多 1； ③完全二叉树一定是平衡二叉树； ④在二叉树的前序序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先； ⑤在查找树中插入一个新结点，总是插入到叶结点下面； ⑥树的后序序列和其对应的二叉树的后序序列的结果是一样的； ⑦对 B 树删除某一个关键字值时，可能会引起结点的分裂； ⑧在含有 n 个结点的树中，边数只能是 n-1 条；
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! ⑨最佳査找树就是检索效率最高的查找树: ⑩中序遍历二叉链存储的二叉树时,一般要用堆栈:中序遍历检索二叉树时,也必须使用堆 栈 【解析】 由二叉树的定义可知,二叉树是一种树形结构,但不是树。二叉树是结点的有限集,可以是 空集。任一结点至多有两棵不相交的子树-左子树和右子树。即使只有一棵子树也必须区分 清它是左子树还是右子树。 二叉树与树有着密切的关系:任一棵树都可用一棵二叉树唯一地表示。当然树中结点之间的 父子、兄弟的关系在它所对应的二叉树中会有变化。树和二叉树的层次遍历方法有前序法 后序法、中序法三种。 由于树转换为二叉树时,其对应结点的位置发生了变化,因此树的后序序列和其对应的二叉 树的后序序列一般是不同的。无论在树还是在二叉树的前序序列中,排序在前的结点未必是 排序在后的结点父结点,它们可以是兄弟或处于不同的子树中。二叉树用中序遍历方法存储 时,一般用堆栈,而检索时,未必用堆栈 在树中,每个结点,除了唯一的根结点外都只有一个父结点,而根结点是没有父结点的。由 于每个结点有且仅有一条边与父结点相连,因此,在有n个结点的树中,其边数只能是n-1 条 完全二叉树是一种特殊的二叉树,这是一种只允许最下二层结点的度数小于2(其他均为2) 并且最下面一层的结点都集中在该层靠左边的若干位置上。在二叉树中定义非空二叉树T 的高度h(T=max{h(T1)h(T2)}+1。其中,T1、T2分别为T的左子树和右子树。若一棵二叉 树中任一结点的左子树高度与右子树高度之差不超过1,则该称二叉树为平衡二叉树。根据 完全二叉树与平衡树的定义,可知完全二叉树一定是平衡二叉树。 查找树也是一种二叉树,若二叉树T的结点按中序遍历,结点u的左子树的所有结点的键 值都小于结点u的键值,而且结点u的右子树的所有结点的键值都大于结点u的键值。查找 树有3种操作:查找、插入和删除。当向查找树插入一个新结点时,总是插在叶结点的下面 对给定的查找二叉树,在结点的每个空指针上都有附加结点作为该结点的子结点,称这些附 加结点为外部结点,而原树的结点称为内部结点。哈夫曼树就是一种扩充二叉树。 在查找二叉树中查找结点,有许多种方法。最大查找时间在Oog2n)和O(n)之间。由于所查 找的结点是随机的,因此将平均査找时间作为代价函数。最佳查找树就是通过构造出各种可 能的査找树,计算出每棵查找树的代价,然后挑选其中代价最小的树而获得的,因而检索效 率是最高的 B树是一种平衡的多叉树,是索引文的有效结构。在B树中删除某一键值时,常采用与分 裂相反的处理过程-联接,这样做有可能使整棵B树减少一层,但不会引起结点的分裂。 【答案】:A:②B:③C:⑤D:⑧E:⑨ 试题9(1994年试题15) 从供选择的答案中,选出应填入下面有关排序算法复杂性的叙述中{}内的正确答案,把编 号写在答卷的对应栏内 对由n个记录所组成的有按关键码排序时,下列各常用排序算法的平均比较次数分别是: 路归并排序为A,冒泡排序B,快速排序为C。其中,归并排序和快速排序所需要的辅助存 储分别是D和E。 供选择的答案 AE:①O(1)②( logan)③O()④Om2) ⑤O(n(og2n)2)( nlog,n) 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn9818j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 18 页 ⑨最佳查找树就是检索效率最高的查找树； ⑩中序遍历二叉链存储的二叉树时，一般要用堆栈；中序遍历检索二叉树时，也必须使用堆 栈。 【解析】 由二叉树的定义可知，二叉树是一种树形结构，但不是树。二叉树是结点的有限集，可以是 空集。任一结点至多有两棵不相交的子树--左子树和右子树。即使只有一棵子树也必须区分 清它是左子树还是右子树。 二叉树与树有着密切的关系：任一棵树都可用一棵二叉树唯一地表示。当然树中结点之间的 父子、兄弟的关系在它所对应的二叉树中会有变化。树和二叉树的层次遍历方法有前序法、 后序法、中序法三种。 由于树转换为二叉树时，其对应结点的位置发生了变化，因此树的后序序列和其对应的二叉 树的后序序列一般是不同的。无论在树还是在二叉树的前序序列中，排序在前的结点未必是 排序在后的结点父结点，它们可以是兄弟或处于不同的子树中。二叉树用中序遍历方法存储 时，一般用堆栈，而检索时，未必用堆栈。 在树中，每个结点，除了唯一的根结点外都只有一个父结点，而根结点是没有父结点的。由 于每个结点有且仅有一条边与父结点相连，因此，在有 n 个结点的树中，其边数只能是 n-1 条。 完全二叉树是一种特殊的二叉树，这是一种只允许最下二层结点的度数小于 2(其他均为 2)， 并且最下面一层的结点都集中在该层靠左边的若干位置上。在二叉树中定义非空二叉树 T 的高度 h(T)=max{h(T1),h(T2)}+1。其中，T1、T2 分别为 T 的左子树和右子树。若一棵二叉 树中任一结点的左子树高度与右子树高度之差不超过 1，则该称二叉树为平衡二叉树。根据 完全二叉树与平衡树的定义，可知完全二叉树一定是平衡二叉树。 查找树也是一种二叉树，若二叉树 T 的结点按中序遍历，结点 u 的左子树的所有结点的键 值都小于结点 u 的键值，而且结点 u 的右子树的所有结点的键值都大于结点 u 的键值。查找 树有 3 种操作：查找、插入和删除。当向查找树插入一个新结点时，总是插在叶结点的下面。 对给定的查找二叉树，在结点的每个空指针上都有附加结点作为该结点的子结点，称这些附 加结点为外部结点，而原树的结点称为内部结点。哈夫曼树就是一种扩充二叉树。 在查找二叉树中查找结点，有许多种方法。最大查找时间在 O(log2n)和 O(n)之间。由于所查 找的结点是随机的，因此将平均查找时间作为代价函数。最佳查找树就是通过构造出各种可 能的查找树，计算出每棵查找树的代价，然后挑选其中代价最小的树而获得的，因而检索效 率是最高的。 B 树是一种平衡的多叉树，是索引文的有效结构。在 B 树中删除某一键值时，常采用与分 裂相反的处理过程--联接，这样做有可能使整棵 B 树减少一层，但不会引起结点的分裂。 【答案】：A：② B：③ C：⑤ D：⑧ E：⑨ 试题 9(1994 年试题 15) 从供选择的答案中，选出应填入下面有关排序算法复杂性的叙述中{ }内的正确答案，把编 号写在答卷的对应栏内。 对由 n 个记录所组成的有按关键码排序时，下列各常用排序算法的平均比较次数分别是：二 路归并排序为 A，冒泡排序 B，快速排序为 C。其中，归并排序和快速排序所需要的辅助存 储分别是 D 和 E。 供选择的答案 A-E：① ② O(1) (nlog2n) O(n) O(n ③ ④ 2 ) ⑤O（n(log2n)2）⑥(nlog2n)
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 【解析】 排序就是对由n个记录所组成的表按某个关键字的值的大小对记录重新排列。这是数据处理 中常见的重要运算。排序的方法很多,衡量一个排序方法的优劣,主要看排序算法的时间复 杂性和空间复杂性,即平均运算次数及所需要的辅助存储空间的大小。 冒泡排序( bubble sort):从上到下对每对相邻记录比较关键字大小,使较小关键字的记录 上升,比较一遍后最大的关键字的记录将排在最后,再对其余记录重复上述方法,反复执行 ,直到无记录上升为止,n个记录的平均运算次数是O(n)2 归并排序( merge sort):是把待排序的文件分成n个已排序的子文件,将这些文件合并得到 完全排序的文件。n个记录的平均运算次数是 O(nlog2n,所需的辅助存储空间是O(n) 快速排序( quick sort)):又称分区交换排序。先取一个记录作为基准,用交换的办法把所有 记录按关键字值比基准值大或小分列在基准记录的两边,然后再分别对这两边的记录重复上 述步骤,直到排序完成。n个记录的平均运算次数是 O(nlog,n),所需的辅助存储空间是 【答案】:A:②B:④C:②D:③E:⑥ 试题10(1993年试题6) 从供选择的答案中,选出应填入下面关于数据结构叙述中{}内的正确答案,把编号写在答 卷的对应栏内。 图2-4所示是带权的有向图G的邻表表示法。以结点V1出发,深度遍力图G所得的结点序 列为A:广度遍力图G所得的结点序列是B:G的一个拓扑序列是C:从结点到v1到结点 V8的最短路径是D:从结点V1到结点Ⅴ8的关键路径是E。 -2I6[o 5121 120A 241993年试题6 供选择的答案 A~C:①V1,V2,V3,V4,V5,V6,V7,V8 ②V,V2,V4,V6,V5,V3,V7,V8 ③V,V2,V4,V6,V3,V5,V7,V8 ⑤Vl V3,v8,v4,V5,V6,v7 ⑥Vl, v3,v8,ⅵ4,V5,V7,V6 ⑦V1,V2,V3,V8,V5,V7,V4,V6 D、E①(V1,V2,V4,V5,V3,V8) 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn33
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 19 页 【解析】 排序就是对由 n 个记录所组成的表按某个关键字的值的大小对记录重新排列。这是数据处理 中常见的重要运算。排序的方法很多，衡量一个排序方法的优劣，主要看排序算法的时间复 杂性和空间复杂性，即平均运算次数及所需要的辅助存储空间的大小。 冒泡排序(bubble sort)：从上到下对每对相邻记录比较关键字大小，使较小关键字的记录 上升，比较一遍后最大的关键字的记录将排在最后，再对其余记录重复上述方法，反复执行 ，直到无记录上升为止，n 个记录的平均运算次数是 O(n)2。 归并排序(merge sort)：是把待排序的文件分成 n 个已排序的子文件，将这些文件合并得到 完全排序的文件。n 个记录的平均运算次数是 O(nlog2n)，所需的辅助存储空间是 O(n)。 快速排序(quick sort)：又称分区交换排序。先取一个记录作为基准，用交换的办法把所有 记录按关键字值比基准值大或小分列在基准记录的两边，然后再分别对这两边的记录重复上 述步骤，直到排序完成。n 个记录的平均运算次数是 O(nlog2n)，所需的辅助存储空间是 O(log2n)。 【答案】：A：② B：④ C：② D：③ E：⑥ 试题 10(1993 年试题 6) 从供选择的答案中，选出应填入下面关于数据结构叙述中{ }内的正确答案，把编号写在答 卷的对应栏内。 图 2-4 所示是带权的有向图 G 的邻表表示法。以结点 V1 出发，深度遍力图 G 所得的结点序 列为 A；广度遍力图 G 所得的结点序列是 B；G 的一个拓扑序列是 C；从结点到 V1 到结点 V8 的最短路径是 D；从结点 V1 到结点 V8 的关键路径是 E。 供选择的答案 A～C：①V1，V2，V3，V4，V5，V6，V7，V8 ②V，V2，V4，V6，V5，V3，V7，V8 ③V1，V2，V4，V6，V3，V5，V7，V8 ④V1，V2，V4，V6，V7，V3，V5，V8 ⑤V1，V2，V3，V8，V4，V5，V6，V7 ⑥V1，V2，V3，V8，V4，V5，V7，V6 ⑦V1，V2，V3，V8，V5，V7，V4，V6 D、E (V1 ① ，V2，V4，V5，V3，V8)
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! ②(V1,V6,V5,V3,V8) ③(V1,V6,V7,V8) ④(V1,V2,V5,V7,V8) 【解析】 邻接表表示法可保存一个顺序存储的结点表,是图常用的一种存储方式。结点表的每一个表 目对应于图的一个结点,包括结点的数据或指向结点数据的指针,以及指向此结点的边表的 指针的两个字段。边表的每个表目对应于与该结点相关联的一条边,结点表的每个表目对应 个链接存储的边表,包括与该结点相关联的一个结点的序号及指向边表下一个表目的指针 的两个字段。因此,题中邻接表所对应的如图25所示 50 ,Y,2 nd,v V 图251993年试题6 图的深度优先遍历是从图中某个结点Ⅴ1了发,访问此结点,然后依次从Ⅴ1的未被访问的 相邻 结点出发进行深度优先遍历,直至图中所有和Vl有路径相通的结点都被访问到。此时图中 若 尚有未被访问的结点,则另选图中一个未被访问到的结点作起始点。重复上述过程,直至图 中所有结点都被访问到为止。因此,邻接表图的深度优先遍历是V1,V2,V3,V8,V5, V7,V4,V6。 广度优先遍历是先访问结点V1,然后访问V1连接到的所有未被访问的结点V2,V3, Vt,再依次访问V2,V3,…,Vt连接到的所有未被访问的结点。如此进行下去,直到访问 遍所有结点,因此邻接表图的广度优先遍历是V1,V2,V4,V6,V3,V5,V7,V8 如果有向图的某个结点序列满足如下条件:若从结点v到V有一条路径,则在序列中结点 ⅵi必定在j之前,则称该序列是一个拓扑序列。任何无环有向图的结点都可以排在一个拓 扑序列中。 拓扑排序的方法是重复执行下列步骤(1)和(2),直到所有结点均已被输出 (1)从图中选择一个入度为0的结点且输出之 (2)从图中删除此结点及其所有的出边 在可供选择的答案中,②是一个拓扑序列 最短路径是两个结点间长度最短的路径。这里的路径长度是指路径上的边所带权的总和,而 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn920j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 20 页 ②(V1，V6，V5，V3，V8) ③(V1，V6，V7，V8) ④(V1，V2，V5，V7，V8) 【解析】 邻接表表示法可保存一个顺序存储的结点表，是图常用的一种存储方式。结点表的每一个表 目对应于图的一个结点，包括结点的数据或指向结点数据的指针，以及指向此结点的边表的 指针的两个字段。边表的每个表目对应于与该结点相关联的一条边，结点表的每个表目对应 一个链接存储的边表，包括与该结点相关联的一个结点的序号及指向边表下一个表目的指针 的两个字段。因此，题中邻接表所对应的如图 2-5 所示。 图的深度优先遍历是从图中某个结点 V1 了发，访问此结点，然后依次从 V1 的未被访问的 相邻 结点出发进行深度优先遍历，直至图中所有和 V1 有路径相通的结点都被访问到。此时图中 若 尚有未被访问的结点，则另选图中一个未被访问到的结点作起始点。重复上述过程，直至图 中所有结点都被访问到为止。因此，邻接表图的深度优先遍历是 V1，V2，V3，V8，V5， V7，V4，V6。 广度优先遍历是先访问结点 V1，然后访问 V1 连接到的所有未被访问的结点 V2，V3，…， Vt，再依次访问 V2，V3，…，Vt 连接到的所有未被访问的结点。如此进行下去，直到访问 遍所有结点，因此邻接表图的广度优先遍历是 V1，V2，V4，V6，V3，V5，V7，V8。 如果有向图的某个结点序列满足如下条件：若从结点 Vi 到 Vj 有一条路径，则在序列中结点 Vi 必定在 Vj 之前，则称该序列是一个拓扑序列。任何无环有向图的结点都可以排在一个拓 扑序列中。 拓扑排序的方法是重复执行下列步骤(1)和(2)，直到所有结点均已被输出。 (1)从图中选择一个入度为 0 的结点且输出之； (2)从图中删除此结点及其所有的出边。 在可供选择的答案中，②是一个拓扑序列。 最短路径是两个结点间长度最短的路径。这里的路径长度是指路径上的边所带权的总和，而