《软件设计师历年试题分析与解答》PDF电子书.pdf_大学文库

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 1 页目录一软件基础知识试题精解 .........................................................................................................3 1.1 数据结构基础 ....................................................................................................................3 1.1.1 主要知识点 .................................................................................................................3 1.1.2 线性表 .........................................................................................................................3 1.1.3 试题解析 .....................................................................................................................7 1.2 程序语言基础知识 ..........................................................................................................24 1.2.1 主要知识点 ...............................................................................................................24 1.2.2 试题分析 ...................................................................................................................27 1.3 操作系统基础知识 ..........................................................................................................38 1.3.1 主要知识点 ...............................................................................................................38 1.3.2 试题解析.......................................................................................................................42 1.4 软件工程基础知识..............................................................................................................53 1.4.1 主要知识点...................................................................................................................53 1.4.2 试题解析.......................................................................................................................57 1.5 数据库系统基础知识 ......................................................................................................74 1.5.1 主要知识点 ...............................................................................................................74 1.5.2 试题解析 ...................................................................................................................76 1.6 多媒体基础知识..................................................................................................................88 1.6.1 主要知识点....................................................................................................................88 1.6.2 试题解析........................................................................................................................89 二硬件基础知识试题精解...........................................................................................................94 2.1 计算机体系结构的主要部件...............................................................................................94 2.1.1 主要知识点....................................................................................................................94 2.1.2 试题解析........................................................................................................................95 2.2 存储器系统........................................................................................................................106 2.2.1 主要知识点..................................................................................................................106 2.2.2 试题解析.....................................................................................................................108 2.3 安全性、可靠性和性能评价............................................................................................115 2.3.1 主要知识点.................................................................................................................. 115 2.3.2 试题解析...................................................................................................................... 117 2.4 体系结构其他基础知识....................................................................................................125 2.4.1 主要知识点..................................................................................................................125 2.4.2 试题分析......................................................................................................................127 2.5 综合性试题........................................................................................................................131 三网络基础知识试题精解.........................................................................................................135 3.1 主要知识点........................................................................................................................135 3.1.1 网络的功能、分类和组成.........................................................................................135 3.1.2 网络协议与标准.........................................................................................................136 3.1.3 局域网技术..................................................................................................................137

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 2 页 3.1.4 广域网技术 .............................................................................................................137 3.1.5 网络的安全性 .........................................................................................................138 3.1.6 Internet/Intranet ......................................................................................................139 3.1.7 客户机/服务器模式 ................................................................................................140 3.1.8 网络计算与电子商务 .............................................................................................140 3.1.9 网络管理基本概念 .................................................................................................141 3.2 试题分析 ........................................................................................................................141 四专业英语试题精解.................................................................................................................153 五软件设计试题精解.................................................................................................................167 5.1 2000 年度软件设计试题解析 ........................................................................................167 5.2 1999 年度软件设计试题解析 ........................................................................................177 5.3 1998 年度软件设计试题解析 ........................................................................................185 5.4 1997 年度软件设计试题解析............................................................................................193 5.5 1996 年度软件设计试题解析............................................................................................199 5.6 1995 年度软件设计试题解析............................................................................................205 5.7 1994 年度软件设计试题解析............................................................................................216 5.8 1993 年度软件设计试题解析............................................................................................226 5.9 1992 年度软件设计试题解析............................................................................................236 5.10 1991 年度软件设计试题解析..........................................................................................247 5.11 1990 年度软件设计试题解析..........................................................................................256 六 CASL 语言程序编制度量精解...........................................................................................267 七 C 语言程序编制度量精解.....................................................................................................293 八 2001 年度上午试题分析与解答............................................................................................337 九 2001 年度下午试题分析与解答............................................................................................348 十 2002 年上午试题分析与解答................................................................................................352 十一 2002 年度下午试题分析与解答........................................................................................371

SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 软件基础知识试题精解高级程序员级软件基础知识试题覆盖面宽,有一定的理论深度,需要考生全面系统地掌握大纲所规定的内容。数据结构、操作系统、程序语言、软件工程是考核的重点。二叉树、图、存储管理、编译原理、软件设计方法等知识点考查的次数比较多,应当是重点中的重点。 1990~2000年软件基础知识试题,按所涉及的知识点统计如下:数据结构基础知识14道题,程序语言基础知识13道题,操作系统基础知识17道题,软件工程21道题,数据库基础知13道题,多媒体基础知识5道题。 1.1数据结构基础 1.1.1主要知识点掌握线情表、多维数组、阵列、栈、树、二叉树,图的定义、存储和操作以及常见的排序和查找算法。重点是二叉树和图以及与其相关的算法。 1.1.1.1数据结构概述数据结构是指数据对象及其相互关系和构造方法,一个数据结构B形式上可以用一个二元组表示为B=(A,R)。其中,A是数据结构中的数据(称为结点)的非空有限集合,R是定义在A上的关系的非空有限集合。数据结构按逻辑关系的不同分为线性结构和非线性结构两大为,共中非线性结构又可分为树形结构和图结构,树形结构又可分为树结构和二叉树结构 1.1.2线性表数据结构中,线性结构习惯称为线性表。线性表是最简单也是最常用的一咱数据结构它是由相同类型的结点组成的有限序列。一个由n个结点e0,e1,en-1组成的线性表记性表,简称n1)线性表的结点个数称为线性表的长度,长度为0的线性表称为空的线为(e0, 性表,简称空表。对于非空线性表,e0是线性表的第一个结点,en-1是线性表的最后一个结点。线性表的结点构成一个序列,对序列中两个相邻结点e-1和ei,称前者是后者的前驱结点,后者是前者的后继结点。线性表最重要的性质是线性表中结点的相对位置是确定的。线性表的结点也称为表元,或称记录,要求线性表的结点是同一类型的任何数据。线性表的结点可由若干个成分组成,其中能唯一标识表元的成分称为了,简称键。线性表包含的表元个数可以动态增加或减少,可以在任何位置插入或删除表元线性表常用的运算可分成4类:査找运算、插入运算、删除运算和其他运算。每类又包括若干种运算。如查找运算就有两种,一种是查找线性表中某个结点的值,另一种是在线性表中查找具有给定键值的记录。有多种存储方式能将线性表存储在计算机内,其中最常用的是顺序存储和链接存储。 (1)线性表的顺序存储线性表的顺序存储是最简单的存储方式。程序通常使用一个足够在的数组,从数组的第个元素开始,将线性表的结点依次存储在数组中。用数组元素的顺序存储来体现线性表中中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.com.cn383j1

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 3 页一软件基础知识试题精解高级程序员级软件基础知识试题覆盖面宽，有一定的理论深度，需要考生全面系统地掌握大纲所规定的内容。数据结构、操作系统、程序语言、软件工程是考核的重点。二叉树、图、存储管理、编译原理、软件设计方法等知识点考查的次数比较多，应当是重点中的重点。 1990～2000 年软件基础知识试题，按所涉及的知识点统计如下：数据结构基础知识 14 道题，程序语言基础知识 13 道题，操作系统基础知识 17 道题，软件工程 21 道题，数据库基础知 13 道题，多媒体基础知识 5 道题。 1.1 数据结构基础 1.1.1 主要知识点掌握线情表、多维数组、阵列、栈、树、二叉树，图的定义、存储和操作以及常见的排序和查找算法。重点是二叉树和图以及与其相关的算法。 1.1.1.1 数据结构概述数据结构是指数据对象及其相互关系和构造方法，一个数据结构 B 形式上可以用一个二元组表示为 B=(A，R)。其中，A 是数据结构中的数据(称为结点)的非空有限集合，R 是定义在 A 上的关系的非空有限集合。数据结构按逻辑关系的不同分为线性结构和非线性结构两大为，共中非线性结构又可分为树形结构和图结构，树形结构又可分为树结构和二叉树结构。 1.1.2 线性表数据结构中，线性结构习惯称为线性表。线性表是最简单也是最常用的一咱数据结构，它是由相同类型的结点组成的有限序列。一个由 n 个结点 e0，e1，…en-1 组成的线性表记为(e0，e1，…en-1)。线性表的结点个数称为线性表的长度，长度为 0 的线性表称为空的线性表，简称空表。对于非空线性表，e0 是线性表的第一个结点，en-1 是线性表的最后一个结点。线性表的结点构成一个序列，对序列中两个相邻结点 ei-1 和 ei，称前者是后者的前驱结点，后者是前者的后继结点。线性表最重要的性质是线性表中结点的相对位置是确定的。线性表的结点也称为表元，或称记录，要求线性表的结点是同一类型的任何数据。线性表的结点可由若干个成分组成，其中能唯一标识表元的成分称为了，简称键。线性表包含的表元个数可以动态增加或减少，可以在任何位置插入或删除表元。线性表常用的运算可分成 4 类：查找运算、插入运算、删除运算和其他运算。每类又包括若干种运算。如查找运算就有两种，一种是查找线性表中某个结点的值，另一种是在线性表中查找具有给定键值的记录。有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。 (1)线性表的顺序存储线性表的顺序存储是最简单的存储方式。程序通常使用一个足够在的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。用数组元素的顺序存储来体现线性表中

SMI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军)培训资料,请勿散发! 结点的先后次序关系。其最大优点是能直接访问线性表中的任意一个结点 (2)线性表的链接存储用单链表存储线性表是线性表的链接方存储方式。从链表的第一个表元开始,将线性表的结点依次存储在链表的各表元中。链表的每个表元除了要存储线性表结点的信息外,还要有一个成分用来存储其后继结点的指针 1.1.1.3栈和队列栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶,另一端为栈底。若有栈S=(S0,sl,,Sn1),则s0为栈底结点,Sn1为栈顶结点。习惯称插入栈的结点为进栈,删除栈的结点为出栈。因为最后进栈的结点必定最先出栈,所以栈具有后进先出的的特性。可以用顺序存储线性表来表示栈,栈也可以用链表实现,用链表实现的栈称为链接栈队列是只允许在一端进入插入,另一端进行删除运算的线性表。允许删除运算的一端称为队首,允许插入运算的端为队尾。习惯称插入队列结点为进队,删除队列结点为出队。若有队列Q=(q,q1,…,qn1)q0为队首结点,qm为队尾结点。因最先进入队列的结点将最先出队,所以队列具有先进先出的特性。可以用顺序存储线性表来表示队列,也可以用链表实现,用链表实现的栈称为链接队列。 1.1.1.4数组和字符串数组是最常用的数据结构之一,一般用来顺序存储线性表。数组由固定个数的元素组成, 全部元素的类型相同,元素依次顺序存储。每个元素对应一个下标,数组元素按数组名和元素的下标引用,数组元素的下标个数称为数组的维数。在C语言中,约定数组的第1个元素的下标为0,其余依次类推,由n个元素组成的数组,其最后一个元素的下标为n-1。数组元素可以是任何类型的,当元素本身又是数组时,就构成多维数组多维数组是一维数组的推广,多维数组中最常用的是二维数组。多维数组的所有元素并未排在一个线性序列里,要顺序存储多维数组就需要按一定次序把所有的数组元素排在一个线性序列里,常用的排列次序有行优先顺序和列优先顺序两种。对于多维数组,C语言按行优先顺序存放字符串是非数值处理应用中重要的处理对象。字符串是由某字符集上的字符所组成的任何有限字符序列。不包含任何字符的字符串称为空字符串。字符串所包含的有效字符数称为字符串长度。一个字符串中任意连续的子序列称为该字符串的子串。 1.1.1.5树树和二叉树是非线性数据结构,用它们能很好地描述有分支和层次特性的数据集合。习惯称树和二叉树数据结枃为树形结构。在许多算法中,都经常使用树形结构描述问题的求解过程或表示求解的对策等。由于二叉树有确定的分支个数,又可以为空,有良好的递归性质, 与一般树相比较,特别适宜于程序设计,因此也常将树转换成二叉树进行处理。 (1)树的基本概念树是一种多分支多层次数据结构,由一组结点组成。由于它呈现出与自然界的树类似的结构形式,所以称它为树。树是由一个或多个结点组成的有限集T,它满足以下两个条件 ①有一个特定的结点,称为根结点中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.com.cn384j1

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 4 页结点的先后次序关系。其最大优点是能直接访问线性表中的任意一个结点。（2）线性表的链接存储用单链表存储线性表是线性表的链接方存储方式。从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。链表的每个表元除了要存储线性表结点的信息外，还要有一个成分用来存储其后继结点的指针。 1.1.1.3 栈和队列栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶，另一端为栈底。若有栈 S=(s0，s1，…，sn-1)，则 s0 为栈底结点，sn-1 为栈顶结点。习惯称插入栈的结点为进栈，删除栈的结点为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的的特性。可以用顺序存储线性表来表示栈，栈也可以用链表实现，用链表实现的栈称为链接栈。队列是只允许在一端进入插入，另一端进行删除运算的线性表。允许删除运算的一端称为队首，允许插入运算的端为队尾。习惯称插入队列结点为进队，删除队列结点为出队。若有队列 Q=(q0，q1，…，qn-1)q0 为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，所以队列具有先进先出的特性。可以用顺序存储线性表来表示队列，也可以用链表实现，用链表实现的栈称为链接队列。 1.1.1.4 数组和字符串数组是最常用的数据结构之一，一般用来顺序存储线性表。数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，数组元素的下标个数称为数组的维数。在 C 语言中，约定数组的第 1 个元素的下标为 0，其余依次类推，由 n 个元素组成的数组，其最后一个元素的下标为 n-1。数组元素可以是任何类型的，当元素本身又是数组时，就构成多维数组。多维数组是一维数组的推广，多维数组中最常用的是二维数组。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组就需要按一定次序把所有的数组元素排在一个线性序列里，常用的排列次序有行优先顺序和列优先顺序两种。对于多维数组，C 语言按行优先顺序存放。字符串是非数值处理应用中重要的处理对象。字符串是由某字符集上的字符所组成的任何有限字符序列。不包含任何字符的字符串称为空字符串。字符串所包含的有效字符数称为字符串长度。一个字符串中任意连续的子序列称为该字符串的子串。 1.1.1.5 树树和二叉树是非线性数据结构，用它们能很好地描述有分支和层次特性的数据集合。习惯称树和二叉树数据结构为树形结构。在许多算法中，都经常使用树形结构描述问题的求解过程或表示求解的对策等。由于二叉树有确定的分支个数，又可以为空，有良好的递归性质，与一般树相比较，特别适宜于程序设计，因此也常将树转换成二叉树进行处理。 (1)树的基本概念树是一种多分支多层次数据结构，由一组结点组成。由于它呈现出与自然界的树类似的结构形式，所以称它为树。树是由一个或多个结点组成的有限集 T，它满足以下两个条件： ①有一个特定的结点，称为根结点；

