计算机二级公共基础知识题库及答案分析

全国计算机等级考试二级公共基础知识考题库

第一章 数据结构

一、选择题

（1）下列数据结构中，能用二分法进行查找的是

A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 【答案】A

【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大．但允许相邻元素值相等)的。选项A正确。

（2）下列关于栈的描述正确的是

A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素

C）栈是特殊的线性表，只能在一端插入或删除元素

D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 【答案】C

【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项A、选项B和选项D错误，正确答案是选项C。

（3）下列叙述中正确的是

A）一个逻辑数据结构只能有一种存储结构

B）数据的逻辑结构属于线性结构，存储结构属于非线性结构

C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 【答案】D

【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。

(4)算法执行过程中所需要的存储空间称为算法的

A）时间复杂度B）计算工作量C）空间复杂度D）工作空间 【答案】c

【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据 所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。

1 / 91

(5)下列关于队列的叙述中正确的是

A）在队列中只能插入数据B）在队列中只能删除数据 C）队列是先进先出的线性表D）队列是先进后出的线性表 【答案】c

【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。 (6)设有下列二叉树： 对此二叉树后序遍历的结果为 A）ABCDEF B）BDAECF C）ABDCEF D）DBEFCA 【答案】D

【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求后序遍历。其遍历顺序应该为：后序遍历左子树一>后序遍历右子树一>访问根结点。按照定义，后序遍历序列是DBEFCA，故答案为D。

(7) 下列叙述中正确的是( )

A)程序执行的效率与数据的存储结构密切相关 B)程序执行的效率只取决于程序的控制结构 C)程序执行的效率只取决于所处理的数据量 D)以上三种说法都不对 【答案】A

【解析】本题考查程序效率。程序效率是指程序运行速度和程序占用的存储空间。影响程序效率的因素是多方面的，包括程序的设计、使用的算法、数据的存储结构等。在确定数据逻辑结构的基础上，选择一种合适的存储结构，可以使得数据操作所花费的时间少，占用的存储空间少，即提高程序的效率。因此，本题选项A的说法是正确的。

(8) 下列叙述中正确的是( )

A)数据的逻辑结构与存储结构必定是一一对应的

B)由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C)程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线线结构 D)以上三种说法都不对

2 / 91

A B C D E F 【答案】D

【解析】本题考查数据结构的基本知识。

数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种，即顺序存储结构和链式存储结构。顺序存储结构是把数据元素存储在一块连续地址空间的内存中；链式存储结构是使用指针把相互直接关联的节点链接起来。因此，这两种存储结构都是线性的。可见，逻辑结构和存储结构不是一一对应的。因此，选项A和选项B的说法都是错误的。

无论数据的逻辑结构是线性的还是非线性的，只能选择顺序存储结构或链式存储结构来实现存储。程序设计语言中，数组是内存中一段连续的地址空间，可看作是顺序存储结构。可以用数组来实现树型逻辑结构的存储，比如二叉树。因此，选项c的说法是错误的

(9) 冒泡排序在最坏情况下的比较次数是( ) A)n(n+1)/2 B)nlog2n C)n(n-1)/2 D)n/2 【答案】C

【解析】冒泡排序的基本思想是：将相邻的两个元素进行比较，如果反序，则交换；对于一个待排序的序列，经一趟排序后，最大值的元素移动到最后的位置，其他值较大的元素也向最终位置移动，此过程称为一趟冒泡。对于有n个数据的序列，共需n-1趟排序，第i趟对从l到n-i个数据进行比较、交换。冒泡排序的最坏情况是待排序序列逆序，第l趟比较n-1次，第2趟比较n-2次。依此类推，最后趟比较1次，一共进行n-l趟排序。因此，冒泡排序在最坏情况下的比较次数是(n-1)+(n-2)+…+l，结果为n(n-1)/2。本题的正确答案是选项c。

(10) 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为( ) A)219 B)221 C)229 D)231 【答案】A

【解析】本题考查数据结构中二叉树的性质。二叉树满足如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点)数为n0，而其度数为2的结点数为n2，则n0= n2+l。

根据这条性质可知，若二叉树中有70个叶子结点，则其度为2的结点数为70-1，即69个。二叉树的总结点数是度为2、度为1和叶子结点的总和，因此，题目中的二叉树总结点数为69+80+70，即219。因此，本题的正确答案是选项A。

(11) 下列叙述中正确的是( )

A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的

D)算法的时间复杂度与空间复杂度一定相关 【答案】B

【解析】本题考查数据结构中有关算法的基本知识和概念。数据的结构，直接影响算法的选择和效率。而数据结构包括两方面，即数据的逻辑结构和数据的存储结构。因此，数据的逻辑结构和存储结构都影响算

3 / 91

法的效率。选项A的说法是错误的。算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。因此，选项B的说法是正确的。

数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种，即顺序存储结构和链式存储结构。可见，逻辑结构和存储结构不是一一对应的。因此，选项c的说法是错误的。有时人们为了提高算法的时间复杂度，而以牺牲空间复杂度为代价。但是，这两者之间没有必然的联系。因此，选项D的说法是错误的。

(12)下列关于算法的时间复杂度陈述正确的是 A） 算法的时间复杂度是指执行算法程序所需要的时间 B） 算法的时间复杂度是指算法程序的长度

C） 算法的时间复杂度是指算法执行过程中所需要的基本运算次数 D） 算法的时间复杂度是指算法程序中的指令条数 【答案】C

【解析】算法的时间复杂度是指执行算法所需要的计算工作量，也就是算法在执行过程中所执行的基本运算的次数，而不是指程序运行需要的时间或是程序的长度。

(13)下列关于栈的叙述中正确的是

A）在栈中只能插入数据 B）在栈中只能删除数据 C）栈是先进先出的线性表 D）栈是先进后出的线性表 【答案】D

【解析】对栈可进行插入和删除数据的操作，但必须牢记插入和删除数据都只能是在栈顶，是一种特殊的线性表。所以栈是先进后出的线性表。

(14)设有下列二叉树：

A B C

FF D E F

对此二叉树中序遍历的结果为

A）ABCDEF B）DAECF C）BDAECF D）DBEFCA 【答案】C

【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求中序遍历，其遍历顺序应该为：中序遍历左子树->访问根结点->中序遍历右子树。按照定义，中序遍历序列是BDAECF，故答案为B。

4 / 91

(15)按照“后进先出”原则组织数据的数据结构是 A）队列 B）栈 C）双向链表 【答案】B

【解析】“后进先出”表示最后被插入的元素最先能被删除。选项A中，队列是指允许在一端进行插入、而在另一端进行删除的线性表，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除，队列又称为“先进先出”的线性表，它体现了“先来先服务”的原则：选项B中，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素，栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。队列和栈都属于线性表，它们具有顺序存储的特点，所以才有“先进先出”和“后进先出”的数据组织方式。双向链表使用链式存储方式．二叉树也通常采用链式存储方式，它们的存储数据的空间可以是不连续的，各个数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。所以选项c和选项D错。

(16)下列叙述中正确的是

A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 【答案】A

【解析】一个非空的数据结构如果满足下列两个条件：(1)有且只有一个根结点;(2)每一个结点最多有一个前件，也最多有一个后件。则称为线性结构。线性链表是线性表的链式存储结构，选项A的说法是正确的。栈与队列是特殊的线性表，它们也是线性结构，选项B的说法是错误的；双向链表是线性表的链式存储结构，其对应的逻辑结构也是线性结构，而不是非线性结构，选项c的说法是错误的；二叉树是非线性结构，而不是线性结构，选项D的说法是错误的。因此，本题的正确答案为A

(17)对如下二叉树

进行后序遍历的结果为 A）ABCDEF C）ABDECF 【答案】D

5 / 91

D）二叉树

A B C D E F B）DBEAFC D）DEBFCA

【解析】二叉树后序遍历的简单描述如下：若二叉树为空，则结束返回。否则（1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。也就是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。根据后序遍历的算法，后序遍历的结果为DEBFCA。

(18) 下列对队列的叙述正确的是( ) A)队列属于非线性表

B)队列按“先进后出”原则组织数据 C)队列在队尾删除数据

D)队列按“先进先出”原则组织数据 【答案】D

【解析】本题考查数据结构中队列的基本知识。队列是一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。在队列中，允许插入元素的一端叫做队尾，允许删除的一端则称为队头。这与日常生活中的排队是一致的，最早进入队列的人最早离开，新来的人总是加入到队尾。因此，本题中只有选项D的说法是正确的。

(19) 对下列二叉树进行前序遍历的结果为( )

A) DYBEAFCZX B) YDEBFZXCA C) ABDYECFXZ D) ABCDEFXYZ 【答案】C

【解析】本题考查数据结构中二叉树的遍历。根据对二叉树根的访问先后顺序不同，分别称为前序遍历、中序遍历和后序遍历。这三种遍历都是递归定义的，即在其子树中也按照同样的规律进行遍历。下面就是前序遍历方法的递归定义。当二叉树的根不为空时，依次执行如下3个操作： (1)访问根结点 (2)按先序遍历左子树 (3)按先序遍历右子树

