【考研类试卷】考研计算机学科专业基础综合-2-1及答案解析.doc

《【考研类试卷】考研计算机学科专业基础综合-2-1及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】考研计算机学科专业基础综合-2-1及答案解析.doc（17页珍藏版）》请在麦多课文档分享上搜索。

1、考研计算机学科专业基础综合-2-1 及答案解析(总分：149.98，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.设有 3 个作业，其运行时间分别为 2 小时、5 小时、3 小时，假定它们同时到达，并在同一台处理机上以单道运行方式运行，则平均周转时间最小的执行顺序是( )。（分数：2.00）A.J1，J2，J3B.J3，J2，J1C.J2，J1，J3D.J1，J3，J22.下列关于指令周期的说法中正确的是( )。（分数：2.00）A.指令周期即时钟周期B.指令周期是指 CPU 执行一条指令的时间C.指令周期是指 CPU 取出一条指令并执行该指令的时间D.以上说

2、法都不对3.按照二叉树的定义，具有 3 个结点的二叉树有( )种。（分数：2.00）A.3B.4C.5D.64.某高度为 k 的完全二叉树中，所含叶子结点的个数最少为( )。（分数：2.00）A.2kB.kC.2k-2D.2k-15.操作系统采用页式存储管理方法，要求( )。（分数：2.00）A.每个进程拥有一张页表，且进程的页表驻留在内存中B.每个进程拥有一张页表，但只要执行进程的页表驻留在内存中，其他进程的页表不必驻留在内存中C.所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中D.所有进程共享一张页表，只有页表当前使用的页面必须驻留在内存中，以最大限度地节约有限的内存空间

3、6.在无噪声情况下，若某通信链路的带宽为 3kHz，采用 4 个相位，每个相位具有 4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是( )。（分数：2.00）A.12kbpsB.24kbpsC.48kbpsD.96kbps7.根据使用频率为 5 个字符的哈夫曼编码不可能的是( )。（分数：2.00）A.111，110，10，01，00B.000，001，010，011，1C.100，11，10，1，0D.001，000，01，11，108.分页系统中的页面是为( )。（分数：2.00）A.用户所感知的B.操作系统所感知的C.编译系统所感知的D.连接装配系统程序所感知的9.为解决

4、计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。（分数：2.00）A.栈B.队列C.树D.图10.在下列排序方法中不需要对排序码进行比较就能进行排序的是( )。（分数：2.00）A.基数排序B.快速排序C.直接插入排序D.堆排序11.若一组记录的排序码序列 F=50，80，30，40，70，60，利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为( )。（分数：2.00）A.30，40，50，60，70，80B.40，30，50，80，70，60C.50，30，4

5、0，70，60，80D.40，50，30，70，60，8012.在读写文件的操作中，通常使用“块高速缓存”，以减少访问磁盘的次数，但为了保证系统的( )，关键块必须尽早写盘。（分数：2.00）A.一致性B.安全性C.性能D.可扩性13.以太网地址是由( )个字节组成的。（分数：2.00）A.3B.4C.5D.614.下列关于 RISC 机的说法中错误的是( )。（分数：2.00）A.指令长度固定，指令格式种类少，寻址方式种类少B.配备大量通用寄存器C.强调采用流水线技术进行优化D.较少使用硬布线逻辑实现15.在 OSI 的层次模型中，( )是控制对等实体间进行通信的规则的集合。（分数：2.00

6、）A.协议B.服务C.接口D.原语16.在单发射、按序流动的普通流水线中，可能出现下列哪种数据相关问题( )。（分数：2.00）A.写后读相关 RAWB.读后写相关 WARC.写后写相关 WAWD.以上都有可能17.计算机的外围设备是指( )。（分数：2.00）A.主存储器B.外存储器C.除主机外的其他设备D.除 CPU 外的其他设备18.线性表的静态链表存储结构与顺序存储结构相比优点是( )。（分数：2.00）A.所有的操作算法实现简单B.便于随机存取C.便于插入与删除D.便于利用零散的存储器空间19.某字节多路通道的最大数据传输率为 1000B/s，它有 5 个子通道，则每个子通道的最大数

7、据传输率为( )。（分数：2.00）A.200B/sB.1000B/sC.介于 A、B 之间D.以上都不对20.计算机硬件系统中“主机”是指( )。（分数：2.00）A.主机箱及其内部硬件设备B.运算器和控制器C.CPU 和主存储器D.CPU、主存和输入输出设备21.中断向量的地址是( )。（分数：2.00）A.子程序入口地址B.中断服务例行程序入口地址C.中断服务例行程序入口地址的地址D.例行程序入口地址22.某计算机系统中，各个主设备得到总线使用权的机会基本相等，则该系统采用的总线判优控制方式一定不是( )。（分数：2.00）A.链式查询方式B.计数器定时查询方式C.独立请求方式D.以上选

8、项都不正确23.下列有关存储器的说法错误的是( )。（分数：2.00）A.访问存储器的请求是由 CPU 发出的B.Cache 与主存统一编址，即主存空间的某一部分属于 CacheC.Cache 的功能全由硬件实现D.Cache主存层次主要为了解决存储系统的速度问题24.在 DNS 的递归查询中，由( )给客户端返回地址。（分数：2.00）A.最开始连接的服务器B.最后连接的服务器C.目的地址所在的服务器D.不确定25.有一条 TCP 连接，它的最大报文段长度是 2KB，TCP 拥塞窗口为 24KB，这时候发生了超时事件，那么该拥塞窗口变成了( )。（分数：2.00）A.1KBB.2KBC.5K

9、BD.7KB26.TCP 使用三次握手协议来建立连接假设甲乙双方发送报文的初始序列号分别为 X 和 Y，甲方发送SYN=1，序号=X 的报文给乙方，乙方接收报文后发送( )的报文给甲方，然后甲方发送一个确认报文给乙方便建立了连接。（分数：2.00）A.SYN=0，序号=Y；ACK=1，确认序号=X+1B.SYN=1，序号=Y；ACK=0，确认序号=X+1C.SYN=1，序号=Y；ACK=1，确认序号=X+1D.SYN=1，序号=Y；ACK=1，确认序号=X27.在请求分页存储管理中，若采用 FIFO 的页面淘汰算法，当分配的页面数增加时，缺页中断的次数( )。（分数：2.00）A.减少B.增加

10、C.无影响D.可能增加也可能减少28.( )进程调度算法综合考虑到了 CPU 密集型进程和 I/O 密集型进程。（分数：2.00）A.时间轮转B.优先级C.多重队列D.FIFO29.用 P 代表入栈，O 代表出栈。栈的初始状态和最终状态都为空，则下列栈操作正确的是( )。（分数：2.00）A.POOPOOPPB.POPOPOOPC.PPPOOOPPD.PPPOOPOO30.某浮点机字长 16 位，其中，阶码 5 位(含 1 位阶符)，采用补码表示，基数为 4；尾数 11 位(含 1 位数符)，采用补码表示，且为规格化形式，则其可以表示的最小正数是( )。（分数：2.00）A.2-17B.2-2

11、6C.2-34D.2-4231.3 个进程共享 4 个同类资源，这些资源的分配与释放只能一次一个。已知每一个进程最多占有两个该类资源，则该系统( )。（分数：2.00）A.有某进程可能用于得不到该类资源B.必然有死锁C.进程请求该类资源立刻能得到D.必然无死锁32.求最短路径常用的算法有( )。（分数：2.00）A.Prim 算法和 Kruskal 算法B.深度优先遍历算法和广度优先遍历算法C.Dijkstra 算法和 Floyd 算法D.拓扑排序算法33.x补 =1.x1x2x3x4，则当满足( )时，x-1/2 成立。（分数：2.00）A.x1必为 0，x 2x 4至少有一个为 1B.x1

12、必为 0，x 2x 4任意C.x1必为 1，x 2x 4至少有一个为 1D.x1必为 1，x 2x 4任意34.程序员利用系统调用打开 I/O 设备时，通常使用的设备标识是( )。（分数：2.00）A.逻辑设备名B.物理设备名C.主设备号D.从设备号35.下列哪种寻址方式下，操作数在主存储器( )。（分数：2.00）A.直接寻址B.寄存器直接寻址C.立即数寻址D.以上都不对36.假设一个应用每秒产生 60bytes 的数据块，每个数据块被封装在一个 TCP 报文中，然后再封装到一个IP 数据报中。那么最后每个数据报所含有的应用数据所占的百分比是( )。（分数：2.00）A.20%B.40%C.

13、60%D.80%37.下列叙述正确的个数是( )。 1) 向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。 2) 对 B 一树中任一非叶子结点中的某关键字 K，比 K 小的最大关键字和比 K 大的最小关键字一定都在叶子结点中。 3) 所谓平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉树。 4) 删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树。（分数：2.00）A.4B.3C.2D.138.下面关于进程的叙述中，正确的是( )。（分数：2.00）A.进程获得 CPU 运行是通过调度得到的B.优先级是进程调度的重要依据，一旦确定就不能改变C.在

