SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 根据以上定义,如果进行中序遍历,即可得到一个从小到大的结点序列。 1.1.1.8图 (1)图的基本概念 图是比较树形结构更复杂的一种数据结构。在线性结构中,除首结点没有前驱结点,末 结点没有后继结点之外,一个结点只有一个前驱结点和一个后继结点。在树形结构中,除根 结点没有前驱结点外,一个结点虽只有一个前驱结点,但可以有多个后继结点。但在图结构 中,一个结点的前驱结点和后继结点的个数是任意 在图中,数据结构中的结点被称为顶点,结点之间的关系被称为边。一个图G由非空 有限的顶点集合V和有限的边的集合E组成,记为G=(V,E 图分有向图和无向图。图中代表边的结点的偶对如果是有序的,则称此图为有向图。在 有向图中用(V1,V2)表示一条有向边,V1称为边的起点,V2称为边的终点。(V1,V2)和(V2, V1)代表不同的边。图中代表一条边的结点的偶对如果是无序的,则称此图为无向图。在无 向图中,(V1,V2)和(V2,V1)这两个偶对表示同一条边 如果限定任何一条边或弧的两个顶点都不相同,一个有n个顶点的无向图至多有 n(n-1)/2条边,这样的无向图称为无向完全图。一个有向图至多有n(n-1)条弧,这样的有向 图称为有向完全图。如果给图的每条边赋予一个实数作为边的权,则该图称为带权图,或称 (2)图的存储结构 最常用的图的存储结构是邻接矩阵和邻接表。 图的邻接矩阵是反映顶点间邻接关系的矩阵,设G(V,E)是具有n(n≥1)个顶点的图,G 的邻接矩阵M是一个n行n列的矩阵,若(i,j)或(,jE,则M[i[j]=1;香则M[i [j]=0。由邻接矩阵的定义可知,无向图的邻接矩阵是对称的,有向图的邻接矩阵不定的 对称 图也可用邻接表来存储,为图的每个顶点建立一个链表。且第i个链表中的结点表示与 顶点i相关联的一条边,或由顶点i出发的一条弧。有n个顶点的图,需要这n个链表的头 指针按顺序线性表方方式存储。在无向图的邻接表中,对应某结点的链表的结点个数就是该 顶点的度。 (3)图的遍历 图的遍历是指从图中的某个顶点出发,沿着图中的边或弧访问图中的每个顶点,并且每 个顶点只被访问一次。图的遍历通常采用深度优先搜索或广度优先搜索方法 图的深度优先搜索类似于树的前序遍历。从图中某个结点出发,访问此结点,然后依次 从此结点未被访问的邻接点出发进行深度优先搜索,直至图中所有该结点有路径相通的结点 均被访问到。若此时图中尚有结点未被访问,则另选图中一个未被访问的结点作起始点, 重复上述过程,直至图中所有结点都被访问到为止 广度优先搜索类似于树的层次遍历。从某个结点出发,访问此结点,然后依次访问与此 结点邻接的、未被访问过的结点,然后再分别从这些为出发进行广度优先周游,直至图中所 有被访问过的结点的相邻结点都被访问到。若此时图中有结点尚未被访问,则另选图中一个 未曾访问过的结点作为起点,重复上述过程,直至图中所有结点都被访问到为止 (4)最小代价生成树 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.com.cn386j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 6 页 根据以上定义，如果进行中序遍历，即可得到一个从小到大的结点序列。 1.1.1.8 图 (1)图的基本概念 图是比较树形结构更复杂的一种数据结构。在线性结构中，除首结点没有前驱结点，末 结点没有后继结点之外，一个结点只有一个前驱结点和一个后继结点。在树形结构中，除根 结点没有前驱结点外，一个结点虽只有一个前驱结点，但可以有多个后继结点。但在图结构 中，一个结点的前驱结点和后继结点的个数是任意。 在图中，数据结构中的结点被称为顶点，结点之间的关系被称为边。一个图 G 由非空 有限的顶点集合 V 和有限的边的集合 E 组成，记为 G=(V，E)。 图分有向图和无向图。图中代表边的结点的偶对如果是有序的，则称此图为有向图。在 有向图中用(V1，V2)表示一条有向边，V1 称为边的起点，V2 称为边的终点。(V1，V2)和(V2， V1)代表不同的边。图中代表一条边的结点的偶对如果是无序的，则称此图为无向图。在无 向图中，(V1，V2)和(V2，V1)这两个偶对表示同一条边。 如果限定任何一条边或弧的两个顶点都不相同，一个有 n 个顶点的无向图至多有 n(n-1)/2 条边，这样的无向图称为无向完全图。一个有向图至多有 n(n-1)条弧，这样的有向 图称为有向完全图。如果给图的每条边赋予一个实数作为边的权，则该图称为带权图，或称 为网。 (2)图的存储结构 最常用的图的存储结构是邻接矩阵和邻接表。 图的邻接矩阵是反映顶点间邻接关系的矩阵，设 G(V，E)是具有 n(n≥1)个顶点的图，G 的邻接矩阵 M 是一个 n 行 n 列的矩阵，若(i，j)或(i，j) E，则 M［i］［j］=1；否则 M［i］ ［j］=0。由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵不定的 对称。 图也可用邻接表来存储，为图的每个顶点建立一个链表。且第 i 个链表中的结点表示与 顶点 i 相关联的一条边，或由顶点 i 出发的一条弧。有 n 个顶点的图，需要这 n 个链表的头 指针按顺序线性表方方式存储。在无向图的邻接表中，对应某结点的链表的结点个数就是该 顶点的度。 (3)图的遍历 图的遍历是指从图中的某个顶点出发，沿着图中的边或弧访问图中的每个顶点，并且每 个顶点只被访问一次。图的遍历通常采用深度优先搜索或广度优先搜索方法。 图的深度优先搜索类似于树的前序遍历。从图中某个结点出发，访问此结点，然后依次 从此结点未被访问的邻接点出发进行深度优先搜索，直至图中所有该结点有路径相通的结点 均被 访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点作起始点， 重复上述过程，直至图中所有结点都被访问到为止。 广度优先搜索类似于树的层次遍历。从某个结点出发，访问此结点，然后依次访问与此 结点邻接的、未被访问过的结点，然后再分别从这些为出发进行广度优先周游，直至图中所 有被访问过的结点的相邻结点都被访问到。若此时图中有结点尚未被访问，则另选图中一个 未曾访问过的结点作为起点，重复上述过程，直至图中所有结点都被访问到为止。 (4)最小代价生成树
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 设G=(VE)是一个连通的无向图,若G1是包含G中所有顶点的一个无回路的连通子, 则称G1为G的一棵生成树。含有n个顶点的连通图的生成树有n个顶点和n-1条边。对 个带权的图(网),在一棵生成树中,各条边的权值之和称为这棵生成树的代价。一个图可以 有许多不同的生成树,其中代价最小的生成树称为最小代价生成树。 (5)求最短路径 求最短路径就是从图中某个顶点到其他顶点的最短路径。基本思想是把图中所有结点分 成两组,第一组包括已确定最短路径的结点,第二组包括尚未确定最短径的结点,按最短路 径长度递增的顺序逐个把第二组的结点加到第一组中去,直至从某结点出发可以到达的所有 结点都包括到第一组中。在这个过程中,总保护从该结点到第一组各结点的最短路径长度都 不大于从该结点到第二组的任何结点的最短路径长度 另外,拓扑排序和计算关键路径都是有向图的重要运算 1.1.1.9排序与查找 对于有n个结点的线性表(eo,e,….en-),按照结点中某些数据项的值递增或递减的次 序,重新排列线性表结点的过程,称为排序。排序时参照的数据项称为排序码,通常选择结 点的键值作为排序码。在排序过程中,线性表的全部结点都在内存、并在内存中调整它们在 线性表中的存储顺序,称为内排序。在排序过程中,线性表只有部分结点被调入内存、并借 助内存调整结点在外存中的存放顺序的排序方法称为外排序。常用的排序方法有:选择排序 、直接插入排序、冒泡排序、希尔排序、堆排序、快速排序、合并排序和外排序,其中外排 序是对大文件的排序。 查找就是在按某种数据结构存储的数据集全中,找出满足指定条件的结点的过程。按查 找的条件分类,有按结点的关键码査找、按关键码以外的其他数据项查找和按关键码以外的 其他数据项的组合查找等。按查找数据在内存还是在外存分为内存查找和外存查找。按查找 的目的分类,如果査找只是为了确定指定条件的结点存在与否,称为静态查找。如果查找是 为确定结点的插入位置或为了删除找到的结点,称为动态查找。 散列表又称杂凑表,是一种非常实用的查找技术。由于查找码与结点在数据结构中的位 置之间不存在确定的关系,查找只能通过查找码与结点的关键码的反复比较来实现。对于通 过比较来缩小査找范围来说,唯一能提高査找效率的办法是通过一次比较能大幅减小査找范 最理想的情况是直接利用查找码的信息,一次或几次存取便能存取所查结点。为此必须 在结点的存储位置和它的关键码间建立一个确定的关系,从而让查找码直接利用这个关系确 定结点的位置。 1.1.3试题解析 数据结构是每年必考的知识点,与初级程序员级考试和程序员级考试相比,高级程序员 级考试涉及的内容具有一定的广度和深度。从历年试题统计(见表2-1)来看,考查的内容主 要是树、二叉树、图和排序算法,特别是排序算法的平均比较比较次数,考査的次数相当多, 复习是应作为重点,并应熟练掌握相关的算法。 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.com.cn387j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 7 页 设 G=(V,E)是一个连通的无向图，若 G1 是包含 G 中所有顶点的一个无回路的连通子， 则称 G1 为 G 的一棵生成树。含有 n 个顶点的连通图的生成树有 n 个顶点和 n-1 条边。对一 个带权的图(网)，在一棵生成树中，各条边的权值之和称为这棵生成树的代价。一个图可以 有许多不同的生成树，其中代价最小的生成树称为最小代价生成树。 (5)求最短路径 求最短路径就是从图中某个顶点到其他顶点的最短路径。基本思想是把图中所有结点分 成两组，第一组包括已确定最短路径的结点，第二组包括尚未确定最短径的结点，按最短路 径长度递增的顺序逐个把第二组的结点加到第一组中去，直至从某结点出发可以到达的所有 结点都包括到第一组中。在这个过程中，总保护从该结点到第一组各结点的最短路径长度都 不大于从该结点到第二组的任何结点的最短路径长度。 另外，拓扑排序和计算关键路径都是有向图的重要运算。 1.1.1.9 排序与查找 对于有 n 个结点的线性表(e0，e1，…en-1)，按照结点中某些数据项的值递增或递减的次 序，重新排列线性表结点的过程，称为排序。排序时参照的数据项称为排序码，通常选择结 点的键值作为排序码。在排序过程中，线性表的全部结点都在内存、并在内存中调整它们在 线性表中的存储顺序，称为内排序。在排序过程中，线性表只有部分结点被调入内存、并借 助内存调整结点在外存中的存放顺序的排序方法称为外排序。常用的排序方法有：选择排序 、直接插入排序、冒泡排序、希尔排序、堆排序、快速排序、合并排序和外排序，其中外排 序是对大文件的排序。 查找就是在按某种数据结构存储的数据集全中，找出满足指定条件的结点的过程。按查 找的条件分类，有按结点的关键码查找、按关键码以外的其他数据项查找和按关键码以外的 其他数据项的组合查找等。按查找数据在内存还是在外存分为内存查找和外存查找。按查找 的目的分类，如果查找只是为了确定指定条件的结点存在与否，称为静态查找。如果查找是 为确定结点的插入位置或为了删除找到的结点，称为动态查找。 散列表又称杂凑表，是一种非常实用的查找技术。由于查找码与结点在数据结构中的位 置之间不存在确定的关系，查找只能通过查找码与结点的关键码的反复比较来实现。对于通 过比较来缩小查找范围来说，唯一能提高查找效率的办法是通过一次比较能大幅减小查找范 围。 最理想的情况是直接利用查找码的信息，一次或几次存取便能存取所查结点。为此必须 在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确 定结点的位置。 1.1.3 试题解析 数据结构是每年必考的知识点，与初级程序员级考试和程序员级考试相比，高级程序员 级考试涉及的内容具有一定的广度和深度。从历年试题统计(见表 2-1)来看，考查的内容主 要是树、二叉树、图和排序算法，特别是排序算法的平均比较比较次数，考查的次数相当多， 复习是应作为重点，并应熟练掌握相关的算法
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 历年高级程序员绂败据结构基础试题统计 游这的均长度(+ 9年试题3 树“叉树 魔用序法 1903年试题6 用择序算这的平均比较次数 905年试题 料二叉 19年试题4 性表三义树三了西的结是其遍历方法 19年试题 常用排序算法 家附序法 r9年试题2 图的念及的存储精构 300年试题1 试题1(2000年试题1) 从供选择的答案中,选出应填入下面叙述中{}内的最确切的解答,把相应编号写在答卷的 对应栏内 二叉树的前序、中序和后序遍历法最适合采用{A}来实现 查找树中,由根结点到所有其他结点的路径长度的总和称为{B},而使上述路径长度总和 达到最小的树称为{C},它一定是{D} 在关于树的几个叙述中,只有{E}是正确的。 供选择的答案 A:①递归程序②迭代程序③队列操作④栈操作 B:①路径和②内部路径长度③总深度④深度和 C:①B-树②B+-树③丰满树④穿线树 D:①B-树②平衡树③非平衡树④穿线树 E:①用指针方式存储有n个结点的二叉树,至少要有n+1个指针 ②m阶B-树中,每个非叶子结点的后件个数≥[m2] ③m阶B-树中,具有k个后件的结点,必含有k-1个键值 ④平衡树一定是丰满树 【解析】 本题综合考查树形数据结构知识。部分内容与1991年试题3相似 由于二叉树的前序、中序和后序遍历方法都是递归定义,所以最适合采用递归程序来实现。 查找树中,由根结点到所有其他结点的路径长度总和称为内部路径长度。具有最小内部路径 长度的树是丰满树,对丰满树的査找树进行插入或者删除操作后,会产生一棵非丰满树。平 衡二叉树是指其上任一结点的左右子树的高度(或者结点个数)保持一定比例的树,即平衡树 上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近,但是在插入或者 删除结点时,更能动态地平衡树的特点。由丰满树同平衡树定义可知,丰满树一定是平稳树 但是平衡树不一定是丰满树 m阶B-树是一种平衡的m叉树,具有如下的性质: (1)每个结点的后件个数小于等于m (2)除了根结点的各结点之外,每个结点的后件个数大于等于(m/2) (3)具有k个后件的非叶结点含有k-1个键值 (4)所有叶结点在同一层上,而且不附有信息 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.com.cn388j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 8 页 试题 1(2000 年试题 1) 从供选择的答案中，选出应填入下面叙述中 { }内的最确切的解答，把相应编号写在答卷的 对应栏内。 二叉树的前序、中序和后序遍历法最适合采用{ A }来实现。 查找树中，由根结点到所有其他结点的路径长度的总和称为{ B }，而使上述路径长度总和 达到最小的树称为{ C }，它一定是{ D }。 在关于树的几个叙述中，只有{ E }是正确的。 供选择的答案 A： ①递归程序 ②迭代程序 ③队列操作 ④栈操作 B： ①路径和 ②内部路径长度 ③总深度 ④深度和 C： B ① -树 B+ ② -树 ③丰满树 ④穿线树 D： B ① -树 ②平衡树 ③非平衡树 ④穿线树 E：①用指针方式存储有 n 个结点的二叉树，至少要有 n+1 个指针 ②m 阶 B-树中，每个非叶子结点的后件个数≥［m/2］ ③m 阶 B-树中，具有 k 个后件的结点，必含有 k-1 个键值 ④平衡树一定是丰满树 【解析】 本题综合考查树形数据结构知识。部分内容与 1991 年试题 3 相似。 由于二叉树的前序、中序和后序遍历方法都是递归定义，所以最适合采用递归程序来实现。 查找树中，由根结点到所有其他结点的路径长度总和称为内部路径长度。具有最小内部路径 长度的树是丰满树，对丰满树的查找树进行插入或者删除操作后，会产生一棵非丰满树。平 衡二叉树是指其上任一结点的左右子树的高度(或者结点个数)保持一定比例的树，即平衡树 上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近，但是在插入或者 删除结点时，更能动态地平衡树的特点。由丰满树同平衡树定义可知，丰满树一定是平稳树 ，但是平衡树不一定是丰满树。 m 阶 B-树是一种平衡的 m 叉树，具有如下的性质： (1)每个结点的后件个数小于等于 m； (2)除了根结点的各结点之外，每个结点的后件个数大于等于(m/2)； (3)具有 k 个后件的非叶结点含有 k-1 个键值； (4)所有叶结点在同一层上，而且不附有信息
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 【答案】:A:①B:②C:③D:②E:③ 试题2(1999年试题1) 从供选择的答案中,选出应填入下面叙述中{}内的最确切的解答,把相应编号写在答卷的 对应栏内 结定结点的关键字序列(F,B,J,G,E,A,L,D,C,H)。对它按字母的字典顺序进行排 列,采用不同方法,其最终结果相同,但中间结果是不同的。 She|排序的第一趟扫描(步长为5) 结果是结果应为{A}。 冒泡排序(大数下沉)的第一趟起泡的效果是{B} 快速排序的第一趟结果是{C}。 二路归并排序的第一趟结局是{D} 若以层次序列来建立对应的完全二叉树后,采用筛选法建堆,其第一趟建的堆是{E}。 供选择的答案 A: O (B, F, G, J, A, D, L,E, H, C) 2(B, F,G, J,A,E,D,I,C,H (A, B, D, C, E, F,I, J, G,H 4(C, B, D, A,E, F, L, G,J, H B: (A, B, D, C,F,E, I, J, H, G) 2(A, B, D, C, E, F, I, H, G, J) 3(B, F, G, E, A, I, D, C, H, J) @(B, F, G, J, A, E, D, L, C,H) C:O(C, B, D, A, F,E, I, J, G, H) 2(C,B, D,A,E,F,I, G,J,H (B, A, D, E, F, G, I, J, H, C @(B, C, D, A, E, F, I, J, G,H) D: (B, F, G, J, A, E, D, I, C, H) 2(B, A, D, E, F, G, I, J, H, C) B(A,B, D, C, E, F, I, J, G, H) O(A,B, D, C, F, E,J, I, H, G 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.com.cn389j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 9 页 【答案】：A：① B：② C：③ D：② E：③ 试题 2(1999 年试题 1) 从供选择的答案中，选出应填入下面叙述中{ }内的最确切的解答，把相应编号写在答卷的 对应栏内。 结定结点的关键字序列(F，B，J，G，E，A，I，D，C，H)。对它按字母的字典顺序进行排 列，采用不同方法，其最终结果相同，但中间结果是不同的。 Shell 排序的第一趟扫描(步长为 5) 结果是结果应为{ A }。 冒泡排序(大数下沉)的第一趟起泡的效果是{ B }。 快速排序的第一趟结果是{ C }。 二路归并排序的第一趟结局是{ D }。 若以层次序列来建立对应的完全二叉树后，采用筛选法建堆，其第一趟建的堆是{ E }。 供选择的答案 A：①(B，F，G，J，A，D，I，E，H，C) ②(B，F，G，J，A，E，D，I，C，H) ③(A，B，D，C，E，F，I，J，G，H) ④(C，B，D，A，E，F，I，G，J，H) B：①(A，B，D，C，F，E，I，J，H，G) ②(A，B，D，C，E，F，I，H，G，J) ③(B，F，G，E，A，I，D，C，H，J) ④(B，F，G，J，A，E，D，I，C，H) C：①(C，B，D，A，F，E，I，J，G，H) ②(C，B，D，A，E，F，I，G，J，H) ③(B，A，D，E，F，G，I，J，H，C) ④(B，C，D，A，E，F，I，J，G，H) D：①(B，F，G，J，A，E，D，I，C，H) ②(B，A，D，E，F，G，I，J，H，C) ③(A，B，D，C，E，F，I，J，G，H) ④(A，B，D，C，F，E，J，I，H，G) E：
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! H 【解析】 解答本题的关键是要掌握几种主要的排序算法。排序是数据处理中经常使用的一种重要运 算。插入排序、选择排序、交换排序、基数排序和归并排序是几种常用的排序方法,每种方 法中还包括更具体的方法 插入排序的基本思想是:每一步将一个待排序的记录按其关键码值的大小插入到前面已排序 的文件中的适当位置上,直到全部插完为止。 Shell排序是插入排序的一种,按增量将待排 序记录分组,先取增量i<n,把全部记录分成i个组,所有距离为i的倍数的记录放在一组 中,各组内采用插入顺序。然后取j<i作为增量,重复上述分组和排序工作,直至增量为1, 即所有记录放在一个组中排序为止。题中步长i=5,先将文件分为5组,如下所示 F B A I D C H 然后在组内用插入法排序,进行第1趟扫描,结果如下,只有用箭头连接的组排序位置发生 变化。 ) CE F I G H 交换排序的基本思想是两两比较待排序记录的关键码值,并交换不满足顺序要求的那些偶 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn910j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 10 页 【解析】 解答本题的关键是要掌握几种主要的排序算法。排序是数据处理中经常使用的一种重要运 算。插入排序、选择排序、交换排序、基数排序和归并排序是几种常用的排序方法，每种方 法中还包括更具体的方法。 插入排序的基本思想是：每一步将一个待排序的记录按其关键码值的大小插入到前面已排序 的文件中的适当位置上，直到全部插完为止。Shell 排序是插入排序的一种，按增量将待排 序记录分组，先取增量 i＜n，把全部记录分成 i 个组，所有距离为 i 的倍数的记录放在一组 中，各组内采用插入顺序。然后取 j＜i 作为增量，重复上述分组和排序工作，直至增量为 1， 即所有记录放在一个组中排序为止。题中步长 i=5，先将文件分为 5 组，如下所示： 然后在组内用插入法排序，进行第 1 趟扫描，结果如下，只有用箭头连接的组排序位置发生 变化。 交换排序的基本思想是两两比较待排序记录的关键码值，并交换不满足顺序要求的那些偶