当前位置：问答库＞考研试题

一、判断题

1． 数组不适合作为任何二叉树的存储结构。（ ）

【答案】 ×

【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构是高效率的(存储密度大) 。

2． 深度为k 的二叉树中结点总数小于等于2k ﹣l 。（ ）

【答案】 √

【解析】深度为K 的二叉树，当结点数最多时为满二叉树，此时结点数为2k ﹣l 。

3． 无环有向图才能进行拓扑排序。（ ）

【答案】√

【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。

4． 平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）

【答案】×

【解析】平衡因子定义为该结点的左子树的深度减去右子树的深度，一个平衡二叉树中，某节点的左右孩子的平衡因子为0，说明左孩子的左子树和右子数的深度相同，而且右子树的左子树和右子数的深度相同，但这不能说明该节点的左子树和右子树的深度相同。

5． 在链队列中，即使不设置尾指针也能进行入队操作。（ ）

【答案】 √

【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。

6． 一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（ ）

【答案】 ×

【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。

二、填空题

7． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

8． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】

。当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为

一个元素时，此时堆的元素个数最少，元素个数为。

9． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行

(2)q //将当前结点作为头结点后的第一元素结点插入

10．假定查找有序表

【答案】

表

平均查找次数为。

11．当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

12．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有

检索和_____检索。 【答案】关键字；记录号；记录号；顺序；直接 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【解析】折半查找时每个的次数如表所示:

三、单项选择题

13．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。

A. 直接插入排序

B. 起泡排序

C. 简单选择排序

D. 快速排序

【答案】A

【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n －1趟排序，也即时间复杂度仍为0(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也

2即n －1趟，比较的时间复杂度由O(n) 降至O(n)。

14．FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。

A. 建立在TCP 之上的控制连接

B. 建立在TCP 之上的数据连接

C. 建立在UDP 之上的控制连接

D•建立在UDP 之上的数据连接

【答案】A

【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接:一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。

15．设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S. 若每个元素出

d ，c ，f ，e ，a ，g ，. 栈后立即进入队列Q ，且7个元素出队的顺序是b ，则找S 的容量至少是（ ）

A.1

B.2

C.3

D.4

【答案】C

【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序.. 在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序. 根据出桟顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2；第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3；c 出栈后，剩余元素为a ，c 出栈前的深度为2；f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3；e 出栈后，剩余元素为a ，e 出栈前的深度为2；a 出栈后，无剩余元