计算机二级公共基础知识题库及答案分析_学霸学习网
计算机二级公共基础知识题库及答案分析
全国计算机等级考试二级公共基础知识考题库第一章 数据结构一、选择题 （1）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 C）二叉链表 【答案】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 【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据 所占的存储空间 B）线性链表 D）有序线性链表以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据 结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。 (5)下列关于队列的叙述中正确的是 A）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是先进后出的线性表 【答案】c【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以 队列是先进先出的线性表。 (6)设有下列二叉树： ABCD 对此二叉树后序遍历的结果为 A）ABCDEF B）BDAECF 【答案】DEFC）ABDCEFD）DBEFCA【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求后序遍历。其遍历顺序应该为： 后序遍历左子树一&后序遍历右子树一&访问根结点。按照定义，后序遍历序列是 DBEFCA，故答案为 D。 (7) 下列叙述中正确的是( ) A)程序执行的效率与数据的存储结构密切相关 B)程序执行的效率只取决于程序的控制结构 C)程序执行的效率只取决于所处理的数据量 D)以上三种说法都不对 【答案】A 【解析】本题考查程序效率。程序效率是指程序运行速度和程序占用的存储空间。影响程序效率的因素是 多方面的，包括程序的设计、使用的算法、数据的存储结构等。在确定数据逻辑结构的基础上，选择一种 合适的存储结构，可以使得数据操作所花费的时间少，占用的存储空间少，即提高程序的效率。因此，本 题选项 A 的说法是正确的。 (8) 下列叙述中正确的是( ) A)数据的逻辑结构与存储结构必定是一一对应的 B)由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C)程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线线结构 D)以上三种说法都不对 【答案】D 【解析】本题考查数据结构的基本知识。 数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状 结构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储 结构在计算机中有两种，即顺序存储结构和链式存储结构。顺序存储结构是把数据元素存储在一块连续 地址空间的内存中；链式存储结构是使用指针把相互直接关联的节点链接起来。因此，这两种存储结构 都是线性的。可见，逻辑结构和存储结构不是一一对应的。因此，选项 A 和选项 B 的说法都是错误的。 无论数据的逻辑结构是线性的还是非线性的，只能选择顺序存储结构或链式存储结构来实现存储。程序设计语言中，数组是内存中一段连续的地址空间，可看作是顺序存储结构。可以用数组来实现树型逻辑结构 的存储，比如二叉树。因此，选项 c 的说法是错误的 (9) 冒泡排序在最坏情况下的比较次数是( A)n(n+1)/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 【答案】A 【解析】本题考查数据结构中二叉树的性质。二叉树满足如下一条性质，即：对任意一棵二叉树，若终端 结点(即叶子结点)数为 n0，而其度数为 2 的结点数为 n2，则 n0= n2+l。 根据这条性质可知，若二叉树中有 70 个叶子结点，则其度为 2 的结点数为 70-1，即 69 个。二叉树的总结 点数是度为 2、度为 1 和叶子结点的总和，因此，题目中的二叉树总结点数为 69+80+70，即 219。因此， 本题的正确答案是选项 A。 (11) 下列叙述中正确的是( ) B)221 C)229 D)231 B)nlog2n C)n(n-1)/2 ) D)n/2A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关 【答案】B 【解析】本题考查数据结构中有关算法的基本知识和概念。数据的结构，直接影响算法的选择和效率。而 数据结构包括两方面，即数据的逻辑结构和数据的存储结构。因此，数据的逻辑结构和存储结构都影响算 法的效率。选项 A 的说法是错误的。算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与时 间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。因此，选项 B 的说法是正确 的。 数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结 构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构 在计算机中有两种，即顺序存储结构和链式存储结构。可见，逻辑结构和存储结构不是一一对应的。因此， 选项 c 的说法是错误的。有时人们为了提高算法的时间复杂度，而以牺牲空间复杂度为代价。但是，这两 者之间没有必然的联系。因此，选项 D 的说法是错误的。 (12)下列关于算法的时间复杂度陈述正确的是 A） 算法的时间复杂度是指执行算法程序所需要的时间 B） 算法的时间复杂度是指算法程序的长度C） 算法的时间复杂度是指算法执行过程中所需要的基本运算次数 D） 算法的时间复杂度是指算法程序中的指令条数 【答案】C 【解析】算法的时间复杂度是指执行算法所需要的计算工作量，也就是算法在执行过程中所执行的基本运 算的次数，而不是指程序运行需要的时间或是程序的长度。 (13)下列关于栈的叙述中正确的是 A）在栈中只能插入数据 C）栈是先进先出的线性表 【答案】D 【解析】对栈可进行插入和删除数据的操作，但必须牢记插入和删除数据都只能是在栈顶，是一种特殊的 线性表。所以栈是先进后出的线性表。 (14)设有下列二叉树： A B D 对此二叉树中序遍历的结果为 A）ABCDEF 【答案】C 【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求中序遍历，其遍历顺序应该为：中 序遍历左子树-&访问根结点-&中序遍历右子树。按照定义，中序遍历序列是 BDAECF，故答案为 B。 (15)按照“后进先出”原则组织数据的数据结构是 A）队列 C）双向链表 【答案】B 【解析】 “后进先出”表示最后被插入的元素最先能被删除。选项 A 中，队列是指允许在一端进行插入、 而在另一端进行删除的线性表，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后 插入的元素将最后才能被删除，队列又称为“先进先出”的线性表，它体现了“先来先服务”的原则：选 项 B 中，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素，栈底元素总是最先被插入的元 素，从而也是最后才能被删除的元素。队列和栈都属于线性表，它们具有顺序存储的特点，所以才有“先 进先出”和“后进先出”的数据组织方式。双向链表使用链式存储方式．二叉树也通常采用链式存储方式， 它们的存储数据的空间可以是不连续的，各个数据结点的存储顺序与数据元素之间的逻辑关系可以不一 致。所以选项 c 和选项 D 错。 (16)下列叙述中正确的是 A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 B）栈 D）二叉树 B）DAECF C）BDAECF D）DBEFCA E C FF F B）在栈中只能删除数据 D）栈是先进后出的线性表C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 【答案】A 【解析】一个非空的数据结构如果满足下列两个条件：(1)有且只有一个根结点;(2)每一个结点最多有一 个前件，也最多有一个后件。则称为线性结构。线性链表是线性表的链式存储结构，选项 A 的说法是正确 的。栈与队列是特殊的线性表，它们也是线性结构，选项 B 的说法是错误的；双向链表是线性表的链式存 储结构，其对应的逻辑结构也是线性结构，而不是非线性结构，选项 c 的说法是错误的；二叉树是非线性 结构，而不是线性结构，选项 D 的说法是错误的。因此，本题的正确答案为 A (17)对如下二叉树ABCDEF进行后序遍历的结果为 A）ABCDEF C）ABDECF 【答案】D 【解析】二叉树后序遍历的简单描述如下：若二叉树为空，则结束返回。否则（1)后序遍历左子树；(2) 后序遍历右子树；(3)访问根结点。也就是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这 三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历 左子树，然后遍历右子树，最后访问根结点。根据后序遍历的算法，后序遍历的结果为 DEBFCA。 (18) 下列对队列的叙述正确的是( A)队列属于非线性表 B)队列按“先进后出”原则组织数据 C)队列在队尾删除数据 D)队列按“先进先出”原则组织数据 【答案】D 【解析】本题考查数据结构中队列的基本知识。队列是一种限定性的线性表，它只允许在表的一端插入 元素，而在另一端删除元素，所以队列具有先进先出的特性。在队列中，允许插入元素的一端叫做队尾， 允许删除的一端则称为队头。这与日常生活中的排队是一致的，最早进入队列的人最早离开，新来的人 总是加入到队尾。因此，本题中只有选项 D 的说法是正确的。 (19) 对下列二叉树进行前序遍历的结果为( ) ) B）DBEAFC D）DEBFCAA) DYBEAFCZX 【答案】CB) YDEBFZXCAC) ABDYECFXZD) ABCDEFXYZ【解析】本题考查数据结构中二叉树的遍历。根据对二叉树根的访问先后顺序不同，分别称为前序遍历、 中序遍历和后序遍历。这三种遍历都是递归定义的，即在其子树中也按照同样的规律进行遍历。下面就是 前序遍历方法的递归定义。当二叉树的根不为空时，依次执行如下 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 的结点，则该二叉树中的叶子结点数为( A) n+1 【答案】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）上述三种说法都不对 【答案】Dk-1 7-1 k-1 k-1)B) n-1C) 2nD) n/2B）31C）64D）63【解析】时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需 存储空间大小的度量。人们都希望选择一个既省存储空间、又省执行时间的算法。然而，有时为了加快算 法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。时间 和空间的效率往往是一对矛盾，很难做到两全。但是，这不适用于所有的情况，也就是说时间复杂度和空 间复杂度之间虽然经常矛盾。但是二者不存在必然的联系。因此，选项 A、B、c 的说法都是错误的。故本 题的正确答案是 D。 (23)在长度为 64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为 A）63 【答案】B 【解析】在长度为 64 的有序线性表中，其中的 64 个数据元素是按照从大到小或从小到大的顺序排列有序 的。 在这样的线性表中进行顺序查找， 最坏的情况就是查找的数据元素不在线性表中或位于线性表的最后。 按照线性表的顺序查找算法，首先用被查找的数据和线性表的第一个数据元素进行比较。若相等，则查找 成功，否则，继续进行比较，即和线性表的第二个数据元素进行比较。同样，若相等，则查找成功，否则， 继续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最后一个元素，算法才结束。 因此，在长度为 64 的有序线性表中进行顺序查找，最坏的情况下需要比较 64 次。因此，本题的正确答案 为 B。 (24)对下列二叉树 进行中序遍历的结果是 A）ACBDFEG C）ABDCGEF B）ACBDFGE D）FCADBEG F C A B 【答案】A 【解析】二叉树的中序遍历递归算法为：如果根不空，则(1)按中序次序访问左子树；(2)访问根结点：(3) 按中序次序访问右子树。否则返回。本题中，根据中序遍历算法．应首先按照中序次序访问以 c 为根结点 的左子树，然后再访问根结点 F，最后才访问以 E 为根结点的右子树。遍历以 c 为根结点的左子树同样要 遵循中序遍历算法，因此中序遍历结果为 ACBD；然后遍历根结点 F；遍历以 E 为根结点的右子树，同样要 遵循中序遍历算法，因此中序遍历结果为 EG。最后把这三部分的遍历结果按顺序连接起来，中序遍历结果 为 ACBDFEG。因此，本题的正确答案是 A。 （25）数据的存储结构是指______。 A）存储在外存中的数据 B）数据所占的存储空间量 D E G B）64 C）6 D）7C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 【答案】D 【解析】数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。所 以选项D正确。（26）下列关于栈的描述中错误的是______。 A） 栈是先进后出的线性表 B） 栈只能顺序存储 C） 栈具有记忆作用 D） 对栈的插入与删除操作中，不需要改变栈底指针 【答案】B 【解析】本题考核栈的基本概念，我们可以通过排除法来确定本题的答案。栈是限定在一端进行插入与删 除的线性表，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入 的元素，从而也是最后才能被删除的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的， 这便是栈的记忆作用，所以选项 A 和选项 C 正确。对栈进行插入和删除操作时，栈顶位置是动态变化的， 栈底指针不变，选项 D 正确。由此可见，选项 B 的描述错误。 （27）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。 A）冒泡排序为n/2 C）快速排序为n 【答案】D 【解析】假设线性表的长度为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 个。nB）冒泡排序为n D）快速排序为n(n-1)/2B）n/2C）nD）n+1（1）线性表若采用链式存储结构时，要求内存中可用存储单元的地址 A）必须是连续的 B）部分地址必须是连续的 C）一定是不连续的D）连续不连续都可以 解析： 在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的 存储顺序与数据元素之间的逻辑关系可以不一致。故本题答案应该为选项 D） （2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A）冒泡排序 B）选择排序 C）快速排序 D）归并排序 解析： 从平均时间性能而言，快速排序最佳，其所需时间最少，但快速排序在最坏情况下的时间性能不 如堆排序和归并排序。当序列中的记录基本有序或元素个数较少时，冒泡排序和简单选择排序为最佳排序 方法，故本题答案应该为选项 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） 。（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 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）循环链表的主要优点是 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 C）p-&next=head D）p=head 解析： 循环链表就是将链表的最后一个结点指向链表头结点（或第一个结点） ，即 p-&next=head。故本题 答案应该为选项 C） 。 （3）已知数据表 A 中每个元素距其最终位置不远，为节省时间，应采用的算法是 A）堆排序 B）直接插入排序nC）快速排序 D）直接选择排序 解析： 当数据表 A 中每个元素距其最终位置不远，说明数据表 A 按关键字值基本有序，在待排序序列基 本有序的情况下，采用插入排序所用时间最少，故答案为选项 B） 。 （1）假设线性表的长度为 n，则在最坏情况下，冒泡排序需要的比较次数为 A）log2 B）n2 nC）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） 。 （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）节省存储空间，降低上溢发生的机率 C）减少存取时间，降低上溢发生的机率 D）节省存储空间，降低下溢发生的机率 解析： 常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空 间。但实际中，很难准确地估计，若每个栈都分配过大的存储空间，势必造成系统空间紧张；若让多个栈 共用一个足够大的连续存储空间，则可利用栈的动态特性使他们的存储空间互补。故本题答案应该为选项 B） 。 （2）设有两个串 p 和 q，求 q 在 p 中首次出现位置的运算称作 A）连接 B）模式匹配 C）求子串 D）求串长 解析： 子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思 想是：从主串的开始字符起和模式的第一个字符比较，若相等则继续比较后续字符，否则从主串的下一个 字符起再重新和模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序 列相等，称匹配成功，否则称匹配不成功。 （3）下列关于队列的叙述中正确的是______。A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 解析：C 队列是先进先出的，栈是先进后出的，2 者的区别一定要搞清楚。 (1)算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数 C)执行算法程序所占的存储空间 D)算法执行过程中所需要的存储空间 【答案】D 【解析】算法的空间复杂度一般是指这个算法执行时所需要的内存空间，其中包括算法程序所占的空间、 输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执 行过程的工作单元以及某种数据结构所需要的附加存储空间。 （2）线性表的链式存储结构是一种 A)随机结构 B)顺序结构 C)索引结构 D)散列结构 【答案】B 【解析】线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指 向一个与本结点有逻辑关系的结点。此类存储方式属于顺序存储。 （3）设有下列二叉树：对此二叉树先序遍历的结果是 A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA 【答案】C 【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求先序遍历；遍历顺序应该为：访问 根结点-＞先序遍历左子树-＞先序遍历右子树。按照定义，先序遍历序列是 ABDECF。 （1）算法分析的目的是______。 A）找出数据结构的合理性 B）找出算法中输入和输出之间的关系 C）分析算法的易懂性和可靠性 D）分析算法的效率以求改进 答案：D 评析：算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时 间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执 行效率。（3）已知数据表 A 中每个元素距其最终位置不远，为节省时间，应采用的算法是______。 A）堆排序 C）快速排序 答案：B 评析：当数据表 A 中每个元素距其最终位置不远，说明数据表 A 按关键字值基本有序，在待排序序列基本 有序的情况下，采用插入排序所用时间最少，故答案为选项 B。 （4）用链表表示线性表的优点是______。 A）便于插入和删除操作 B）数据元素的物理顺序与逻辑顺序相同 D）便于随机存取 B）直接插入排序 D）直接选择排序C）花费的存储空间较顺序存储少 答案：A评析：链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻 辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。 1. 以下数据结构中不属于线性数据结构的是______。 A、队列 B、线性表 C、二叉树 D、栈 解析:线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表， 这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。 一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称后进 先出表（Last In First Out）；队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入 的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素，队列的最后一个元素一定是 最新入队的元素。因此队列又称先进先出表（First In First Out）。 本题答案为 C。 5. 下列关于栈的叙述中正确的是______。 A、在栈中只能插入数据 B、在栈中只能删除数据 C、栈是先进先出的线性表 D、栈是先进后出的线性表 解析:栈是限定在一端进行插入与删除的线性表。 栈是按照&先进后出&的或后进先出的原则组织数据的，因此，栈也被称为&先进后出&表或&后进先出& 表。 本题答案是 D。 7. 对长度为 N 的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。 A、N+1 B、N C、(N+1)/2 D、N/2 解析:在进行顺序查找过程中，如果线性表中被查的元素是线性表中的最后一个，或者被查元素根本不在 线性表中，则为了查找这个元素需要与线性表中所有元素进行比较，这是顺序查找最坏的情况。 本题答案为 B。 1. 在一棵二叉树上第 5 层的结点数最多是______。 A、8 B、16C、32 D、15 解析:根据二叉树的性质：二叉树第 i（i≥1）层上至多有 2 个结点。得到第 5 层的结点数最多是 16。 本题答案为 B。 3. 下列叙述中正确的是______。 A、线性表是线性结构 B、栈与队列是非线性结构 C、线性链表是非线性结构 D、二叉树是线性结构 解析:根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线性结构 与非线性结构。 如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一 个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。 所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。 本题答案是 A。 7. 在下列选项中，哪个不是一个算法一般应该具有的基本特征______。 A、确定性 B、可行性 C、无穷性 D、拥有足够的情报 解析:作为一个算法，一般应具有以下几个基本特征。 1)可行性 2)确定性 3)有穷性 4)拥有足够的情报 本题答案为 C。 5. 在计算机中，算法是指______。 A、查询方法 B、加工方法 C、解题方案的准确而完整的描述 D、排序方法 解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性 和拥有足够的情报。 本题答案为 C。 7. 在单链表中，增加头结点的目的是______。 A、方便运算的实现 B、使单链表至少有一个结点 C、标识表结点中首结点的位置 D、说明单链表是线性表的链式存储实现 解析:头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头， 就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。 本题答案为 A。 1. 数据的存储结构是指______。i-1A、存储在外存中的数据 B、数据所占的存储空间量 C、数据在计算机中的顺序存储方式 D、数据的逻辑结构在计算机中的表示 解析:本题考查的是数据结构的基本概念。 数据的逻辑结构在计算机存储空间中的存放形式形式称为数据的存储结构（也称数据的物理结构）。 故本题答案为 D。 2. 下列关于栈的描述中错误的是______。 A、栈是先进后出的线性表 B、栈只能顺序存储 C、栈具有记忆作用 D、对栈的插入与删除操作中，不需要改变栈底指针 解析:本题考查的是栈和队列。 栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端 称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被 插入的元素。所以栈又称先进后出表（FILO-First In Last Out）。线性表可以顺序存储，也可以链式存 储，而栈是一种线性表，也可以采用链式存储结构。 故本题答案为 B。 3. 对于长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。 A、冒泡排序为 n/2 B、冒泡排序为 n C、快速排序为 n D、快速排序为 n(n-1)/2 解析:本题考查的是基本排序算法。 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n/2 遍的从前往后扫描和 n/2 遍的从后 往前扫描，需要比较次数为 n(n-1)/2。快速排序法的最坏情况比较次数也是 n(n-1)/2。 故本题答案为 D。 4. 对长度为 n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。 A、log2n B、n/2 C、n D、n+1 解析:本题考查的是顺序查找。 在进行顺序查找过程中， 如果线性表中的第一个元素就是被查找元素， 则只需做一次比较就查找成功， 查找效率最高； 但如果被查找的元素是线性表中的最后一个元素， 或者被查找的元素根本就不在线性表中， 则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。所以对长度为 n 的 线性表进行顺序查找，在最坏情况下需要比较 n 次。 故本题答案为 C。 5. 下列对于线性链表的描述中正确的是______。 A、存储空间不一定是连续，且各元素的存储顺序是任意的 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。 本题答案是 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、顺序、选择、循环 解析:算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映 了算法的设计是否符合结构化原则。 一个算法一般都可以用顺序、 选择、 循环三种基本控制结构组合而成。 本题答案为 D。 2. 数据的存储结构是指______。 A、数据所占的存储空间量 B、数据的逻辑结构在计算机中的表示 C、数据在计算机中的顺序存储方式 D、存储在外存中的数据 解析:数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。 本题答案为 B。 3. 设有下列二叉树：5-1 4 m K-1ABCDEF对此二叉树中序遍历的结果为______。 A、ABCDEF B、DBEAFC C、ABDECF D、DEBFCA 解析:所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问 根结点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右 子树。 本题答案为 B。 1. 在计算机中，算法是指______。 A、查询方法 B、加工方法 C、解题方案的准确而完整的描述 D、排序方法 解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性 和拥有足够的情报。 本题答案为 C。 2. 栈和队列的共同点是______。 A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 解析:栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈 只允许在表的一端进行插入或删除操作，是一种&后进先出&的线性表；而队列只允许在表的一端进行插入 操作，在另一端进行删除操作，是一种&先进先出&的线性表。 本题答案为 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 解析: 栈操作原则是&后进先出&，栈底至栈顶依次存放元素 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 解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的 若干结点。 具有 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)下列软件系统结构图的宽度为 ____ 。 A B E 【答案】 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。7 k 6 k-1 6-1CD F则应满足 x+(x+1)=127,解该方程得到，x 的值为 63。 结果上述分析可知，在深度为 7 的满二叉树中，度为 2 的结点个数为 63。 (10) 线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是 队列的_____存储结构。 【答案】顺序 【解析】本题考查数据结构的队列。队列是一种特殊的线性表，即限定在表的一端进行删除，在表的另一 端进行插入操作的线性表。允许删除的一端叫做队头，允许插入的一端叫做队尾。线性表的存储结构主要 分为顺序存储结构和链式存储结构。当队列用链式存储结构实现时，就称为链队列；当队列用顺序存储结 构实现时，就称为循环表。因此，本题划线处应填入“顺序” 。 (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）用链表表示线性表的突出优点是 。答案：插入和删除操作方便，不必移动数据元素，执行效率高 解析： 为了克服顺序表中插入和删除时需要移动大量数据元素的缺点，引入了链式存储结构。链表表示 线性表的突出优点是插入和删除操作方便，不必移动数据元素，执行效率高。 （11）算法的基本特征是可行性、确定性、 答案：有穷性 解析： 算法是指解题方案的准确而完整的描述。它有 4 个基本特征，分别是可行性、确定性、有穷性和 和拥有足够的情报。拥有足够的情报。 （12）在长度为 n 的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为 答案：log2n n。解析： 对于长度为 n 的有序线性表，在最坏情况下，二分查找只需要比较 log2 次，而顺序查找需要比较 n 次。 （11）数据结构分为逻辑结构与存储结构，线性链表属于 答案：存储结构 解析： 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结 构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各 数据元素之间的前后件关系的信息。 （11）冒泡排序算法在最好的情况下的元素交换次数为 答案：0 解析： 根据冒泡排序算法思想可知，若待排序的初始序列为“正序”序列，则只需进行一趟排序，在排 序过程中进行 n-1 次关键字间的比较，且不移动和交换记录，这种情况是冒泡排序的最好情况，故冒泡排 序算法在最好的情况下的元素交换次数为 0。 （12）在最坏情况下，堆排序需要比较的次数为 答案：O（nlog2 ） （13）若串 s=&MathTypes&，则其子串的数目是 答案：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）在算法正确的前提下，评价一个算法的两个标准是 答案：时间复杂度和空间复杂度 。 。n。。。（12）将代数式 答案：(x+y*y)/(a+b)转换成程序设计中的表达式为。（11）数据的逻辑结构有线性结构和 答案：非线性结构两大类。解析： 数据的逻辑结构有线性结构和非线性结构两大类。 （12）顺序存储方法是把逻辑上相邻的结点存储在物理位置 答案：也相邻 解析： 常用的存储表示方法有 4 种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法 是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。 （11）当线性表采用顺序存储结构实现存储时，其主要特点是 答案：逻辑结构中相邻的结点在存储结构中仍相邻 解析： 顺序存储结构的主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元 。 的存储单元中。中。在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的。 52. 设一棵完全二叉树共有 500 个结点，则在该二叉树中有______个叶子结点。 解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的 若干结点。 具有 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=&Program&，则其子串的数目是 【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. 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的 ______。 解析:算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。算法所需存储空间大 小是算法的空间复杂性，算法的计算量是算法的时间复杂性。 标准答案为：空间复杂度和时间复杂度 52. 数据结构包括数据的逻辑结构、数据的 ______以及对数据的操作运算。 解析:数据结构包括 3 个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。 标准答案为：存储结构1.5 n n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。 51. 某二叉树中度为 2 的结点有 18 个，则该二叉树中有 标准答案为：19 解析:本题考查的是二叉树的定义及其存储结构。 二叉树的性质 3：在任意一棵二叉树中，度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个。本题 中度为 2 的结点数为 18，故叶子结点数为 18+1=19 个。 55. 问题处理方案的正确而完整的描述称为 标准答案为：算法 。 个叶子结点。本题考查的是算法的基本概念。解析:所谓算法是指解题方案的准确而完整的描述。 51. 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、______遍历 和后序遍历。标准答案为：中序 解析:在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历 和后序遍历。 前序遍历是指在访问根结点、 遍历左子树与遍历右子树这三者中， 首先访问根结点， 然后遍历左子树， 最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点， 最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历右子树，然后访问根结点， 最后遍历左子树；并且遍历左、右子树时，仍然先遍历右子树，然后访问根结点，最后遍历左子树。 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 正确。 (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 【解析】编程风格是在不影响性能的前提下，有效地编排和组织程序，以提高可读性和可维护性。更直接 的说，风格就是意味着要按照规则进行编程。这些规则包括：程序文档化。就是程序文档包含恰当的标识 符．适当的注解和程序的视觉组织等。 （2）数据说明。出于阅读理解和维护的需要，最好使模块前的说明 语句次序规范化。此外，为方便查找，在每个说明语句的说明符后，数据名应按照字典顺序排列。(3)功 能模块化。即把源程序代码按照功能划分为低耦合、高内聚的模块。(4)注意 goto 语句的使用。合理使用 goto 语句可以提高代码的运行效率．但 goto 语句的使用会破坏程序的结构特性。因此，除非确实需要， 否则最好不使用 goto 语，因此，本题的正确答案是 D。 (7) 在结构化程序设计中，模块划分的原则是( A)各模块应包括尽量多的功能 B)各模块的规模应尽量大 C)各模块之间的联系应尽量紧密 D)模块内具有高内聚度、模块间具有低耦合度 )【答案】D 【解析】本题考查软件工程中软件设计的概念和原理。人们在开发计算机软件的长期实践中积累了丰富的 经验，总结这些经验得到如下的启发式规则： 1.改进软件结构，提高模块独立性。通过模块的分解或合并，力求降低耦合提高内聚。低耦合也就是降 低不同模块间相互依赖的紧密程度，高内聚是提高一个模块内各元素彼此结合的紧密程度。 2.模块的规模应适中。一个模块的规模不应过大，过大的模块往往是由于分解不够充分；过小的模块开 销大于有益操作，而且模块过多将使系统接口复杂。因此过小的模块有时不值得单独存在。 3.模块的功能应该可以预测，但也要防止模块功能过分局限。如果模块包含的功能太多，则不能体现模 块化设计的特点；如果模块的功能过分的局限，使用范围就过分狭窄。 经过上述分析，本题的正确答案是选项 D。 (8) 下面选项中不属于面向对象程序设计特征的是( A)继承性 【答案】C 【解析】通常认为，面向对象方法具有封装性、继承性、多态性几大特点。就是这几大特点，为软件开 发提供了一种新的方法学。 封装性：所谓封装就是将相关的信息、操作与处理融合在一个内含的部件中(对象中)。简单地说，封装 就是隐藏信息。这是面向对象方法的中心，是面向对象程序设计的基础。 继承性：子类具有派生它的类的全部属性(数据)和方法，而根据某一类建立的对象也都具有该类的全部， 这就是继承性。继承件自动在类与子类间共享功能与数据，当某个类作了某项修改，其子类会自动改变， 子类会继承其父类所有特性与行为模式，继承有利于提高软件开发效率，容易达到一致性。 多态性：多态性就是多种形式。不同的对象在接收到相同的消息时，采用不同的动作。例如，一个应用 程序包括许多对象，这些对象也许具有同一类型的工作，但是却以不同的做法来实现。不必为每个对象 的过程取一过程名，造成复杂化，可以使过程名复用。同一类型的工作有相同的过程名，这种技术称为 多态性。 经过上述分析可知，选项 C 的说法是错误的。 (9) 在面向对象方法中，实现信息隐蔽是依靠( ) A)对象的继承 C)对象的封装 【答案】c 【解析】通常认为，面向对象方法具有封装性、继承性、多态性几大特点。就是这几大特点，为软件开发 提供了一种新的方法学。 封装性：所谓封装就是将相关的信息、操作与处理融合在一个内含的部件中（对象中)。简单地说，封装 就是隐藏信息。这是面向对象方法的中心，也是面向对象程序设计的基础。 继承性：子类具有派生它的类的全部属性(数据)和方法，而根据某一类建立的对象也都具有该类的全部， 这就是继承性。继承性自动在类与子类间共享功能与数据，当某个类作了某项修改，其子类会自动改变， 子类会继承其父类所有特性与行为模式。继承有利于提高软件开发效率，容易达到一致性。 多态性；多态性就是多种形式。不同的对象在接收到相同的消息时，采用不同的动作。例如，一个应用 程序包括许多对象，这些对象也许具有同一类型的工作．但是却以不同的做法来实现。不必为每个对象 B)对象的多态 D)对象的分类 B)多态性 C)类比性 )D)封装性的过程取一过程名，造成复杂化，可以使过程名复用。同一类型的工作有相同的过程名，这种技术称为 多态性。 经过上述分析可知，在面向对象方法中，实现信息隐蔽是依靠对象的封装。正确答案是选项 c。 (10) 下列叙述中，不符合良好程序设计风格的是( ) A)程序的效率第一，清晰第二 C)程序中有必要的注释 【答案】A 【解析】本题考查软件工程的程序设计风格。软件在编码阶段，力求程序语句简单、直接，不能只为了追 求效率而使语句复杂化。除非对效率有特殊的要求，程序编写要做到清晰第一、效率第二。 人们在软件生存期要经常阅读程序，特别是在软件测试和维护阶段，编写程序的人和参与测试、维护的 人都要阅读程序，因此要求程序的可读性要好。 正确的注释能够帮助读者理解程序，可为后续阶段进行测试和维护提供明确的指导。所以注释不是可有 可无的，而是必须的，它对于理解程序具有重要的作用。 I/O 信息是与用户的使用直接相关的，因此它的格式应当尽可能方便用户的使用。 在以交互式进行输入／ 输出时，要在屏幕上使用提示符明确提示输入的请求，指明可使用选项的种类和取值范围。 经过上述分析可知，选项 A 是不符合良好程序设计风格要求的。 （11）结构化程序设计的 3 种结构是 A）顺序结构、选择结构、转移结构 B）分支结构、等价结构、循环结构 C）多分支结构、赋值结构、等价结构 D）顺序结构、选择结构、循环结构 解析： 顺序结构、选择结构和循环结构（或重复结构）是结构化程序设计的 3 种基本结构。故本题答案 应该为选项 D） 。 （12）在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人 们更重视程序的 A）安全性 B）一致性 C）可理解性 D）合理性 答案：C （13）对建立良好的程序设计风格，下面描述正确的是 A）程序应简单、清晰、可读性好 B）符号名的命名只要符合语法 C）充分考虑程序的执行效率 D）程序的注释可有可无 解析： 程序设计应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。故本题答 案应该为选项 A） 。 （14）结构化程序设计主要强调的是 B)程序的可读性好 D)输入数据前要有提示信息A）程序的规模 B）程序的效率 C）程序设计语言的先进性 D）程序易读性 解析： 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用 goto 语句， 总的来说可使程序结构良好、易读、易理解、易维护。故本题答案应该为选项 D） 。 （15）对象实现了数据和操作的结合，是指对数据和数据的操作进行 A）结合 B）隐藏 C）封装 D）抽象 解析： 对象是由数据及可以对这些数据施加的操作组成的统一体。对象的内部，即处理能力的实行和内 部状态，对外是看不见的，这一特性称做对象的封装。故本题答案应该为选项 C） 。 （4）编制一个好的程序，首先要保证它的正确性和可靠性，还应强调良好的编程风格，在书写功能性注 释时应考虑 A)仅为整个程序作注释 B)仅为每个模块作注释 C)为程序段作注释 D)为每个语句作注释 【答案】C 【解析】功能性注释是嵌在源程序体中的，用以描述其后的语句或程序段是在做什么工作，或者执行了下 面的语句会怎么样。所以它描述的是一段程序，是为程序段做注释，而不是每条语句。 （5）下列哪个是面向对象程序设计不同于其他语言的主要特点？ A)继承性 B)消息传递 C)多态性 D)静态联编 【答案】A 【解析】继承是一个子类直接使用父类的所有属性和方法。它可以减少相似的类的重复说明，从而体现出 一般性与特殊性的原则，这使得面向对象程序设计语言有了良好的重用性，也是其不同于其他语言的主要 特点。 3. 结构化程序设计主要强调的是______。 A、程序的规模 B、程序的易读性 C、程序的执行效率 D、程序的可移植性 解析:结构化程序设计主要强调的是结构化程序清晰易读，可理解性好，程序员能够进行逐步求精、程序 证明和测试，以保证程序的正确性。 本题答案为 B。2. 下面概念中，不属于面向对象方法的是______。 A、对象 B、继承 C、类 D、过程调用 解析:面向对象方法是一种运用对象、类、封装、继承、多态和消息等概念来构造、测试、重构软件的方 法。面向对象方法从对象出发，发展出对象，类，消息，继承等概念。 本题答案为 D。 3. 面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是______。 A、模拟现实世界中不同事物之间的联系 B、强调模拟现实世界中的算法而不强调概念 C、使用现实世界的概念抽象地思考问题从而自然地解决问题 D、鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考 解析:面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是，使用现实世界的概 念抽象地思考问题从而自然地解决问题。它强调模拟现实世界中的概念而不强调算法，它鼓励开发者在软 件开发的绝大部分中都用应用领域的概念去思考。 本题答案为 C。 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、程序应简单、清晰、可读性好 B、符号名的命名要符合语法 C、充分考虑程序的执行效率 D、程序的注释可有可无 解析:要形成良好的程序设计风格，主要应注重和考虑下述一些因素：符号名的命名应具有一定的实际含 义，以便于对程序功能的理解；正确的注释能够帮助读者理解程序；程序编写应优先考虑清晰性，除非对 效率有特殊要求，程序编写要做到清晰第一，效率第二。 本题答案为 A。二、填空题 (1)在面向对象方法中， ______描述的是具有相似属性与操作的一组对象。 【答案】类 【解析】在面向对象方法中，类描述的是具有相似属性与操作的一组对象。 （2）在面向对象方法中，类的实例称为 ______。 【答案】对象 【解析】类描述的是具有相似性质的一组对象。例如，每本具体的书是一个对象，而这些具体的书都有共 同的性质，它们都属于更一般的概念“书”这一类对象。一个具体对象称为类的实例。 （3）子程序通常分为两类： 答案：过程 解析： 当程序之间发生调用关系时，调用命令所在的代码段被称为主程序，被调用的代码段被称为子程 序。子程序是对功能的抽象，可分为过程和函数两类，两者的区别是函数是通过函数名来返回值的，而过 程只能通过形式参数或对全局变量进行修改以返回值。 （4）在面向对象的程序设计中，类描述的是具有相似性质的一组 答案：对象 解析： 将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。 （5）在面向对象方法中，类之间共享属性和操作的机制称为 答案：继承 解析： 类是面向对象语言中必备的程序语言结构，用来实现抽象数据类型。类与类之间的继承关系实现 了类之间的共享属性和操作，一个类可以在另一个已定义的类的基础上定义，这样使该类型继承了其超类 的属性和方法，当然，也可以定义自己的属性和方法。 。 。 和函数，前者是命令的抽象，后者是为了求值。（6）在面向对象的设计中，用来请求对象执行某一处理或回答某些信息的要求称为 答案：消息。解析： 在面向对象技术中，主要用到对象（object） 、类（class） 、方法（method） 、消息（message） 、 继承（inheritance） 、封装（encapsulation）等基本概念。其中消息是用来请求对象执行某一处理或回 答某些信息的要求。 （7）一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件 的 答案：可重用性 解析： 本题考查了继承的优点： 相似的对象可以共享程序代码和数据结构， 从而大大减少了程序中的冗余， 提高软件的可重用性。 53. 一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的______。 解析:继承的优点：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余，提高软件 的可重用性。 标准答案为：可重用性 或 重用性 或 复用性 或 可复用性 54. 面向对象的模型中，最基本的概念是对象和 ______。 解析:面向对象模型中，最基本的概念是对象和类。对象是现实世界中实体的模型化；将属性集和方法集 相同的所有对象组合在一起，可以构成一个类。 标准答案为：类 54. 在面向对象方法中，信息隐蔽是通过对象的______性来实现的。 解析:软件工程的基本原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。 信息隐蔽是指采用封装技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单。 标准答案为：封装 51. 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个______。 解析:面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个 基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。 标准答案为：实体 52. 在面向对象方法中，类的实例称为 标准答案为：对象 解析:本题考查的是面向对象方法的基本概念。 将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。所以，类 是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。 52. 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、______和限制使用 goto 语句。 标准答案为：模块化 解析:结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化和限制使用 goto 语句。 自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开 始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。 逐步求精：对复杂问题，应设计一些子目标作过度，逐步细化。 模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分 目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 限制使用 goto 语句。 。 。53. 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个______。 标准答案为：实体 解析:面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个 基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。第三章软件工程基础一、选择题 (1) 下列叙述中正确的是( )A)软件测试的主要目的是发现程序中的错误 B)软件测试的主要目的是确定程序中错误的位置 C)为了提高软件测试的效率，最好由程序编制者自己来完成软件测试的工作 D)软件测试是证明软件没有错误 【答案】A 【解析】本题考查软件工程中测试的目的和方法。仅就软件测试而言， ，它的目的是发现软件中的错}