SMI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军)培训资料,请勿散发! ②其余的结点分成(m>m=0)个互不相交的有限集T0,T1,…,Tm-1。其中每个集合又都是一棵树,称T0,T1,…,Tm-1为根结点的子树。树的定义是递归的,即一棵树由子树构成,子树又由更小的子树构成。一棵树至少有个结点。一个结点的子树数目,称为结点的度。树中各结点的度的最大值称为树的度。 (2)树的存储结构树是非线性的结构,不能简单地用结点的线性表来表示。树有多种实用的存储结构,最常用是标准存储结构和带逆存储结构。在树的标准存储结构中,树中的结点内容可分成两部分:结点的数据和指向子结点的指针数组。当程序需从结点返回到其父结点时,需要在树的结点中存有其父结点的位置信息,这种存储形式就是带逆存储结构。 (3)树的遍历在应用树结构时,常要求按某种次序获得树中全部结点的信息,这可通过树的遍历操作来实现。常用的树的遍存方法有: 树的前序遍历。首先访问根结点,然后从左到右按前序遍历根结点的各棵子树。树的后序遍历。首先从左到右按后序遍历根结点的各棵子树,然后访问根结点树的层次遍历。首先访问处于0层上的根结点,然后从左到有依次访问处于1层层上的结点等,即自上而下从左到右逐层访问树各层上的结点。访问树中的所有叶子结点 1.1.1.6二叉树 (1)二叉树的基本概念与一般的树结构相比较,二叉树在结构上更规范、更有确定性,二叉树的每个结点有两棵子二叉树,分别简称为左子树和右子树。因二叉树可以为空,所以二叉树中的结点可能没有子结点。二叉树的定义为:二叉树是一个有限的结点集合,该集合或者为空,或者由一个根结点及其两棵互不相交的、左右二叉子树所组成二叉树与树不同,首先二叉树可以为空,空的二叉树没有结点。另外,在二叉树中,结点的子树是有序的,分左、右两棵子二叉树。一般情况下,二叉树常采用类似树的标准存储形式来存储 (2)二叉树的遍历树的所有遍历方法都适用于二叉树,常用的二叉树遍历方法有3种前序遍历。访问根结点→按前序遍历根结点的左子树→按前序遍历根结点的右子树中序遍历。按中序遍历根结点的左子树→访问根结点→按中序遍历根结点的右子树后序遍历。按后序遍历根结点的左子树→按后序遍历根结点的右子树→访问根结点注意以上3种遍历方法都是递定义的 1.1.1.7二叉查找树査找树便于链式存储,还能实现快速查找。作为一种特殊的二叉树,它或者为空,或者满足下列条件: 若该树根结点的左子树非空,其左子树所有结点的键值都小于该树根结点的键值若该树根结点的右子树非空,其左子树所有结点的键值都大于该树根结点的键值。该树的根结点的左子树和右子树均为查找树。中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.com.cn385j1

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 5 页 ②其余的结点分成(m＞m=0)个互不相交的有限集 T0，T1，…，Tm-1。其中每个集合又都是一棵树，称 T0，T1，…，Tm-1 为根结点的子树。树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。一棵树至少有一个结点。一个结点的子树数目，称为结点的度。树中各结点的度的最大值称为树的度。 (2)树的存储结构树是非线性的结构，不能简单地用结点的线性表来表示。树有多种实用的存储结构，最常用是标准存储结构和带逆存储结构。在树的标准存储结构中，树中的结点内容可分成两部分：结点的数据和指向子结点的指针数组。当程序需从结点返回到其父结点时，需要在树的结点中存有其父结点的位置信息，这种存储形式就是带逆存储结构。 (3)树的遍历在应用树结构时，常要求按某种次序获得树中全部结点的信息，这可通过树的遍历操作来实现。常用的树的遍存方法有： ·树的前序遍历。首先访问根结点，然后从左到右按前序遍历根结点的各棵子树。 ·树的后序遍历。首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。 ·树的层次遍历。首先访问处于 0 层上的根结点，然后从左到有依次访问处于 1 层、2 层上的结点等，即自上而下从左到右逐层访问树各层上的结点。 ·访问树中的所有叶子结点。 1.1.1.6 二叉树 (1)二叉树的基本概念与一般的树结构相比较，二叉树在结构上更规范、更有确定性，二叉树的每个结点有两棵子二叉树，分别简称为左子树和右子树。因二叉树可以为空，所以二叉树中的结点可能没有子结点。二叉树的定义为：二叉树是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的、左右二叉子树所组成。二叉树与树不同，首先二叉树可以为空，空的二叉树没有结点。另外，在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。一般情况下，二叉树常采用类似树的标准存储形式来存储。 (2)二叉树的遍历树的所有遍历方法都适用于二叉树，常用的二叉树遍历方法有 3 种： ·前序遍历。访问根结点→按前序遍历根结点的左子树→按前序遍历根结点的右子树 ·中序遍历。按中序遍历根结点的左子树→访问根结点→按中序遍历根结点的右子树 ·后序遍历。按后序遍历根结点的左子树→按后序遍历根结点的右子树→访问根结点注意以上 3 种遍历方法都是递定义的。 1.1.1.7 二叉查找树查找树便于链式存储，还能实现快速查找。作为一种特殊的二叉树，它或者为空，或者满足下列条件： ·若该树根结点的左子树非空，其左子树所有结点的键值都小于该树根结点的键值。 ·若该树根结点的右子树非空，其左子树所有结点的键值都大于该树根结点的键值。 ·该树的根结点的左子树和右子树均为查找树

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)所有叶结点在同一层上，而且不附有信息