14、单 CPU 的系统中，任意时刻都有一个进程处于运行状态D.进程申请 CPU 得不到满足时，其状态变为阻塞39.数据链路层采用了后退 N 帧的(GBN)协议，如果发送窗口的大小是 32，那么至少需要( )位的序列号才能保证协议不出错。（分数：2.00）A.4 位B.5 位C.6 位D.7 位40.一个四体并行的低位交叉编址存储器，每个存储体的存取周期为 200ns，总线传输周期为 50ns，则连续读取 10 个存储字需时( )。（分数：2.00）A.2000nsB.600nsC.650nsD.300ns二、B综合应用题/B(总题数：4，分数：70.00)41.编写一个算法，实现以较高的效率从有序

15、顺序表 A 中删除其值在 x 和 y 之间 xAiy 的所有元素。（分数：10.00）_已知散列函数为 H(key)=key%11，处理冲突的方法为二次探测法，探测的序列为：1，-1.4，-4，j 2，-j 2(j-m/2)： 当 diO 时，H i=(H(key)+di)%m 当 di0 时，H i=(H(key)+di+m)%m 散列表如下表所示，试回答下面的问题：（分数：36.00）(1).对表中每个关键字进行查找时，各需要进行的比较次数；（分数：4.00）_(2).在等概率情况下查找时，查找成功的平均查找长度。（分数：4.00）_(3).原码定点小数；（分数：4.00）_(4).补码定