根据如上前序遍历规则，来遍历本题中的二叉树。首先访问根结点，即A，然后遍历A的左子树。遍历左子树同样按照相同的规则首先访问根结点B，然后遍历B的左子树。遍历B的左子树，首先访问D，然后访问D的左子树，D的左子树为空,接下来访问D的右子树，即Y。遍历完B的左子树后，再遍历B的右子树，即E。到此遍历完A的左子树，接下来遍历A的右子树。按照同样的规则，首先访问C，然后遍历c的左子树。即F。c的左子树遍历完，接着遍历c的右子树。首先访问右子树的根结点X，然后访问X的左子树，X的左子树，即Z，接下来访问X的右子树，右子树为空。到此，把题目的二叉树进行了一次前序遍历。遍历的结果为ABDYECFXZ，故本题的正确答案为选项C。

(20) 某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为( )

6 / 91

A) n+1 B) n-1 C) 2n D) n/2 【答案】A

【解析】本题考查数据结构中二叉树的性质。 二叉树满足如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点)数为no，而其度数为2的结点数为n2，则n0=n2+l。

根据这条性质可知，若二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为n+l。因此，本题的正确答案是选项A。

(21)在深度为7的满二叉树中，叶子结点的个数为 A）32 【答案】C

【解析】在二叉树的第k层上，最多有2(k≥1)个结点。对于满二叉树来说，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2个结点。因此，在深度为7的满二叉树中，所有叶子结点在第7层上．即其结点数为2=2=64因此．本题的正确答案为c。

(22)下列叙述中正确的是

A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则期时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对 【答案】D

【解析】时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。人们都希望选择一个既省存储空间、又省执行时间的算法。然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。时间和空间的效率往往是一对矛盾，很难做到两全。但是，这不适用于所有的情况，也就是说时间复杂度和空间复杂度之间虽然经常矛盾。但是二者不存在必然的联系。因此，选项A、B、c的说法都是错误的。故本题的正确答案是D。

(23)在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为 A）63 【答案】B

【解析】在长度为64的有序线性表中，其中的64个数据元素是按照从大到小或从小到大的顺序排列有序的。在这样的线性表中进行顺序查找，最坏的情况就是查找的数据元素不在线性表中或位于线性表的最后。按照线性表的顺序查找算法，首先用被查找的数据和线性表的第一个数据元素进行比较。若相等，则查找成功，否则，继续进行比较，即和线性表的第二个数据元素进行比较。同样，若相等，则查找成功，否则，继续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最后一个元素，算法才结束。因此，在长度为64的有序线性表中进行顺序查找，最坏的情况下需要比较64次。因此，本题的正确答案为B。

7 / 91

k-1

7-1

k-1

k-1

B）31 C）64 D）63

B）64 C）6 D）7

(24)对下列二叉树 进行中序遍历的结果是 A）ACBDFEG C）ABDCGEF

【答案】A

【解析】二叉树的中序遍历递归算法为：如果根不空，则(1)按中序次序访问左子树；(2)访问根结点：(3)按中序次序访问右子树。否则返回。本题中，根据中序遍历算法．应首先按照中序次序访问以c为根结点的左子树，然后再访问根结点F，最后才访问以E为根结点的右子树。遍历以c为根结点的左子树同样要遵循中序遍历算法，因此中序遍历结果为ACBD；然后遍历根结点F；遍历以E为根结点的右子树，同样要遵循中序遍历算法，因此中序遍历结果为EG。最后把这三部分的遍历结果按顺序连接起来，中序遍历结果为ACBDFEG。因此，本题的正确答案是A。

（25）数据的存储结构是指______。

A）存储在外存中的数据

B）数据所占的存储空间量

A B C D F E G

B）ACBDFGE

D）FCADBEG

C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 【答案】D

【解析】数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。所以选项D正确。

（26）下列关于栈的描述中错误的是______。

A） 栈是先进后出的线性表 B） 栈只能顺序存储 C） 栈具有记忆作用

D） 对栈的插入与删除操作中，不需要改变栈底指针 【答案】B

【解析】本题考核栈的基本概念，我们可以通过排除法来确定本题的答案。栈是限定在一端进行插入与删除的线性表，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的，这便是栈的记忆作用，所以选项A和选项C正确。对栈进行插入和删除操作时，栈顶位置是动态变化的，栈底指针不变，选项D正确。由此可见，选项B的描述错误。

（27）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。

A）冒泡排序为n/2

B）冒泡排序为n

8 / 91

C）快速排序为n 【答案】D

D）快速排序为n(n-1)/2

【解析】假设线性表的长度为n，在最坏情况下，冒泡排序和快速排序需要的比较次数为n(n—1)／2。由此可见，选项D正确。

（28）对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A）log2 【答案】C

【解析】在长度为n的线性表中进行顺序查找，最坏情况下需要比较n次。选项C正确。

（29）下列对于线性链表的描述中正确的是______。

A） 存储空间不一定是连续，且各元素的存储顺序是任意的 B） 存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C） 存储空间必须连续，且前件元素一定存储在后件元素的前面 D） 存储空间必须连续，且各元素的存储顺序是任意的 【答案】A

【解析】在链式存储结构中，存储数据的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据元素之间的逻辑关系，是由指针域来确定的。由此可见，选项A的描述正确。

（30）某二叉树中度为2的结点有18个，则该二叉树中有 ____ 个叶子结点。 【答案】19

【解析】二叉树具有如下性质：在任意一棵二叉树中，度为O的结点(即叶子结点)总是比度为2的结点多一个。根据题意，度为2的节点为18个，那么，叶子结点就应当是19个。

（1）线性表若采用链式存储结构时，要求内存中可用存储单元的地址 A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的 D）连续不连续都可以

解析： 在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。故本题答案应该为选项D）

（2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A）冒泡排序 B）选择排序 C）快速排序 D）归并排序

解析： 从平均时间性能而言，快速排序最佳，其所需时间最少，但快速排序在最坏情况下的时间性能不

9 / 91

n

B）n/2 C）n D）n+1

如堆排序和归并排序。当序列中的记录基本有序或元素个数较少时，冒泡排序和简单选择排序为最佳排序方法，故本题答案应该为选项A）。

（3）下列叙述中，错误的是

A）数据的存储结构与数据处理的效率密切相关 B）数据的存储结构与数据处理的效率无关

C）数据的存储结构在计算机中所占的空间不一定是连续的 D）一种数据的逻辑结构可以有多种存储结构

解析： 一般来说，一种数据结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。故本题答案应该为选项B）。

（4）希尔排序属于 A）交换排序 B）归并排序 C）选择排序 D）插入排序

解析： 希尔排序的基本思想是把记录按下标的一定增量分组，对每组记录使用插入排序，随增量的逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时，整个数据合成一组，构成一组有序记录，故其属于插入排序方法。故本题答案应该为选项D）。

（1）栈和队列的共同特点是 A）都是先进先出 B）都是先进后出

C）只允许在端点处插入和删除元素 D）没有共同点

解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。故本题答案应该为选项C）。

（2）已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 A）acbed B）decab C）deabc D）cedba

解析： 依据后序遍历序列可确定根结点为c；再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为e，由中序遍历序列可知其左子树为d，右子树由ba构成，如下图所示。求得该二叉树的前序遍历序列为选项D）。

10 / 91

（3）链表不具有的特点是 A）不必事先估计存储空间 B）可随机访问任一元素 C）插入删除不需要移动元素 D）所需空间与线性表长度成正比

解析： 链表采用的是链式存储结构，它克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：① 每个结点中的指针域需额外占用存储空间；② 链式存储结构是一种非随机存储结构。故本题答案应该为选项D）。

（6）算法的时间复杂度是指 A）执行算法程序所需要的时间 B）算法程序的长度

C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数

解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。故本题答案应该为选项A）。

（1）已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为 A）GEDHFBCA B）DGEBHFCA C）ABCDEFGH D）ACBFEDHG

解析： 利用前序和中序遍历的方法可以确定二叉树的结构，具体步骤如下：① 前序遍历的第一个结点A为树的根结点；② 中序遍历中A的左边的结点为A的左子树，A右边的结点为A的右子树；③ 再分别对A的左右子树进行上述两步处理，直到每个结点都找到正确的位置。故本题答案应该为选项B）。

（2）树是结点的集合，它的根结点数目是 A）有且只有1 B）1或多于1

11 / 91

C）0或1 D）至少2

解析： 树是一个或多个结点组成的有限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时又是一棵树。树有且只有1个根结点。故本题答案应该为选项A）。

（3）如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 A）e3,e1,e4,e2 B）e2,e4,e3,e1 C）e3,e4,e1,e2 D）任意顺序

解析： 由栈\后进先出\的特点可知：A）中e1不可能比e2先出，C）中e3不可能比e4先出，且e1不可能比e2先出，D）中栈是先进后出的，所以不可能是任意顺序。B）中出栈过程如图所示：

故本题答案应该为选项B）。

（4）在设计程序时，应采纳的原则之一是 A）不限制goto语句的使用 B）减少或取消注解行 C）程序越短越好

D）程序结构应有助于读者理解

解析：滥用goto 语句将使程序流程无规律，可读性差，因此A）不选；注解行有利于对程序的理解，不应减少或取消，B）也不选；程序的长短要依照实际情况而论，而不是越短越好，C）也不选。故本题答案应该为选项D）。

