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

具有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 / 90

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 / 90

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 / 90

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 / 90

具有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 / 90

1.5

n

n

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库计算机二级公共基础知识题库及答案分析(6)在线全文阅读。