16、点小数；（分数：4.00）_(5).反码定点小数；（分数：4.00）_(6).IBEE754 标准短实数。 注题中机器数中间加空格是为了度写方便，并非机器数的一部分，答题时如有需要可类似表示。（分数：4.00）_(7).主存地址位数为多少?（分数：4.00）_(8).画出主存地址格式示意图，注明各字段名称及位数。（分数：4.00）_(9).设该 Cache 的命中率为 98%，如果 Cache 的速度是主存的 5 倍，则该机采用Cache 时存储系统的速度是不采用 Cache 时的多少倍(设 CPU 访存时同时访问Cache 和主存，若 Cache 命中则中断主存访问)?（分数：4.00）_4

17、2.桌上有一空盘，只允许放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子，女儿专等着吃盘中的苹果，儿子专等着吃盘中的橘子。试用 P，V 原语实现爸爸、妈妈、儿子和女儿间能同步的程序。（分数：7.00）_关于分页系统，回答下列问题：（分数：16.98）(1).在页表中，哪些数据项是为实现换页而设置的?（分数：2.83）_(2).设某系统为每个作业进程分配 3 个内存块，某作业进程在运行访问中的轨迹为1，4，3，1，6，8，1，且每一页都是按请求装入的。问：先进先出页面置换算法(FIFO)和最近未使用页面置换算法(LRU)下，产生缺页的次数各是多少?(画出必要的数据图)（分数：2.83）_(3

18、).在什么情况下，上述两种页面淘汰算法执行效果是一样的?为什么?（分数：2.83）_(4).经过计算后 A 到各个顶点的最短距离是多少?（分数：2.83）_(5).A 到各个顶点的最短路径是什么?（分数：2.83）_(6).如果此时 B 到 D 的链路长度更新为 3，那么 A 到各个节点的最短路径有什么变化? （分数：2.83）_考研计算机学科专业基础综合-2-1 答案解析(总分：149.98，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.设有 3 个作业，其运行时间分别为 2 小时、5 小时、3 小时，假定它们同时到达，并在同一台处理机上以单道运行方式运行，

19、则平均周转时间最小的执行顺序是( )。（分数：2.00）A.J1，J2，J3B.J3，J2，J1C.J2，J1，J3D.J1，J3，J2 解析：本题考查平均周转时间的概念，周转时间=等待时间+运行时间，平均运行时间=总周转时间/n。2.下列关于指令周期的说法中正确的是( )。（分数：2.00）A.指令周期即时钟周期B.指令周期是指 CPU 执行一条指令的时间C.指令周期是指 CPU 取出一条指令并执行该指令的时间 D.以上说法都不对解析：指令周期即 CPU 从主存取出一条指令并执行该指令的时间，C 选项为正确选项。3.按照二叉树的定义，具有 3 个结点的二叉树有( )种。（分数：2.00）A.

20、3B.4C.5 D.6解析：由于二叉树分左右子树，则由 n 个结点构成的二叉树共有 5 种。4.某高度为 k 的完全二叉树中，所含叶子结点的个数最少为( )。（分数：2.00）A.2kB.kC.2k-2 D.2k-1解析：完全二叉树只有高度最大的那一层可能不满，k-1 层应都是满的。5.操作系统采用页式存储管理方法，要求( )。（分数：2.00）A.每个进程拥有一张页表，且进程的页表驻留在内存中 B.每个进程拥有一张页表，但只要执行进程的页表驻留在内存中，其他进程的页表不必驻留在内存中C.所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中D.所有进程共享一张页表，只有页表当前使

21、用的页面必须驻留在内存中，以最大限度地节约有限的内存空间解析：在分页系统中为每个进程都配置一张页表，进程逻辑地址空间中的每一页在页表中都有一个页表项。6.在无噪声情况下，若某通信链路的带宽为 3kHz，采用 4 个相位，每个相位具有 4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是( )。（分数：2.00）A.12kbpsB.24kbps C.48kbpsD.96kbps解析：采用四个相位每个相位有 4 种振幅的 QAM 调制技术后，每个信号可以有 16 种变化，传输 4bit 的数据。而链路带宽为 3kHz，根据奈奎斯特定理，可以用 6kHz 的频率对信道采样，所以最大传输速

22、率是24kbps。7.根据使用频率为 5 个字符的哈夫曼编码不可能的是( )。（分数：2.00）A.111，110，10，01，00B.000，001，010，011，1C.100，11，10，1，0 D.001，000，01，11，10解析：C 中 100 和 10 冲突，即一个结点既是叶子结点又是内部结点，哈夫曼树中不可能出现这种情况。8.分页系统中的页面是为( )。（分数：2.00）A.用户所感知的B.操作系统所感知的 C.编译系统所感知的D.连接装配系统程序所感知的解析：页面信息是由操作系统管理的。9.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的

23、数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。（分数：2.00）A.栈B.队列 C.树D.图解析：10.在下列排序方法中不需要对排序码进行比较就能进行排序的是( )。（分数：2.00）A.基数排序 B.快速排序C.直接插入排序D.堆排序解析：11.若一组记录的排序码序列 F=50，80，30，40，70，60，利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为( )。（分数：2.00）A.30，40，50，60，70，80 B.40，30，50，80，70，60C.50，30，40，70，60，80D.40，50，30，70，60，80解

24、析：12.在读写文件的操作中，通常使用“块高速缓存”，以减少访问磁盘的次数，但为了保证系统的( )，关键块必须尽早写盘。（分数：2.00）A.一致性 B.安全性C.性能D.可扩性解析：为了保证数据一致性，必须保证先写后读。13.以太网地址是由( )个字节组成的。（分数：2.00）A.3B.4C.5D.6 解析：以太网地址由 48 比特组成，常用 6 个字节表示。而 IPv4 的地址由 32 比特组成，常使用 4 个字节表示。14.下列关于 RISC 机的说法中错误的是( )。（分数：2.00）A.指令长度固定，指令格式种类少，寻址方式种类少B.配备大量通用寄存器C.强调采用流水线技术进行优化D

25、.较少使用硬布线逻辑实现 解析：RISC 机由于结构较简单，故常采用速度较陕的硬布线逻辑来实现，D 选项错误。15.在 OSI 的层次模型中，( )是控制对等实体间进行通信的规则的集合。（分数：2.00）A.协议 B.服务C.接口D.原语解析：协议是控制两个对等实体进行通信的规则的集合，而服务是指某一层向它上一层提供的一组原语。服务是由下层向上层通过层间接口提供的，而原语则是用来描述操作的。服务和协议的关系可以由下图来描述：16.在单发射、按序流动的普通流水线中，可能出现下列哪种数据相关问题( )。（分数：2.00）A.写后读相关 RAW B.读后写相关 WARC.写后写相关 WAWD.以上都

26、有可能解析：指令取操作数的动作一定在写回结果之前，故在按序流动的单发射(普通标量)普通流水线中，先进入流水线的指令的取操作数和写回结果的动作一定位于后续指令写回结果的动作之前，故不可能出现 WAR和 WAW；唯一可能的数据相关问题是后续指令在前一指令写回结果之前读相关的操作数，即 RAW，写后读相关。而在非按序流动的流水线中，允许后进入流水线的指令超过先进入流水线的指令而先流出流水线，故三种数据相关问题都可能出现。17.计算机的外围设备是指( )。（分数：2.00）A.主存储器B.外存储器C.除主机外的其他设备 D.除 CPU 外的其他设备解析：外围设备是相对主机而言，即除 CPU 和主存储器

27、外的其他设备。18.线性表的静态链表存储结构与顺序存储结构相比优点是( )。（分数：2.00）A.所有的操作算法实现简单B.便于随机存取C.便于插入与删除 D.便于利用零散的存储器空间解析：静态链表具有链表的插入和删除方便的优点，也不需要移动较多的元素。19.某字节多路通道的最大数据传输率为 1000B/s，它有 5 个子通道，则每个子通道的最大数据传输率为( )。（分数：2.00）A.200B/s B.1000B/sC.介于 A、B 之间D.以上都不对解析：字节多路通道轮流对各个子通道进行传送，每次连接一个子通道只传送一个字节便转向下一个子通道，故字节多路通道的最大数据传输率为各个子通道最大

28、数据传输率之和，即每个子通道的最大数据传输率为 1000/5=200B/s。20.计算机硬件系统中“主机”是指( )。（分数：2.00）A.主机箱及其内部硬件设备B.运算器和控制器C.CPU 和主存储器 D.CPU、主存和输入输出设备解析：CPU 和主存储器合称主机。21.中断向量的地址是( )。（分数：2.00）A.子程序入口地址B.中断服务例行程序入口地址C.中断服务例行程序入口地址的地址 D.例行程序入口地址解析：中断向量包括两个字，一个是中断处理程序的入口地址，另一个是中断处理程序的程序状态字。那么显然，中断向量地址就是中断处理程序的入口地址的地址了。22.某计算机系统中，各个主设备得

29、到总线使用权的机会基本相等，则该系统采用的总线判优控制方式一定不是( )。（分数：2.00）A.链式查询方式 B.计数器定时查询方式C.独立请求方式D.以上选项都不正确解析：链式查询方式下，越靠近总线仲裁机构的主设备优先级越高，且其优先级顺序不可改变故不可能出现各主设备得到总线使用权机会基本相等的情况。23.下列有关存储器的说法错误的是( )。（分数：2.00）A.访问存储器的请求是由 CPU 发出的B.Cache 与主存统一编址，即主存空间的某一部分属于 Cache C.Cache 的功能全由硬件实现D.Cache主存层次主要为了解决存储系统的速度问题解析：Cache 中字块保存的是主存中相

30、应字块的副本，Cache 是一种缓冲，而不是与主存处于同等地位的存储器，故不需要占用主存空间，B 选项错误。24.在 DNS 的递归查询中，由( )给客户端返回地址。（分数：2.00）A.最开始连接的服务器 B.最后连接的服务器C.目的地址所在的服务器D.不确定解析：在递归查询中，每台不包含被请求信息的服务器都转到别的地方去查找，然后它再往回发送结果。所以客户端最开始连接的服务器最终将返回给它正确的信息。25.有一条 TCP 连接，它的最大报文段长度是 2KB，TCP 拥塞窗口为 24KB，这时候发生了超时事件，那么该拥塞窗口变成了( )。（分数：2.00）A.1KBB.2KB C.5KBD.

31、7KB解析：在 TCP 中，当发生超时事件，阀值被设置成当前拥塞窗口的一半，而拥塞窗口被设为一个最大报文段。26.TCP 使用三次握手协议来建立连接假设甲乙双方发送报文的初始序列号分别为 X 和 Y，甲方发送SYN=1，序号=X 的报文给乙方，乙方接收报文后发送( )的报文给甲方，然后甲方发送一个确认报文给乙方便建立了连接。（分数：2.00）A.SYN=0，序号=Y；ACK=1，确认序号=X+1B.SYN=1，序号=Y；ACK=0，确认序号=X+1C.SYN=1，序号=Y；ACK=1，确认序号=X+1 D.SYN=1，序号=Y；ACK=1，确认序号=X解析：本题考查 TCP 协议建立的三次握手

32、，乙方接受到甲方的建立连接请求后再发送一个 SYN=1 的报文请求建立本方连接。而题目中说明甲方再回复一个确认报文就可以建立连接，说明了乙方在报文中捎带了确认即 ACK=1。确认号是 X+1，所以答案是 C。27.在请求分页存储管理中，若采用 FIFO 的页面淘汰算法，当分配的页面数增加时，缺页中断的次数( )。（分数：2.00）A.减少B.增加C.无影响D.可能增加也可能减少 解析：为 FIFO 算法存在 Belady 现象，所以可能增加也可能减少。28.( )进程调度算法综合考虑到了 CPU 密集型进程和 I/O 密集型进程。（分数：2.00）A.时间轮转B.优先级C.多重队列 D.FIF

33、O解析：多重队列通过将进程分类，在系统中设置若干队列进行进程调度，综合考虑到了 CPU 密集型进程和I/O 密集型进程。29.用 P 代表入栈，O 代表出栈。栈的初始状态和最终状态都为空，则下列栈操作正确的是( )。（分数：2.00）A.POOPOOPPB.POPOPOOPC.PPPOOOPPD.PPPOOPOO 解析：A，B 会出现下溢，即出栈时栈为空。C 中出现最终状态不为空。30.某浮点机字长 16 位，其中，阶码 5 位(含 1 位阶符)，采用补码表示，基数为 4；尾数 11 位(含 1 位数符)，采用补码表示，且为规格化形式，则其可以表示的最小正数是( )。（分数：2.00）A.2-

34、17B.2-26C.2-34 D.2-42解析：根据题意，该机可以表示的正数的机器数形式为：1.0000；0.0100000000，其真值为 4-16(14-1)=4-17=2-34，选 C。本题要注意基数为 4 时尾数的规格化形式。31.3 个进程共享 4 个同类资源，这些资源的分配与释放只能一次一个。已知每一个进程最多占有两个该类资源，则该系统( )。（分数：2.00）A.有某进程可能用于得不到该类资源B.必然有死锁C.进程请求该类资源立刻能得到D.必然无死锁 解析：根据题意，则任意时刻总有一个进程可以获得其所有资源，从而能在有限的时间内运行完毕，所以系统那个必然无死锁。32.求最短路径常

35、用的算法有( )。（分数：2.00）A.Prim 算法和 Kruskal 算法B.深度优先遍历算法和广度优先遍历算法C.Dijkstra 算法和 Floyd 算法 D.拓扑排序算法解析：A 是最小生成树的算法，B 是图的遍历算法，D 中的回溯法是求解递归过程的一种重要方法。33.x补 =1.x1x2x3x4，则当满足( )时，x-1/2 成立。（分数：2.00）A.x1必为 0，x 2x 4至少有一个为 1B.x1必为 0，x 2x 4任意C.x1必为 1，x 2x 4至少有一个为 1 D.x1必为 1，x 2x 4任意解析：可采用排除法，1.0001 符合 A、B 选项的要求，其值-15/1

36、6-1/2，排除 A、B；1.1000 符合 D 选项的要求，其值=-1/2，排除 D；故选 C。34.程序员利用系统调用打开 I/O 设备时，通常使用的设备标识是( )。（分数：2.00）A.逻辑设备名 B.物理设备名C.主设备号D.从设备号解析：程序员所看到的是设备的逻辑设备名。35.下列哪种寻址方式下，操作数在主存储器( )。（分数：2.00）A.直接寻址 B.寄存器直接寻址C.立即数寻址D.以上都不对解析：直接寻址时，形式地址 A 为有效地址，即操作数在主存储器的地址，也就是说操作数在主存储器。36.假设一个应用每秒产生 60bytes 的数据块，每个数据块被封装在一个 TCP 报文中

37、，然后再封装到一个IP 数据报中。那么最后每个数据报所含有的应用数据所占的百分比是( )。（分数：2.00）A.20%B.40%C.60% D.80%解析：一个 TCP 的头部长度是 20 字节，一个 IP 头部的长度是 20 字节，再加上 60 字节的数据，一个 IP数据报的总长度为 100 个字节，其中数据占 60%。37.下列叙述正确的个数是( )。 1) 向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。 2) 对 B 一树中任一非叶子结点中的某关键字 K，比 K 小的最大关键字和比 K 大的最小关键字一定都在叶子结点中。 3) 所谓平衡二叉树是指左、右子树的高度差