（5）程序设计语言的基本成分是数据成分、运算成分、控制成分和 A）对象成分 B）变量成分 C）语句成分 D）传输成分

解析： 程序设计语言是用于书写计算机程序的语言，其基本成分有以下4种，数据成分：用来描述程序中的数据。运算成分：描述程序中所需的运算。控制成分：用来构造程序的逻辑控制结构。传输成分：定义数据传输成分，如输入输出语言。故本题答案应该为选项D）。

（1）循环链表的主要优点是

12 / 91

A）不再需要头指针了

B）从表中任一结点出发都能访问到整个链表

C）在进行插入、删除运算时，能更好的保证链表不断开 D）已知某个结点的位置后，能够容易的找到它的直接前件

解析： 循环链表就是将单向链表中最后一个结点的指针指向头结点，使整个链表构成一个环形，这样的结构使得从表中的任一结点出发都能访问到整个链表。故本题答案应该为选项B）。

（2）栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是 A）ABCED B）DCBEA C）DBCEA D）CDABE

解析： 栈操作原则上“后进先出”，栈底至栈顶依次存放元素A、B、C、D，则表明这4个元素中D是最后进栈，B、C处于中间，A最早进栈。所以出栈时一定是先出D，再出C，最后出A。故本题答案应该为选项B）。

（3）对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。 A) N+1 B) N C) (N+1)/2 D) N/2

解析：[答案]B，很简单，我们的二级程序设计语言书中都有此算法，另外还要掌握二分法查找，这也是我们二级中常考的。那么二分法最坏的情况为多少次呢？log2 的最小整数值。比如n为4，最坏的情况要比较3次；n为18，最坏的情况要比较5次。

（1）下列叙述中正确的是 A）线性表是线性结构 B）栈与队列是非线性结构 C）线性链表是非线性结构 D）二叉树是线性结构

解析： 线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的；栈、队列、线性链表实际上也是线性表，故也是线性结构；树是一种简单的非线性结构。故本题答案应该为选项A）。

（2）非空的循环单链表head的尾结点（由p所指向），满足 A）p->next==NULL B）p==NULL

13 / 91

n

C）p->next=head D）p=head

解析： 循环链表就是将链表的最后一个结点指向链表头结点（或第一个结点），即p->next=head。故本题答案应该为选项C）。

（3）已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是 A）堆排序 B）直接插入排序 C）快速排序 D）直接选择排序

解析： 当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少，故答案为选项B）。

（1）假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为 A）log2 B）n

2

n

C）O（n1.5） D）n（n-1）/2

解析： 假设线性表的长度为n，则在最坏情况下，冒泡排序要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n（n-1）/2。故本题答案应该为选项D）。

（2）算法分析的目的是 A）找出数据结构的合理性

B）找出算法中输入和输出之间的关系 C）分析算法的易懂性和可靠性 D）分析算法的效率以求改进

解析： 算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。故本题答案应该为选项D）。

（3）线性表L=（a1,a2,a3,…ai，…an），下列说法正确的是 A）每个元素都有一个直接前件和直接后件 B）线性表中至少要有一个元素

C）表中诸元素的排列顺序必须是由小到大或由大到小

D）除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件

解析： 线性表可以为空表；第一个元素没有直接前件，最后一个元素没有直接后件；线性表的定义中，元素的排列并没有规定大小顺序。故本题答案应该为选项D）。

14 / 91

（4）在单链表中，增加头结点的目的是 A）方便运算的实现 B）使单链表至少有一个结点 C）标识表结点中首结点的位置 D）说明单链表是线性表的链式存储实现

解析： 头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。故本题答案应该为选项A）。

（1）算法的空间复杂度是指 A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的存储空间 D）执行过程中所需要的存储空间

解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。故本题答案应该为选项D）。

（2）用链表表示线性表的优点是 A）便于随机存取

B）花费的存储空间较顺序存储少 C）便于插入和删除操作

D）数据元素的物理顺序与逻辑顺序相同

解析： 链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。故本题答案应该为选项C）。

（3）数据结构中，与所使用的计算机无关的是数据的 A）存储结构 B）物理结构 C）逻辑结构 D）物理和存储结构

解析： 数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。故本题答案应该为选项C）。

（1）由两个栈共享一个存储空间的好处是 A）减少存取时间，降低下溢发生的机率 B）节省存储空间，降低上溢发生的机率

15 / 91

B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C、存储空间必须连续，且前件元素一定存储在后件元素的前面 D、存储空间必须连续，且各元素的存储顺序是任意的

解析:本题考查的是线性单链表、双向链表与循环链表的结构及其基本运算。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 故本题答案为A。

1. 算法的时间复杂度是指______。 A、执行算法程序所需要的时间 B、算法程序的长度

C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数

解析:所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。 本题答案是C。

2. 下列叙述中正确的是______。 A、线性表是线性结构 B、栈与队列是非线性结构 C、线性链表是非线性结构 D、二叉树是线性结构

解析:根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。 所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。 本题答案是A。

3. 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。 A、349 B、350 C、255 D、351

解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

具有n个结点的完全二叉树，其父结点数为int(n/2)，而叶子结点数等于总结点数减去父结点数。本题n=699，故父结点数等于int(699/2)=349，叶子结点数等于699-349=350。

21 / 91

本题答案是B。

1. 算法的空间复杂度是指______。 A、算法程序的长度 B、算法程序中的指令条数 C、算法程序所占的存储空间 D、算法执行过程中所需要的存储空间

解析:一个算法的空间复杂度，一般是指执行这个算法所需的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。 本题答案是D。

2. 下列关于栈的叙述中正确的是______。 A、在栈中只能插入数据 B、在栈中只能删除数据 C、栈是先进先出的线性表 D、栈是先进后出的线性表

解析:栈是限定在一端进行插入与删除的线性表。

栈是按照\先进后出\的或后进先出的原则组织数据的，因此，栈也被称为\先进后出\表或\后进先出\表。

本题答案是D。

3. 在深度为5的满二叉树中，叶子结点的个数为______。 A、32 B、31 C、16 D、15

解析:所谓满二叉树是指这样的一种二叉树：除最后一层外，每层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2个结点，且深度为m的满二叉树有2个结点。

在满二叉树中，最后一层的结点个数就是叶子结点的个数，本题中深度为5，故叶子结点数为2=2=16。 本题答案是C。

1. 算法一般都可以用哪几种控制结构组合而成______。 A、循环、分支、递归 B、顺序、循环、嵌套 C、循环、递归、选择 D、顺序、选择、循环

解析:算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。

22 / 91

5-1

4

m

K-1

本题答案为D。

2. 数据的存储结构是指______。 A、数据所占的存储空间量

B、数据的逻辑结构在计算机中的表示 C、数据在计算机中的顺序存储方式 D、存储在外存中的数据

解析:数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。 本题答案为B。

3. 设有下列二叉树：

A B C E F D 对此二叉树中序遍历的结果为______。

A、ABCDEF B、DBEAFC C、ABDECF D、DEBFCA

解析:所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 本题答案为B。

1. 在计算机中，算法是指______。 A、查询方法 B、加工方法

C、解题方案的准确而完整的描述 D、排序方法

解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。 本题答案为C。

2. 栈和队列的共同点是______。 A、都是先进后出 B、都是先进先出

C、只允许在端点处插入和删除元素 D、没有共同点

解析:栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种\后进先出\的线性表；而队列只允许在表的一端进行插入

23 / 91

操作，在另一端进行删除操作，是一种\先进先出\的线性表。 本题答案为C。

3. 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。 A、cedba B、acbed C、decab D、deabc

解析:依据后序遍历序列可确定根结点为c；再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为e，由中序遍历序列可知其左子树为d，右子树由ba构成。求得该二叉树的前序遍历序列为选项A。 本题答案为A。

4. 在下列几种排序方法中，要求内存量最大的是______。 A、插入排序 B、选择排序 C、快速排序 D、归并排序

解析:快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序；插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中，从而得到一个新的序列；选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置），然后对剩下的子表采用同样的方法，直到表空为止；归并排序是将两个或两个以上的有序表组合成一个新的有序表。 本题答案为D。

1. 数据结构中，与所使用的计算机无关的是数据的______。 A、存储结构 B、物理结构 C、逻辑结构 D、物理和存储结构

解析:数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。 本题答案为C。

2. 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。 A、ABCED B、DBCEA C、CDABE D、DCBEA

24 / 91

解析: 栈操作原则是\后进先出\，栈底至栈顶依次存放元素A、B、C、D，则表明这4个元素中D是最后进栈，B、C处于中间，A最早进栈。所以出栈时一定是先出D，再出C，最后出A。 本题答案为D。

3. 线性表的顺序存储结构和线性表的链式存储结构分别是______。 A、顺序存取的存储结构、顺序存取的存储结构 B、随机存取的存储结构、顺序存取的存储结构 C、随机存取的存储结构、随机存取的存储结构 D、任意存取的存储结构、任意存取的存储结构

解析:顺序存储结构中，数据元素存放在一组地址连续的存储单元中，每个数据元素地址可通过公式LOC(ai)=LOC(a1)+(i-1)L计算得到，从而实现了随机存取。对于链式存储结构，要对某结点进行存取，都得从链的头指针指向的结点开始，这是一种顺序存取的存储结构。 本题答案为B。

