2017年中北大学计算机与控制工程学院820数据结构考研强化模拟题
● 摘要
一、选择题
1． 若下图为lOBaseT 网卡接收到的信号波形，则该比特串是（ ）
A.00110110 B.10101101 C.01010010 D.11000101 【答案】A
【解析】以太网采用曼彻斯特编码，其将一个码元分成两个相等的间隔，前一个间隔为高电平而后一个间隔为低电平表示1，反之则表示0。故根据波形图，可得答案为A 。
2． 下列关于无向连通图特性的叙述中，正确的是（ ）。
I. 所有的顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II C.I 和II D.I 和III 【答案】A
【解析】在图中，顶点的度TD 点数，
e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。
之和与边的数目满足关系式：
（n 为图的总结
图
3． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多 B. 负载因子过大 C. 哈希函数选择不当 D. 解决冲突的算法选择不好 【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
4． 元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3 B.4 C.5 D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作：
（1）e 进找后出栈，出梭序列为decba 。 （2）c 出找，e 进找后出栈，出找序列为dceba 。 （3）cb 出找，e 进找后出栈，出找序列为dcbea 。
（4）cba 出找，e 进找后出找，出找序列为dcbae 。
5． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
6． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258
C.384 D.385 【答案】C 【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
7． 下列关于虚拟存储的叙述中，正确的是（ ）。
A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 【答案】D 。
【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。
8． 在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5 B.7 C.8 D.14
【答案】A
【解析】根据B 树的定义可知，跟结点最少含有
个关键字，高度为2的阶B
树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。
9． 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。
I. 开关中断II. 保存通用寄存器的内容III. 形成中断服务程序入口地址并送PC A. 仅I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 、III 【答案】B 。
【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形