38、的绝对值不大于 1 的二叉树。 4) 删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树。（分数：2.00）A.4B.3C.2D.1 解析：只有 3 是正确的。38.下面关于进程的叙述中，正确的是( )。（分数：2.00）A.进程获得 CPU 运行是通过调度得到的 B.优先级是进程调度的重要依据，一旦确定就不能改变C.在单 CPU 的系统中，任意时刻都有一个进程处于运行状态D.进程申请 CPU 得不到满足时，其状态变为阻塞解析：A正确 这是进程获取 CPU 的唯一方法。 B错误 优先级是可以动态改变的。 C错误 没进程的时候，系统可以空闲。 D错误 变为就绪态。39.数据链路层

39、采用了后退 N 帧的(GBN)协议，如果发送窗口的大小是 32，那么至少需要( )位的序列号才能保证协议不出错。（分数：2.00）A.4 位B.5 位C.6 位 D.7 位解析：在后退 N 帧的协议中，序列号个数=MAX_SEQ+1，在题目中发送窗口的大小是 32，那么序列号个数最少应该是 33 个。所以最少需要 6 位的序列号才能达到要求。40.一个四体并行的低位交叉编址存储器，每个存储体的存取周期为 200ns，总线传输周期为 50ns，则连续读取 10 个存储字需时( )。（分数：2.00）A.2000nsB.600nsC.650ns D.300ns解析：四体并行的低位交叉存储器连续读取