4. 在单链表中，增加头结点的目的是______。 A、方便运算的实现 B、使单链表至少有一个结点 C、标识表结点中首结点的位置 D、说明单链表是线性表的链式存储实现

解析:头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。 本题答案为A。

1. 下面叙述正确的是______。

A、算法的执行效率与数据的存储结构无关

B、算法的空间复杂度是指算法程序中指令（或语句）的条数 C、算法的有穷性是指算法必须能在执行有限个步骤之后终止 D、以上三种描述都不对

解析:算法的设计可以避开具体的计算机程序设计语言，但算法的实现必须借助程序设计语言中提供的数据类型及其算法。数据结构和算法是计算机科学的两个重要支柱。它们是一个不可分割的整体。算法在运行过程中需辅助存储空间的大小称为算法的空间复杂度。算法的有穷性是指一个算法必须在执行有限的步骤以后结束。 本题答案为C。

2. 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。 A、349 B、350 C、255 D、351

解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

25 / 91

具有n个结点的完全二叉树，其父结点数为int(n/2)，而叶子结点数等于总结点数减去父结点数。本题n=699，故父结点数等于int(699/2)=349，叶子结点数等于699-349=350。 本题答案是B。

9. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是______。 A、堆排序 B、直接插入排序 C、快速排序 D、直接选择排序

解析:当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少。 本题答案为B。

二、填空题

（1）问题处理方案的正确而完整的描述称为 _____ 。 【答案】算法或程序或流程图

【解析】算法是问题处理方案正确而完整的描述

(2)对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 ____ 。 【答案】45

【解析】在冒泡排序中，最坏情况下，需要比较的次数为n(n-1／2)，也就是：10*（lO-1)／2=45

（3）算法复杂度主要包括时间复杂度和 ____ 【答案】空间

【解析】算法的复杂度主要包括时间复杂度和空间复杂度。所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

（4）一棵二叉树第六层（根结点为第一层）的结点数最多为 _______【答案】32

【解析】二叉树的一个性质是，在二叉树的第k层上，最多有2(k≥1)个结点。此，2等于32。所以答案为32。

（5）数据结构分为逻辑结构和存储结构，循环队列属于______ 结构。 【答案】存储或物理或存储结构或物理结构

【解析】数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。可知，循环队列应当是物理结构。

(6)下列软件系统结构图的宽度为 ____ 。

26 / 91

k-1

6-1

A

【答案】 3

【解析】题目中的图形是倒置的树状结构，这是用层次图表示的软件结构。结构图中同一层模块的最大模块个数称为结构的宽度，它表示控制的总分布。根据上述结构图宽度的定义，从图中可以看出，第二层的模块个数最多，即为3。因此，这个系统结构图的宽度就为3。

(7)按“先进后出”原则组织数据的数据结构是 ____ 。 【答案】栈或 Stack

【解析】栈和队列是两种特殊的线性表，其特殊性在于对它们的操作只能在表的端点进行。栈中的数据按照后进先出的原则进行组织，而队列中的数据是按照先进先出的原则进行组织。因此，本题的正确答案是栈(Stack)。

(8)数据结构分为线性结构和非线性结构，带链的队列属于 ___ 。 【答案】 线性结构

【解析】数据结构分为线性结构和非线性结构，其中队列是属于线性结构。队列有两种存储结构，一种是顺序存储结构，称为顺序队列；另一种是链式存储结构，称为链队列。题目中所说的带链的队列就是指链队列。无论队列采取哪种存储结构，其本质还是队列，还属于一种线性结构。因此，本题的正确答案是线性结构。

(9) 在深度为7的满二叉树中，度为2的结点个数为_______。 【答案】63或2-1

【解析】本题考查数据结构中满二叉树的性质。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。深度为k的满二叉树，一共有2-1个结点，其中包括度为2的结点。因此，深度为7的满二叉树，一共有2-1个结点，即127个结点。

根据二叉树的另一条性质，对任意一棵二叉树，若终端结点（即叶子结点）数为n0,而其度数为2的结点数为n2则n0= n2+1。设尝试为7的满二叉树中，度为2的结点个数为x,则改树中中子结点的个数为x+1。则应满足x+(x+1)=127,解该方程得到，x的值为63。

结果上述分析可知，在深度为7的满二叉树中，度为2的结点个数为63。

(10) 线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_____存储结构。 【答案】顺序

【解析】本题考查数据结构的队列。队列是一种特殊的线性表，即限定在表的一端进行删除，在表的另一端进行插入操作的线性表。允许删除的一端叫做队头，允许插入的一端叫做队尾。线性表的存储结构主要

27 / 91

7

k

6

B E C D F 分为顺序存储结构和链式存储结构。当队列用链式存储结构实现时，就称为链队列；当队列用顺序存储结构实现时，就称为循环表。因此，本题划线处应填入“顺序”。

(11) 对下列二叉树进行中序遍历的结果为 ____ 。

【答案】ACBDFEHGP

【解析】本题考查数据结构中二叉树的遍历。根据对二叉树根的访问先后顺序不同，分别称为前序遍历、中序遍历和后序遍历。这三种遍历都是递归定义的，即在其子树中也按照同样的规律进行遍历。下面就是中序遍历方法的递归定义。

当二叉树的根不为空时，依次执行如下3个操作： (1)按中序遍历左子树。 (2)访问根结点。 (3)按中序遍历右子树。

根据如上前序遍历规则，来遍历本题中的二叉树。首先遍历F的左子树，同样按中序遍历。先遍历C的左子树，即结点A，然后访问c，接着访问c的右子树，同样按中序遍历c的右子树，先访问结点B，然后访问结点D，因为结点D没有右子树，因此遍历完C的右子树，以上就遍历完根结点F的左子树。然后访问根结点F，接下来遍历F的右子树．同样按中序遍历。首先访问E的左子树，E的左子树为空，则访问结点E，然后访问结点E的右子树，同样按中序遍历。首先访问G的左子树，即H，然后访问结点G，最后访问G的右子树P。以上就把整个二叉树遍历一遍，中序遍历的结果为ACBDFEHGP。因此．划线处应填入“ACBDFEHGP”。

（11）用链表表示线性表的突出优点是 。 答案：插入和删除操作方便，不必移动数据元素，执行效率高

解析： 为了克服顺序表中插入和删除时需要移动大量数据元素的缺点，引入了链式存储结构。链表表示线性表的突出优点是插入和删除操作方便，不必移动数据元素，执行效率高。

（12）在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 。 答案：log2

解析： 对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2次，而顺序查找需要比较n次。

（11）数据结构分为逻辑结构与存储结构，线性链表属于 。 答案：存储结构

解析： 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结

28 / 91

n

n

构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

（11）冒泡排序算法在最好的情况下的元素交换次数为 。 答案：0

解析： 根据冒泡排序算法思想可知，若待排序的初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动和交换记录，这种情况是冒泡排序的最好情况，故冒泡排序算法在最好的情况下的元素交换次数为0。

（13）若串s=\，则其子串的数目是 。 答案：46

解析： 串s中共有9个字符，由于串中字符各不相同，则其子串中有0个字符的1个（空串），1个字符的9个，2个字符的8个，3个字符的7个，4个字符的6个，5个字符的5个，6个字符的4个，7个字符的3个，8个字符的2个，9个字符的1个，共有1+2+3+4+5+6+7+8+9+1=46。

（11）在算法正确的前提下，评价一个算法的两个标准是 。 答案：时间复杂度和空间复杂度

（12）将代数式答案：(x+y*y)/(a+b)

转换成程序设计中的表达式为 。

（11）数据的逻辑结构有线性结构和 两大类。 答案：非线性结构

解析： 数据的逻辑结构有线性结构和非线性结构两大类。

（12）顺序存储方法是把逻辑上相邻的结点存储在物理位置 的存储单元中。 答案：也相邻

解析： 常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。

（11）当线性表采用顺序存储结构实现存储时，其主要特点是 。 答案：逻辑结构中相邻的结点在存储结构中仍相邻

解析： 顺序存储结构的主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元中。在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的。

52. 设一棵完全二叉树共有500个结点，则在该二叉树中有______个叶子结点。

解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

29 / 91

具有n个结点的完全二叉树，其父结点数为int(n/2)，而叶子结点数等于总结点数减去父结点数。本题n=500，故父结点数等于int(500/2)=250，叶子结点数等于500-250=250。 标准答案为：250

51. 算法的基本特征是可行性、确定性、______和拥有足够的情报。

解析:算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。 标准答案为：有穷性

52. 顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。

解析:常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。 标准答案为：相邻

（1）算法的复杂度主要包括空间复杂度和【1】复杂度。 【答案】空间

【解析】算法的复杂度主要指时间复杂度和空间复杂度。

（2）在线性结构中，队列的操作顺序是先进先出，而栈的操作顺序是【2】 。 【答案】先进后出

【解析】队列和栈都是线性结构，但是不同之处在于队列的操作顺序是先进先出，而栈的操作顺序是先进后出。

（2）在最坏情况下，堆排序需要比较的次数为 【2】 。 答案：O(nlog2)

评析：在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2；简单插入排序所需要的比较次数为n(n-1)/2；希尔排序所需要的比较次数为O（n）；堆排序所需要的比较次数为O(nlog2)。

