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

一、填空题

1． 在一棵m 阶的个数是_____。

【答案】

【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是最少

2． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

3． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

4． 栈是_____的线性表，其运算遵循_____的原则。

；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）

5． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

6． 实现字符串拷贝的函数strcpy 为：

【答案】

7． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ） { if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

第 2 页，共 74 页

树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的

关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字

next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;

if （node->rflag）（3）; else {do t=*x；;

while （*x==node ）; *x=t; } }

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

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

【答案】

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

9． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

10．—棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

二、选择题

11．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。

I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC A. 仅I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 、III 【答案】B 。

【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC ）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。

第 3 页，共 74 页

12．哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。

A. 哈希函数 B. 除余法中的质数 C. 冲突处理

D. 哈希函数和冲突处理 【答案】D

【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。

13．某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机

A. B. C. D.

收到该帧后，向主机

交换机对这两个帧的转发端口分别是（ ）

向主机

发送一个确认帧，

【答案】B

【解析】

第一次交换机没有录这个数据报源MAC

地址的信息

了所以只用从1端口转发。

14．下面关于串的叙述中，不正确的是（ ）。

A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算

D. 串既可以采用顺序存储，也可以采用链式存储 【答案】B

【解析】

空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字

第 4 页，共 74 页

的信息，只能选择从其他端口全部发送，同时记

确认帧发送时已经有

的信息