2017年中国农业科学院天津环保所808数据结构考研冲刺密押题
● 摘要
一、选择题
1． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4 B.5 C.6 D.7
【答案】C
【解析】设度为0的结点数为x 则度为3的树总结点数n=度为0的结点数+度为1的结点数+度为2的结点数+度为3的结点数
从每个结点所指向的结点数的和的角度来计算度
为3
的树总结点数两种方法所计算出来的n 相等，所以 2． 有个分支结点的满二叉树的深度是（ ）。
A.
B.
C.
D. 【答案】C
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树， 所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
3． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并 【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的
记录存放在数组
中，排序过程的某一中间时刻，R
被划分成两个子区间
和
其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨
称其为无序区。将当前无序区的第1
个记录
4． 算法的计算量的大小称为计算的（ ）。
A. 效率 B. 复杂性 C. 现实性 D. 难度 【答案】B
插入到有序区
中适当的位置上。使
变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
5． 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
I. 简单选择排序II. 希尔排序III. 快速排序IV . 堆排V . 二路归并排序 A. 仅 I 、III 、IV B. 仅 I 、II 、III C. 仅 II 、III 、IV D •仅III 、IV 、V 【答案】A 。
【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
6． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。
A. 仅1 B. 仅2 C. 仅 1，2 D. 仅 2, 3 【答案】C
【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响
7． 某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
交换机对这两个帧的转发端口分别是（ ）
向主机
发送一个确认帧，
【答案】B
【解析】第一次交换机没有录这个数据报源MAC
地址的信息了所以只用从1端口转发。
8． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址 B. 根据MAC 地址查询IP 地址 C. 根据域名查询IP ±也址 D. 根据IP 地址查询域名 【答案】A 。
【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。
9． float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中，且x=-8.25, 则FR1的内容是（ ）。
A.C1040000H B.C2420000H C.C1840000H D.C1C20000H 【答案】A
【解析】首先将十进制数转换为二进制数-1000.01，接着把它写成规格化形式
的信息，只能选择从其他端口全部发送，同时记
确认帧发送时已经有
的信息
（按
相关内容
相关标签