（3）若串s=\，则其子串的数目是 【3】 。 答案：29

评析：串s中共有7个字符，由于串中字符各不相同，则其子串中有0个字符的1个（空串），1个字符的7个，2个字符的6个，3个字符的5个，4个字符的4个，5个字符的3个，6个字符的2个，7个字符的1个，共有1+2+3+4+5+6+7+1=29。

51. 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的 ______。

解析:算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。算法所需存储空间大小是算法的空间复杂性，算法的计算量是算法的时间复杂性。 标准答案为：空间复杂度和时间复杂度

30 / 91

1.5

n

n

52. 数据结构包括数据的逻辑结构、数据的 ______以及对数据的操作运算。

解析:数据结构包括3个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。 标准答案为：存储结构

53在最坏情况下，冒泡排序的时间复杂度为______。

解析:冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。 假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。

标准答案为：n(n-1)/2 或 n*(n-1)/2 或 O(n(n-1)/2) 或 O(n*(n-1)/2)

54. 顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。

解析:常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。 标准答案为：相邻

52. 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、______遍历和后序遍历。 标准答案为：中序

解析: 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。

前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历右子树，然后访问根结点，最后遍历左子树；并且遍历左、右子树时，仍然先遍历右子树，然后访问根结点，最后遍历左子树。

55. 数据结构包括数据的逻辑结构、数据的 ______以及对数据的操作运算。 标准答案为：存储结构

解析: 数据结构包括3个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。

50. 算法具有五个特性，以下选项中不属于算法特性的是______。 A、有穷性 B、简洁性 C、可行性 D、确定性

解析:本题考查的是算法的特性。

有穷性、确定性、有零个或多个输入、有一个或多个输出、有效性是算法的五大特性。 故本题答案为B。

31 / 91

51. 某二叉树中度为2的结点有18个，则该二叉树中有 个叶子结点。 标准答案为：19

解析:本题考查的是二叉树的定义及其存储结构。

二叉树的性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。本题中度为2的结点数为18，故叶子结点数为18+1=19个。

55. 问题处理方案的正确而完整的描述称为 。 标准答案为：算法 本题考查的是算法的基本概念。 解析:所谓算法是指解题方案的准确而完整的描述。

51. 设一棵完全二叉树共有500个结点，则在该二叉树中有______个叶子结点。 标准答案为：250

解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

具有n个结点的完全二叉树，其父结点数为int(n/2)，而叶子结点数等于总结点数减去父结点数。本题n=500，故父结点数等于int(500/2)=250，叶子结点数等于500-250=250。

52. 在最坏情况下，冒泡排序的时间复杂度为______。

标准答案为：n(n-1)/2 或 n*(n-1)/2 或 O(n(n-1)/2) 或 O(n*(n-1)/2)

解析:冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。 假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。

51. 数据结构包括数据的______结构和数据的存储结构。 标准答案为：逻辑

解析:数据结构是指带有结构的数据元素的集合。它包括数据的逻辑结构和数据的存储结构。 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 数据的存储结构是指在计算机存储空间中的存放形式。

第二章 程序设计基础

一、选择题

（1）下列叙述中正确的是

A）程序设计就是编制程序 B）程序的测试必须由程序员自己去完成 C）程序经调试改错后还应进行再测试 D）程序经调试改错后不必进行再测试 【答案】C

【解析】软件测试仍然是保证软件可靠性的主要手段，测试的目的是要尽量发现程序中的错误，调试主要是推断错误的原因，从而进一步改正错误。测试和调试是软件测试阶段的两个密切相关的过程，通常是交替进行的。选项C正确。

32 / 91

(2)下面描述中，不符合结构化程序设计风格的是

A）使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑 B）注重提高程序的可读性 D）使用goto语句 【答案】 D

【解析】在结构化程序设计中，应严格控制使用GOTO语句，必要时才可以使用，故答案为D。

(3)在面向对象设计中，对象有很多基本特点，其中“从外面看只能看到对象的外部特性，而对象的内部对外是不可见的”这一性质指的是对象的 A）分类性B）标识惟一性C）多态性D）封装性 【答案】D

【解析】从外面看只能看到对象的外部特性，而对象的内部，即处理能力的实行和内部状态，指的是对象的封装性。

(4)结构化程序设计的一种基本方法是

A）筛选法B）递归法C）归纳法D）逐步求精法 【答案】D

【解析】在结构化程序设计中通常采取自上而下、逐步求精的方法，其总的思想是先全局后局部、先整体后细节、先抽象后具体。而筛选法、递归法和归纳法指的都是程序的某种具体算法。

(5)函数重载是指

A）两个或两个以上的函数取相同的函数名，但形参的个数或类型不同

B）两个以上的函数取相同的名字和具有相同的参数个数，但形参的类型可以不同 C）两个以上的函数名字不同，但形参的个数或类型相同 D）两个以上的函数取相同的函数名，并且函数的返回类型相同 【答案】A

【解析】函数重载指的是两个或两个以上的函数具有相同的函数名，但形参的个数或类型不同。程序中通过判断主调函数传过来的参数的个数和类型，来决定选择调用哪个具体的函数。

(6)下列选项中不符合良好程序设计风格的是 A）源程序要文档化 B）数据说明的次序要规范化 C）避免滥用goto 语

D）模块设计要保证高耦合、高内聚 【答案】D

【解析】编程风格是在不影响性能的前提下，有效地编排和组织程序，以提高可读性和可维护性。更直接的说，风格就是意味着要按照规则进行编程。这些规则包括：程序文档化。就是程序文档包含恰当的标识

33 / 91

符．适当的注解和程序的视觉组织等。（2）数据说明。出于阅读理解和维护的需要，最好使模块前的说明语句次序规范化。此外，为方便查找，在每个说明语句的说明符后，数据名应按照字典顺序排列。(3)功能模块化。即把源程序代码按照功能划分为低耦合、高内聚的模块。(4)注意goto语句的使用。合理使用goto语句可以提高代码的运行效率．但goto语句的使用会破坏程序的结构特性。因此，除非确实需要，否则最好不使用goto语，因此，本题的正确答案是D。

(7) 在结构化程序设计中，模块划分的原则是( ) A)各模块应包括尽量多的功能 B)各模块的规模应尽量大 C)各模块之间的联系应尽量紧密

D)模块内具有高内聚度、模块间具有低耦合度 【答案】D

【解析】本题考查软件工程中软件设计的概念和原理。人们在开发计算机软件的长期实践中积累了丰富的经验，总结这些经验得到如下的启发式规则：

1.改进软件结构，提高模块独立性。通过模块的分解或合并，力求降低耦合提高内聚。低耦合也就是降低不同模块间相互依赖的紧密程度，高内聚是提高一个模块内各元素彼此结合的紧密程度。

2.模块的规模应适中。一个模块的规模不应过大，过大的模块往往是由于分解不够充分；过小的模块开销大于有益操作，而且模块过多将使系统接口复杂。因此过小的模块有时不值得单独存在。

3.模块的功能应该可以预测，但也要防止模块功能过分局限。如果模块包含的功能太多，则不能体现模块化设计的特点；如果模块的功能过分的局限，使用范围就过分狭窄。 经过上述分析，本题的正确答案是选项D。

(8) 下面选项中不属于面向对象程序设计特征的是( )

A)继承性 B)多态性 C)类比性 D)封装性 【答案】C

【解析】通常认为，面向对象方法具有封装性、继承性、多态性几大特点。就是这几大特点，为软件开发提供了一种新的方法学。

封装性：所谓封装就是将相关的信息、操作与处理融合在一个内含的部件中(对象中)。简单地说，封装就是隐藏信息。这是面向对象方法的中心，是面向对象程序设计的基础。

继承性：子类具有派生它的类的全部属性(数据)和方法，而根据某一类建立的对象也都具有该类的全部，这就是继承性。继承件自动在类与子类间共享功能与数据，当某个类作了某项修改，其子类会自动改变，子类会继承其父类所有特性与行为模式，继承有利于提高软件开发效率，容易达到一致性。

多态性：多态性就是多种形式。不同的对象在接收到相同的消息时，采用不同的动作。例如，一个应用程序包括许多对象，这些对象也许具有同一类型的工作，但是却以不同的做法来实现。不必为每个对象的过程取一过程名，造成复杂化，可以使过程名复用。同一类型的工作有相同的过程名，这种技术称为多态性。 经过上述分析可知，选项C的说法是错误的。

(9) 在面向对象方法中，实现信息隐蔽是依靠( )

34 / 91

A)对象的继承 B)对象的多态 C)对象的封装 D)对象的分类 【答案】c

【解析】通常认为，面向对象方法具有封装性、继承性、多态性几大特点。就是这几大特点，为软件开发提供了一种新的方法学。

封装性：所谓封装就是将相关的信息、操作与处理融合在一个内含的部件中（对象中)。简单地说，封装就是隐藏信息。这是面向对象方法的中心，也是面向对象程序设计的基础。

继承性：子类具有派生它的类的全部属性(数据)和方法，而根据某一类建立的对象也都具有该类的全部，这就是继承性。继承性自动在类与子类间共享功能与数据，当某个类作了某项修改，其子类会自动改变，子类会继承其父类所有特性与行为模式。继承有利于提高软件开发效率，容易达到一致性。