40、 10 个存储字时，读第一个存储字需要一个完整的存取周期，即 200ns，接下来每个存储字的读取只需一个总线传输周期 50ns，故共需时 200+50(10-1)=650ns。二、B综合应用题/B(总题数：4，分数：70.00)41.编写一个算法，实现以较高的效率从有序顺序表 A 中删除其值在 x 和 y 之间 xAiy 的所有元素。（分数：10.00）_正确答案：()解析：逐个检测顺序表中值在 x 和 y 之间的元素，并计数于 k，再将其值大于 y 的元素向前移动 k 个元素。算法描述如下： void DeleteXY(SList* la，int x，int y) int k=0; for(

41、int i=0;ia-size;i+) if(a-datai=xa-datai=y) k+; else a-datai-k=a-datai; a-n=a-n-k; 已知散列函数为 H(key)=key%11，处理冲突的方法为二次探测法，探测的序列为：1，-1.4，-4，j 2，-j 2(j-m/2)： 当 diO 时，H i=(H(key)+di)%m 当 di0 时，H i=(H(key)+di+m)%m 散列表如下表所示，试回答下面的问题：（分数：36.00）(1).对表中每个关键字进行查找时，各需要进行的比较次数；（分数：4.00）_正确答案：()解析：查找成功的比较次数分为： 21:2

42、 57:2 45:3 37:1 50:2(2).在等概率情况下查找时，查找成功的平均查找长度。（分数：4.00）_正确答案：()解析：查找成功的平均查找长度为(2+2+3+1+2)/5=2(3).原码定点小数；（分数：4.00）_正确答案：()解析：该 32 位二进制机器数为原码定点小数时，其真值为 -12-1=-0.5；(4).补码定点小数；（分数：4.00）_正确答案：()解析：该 32 位二进制机器数为补码定点小数时，根据其符号位为 1 可知其为负数，为方便计算，将其连符号位在内取反加 1，得其相反数的补码机器数为 0.1000 0000 0000 0000 0000 0000 0000 000 相反数真值为 12-1=0.5，故原机器数真值为-0.5；(5).反码定点小数；（分数：4.00）_正确答案：()解析：该 32 位二进制机器数为反码定点小数时，根据其符号位为 1 可知其为负数，故将其数值位取反即可得其真值对应的原码机器数为 1.0111 1111 1111 1111 1111 1111 1111 111 其真值为-(02 -1+12-2+12-31)=-(