2018年江西理工大学信息工程学院873数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 对进行基数排序，一趟排序的结果是:（ ）
A. 05， 46， 13， 55， 94， 17， 42 B.
C. 42，13， 94，05， 55， 46，17
D. 05，13， 46，55，17，42，94
【答案】C
【解析】基数排序有两种:最低位优先和最高位优先。
①最低位优先的过程
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是 根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。
②以r 为基数的最低位优先排序的过程 假设线性表由结点序列
成，
其中
分配:开始时，把
收集:把构成，每个结点的关键字由d 元组。在排序过程中，使用r 个队列组。排序过程就是对i=0， 1，... ，d －1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性:
表中的每一个结点各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的。如果的关键字k=k，就把放进Q k 队列中。
线性表。
2． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）
A.007.110.119.114.911.120.122
B.007, 110, 119, 114, 911, 122, 120
C.007, 110, 911, 114, 119, 120, 122
D.110, 120, 911, 122, 114, 007, 119
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。
3． 下列介质访问控制方法中, 可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDMAC
D.FDMA
【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议, 答案为B 。
4． 计算机开后, 操作系统最终被加载到（ ）
A.BIOS
B.ROM
C.EPROM
D.RAM
【答案】D
【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区, 这段区城是RAM , 故答案选D 。
5． 在缺页处理过程中, 操作系统执行的操作可能是（ ）。
Ⅰ. 修改页表
Ⅱ. 磁盘
Ⅲ. 分配页框
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ
C. 仅Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】D
【解析】首先我们要考虑的是, 为什么会发生缺页中断? 当然, 在一个采用虚拟存储管理技术的系统中, 程序是部分装入的, 还有部分是处于外存上的, 因此, 当需要访问那部分位于外存上的代码或数据时, 系统会产生缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存, 据此, 缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页(若没有空闲的页面则要调用页面置换程序找到一处页面, 将该页面的内容处理掉, 或回写磁盘, 或覆盖掉, 然后将此页分配给需要访问的页) , 分配妥当以后,
缺页中断处理程序调用设备驱动程序做磁盘
, 将位于外存(一般是磁盘) 上的页面调入内存, 调入后转身去修改页表, 将页表中代表该页是否在内存的标志位(一般称为存在位或有效位、在位位) 修改为“真”, 将物理页框号填入相应位置, 若必要还需修改其它相关表项等。完成上述任务后, 缺页中断处理程序返回, 继续程序的执行。从上述过程可以看出, 涉及的相关处理非常多, 因此, 答案就显而易见了。
6． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节
B.216字节
C.224字节
D.232字节
【答案】C
【解析】段内位移的最大值就是最大段长. 段号长度占了8位，剩下32﹣8＝24位是段内位移
24空间，因此最大段长为2B.
7． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。
A.13
B.14
C.15
D.16
【答案】B
【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:
①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。
然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:
A. 左子树为空, 右子树为cd ;
b. 左子树为c , 右子树为d ;
c. 左子树为cd , 右子树为空。
按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。
8． 主机甲和乙已建立了TCP 连接, 甲始终以MSS=1KB大小的段发送数据, 并一直有数据发送; 乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗口为8KB , 则从t 时刻起, 不再发生超时的情况下, 经过10个RTT 后, 甲的发送窗口是（ ）
A.10KB
B.12KB
C.14KB
D.15KB
【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值, 这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的, 取最小值。
9． float 类型(即IEEE754单精度浮点数格式) 能表示的最大正整数是（ ）。 A. B. C. D.
【答案】D 。