多态性；多态性就是多种形式。不同的对象在接收到相同的消息时，采用不同的动作。例如，一个应用程序包括许多对象，这些对象也许具有同一类型的工作．但是却以不同的做法来实现。不必为每个对象的过程取一过程名，造成复杂化，可以使过程名复用。同一类型的工作有相同的过程名，这种技术称为多态性。 经过上述分析可知，在面向对象方法中，实现信息隐蔽是依靠对象的封装。正确答案是选项c。

(10) 下列叙述中，不符合良好程序设计风格的是( ) A)程序的效率第一，清晰第二 B)程序的可读性好 C)程序中有必要的注释 D)输入数据前要有提示信息 【答案】A

【解析】本题考查软件工程的程序设计风格。软件在编码阶段，力求程序语句简单、直接，不能只为了追求效率而使语句复杂化。除非对效率有特殊的要求，程序编写要做到清晰第一、效率第二。

人们在软件生存期要经常阅读程序，特别是在软件测试和维护阶段，编写程序的人和参与测试、维护的人都要阅读程序，因此要求程序的可读性要好。

正确的注释能够帮助读者理解程序，可为后续阶段进行测试和维护提供明确的指导。所以注释不是可有可无的，而是必须的，它对于理解程序具有重要的作用。

I/O信息是与用户的使用直接相关的，因此它的格式应当尽可能方便用户的使用。在以交互式进行输入／输出时，要在屏幕上使用提示符明确提示输入的请求，指明可使用选项的种类和取值范围。 经过上述分析可知，选项A是不符合良好程序设计风格要求的。

（11）结构化程序设计的3种结构是 A）顺序结构、选择结构、转移结构 B）分支结构、等价结构、循环结构 C）多分支结构、赋值结构、等价结构 D）顺序结构、选择结构、循环结构

解析： 顺序结构、选择结构和循环结构（或重复结构）是结构化程序设计的3种基本结构。故本题答案应该为选项D）。

（12）在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人

35 / 91

们更重视程序的 A）安全性 B）一致性 C）可理解性 D）合理性 答案：C

（13）对建立良好的程序设计风格，下面描述正确的是 A）程序应简单、清晰、可读性好 B）符号名的命名只要符合语法 C）充分考虑程序的执行效率 D）程序的注释可有可无

解析： 程序设计应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。故本题答案应该为选项A）。

（14）结构化程序设计主要强调的是 A）程序的规模 B）程序的效率

C）程序设计语言的先进性 D）程序易读性

解析： 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用goto语句，总的来说可使程序结构良好、易读、易理解、易维护。故本题答案应该为选项D）。

（15）对象实现了数据和操作的结合，是指对数据和数据的操作进行 A）结合 B）隐藏 C）封装 D）抽象

解析： 对象是由数据及可以对这些数据施加的操作组成的统一体。对象的内部，即处理能力的实行和内部状态，对外是看不见的，这一特性称做对象的封装。故本题答案应该为选项C）。

（4）编制一个好的程序，首先要保证它的正确性和可靠性，还应强调良好的编程风格，在书写功能性注释时应考虑

A)仅为整个程序作注释 B)仅为每个模块作注释 C)为程序段作注释 D)为每个语句作注释 【答案】C

36 / 91

【解析】功能性注释是嵌在源程序体中的，用以描述其后的语句或程序段是在做什么工作，或者执行了下面的语句会怎么样。所以它描述的是一段程序，是为程序段做注释，而不是每条语句。

（5）下列哪个是面向对象程序设计不同于其他语言的主要特点？ A)继承性 B)消息传递 C)多态性 D)静态联编 【答案】A

【解析】继承是一个子类直接使用父类的所有属性和方法。它可以减少相似的类的重复说明，从而体现出一般性与特殊性的原则，这使得面向对象程序设计语言有了良好的重用性，也是其不同于其他语言的主要特点。

3. 结构化程序设计主要强调的是______。

A、程序的规模 B、程序的易读性 C、程序的执行效率 D、程序的可移植性

解析:结构化程序设计主要强调的是结构化程序清晰易读，可理解性好，程序员能够进行逐步求精、程序证明和测试，以保证程序的正确性。 本题答案为B。

2. 下面概念中，不属于面向对象方法的是______。 A、对象 B、继承 C、类 D、过程调用

解析:面向对象方法是一种运用对象、类、封装、继承、多态和消息等概念来构造、测试、重构软件的方法。面向对象方法从对象出发，发展出对象，类，消息，继承等概念。 本题答案为D。

3. 面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是______。 A、模拟现实世界中不同事物之间的联系 B、强调模拟现实世界中的算法而不强调概念

C、使用现实世界的概念抽象地思考问题从而自然地解决问题 D、鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考

解析:面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是，使用现实世界的概念抽象地思考问题从而自然地解决问题。它强调模拟现实世界中的概念而不强调算法，它鼓励开发者在软件开发的绝大部分中都用应用领域的概念去思考。 本题答案为C。

37 / 91

4. 对建立良好的程序设计风格，下面描述正确的是______。 A、程序应简单、清晰、可读性好 B、符号名的命名要符合语法 C、充分考虑程序的执行效率 D、程序的注释可有可无

解析:要形成良好的程序设计风格，主要应注重和考虑下述一些因素：符号名的命名应具有一定的实际含义，以便于对程序功能的理解；正确的注释能够帮助读者理解程序；程序编写应优先考虑清晰性，除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。 本题答案为A。

5. 下面对对象概念描述错误的是______。 A、任何对象都必须有继承性 B、对象是属性和方法的封装体 C、对象间的通讯靠消息传递 D、操作是对象的动态性属性

解析:对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。 本题答案为A。

4. 在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送______。 A、调用语句 B、命令 C、口令 D、消息

解析:面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为消息。消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。 本题答案为D。

5. 在设计程序时，应采纳的原则之一是______。 A、程序结构应有助于读者理解 B、不限制goto语句的使用 C、减少或取消注解行 D、程序越短越好

解析:滥用goto语句将使程序流程无规律，可读性差；添加的注解行有利于对程序的理解，不应减少或取消；程序的长短要依照实际需要而定，并不是越短越好。 本题答案为A。

3. 对建立良好的程序设计风格，下面描述正确的是______。 A、程序应简单、清晰、可读性好

38 / 91

B、符号名的命名要符合语法 C、充分考虑程序的执行效率 D、程序的注释可有可无

解析:要形成良好的程序设计风格，主要应注重和考虑下述一些因素：符号名的命名应具有一定的实际含义，以便于对程序功能的理解；正确的注释能够帮助读者理解程序；程序编写应优先考虑清晰性，除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。 本题答案为A。

二、填空题

(1)在面向对象方法中， ______描述的是具有相似属性与操作的一组对象。 【答案】类

【解析】在面向对象方法中，类描述的是具有相似属性与操作的一组对象。

（2）在面向对象方法中，类的实例称为 ______。 【答案】对象

【解析】类描述的是具有相似性质的一组对象。例如，每本具体的书是一个对象，而这些具体的书都有共同的性质，它们都属于更一般的概念“书”这一类对象。一个具体对象称为类的实例。

（3）子程序通常分为两类： 和函数，前者是命令的抽象，后者是为了求值。 答案：过程

解析： 当程序之间发生调用关系时，调用命令所在的代码段被称为主程序，被调用的代码段被称为子程序。子程序是对功能的抽象，可分为过程和函数两类，两者的区别是函数是通过函数名来返回值的，而过程只能通过形式参数或对全局变量进行修改以返回值。

（4）在面向对象的程序设计中，类描述的是具有相似性质的一组 。 答案：对象

解析： 将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。

（5）在面向对象方法中，类之间共享属性和操作的机制称为 。 答案：继承

解析： 类是面向对象语言中必备的程序语言结构，用来实现抽象数据类型。类与类之间的继承关系实现了类之间的共享属性和操作，一个类可以在另一个已定义的类的基础上定义，这样使该类型继承了其超类的属性和方法，当然，也可以定义自己的属性和方法。

（6）在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为 。 答案：消息

解析： 在面向对象技术中，主要用到对象（object）、类（class）、方法（method）、消息（message）、继承（inheritance）、封装（encapsulation）等基本概念。其中消息是用来请求对象执行某一处理或回

39 / 91

答某些信息的要求。

（7）一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的 。 答案：可重用性

解析：本题考查了继承的优点：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余，提高软件的可重用性。

53. 一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的______。 解析:继承的优点：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余，提高软件的可重用性。

标准答案为：可重用性 或 重用性 或 复用性 或 可复用性

54. 面向对象的模型中，最基本的概念是对象和 ______。

解析:面向对象模型中，最基本的概念是对象和类。对象是现实世界中实体的模型化；将属性集和方法集相同的所有对象组合在一起，可以构成一个类。 标准答案为：类

54. 在面向对象方法中，信息隐蔽是通过对象的______性来实现的。

解析:软件工程的基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。 信息隐蔽是指采用封装技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单。 标准答案为：封装

51. 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个______。

解析:面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。 标准答案为：实体

52. 在面向对象方法中，类的实例称为 。 标准答案为：对象

解析:本题考查的是面向对象方法的基本概念。

