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

一、填空题

1． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。

2． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

3． 外排序的基本操作过程是_____和_____。

【答案】生成有序归并段(顺串) ；归并

4． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。

5． 设有N 个结点的完全二叉树顺序存放在向量

【答案】 中，其下标值最大的分支结点为_____。

【解析】最大的分支结点是最后一个叶子结点的父结点。

二、单项选择题

6． 下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。

【答案】D

【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。

7． 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.

A.. 起泡排序

B. 插入排序

C. 选择排序

D. 二路归并排序

【答案】B

【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序. 显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确.

8． n 个结点的完全有向图含有边的数目（ ）。

A.n*n

B.n(n+1)

C.n/2

D.n*(n－1)

【答案】D

【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则

为n(n－1) 。

9． 下列介质访问控制方法中, 可能发生冲突的是（ ）

A.CDMA

B.CSMA

C.TDMAC

D.FDMA

【答案】B

【解析】介质访向控制协议中能够发生冲突的是CSMA 协议, 答案为B 。

10．若下图为10BaseT 网卡接收到的信号波形, 则该比特串是（ ）

A.00110110

B.10101101

C.01010010

D.11000101

【答案】A

【解析】以太网采用曼彻斯特编码, 其将一个码元分成两个相等的间隔, 前一个间隔为高电平而后一个间隔为低电平表示1, 反之则表示0。故根据波形图, 可得答案为A 。

11．若x=103, y=-25测下列表达式采用8位定点补码运算实现时, 会发生溢出的是（ ）

A.x+y

B.-x+y

C.x-y

D.-x-y

【答案】C

答:8位定点补码能表示的数的范围为:-128~127

A 结果为78, B 结果为-128, D结果为-78都在此范围内, 只有C 结果128超过了8位定点补码能表示的数的范围, 会发生溢出

12．已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆) ，插入关键字3，调整后的小根堆是（ ）.

A.3， 5， 12， 8， 28， 20， 15， 22， 19

B.3， 5， 12， 19， 20， 15， 22， 8， 28

C.3， 8， 12， 5， 20， 15， 22， 28， 19

D.3， 12， 5， 8， 28， 20， 15， 22， 19

【答案】A

【解析】在堆中插入或删除一个元素后，将不再满足堆的性质. 为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素. 具体过程如图(1)〜(5)所示，(1)为原堆，(2)为插入3后，(3)、(4)为