将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。所以，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。

52. 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、______和限制使用goto语句。 标准答案为：模块化

解析:结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化和限制使用goto语句。 自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。

40 / 91

逐步求精：对复杂问题，应设计一些子目标作过度，逐步细化。

模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 限制使用goto语句。

53. 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个______。 标准答案为：实体

解析:面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。

第三章 软件工程基础

一、选择题

(1) 下列叙述中正确的是( )

A)软件测试的主要目的是发现程序中的错误 B)软件测试的主要目的是确定程序中错误的位置

C)为了提高软件测试的效率，最好由程序编制者自己来完成软件测试的工作

D)软件测试是证明软件没有错误 【答案】A

【解析】本题考查软件工程中测试的目的和方法。仅就软件测试而言，，它的目的是发现软件中的错误，但是，发现错误并不是最终目的，最终目的是通过测试发现错误之后还必须诊断并改正错误，这就是调试的目的。由于测试的目标是暴露程序中的错误．从心理学角度看，由程序的编写者自己进行测试是不恰当的。因此，在软件测试阶段通常由其他人员组成测试小组来完成测试工作。因此，经过上述分析可知选项A的说法是正确的，而选项B、c、D的说法是错误的。

（2）下列描述中正确的是

A）软件工程只是解决软件项目的管理问题 B）软件工程主要解决软件产品的生产率问题

C）软件工程的主要思想是强调在软件开发过程中需要应用工程化原则 D）软件工程只是解决软件开发中的技术问题【答案】C

【解析】软件工程学是研究软件开发和维护的普遍原理与技术的一门工程学科。所谓软件工程是指，采用工程的概念、原理、技术和方法指导软件的开发与维护。软件工程学的主要研究对象包括软件开发与维护的技术、方法、工具和管理等方面。由此可见，选项A、B和D的说法均不正确．选项C正确。

41 / 91

（3）在软件设计中，不属于过程设计工具的是

A）PDL(过程设计语言) B）PAD图 C）N-S图 D）DFD图 【答案】D

【解析】数据流图DFD，是结构化分析方法最主要的一种图形工具，不属于过程设计具。

（4）下列叙述中正确的是

A）软件交付使用后还需要进行维护 B）软件一旦交付使用就不需要再进行维护 C）软件交付使用后其生命周期就结束 D）软件维护是指修复程序中被破坏的指令 【答案】A

【解析】本题考核软件维护的概念。维护是软件生命周期的最后一个阶段，也是持续时间最长、付出代价最大的阶段，在软件交付使用后，还需要进行维护。软件维护通常有以下四：为纠正使用中出现的错误而进行的改正性维护；为适应环境变化而进行的适应性维护；为改进原有软件而进行的完善性维护；为将来的可维护和可靠而进行的预防性维护。软件维护不仅包括程序代码的维护，还包括文档的维护。综上所述，本题的正确答案是A，其余选项的说法错误。

(5)用黑盒技术测试用例的方法之一为

A）因果图B）逻辑覆盖C）循环覆盖D）基本路径测试 【答案】A

【解析】黑盒测试主要方法有等价值划分法、边界值分析法、错误推测法、因果图法等。白盒测试的主要方法有逻辑覆盖、基本路径测试循环覆盖等。只有A属于黑盒测试。

(6)软件需求分析阶段的工作可以分为4个方面：需求获取、需求分析、编写需求分析说明书和 A）阶段性报告B）需求评审C）总结D）都不正确 【答案】B

【解析】需求分析的四个方面是：需求获取、需求分析、编写需求分析说明书和需求评审。

(7)在数据库的两级映射中，从概念模式到内模式的映射一般由______实现。 A）数据库系统B）数据库管理系统C）数据库管理员D）数据库操作系统 【答案】B

【解析】从概念模式到内模式的映射一般数据库管理系统(DBMS)实现。

(8)下面不属于软件设计原则的是

A）抽象B）模块化C）自底向上D）信息隐藏 【答案】C

【解析】软件设计的原则包括：抽象、模块化、信息隐蔽和模块独立性。所以自底向上不是软件设计原则。答案为C。

42 / 91

(9) 软件是指( )

A)程序 B)程序和文档

C)算法加数据结构 D)程序、数据和相关文档的集合 【答案】D

【解析】本题考查软件的定义。软件是计算机系统中与硬件相互依存得另一部分，它包括程序、相关数据及其说明文档得总和。因此，本题得正确答案是选项D。

(10) 软件调试的目的是( ) A)发现错误 B)改正错误 C)改善软件的性能 D)验证软件的正确性 【答案】 B

【解析】本题考查软件工程调试。调试与测试是两个不同的过程，有着根本的区别：调试是一个随机的、不可重复的过程，它用于隔离和确认问题发生的原因，然后修改软件来纠正问题；测试是一个有计划的，可以重复的过程，它的目的是为了发现软件中的问题。因此．软件调试的目的是为了改正软件中的错误。本题的正确答案是选项B。

(11)下列选项中不属于结构化程序设计方法的是 A）自顶向下

B）逐步求精

D）可复用

C）模块化 【答案】D

【解析】结构化程序设计方法的主要原则有4点：自顶向下(先从最上层总目标开始设计，逐步使问题具体化)、逐步求精(对于复杂问题，设计一些子目标作为过渡，逐步细化)、模块化(将程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，每个小目标作为一个模块)、限制使用GOTO语句。没有可复用原则，所以选项D为答案。

(12)两个或两个以上模块之间关联的紧密程度称为 A）耦合度 C）复杂度 【答案】A

【解析】本题考核模块独立性的评价，评价模块独立性的主要标准有两个：一是模块之间的耦合．它表明两个模块之间互相独立的程度，也可以说是两个或两个以上模块之间关联的紧密程度(所以，本题的正确答案为选项A)：二是模块内部之间的关系是否紧密，称为内聚。一般来说，要求模块之间的耦合尽可能地弱，即模块尽可能独立，而要求模块的内聚程度尽量地高。

(13)下列叙述中正确的是

A）软件测试应该由程序开发者来完成 B）程序经调试后一般不需要再测试

43 / 91

B）内聚度 D）数据传输特性

C）软件维护只包括对程序代码的维护 D）以上三种说法都不对 【答案】D

【解析】本题考核软件测试、软件调试和软件维护的概念。软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定。软件测试具有挑剔性，测试不是为了证明程序是正确的，而是在设想程序有错误的前提下进行的，其目的是设法暴露程序中的错误和缺陷，就是说，测试是程序执行的过程，目的在于发现错误；一个好的测试在于能发现至今未发现的错误；一个成功的测试是发现了至今未发现的错误。由于测试的这一特征，一般应当避免由开发者测试自己的程序。所以，选项A的说法错误。

调试也称排错，目的是发现错误的位置，并改正错误。经测试发现错误后，可以立即进行调试并改正错误；经过调试后的程序还需进行回归测试，以检查调试的效果，同时也可防止在调试过程中引进新的错误。所以，选项B的说法错误。

软件维护通常有4类：为纠正使用中出现的错误而进行的改正性维护；为适应环境变化而进行的适应性维护；为改进原有软件而进行的完善性维护；为将来的可维护和可靠而进行的预防性维护。软件维护不仅包括程序代码的维护．还包括文档的维护。文档可以分为用户文档和系统文档两类。但无论是哪类文档，都必须与程序代码同时维护。只有与程序代码完全一致的文档才有意义和价值。所以，选项c的说法错误。 综上所述，选项A、B、c的说法都错误，所以，选项D为正确答案。

(14)从工程管理解度，软件设计一般分为两步完成，它们是 A）概要设计与详细设计

B）数据设计与接口设计 D）过程设计与数据设计

C）软件结构设计与数据设计 【答案】A

【解析】从工程管理的角度，软件设计可分为概要设计和详细设计两大步骤。概要设计是根据需求确定软件和数据的总体框架；详细设计是将其进一步精化成软件的算法或表示和数据结构。而在技术上，概要设计和详细设计又由若干活动组成．包括总体结构设计、数据设计和过程设计。因此，本题的正确答案是A。

(15)下列选项中不属于软件生命周期开发阶段任务的是 A）软件测试 C）软件维护 【答案】c

【解析】软件生命周期由软件定义、软件开发和软件维护三个时期组成，每个时期又进一步划分为若干个阶段。软件定义时期的基本任务是确定软件系统的工程需求。软件定义可分为软件系统的可行性研究和需求分析两个阶段。软件开发时期是具体设计和实现在前一时期定义的软件，它通常由下面五个阶段组成：概要设计、详细设计、编写代码、组装测试和确认测试。软件维护时期的主要任务是使软件持久的满足用户的需要。即当软件在使用过程中发现错误时应加以改正：当环境改变时应该修改软件，以适应新的环境；当用户有新要求时应该及时改进软件，以满足用户的新要求。根据上述对软件生命周期的介绍，可知选项c中的软件维护不是软件生命周期开发阶段的任务。因此，本题的正确答案是c。

44 / 91

B）概要设计 D）详细设计

（16）下列对于软件测试的描述中正确的是______。

A） 软件测试的目的是证明程序是否正确 B） 软件测试的目的是使程序运行结果正确 C） 软件测试的目的是尽可能多地发现程序中的错误 D） 软件测试的目的是使程序符合结构化原则 【答案】C

【解析】软件测试的目标是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定。测试不是为了证明程序是正确的，而是在设想程序有错误的前提下进行的，其目的是设法暴露程序中的错误和缺陷。可见选项C的说法正确。

（17）为了使模块尽可能独立，要求______。

A） 模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强 B） 模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱 C） 模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱 D） 模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强 【答案】B

【解析】系统设计的质量主要反映在模块的独立性上。评价模块独立性的主要标准有两个：一是模块之间的耦合，它表明两个模块之间互相独立的程度；二是模块内部之间的关系是否紧密，称为内聚。一般来说，要求模块之间的耦合尽可能地弱，即模块尽可能独立，而要求模块的内聚程度尽量地高。综上所述，选项B的答案正确

（18）下列描述中正确的是______。

A）程序就是软件

B）软件开发不受计算机系统的限制 C）软件既是逻辑实体，又是物理实体 D）软件是程序、数据与相关文档的集合 【答案】D

【解析】计算机软件是计算机系统中与硬件相互依存的另一部分，包括程序、数据与相关文档的完整集合。选项D的描述正确。

（19）下列叙述中，不属于结构化分析方法的是 A）面向数据流的结构化分析方法 B）面向数据结构的Jackson方法

C）面向数据结构的结构化数据系统开发方法 D）面向对象的分析方法

解析： 常见的需求分析方法有结构化分析方法和面向对象的分析方法两类。其中结构化分析方法又包括面向数据流的结构化分析方法（SA－Structured analysis），面向数据结构的Jackson方法（JSD－Jackson system development method）和面向数据结构的结构化数据系统开发方法（DSSD－Data structured system

45 / 91

development method）。故本题答案应该为选项D）。

（20）详细设计的结果基本决定了最终程序的 A）代码的规模 B）运行速度 C）质量 D）可维护性

解析： 详细设计阶段的根本目标是确定应该怎样具体的实现所要求的系统，但详细设计阶段的任务还不是具体的编写程序，而是要设计出程序的“蓝图”，以后程序员将根据这个蓝图写出实际的程序代码，因此，详细设计阶段的结果基本上就决定了最终的程序代码的质量。故本题答案应该为选项C）。

（21）下列不属于静态测试方法的是 A）代码检查 B）白盒法 C）静态结构分析 D）代码质量度量

解析： 静态测试包括代码检查、静态结构分析和代码质量度量等。其中白盒测试属于动态测试。故本题答案应该为选项B）。

（22）公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从职员到部门的联系类型是 A）多对多 B）一对一 C）多对一 D）一对多

解析： 现实世界中事物之间的联系在信息世界中反映为实体集之间的联系，实体集间的联系个数不仅可以是单个的也可以是多个的，这种关系可以有下面几种对应：一对一、一对多（多对一）多对多。两个实体集间的联系可以用下图表示：

故本题答案应该为选项C）。

（23）为了提高测试的效率，应该 A）随机选取测试数据

B）取一切可能的输入数据作为测试数据 C）在完成编码以后制定软件的测试计划 D）集中对付那些错误群集的程序

46 / 91

解析： 测试的目的是发现软件中的错误。经验表明，程序中存在错误的概率与该程序中已发现的错误数成正比。这一现象说明，为了提高测试效率，测试人员应该集中对付那些错误群集的程序。故本题答案应该为选项D）。

（24）软件生命周期中所花费用最多的阶段是 A）详细设计 B）软件编码 C）软件测试 D）软件维护

解析： 软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。本题中，详细设计、软件编码和软件测试都属于软件开发阶段；维护是软件生命周期的最后一个阶段，也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。故本题答案应该为选项D）。

（25）下列叙述中，不属于软件需求规格说明书的作用的是 A）便于用户、开发人员进行理解和交流

B）反映出用户问题的结构，可以作为软件开发工作的基础和依据 C）作为确认测试和验收的依据 D）便于开发人员进行需求分析

解析： 软件需求规格说明书（SRS，Software Requirement Specification）是需求分析阶段的最后成果，是软件开发中的重要文档之一。它有以下几个方面的作用：① 便于用户、开发人员进行理解和交流；② 反映出用户问题的结构，可以作为软件开发工作的基础和依据；③ 作为确认测试和验收的依据。

（26）下列不属于软件工程的3个要素的是 A）工具 B）过程 C）方法 D）环境

解析： 软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。故本题答案应该为选项D）。

（27）模块独立性是软件模块化所提出的要求，衡量模块独立性的度量标准则是模块的 A）抽象和信息隐蔽 B）局部化和封装化 C）内聚性和耦合性 D）激活机制和控制方法

解析： 模块的独立程序是评价设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。故本题答案应该为选项C）。

47 / 91

（28）软件开发的结构化生命周期方法将软件生命周期划分成 A）定义、开发、运行维护 B）设计阶段、编程阶段、测试阶段 C）总体设计、详细设计、编程调试 D）需求分析、功能定义、系统设计

解析：A 通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。它可以分为软件定义、软件开发及软件运行维护3个阶段。

（29）在软件工程中，白箱测试法可用于测试程序的内部结构。此方法将程序看做是 A）路径的集合 B）循环的集合 C）目标的集合 D）地址的集合

解析： 软件的白盒测试方法是把测试对象看做一个打开的盒子，它允许测试人员利用程序内部的逻辑结构及有关信息，设计或选择测试用例，对程序所有逻辑路径进行测试。故本题答案应该为选项A）。

（30）下列不属于结构化分析的常用工具的是 A）数据流图 B）数据字典 C）判定树 D）PAD图

解析： 结构化分析的常用工具有数据流图、数据字典、判定树和判定表。而PAD图是常见的过程设计工具中的图形设计。故本题答案应该为选项D）。

（31）在软件生产过程中，需求信息的给出是 A）程序员 B）项目管理者 C）软件分析设计人员 D）软件用户

解析： 软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。故本题答案应该为选项D）。

（32）下列工具中为需求分析常用工具的是 A）PAD B）PFD C）N-S D）DFD

48 / 91

解析： 需求分析中的常用工具有PAD、PFD及N-S等，而DFD（数据流图）为结构化分析工具。故本题答案应该为选项D）。

（33）NULL是指 A）0 B）空格

C）未知的值或无任何值 D）空字符串

解析： 此题属于记忆性的题目，NULL是指未知的值或无任何值。故本题答案应该为选项C）。

（34）软件工程的出现是由于 A）程序设计方法学的影响 B）软件产业化的需要 C）软件危机的出现 D）计算机的发展

解析： 软件工程概念的出现源自于软件危机。为了消除软件危机，通过认真研究解决软件危机的方法，认识到软件工程是使计算机软件走向工程科学的途径，逐步形成了软件工程的概念。故本题答案应该为选项C）。

（35）软件开发离不开系统环境资源的支持，其中必要的测试数据属于 A）硬件资源 B）通信资源 C）支持软件 D）辅助资源 答案：D

（36）在数据流图（DFD）中，带有名字的箭头表示 A）模块之间的调用关系 B）程序的组成成分 C）控制程序的执行顺序 D）数据的流向

解析： 数据流相当于一条管道,并有一级数据（信息）流经它。在数据流图中，用标有名字的箭头表示数据流。数据流可以从加工流向加工，也可以从加工流向文件或从文件流向加工，并且可以从外部实体流向系统或从系统流向外部实体。故本题答案应该为选项D）。

（37）软件设计包括软件的结构、数据接口和过程设计，其中软件的过程设计是指 A）模块间的关系

B）系统结构部件转换成软件的过程描述

49 / 91

C）软件层次结构 D）软件开发过程

解析： 软件设计包括软件结构设计、数据设计、接口设计和过程设计。其中结构设计是定义软件系统各主要部件之间的关系；数据设计是将分析时创建的模型转化为数据结构的定义；接口设计是描述软件内部、软件和操作系统之间及软件与人之间如何通信；过程设计则是把系统结构部件转换成软件的过程性描述。故本题答案应该为选项B）。

（38）检查软件产品是否符合需求定义的过程称为 A）确认测试 B）集成测试 C）验证测试 D）验收测试

解析： 确认测试的任务是验证软件的功能和性能，以及其他特性是否满足需求规格说明定的各种需求；集成测试的主要目的是发现与接口有关的错误。故本题答案应该为选项A）。

（39）数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是 A）控制流 B）加工 C）数据存储 D）源和潭

解析： 数据流图包括4个方面，即加工（转换）（输入数据经加工变换产生输出）、数据流（沿箭头方向传送数据的通道，一般在旁边标注数据流名）、存储文件（数据源）（表示处理过程中存放各种数据的文件）、源和潭（表示系统和环境的接口，属系统之外的实体）。不包括选项中的控制流。故本题答案应该为选项A）。

（40）下列叙述中，正确的是 A）软件就是程序清单

B）软件就是存放在计算机中的文件 C）软件应包括程序清单及运行结果 D）软件包括程序和文档

解析： 软件（software）是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。故本题答案应该为选项D）。

（41）软件设计中，有利于提高模块独立性的一个准则是 A）低内聚低耦合 B）低内聚高耦合 C）高内聚低耦合

50 / 91

本文来源：https://www.bwwdw.com/article/syeo.html