1、考研计算机学科专业基础综合-8-2 及答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（分数：2.00）A.冒泡排序B.希尔排序C.直接选择排序D.直接插入排序2.某机器指令字长 12 位，有零地址、一地址、二地址三种指令，地址码长 4 位，采用扩展操作码技术。若二地址指令和一地址指令条数都取最大值，则该机指令条数最多为( )。（分数：2.00）A.16B.46C.48D.4 3663.条件转移指令执行时所依据的条件来自( )。（分数：2.00）A.指令寄存
2、器 IRB.程序计数器 PCC.程序状态字寄存器 PSWRD.主存地址寄存器 MAR4.以下( )协议完成了从网卡到 IP 地址的映射。（分数：2.00）A.ARP 协议B.RARP 协议C.IGMP 协议D.ICMP 协议5.假定一台主机的 IP 地址是 222.205.74.56，子网掩码为 255.255.240.0，该子网地址为( )。（分数：2.00）A.222.205.0.0B.222.205.64.0C.222.205.72.0D.222.205.74.06.为了保证操作系统本身的安全，( )是必须加以保护的。（分数：2.00）A.从内核模式转换到用户模式B.从存储操作系统内核的
3、空间读取数据C.从存储操作系统内核的空间读取指令D.打开定时器7.系统功能调用是( )。（分数：2.00）A.用户编写的一个子程序B.高级语言中的库程序C.操作系统中的一条命令D.操作系统向用户提供的接口8.下面关于图的存储结构的叙述中正确的是( )。（分数：2.00）A.用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关B.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点无关C.用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关9.下列哪个选项不可能是微指令格式中的组成部分( )。（分数：2.00）A.操作码字段B.
4、操作控制字段C.外部条件字段D.下地址字段10.关于临界区问题(critical section problem)是一个算法(假设只有进程 P0 和 P1 可能进入该临界区)，算法如下(i 为 0 或 1)，该算法( )。 reapeat retry:if(turn-1)turn:=i； if(turni)go to retry； turn:=-1； critical Section(临界区) turn=O： remainder Section(其他区域) untial false：（分数：2.00）A.不能保证进程互斥进入临界区，且会出现“饥饿”(Starvation)B.不能保证进程互斥进
5、入临界区，但不会出现“饥饿”C.保证进程能互斥进入临界区，但会出现“饥饿”D.保证进程互斥进入临界区，不会出现“饥饿”11.下列关于机器字长与指令字长的说法正确的是( )。（分数：2.00）A.指令字长等于机器字长B.指令字长一定是机器字长的整数倍C.两者长度没有必然关系D.以上说法都不对12.前序遍历和中序遍历结果相同的二叉树为( )。（分数：2.00）A.根结点无左孩子的二叉树B.根结点无右孩子的二叉树C.所有结点只有左子树的二叉树D.所有结点只有右子树的二叉树13.某机中，设备号小的主设备在总线判优时具有较高的优先级，其总线判优方式可能是( )。（分数：2.00）A.链式查询方式B.计数
6、器定时查询方式C.独立请求方式D.以上都有可能14.一个 16 端口的二层以太网交换机，冲突域和广播域的个数分别是( )。（分数：2.00）A.1，1B.16，16C.1，16D.16，115.通常对文件系统来说，文件名及其属性可以集中在( )。（分数：2.00）A.目录B.索引C.字典D.作业控制块16.假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多 1 个，那么，下面列出的 4 种情况中，( )可能发生死锁。情况序号系统中进程数资源总量（分数：2.00）A.1 2B.2 1C.2 2D.2 317.系统拥有一个 CPU，IO1 和 IO2 为两个不同步的输入/输出装置，它们能
7、够同时工作，当使用 CPU 之后控制转向 IO1、IO2 时，或者使用 IO1、IO2 之后控制转向 CPU 时，由控制程序执行中断处理，但这段处理时间忽略不计。有 A、B 两个进程同时被创建，进程 B 的调度优先权比 A 高。但是当进程 A 占有 CPU 时，即使进程 B 需要占用 CPU，也不能打断进程 A 的执行。若在同一系统中分别单独执行，则需要占用CPU、101、102 的时间如下图所示： 进程 A（分数：2.00）A.CPUB.IO1C.CPUD.IO2E.CPUF.IO1G.25msH.30msI.20msJ.20msK.20msL.30ms18.在 HTTP 协议中，一个以 2
8、 开头的响应报文表示( )。（分数：2.00）A.暂时性失败B.永久性失败C.重定向D.成功19.RS-232-C 的电气特性规定逻辑“1”的电平范围为( )。（分数：2.00）A.+5+15VB.-5-15VC.0+5VD.0-5V20.某计算机字长 8 位，采用补码表示小数。若某数真值为-0.1001，则它在该计算机中的机器数形式为( )。（分数：2.00）A.10111B.10110111C.10111000D.1011000021.下列排序算法中，时间复杂度为 O(nlog n)且占用额外空间最少的是( )。（分数：2.00）A.堆排序B.冒泡排序C.快速排序D.希尔排序22.在一个顺
9、序循环队列中删除元素时，首先需要( )。（分数：2.00）A.前移队首指针B.后移队首指针C.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素23.中断向量表中保存的是( )。（分数：2.00）A.被中断程序的返回地址B.中断服务程序入口地址C.中断服务程序入口地址的地址D.中断优先级24.下列二叉排序树中，满足平衡二叉树定义的是( )。（分数：2.00）A.B.C.D.25.下列说法中错误的是( )。（分数：2.00）A.程序查询方式下，CPU 与 I/O 设备串行工作B.程序中断方式下，CPU 与 I/O 设备并行工作C.DMA 方式下，主程序可与 I/O 数据传送并行工作D.
10、实现了 DMA 方式的系统中，程序中断方式没有存在的必要26.下列各选项是采用奇偶校验码编码的 ASCII 码，所有编码都未发生错误，采用偶校验的是( )。（分数：2.00）A.01001101B.0011001C.10101101D.110100027.某通讯线路每 20ms 采样一次，每一个信号共有 64 种不同的状态，那么这个线路的传输速率是( )。（分数：2.00）A.100bpsB.200bpsC.300bpsD.400bps28.在( )的情况下，系统出现死锁。（分数：2.00）A.计算机系统发生重大故障B.有多个封锁的进程同时存在C.若干进程因竞争资源而无休止地相互等待对方释放已
11、占有的资源D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数29.如下图所示一棵二叉排序，其不成功的平均查找长度为( )。（分数：2.00）A.21/7B.28/7C.15/6D.21/630.如果 I/O 设备和存储设备之间的数据交换不经过 CPU 来完成，则这种交换方式是( )。（分数：2.00）A.程序查询方式B.中断方式C.DMA 方式D.外部总线方式31.浮点运算结果满足下列哪个条件时，需做中断处理( )。（分数：2.00）A.尾数双符号位为“01”B.尾数双符号位为“10”C.阶码双符号位为“01”D.阶码双符号位为“10”32.如果对含有 n(n1)个元素的线性表的运
12、算只有 4 种：删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后个元素的后面插入新元素，则最好使用( )。（分数：2.00）A.只有尾结点指针没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环单链表C.只有头结点指针没有尾结点指针的循环单链表D.既有头结点指针也有尾结点指针的循环单链表33.一个 TCP 连接总是以 1KB 的最大段发送 TCP 段，发送方有足够多的数据要发送。当拥塞窗口为 16KB 时发生了超时，如果接下来的 4 个 RTT(往返时间)时间内的 TCP 段的传输都是成功的，那么当第 4 个 RTT 时间内发送的所有 TCP 段都得到肯定应答
13、时，拥塞窗口大小是( )。（分数：2.00）A.7KBB.8KBC.9KBD.16KB34.对包含 n 个关键码的散列表进行检索，平均检索长度为( )。（分数：2.00）A.O(log n)B.O(n)C.O(nlog n)D.不直接依赖于 n35.下列只读存储器中，可编程且可以实现字擦除的是( )。（分数：2.00）A.掩模 ROMB.PROMC.EPROMD.EEPROM36.如果二叉树 T2 是由有序树 T1 转换而来的二叉树，那么 T1 中结点的后序就是 T2 中结点的( )。（分数：2.00）A.先序B.中序C.后序D.层次序37.一个分段存储管理系统中，地址长度为 32 位，其中段
14、号占 8 位，则最大段长是( )。（分数：2.00）A.28字节B.216字节C.224字节D.232字节38.定点数采用模 4 补码，即变形补码进行加减运算时，判断溢出的方法是( )。（分数：2.00）A.符号位进位与最高数值位进位相异时表明溢出B.实际参与运算的两数符号位相同，结果又与原操作数符号不同时表明溢出C.双符号位不同时表明溢出D.以上都正确39.下列交换方式中，( )一次连接沿着一条路由路径发送所有的数据。（分数：2.00）A.分组交换B.报文交换C.电路交换D.以上都不是40.以下关于 UNIX 操作系统的叙述中，( )是错误的。（分数：2.00）A.UNIX 对实时系统是不合
15、适的，因为进程在核心态不可抢占B.UNIX 终究会在市场上消失的C.UNIX 是目前最流行的操作系统之一D.UNIX 比较适用于高档计算机系统和网络环境，它不能用于普通的微机二、B综合应用题/B(总题数：5，分数：70.00)41.设算术表达式由字符串 b 表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“( )( )”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。（分数：10.00）_42.带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题
16、的方法： 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点； 选择离 u 最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点 u=v; 重复步骤，直到 u 是目标顶点时为止。 请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。（分数：15.00）_43.某计算机字长 16 位，采用 16 位定长指令字结构，部分数据通路结构如下图所示。图中所有控制信号为 1 时表示有效、为 O 时表示无效。例如控制信号 MDRinE 为 1 表示允许数据从 DB 打入 MDR，MDRin 为 1表示允许数据从内总线打入 MDR。假设 MAR 的输出一直处于使能状态
17、。加法指令“ADD(R1)，R0”的功能为(R0)+(R1)(R1)，即将 R0 中的数据与 R1 的内容所指主存单元的数据相加，并将结果送入 R1 的内容所指主存单元中保存。 下表给出了上述指令取值和译码阶段每个节拍(时钟周期)的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。B功能和控制信号/B时钟 功能 有效控制信号C1 MAR(PC) PCout，MARinC2 MDRM(MAR)PC(PC)+1MemR，MDRinEPC+1C3 IR(MDR) MDRout，IRinC4 指令译码 无（分数：13.00）_44.某计算机系统字长为 32 位，包
18、含 2 个选择通道和 1 个字节多路通道，每个选择通道上连接了 2 台磁盘机和 2 台磁带机，字节多路通道上连接了 2 台行式打印机、2 台读卡器、10 台终端。假定各设备的传输率如下： 磁盘机：800KB/s 磁带机：200KB/s 行打机：6.6KB/s 读卡机：1.2KB/s 终端：1KB/s 计算该计算机系统最大 I/O 数据传输率。（分数：8.00）_某请求页式存储管理，允许用户空间为 32 个页面(每页 1KB)，主存为 16KB。如果一个用户程序有 10 页长，且某时刻用户进程的页表如下表所示： 虚页号 物理页号 是否在 TLB 中0 8 是1 7 是2 4 否3 10 否4 5
19、 否5 3 是6 2 是其他 not valid（分数：24.00）(1).如果程序执行遇到以下两个虚地址：0AC5H、1AC5H，试计算它们对应的物理地址。（分数：3.00）_(2).页表存放在主存中，对主存的一次存取需要 1.5 微秒，对 TLB 的查找时间忽略为 0，试问这两次访问共耗费多少时间?（分数：3.00）_(3).简述判断死锁的必要条件。（分数：3.00）_(4).一种哲学家就餐问题的解决方案如下所述(对每位哲学家都采用这种算法)，分析其死锁的可能性并提出解决方案。 Philosopher i: dowait(chopstsicki； wait(chopstick(i+1)%5
20、) eat signal(chopsticki)； signal(chopstick(i+1)%5)； think while(1)；（分数：3.00）_(5).由个人主机发送给本地 DNS 服务器的数据是采用什么传输层协议发送的?利用了哪个端口?（分数：3.00）_(6).由个人主机到本地 DNS 服务器查询是采用了什么方式?（分数：3.00）_(7).有本地 DNS 服务器到各个域名服务器的查询采用了什么方式?（分数：3.00）_(8).本地 DNS 服务器的查询顺序是什么? （分数：3.00）_考研计算机学科专业基础综合-8-2 答案解析(总分：150.00，做题时间：90 分钟)一、B
21、单项选择题/B(总题数：40，分数：80.00)1.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（分数：2.00）A.冒泡排序B.希尔排序C.直接选择排序 D.直接插入排序解析：A、C 每一趟都能选出一个元素放在最终位置上，但只有 C 是不稳定的。2.某机器指令字长 12 位，有零地址、一地址、二地址三种指令，地址码长 4 位，采用扩展操作码技术。若二地址指令和一地址指令条数都取最大值，则该机指令条数最多为( )。（分数：2.00）A.16B.46 C.48D.4 366解析：根据题意，二地址指令的操作码长度为 12-42=4，留一个编码用于扩展，故最多可定义
22、15 条二地址指令；一地址指令扩展长度为 4 位，留一个编码用于扩展，故最多可定义 15 条一地址指令；零地址指令可在一地址指令的基础上扩展 4 位，故最多可定义 16 条零地址指令，根据题意，该机指令条数最多为(15+15+16=)46 条。3.条件转移指令执行时所依据的条件来自( )。（分数：2.00）A.指令寄存器 IRB.程序计数器 PCC.程序状态字寄存器 PSWR D.主存地址寄存器 MAR解析：程序状态字寄存器 PSWR 用来保存根据运算结果设置的各种状态位，这些状态位可以被测试；条件转移指令正是通过测试这些状态位来决定是否跳转。4.以下( )协议完成了从网卡到 IP 地址的映射
23、。（分数：2.00）A.ARP 协议 B.RARP 协议C.IGMP 协议D.ICMP 协议解析：地址解析协议 ARP 用来在局域网上从目的 IP 地址得到目的 MAC 地址。5.假定一台主机的 IP 地址是 222.205.74.56，子网掩码为 255.255.240.0，该子网地址为( )。（分数：2.00）A.222.205.0.0B.222.205.64.0 C.222.205.72.0D.222.205.74.0解析：240 的二进制表示是 1111 0000，74 的二进制表示是 0100 1010，子网地址的第 3 字节是二进制0100 0000，即 64。6.为了保证操作系统
24、本身的安全，( )是必须加以保护的。（分数：2.00）A.从内核模式转换到用户模式B.从存储操作系统内核的空间读取数据C.从存储操作系统内核的空间读取指令D.打开定时器 解析：打开定时器会影响系统的时间。7.系统功能调用是( )。（分数：2.00）A.用户编写的一个子程序B.高级语言中的库程序C.操作系统中的一条命令D.操作系统向用户提供的接口 解析：本题考查系统调用的概念。8.下面关于图的存储结构的叙述中正确的是( )。（分数：2.00）A.用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关 B.用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点无关C.用邻接表存储图占用空间大小只与
25、图中顶点数有关，与边数无关D.用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关解析：9.下列哪个选项不可能是微指令格式中的组成部分( )。（分数：2.00）A.操作码字段 B.操作控制字段C.外部条件字段D.下地址字段解析：操作码字段是机器指令的组成部分，垂直型微指令中可能有微操作码字段，水平型微指令中无相应字段，故选 A。10.关于临界区问题(critical section problem)是一个算法(假设只有进程 P0 和 P1 可能进入该临界区)，算法如下(i 为 0 或 1)，该算法( )。 reapeat retry:if(turn-1)turn:=i； if(turni)
26、go to retry； turn:=-1； critical Section(临界区) turn=O： remainder Section(其他区域) untial false：（分数：2.00）A.不能保证进程互斥进入临界区，且会出现“饥饿”(Starvation) B.不能保证进程互斥进入临界区，但不会出现“饥饿”C.保证进程能互斥进入临界区，但会出现“饥饿”D.保证进程互斥进入临界区，不会出现“饥饿”解析：例如当 PO 执行完语句 turn:=-1；进入临界区时，CPU 调度 P1 执行，P1 顺利进入临界区，不能满足互斥。 当 P0 执行完临界区时，CPU 调度 P1 执行，P1 在
27、 retry 循环，CPU 调度 P0 执行，P0 继续执行，重复以上过程，会导致 P1 饥饿。11.下列关于机器字长与指令字长的说法正确的是( )。（分数：2.00）A.指令字长等于机器字长B.指令字长一定是机器字长的整数倍C.两者长度没有必然关系 D.以上说法都不对解析：指令字长取决于操作码的长度、操作数地址的长度和操作数地址的个数，与机器字长没有必然的联系；但为了硬件设计方便，指令字长一般取字节或存储字长的整数倍。12.前序遍历和中序遍历结果相同的二叉树为( )。（分数：2.00）A.根结点无左孩子的二叉树B.根结点无右孩子的二叉树C.所有结点只有左子树的二叉树D.所有结点只有右子树的二
28、叉树 解析：前序遍历是根结点，左子树，右子树；中序遍历是左子树，根结点，右子树。易知，如果没有左子树，则两者相同。13.某机中，设备号小的主设备在总线判优时具有较高的优先级，其总线判优方式可能是( )。（分数：2.00）A.链式查询方式B.计数器定时查询方式C.独立请求方式D.以上都有可能 解析：三种集中仲裁方式都有可能，其实现方式分别为：链式请求方式下，将总线同意线上靠近仲裁中心的设备分配较小的设备号；计数器定时方式下，计数器从 0 开始计时；独立请求方式下，通过程序设置赋予设备号较少的主设备较高的优先级。14.一个 16 端口的二层以太网交换机，冲突域和广播域的个数分别是( )。（分数：2
29、.00）A.1，1B.16，16C.1，16D.16，1 解析：二层以太网交换机的每个端口都是冲突域的终止点，但 LAN 交换机不隔离广播，所以本题中，冲突域和广播域的个数分别是 16 和 1。15.通常对文件系统来说，文件名及其属性可以集中在( )。（分数：2.00）A.目录 B.索引C.字典D.作业控制块解析：目录里存文件名及其基本信息。16.假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多 1 个，那么，下面列出的 4 种情况中，( )可能发生死锁。情况序号系统中进程数资源总量（分数：2.00）A.1 2B.2 1C.2 2 D.2 3解析：C 当系统的 2 个进程各拥有 1
30、 个资源，都申请另一个资源时，会发生死锁，因为没资源分配给它们。17.系统拥有一个 CPU，IO1 和 IO2 为两个不同步的输入/输出装置，它们能够同时工作，当使用 CPU 之后控制转向 IO1、IO2 时，或者使用 IO1、IO2 之后控制转向 CPU 时，由控制程序执行中断处理，但这段处理时间忽略不计。有 A、B 两个进程同时被创建，进程 B 的调度优先权比 A 高。但是当进程 A 占有 CPU 时，即使进程 B 需要占用 CPU，也不能打断进程 A 的执行。若在同一系统中分别单独执行，则需要占用CPU、101、102 的时间如下图所示： 进程 A（分数：2.00）A.CPU B.IO1
31、C.CPUD.IO2E.CPUF.IO1G.25msH.30msI.20msJ.20msK.20msL.30ms解析：画出甘特图，可得 A。18.在 HTTP 协议中，一个以 2 开头的响应报文表示( )。（分数：2.00）A.暂时性失败B.永久性失败C.重定向D.成功 解析：HTTP 协议中以 2 开头的响应报文表示请求成功。19.RS-232-C 的电气特性规定逻辑“1”的电平范围为( )。（分数：2.00）A.+5+15VB.-5-15V C.0+5VD.0-5V解析：RS-232-C 关于电气信号特性的要求，规定逻辑“1”的电平为低于-3V，为了表示一个逻辑 1 或MARK 条件，驱动
32、器必须提供-5V-15V 之间的电压；为了表示一个逻辑 0 或 SPACE 条件，驱动器必须给出+5V+15V 之间的电压。20.某计算机字长 8 位，采用补码表示小数。若某数真值为-0.1001，则它在该计算机中的机器数形式为( )。（分数：2.00）A.10111B.10110111C.10111000 D.10110000解析：-0.1001=-0.1001000，将-0.1001000 连符号位在内取反加 1 即可得-0.1001000 的补码形式：1.0111000。21.下列排序算法中，时间复杂度为 O(nlog n)且占用额外空间最少的是( )。（分数：2.00）A.堆排序 B.
33、冒泡排序C.快速排序D.希尔排序解析：堆排序占用额外空间为 O(1)。22.在一个顺序循环队列中删除元素时，首先需要( )。（分数：2.00）A.前移队首指针B.后移队首指针 C.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素解析：23.中断向量表中保存的是( )。（分数：2.00）A.被中断程序的返回地址B.中断服务程序入口地址 C.中断服务程序入口地址的地址D.中断优先级解析：中断向量表中保存的是各中断服务程序的入口地址，CPU 响应中断时，由硬件生成中断向量(又称中断向量表指针)，CPU 通过访问该中断向量指出的主存单元就可得到中断服务程序入口地址。24.下列二叉排序树中，
34、满足平衡二叉树定义的是( )。（分数：2.00）A.B. C.D.解析：25.下列说法中错误的是( )。（分数：2.00）A.程序查询方式下，CPU 与 I/O 设备串行工作B.程序中断方式下，CPU 与 I/O 设备并行工作C.DMA 方式下，主程序可与 I/O 数据传送并行工作D.实现了 DMA 方式的系统中，程序中断方式没有存在的必要 解析：DMA 方式比较适合成块数据的 IO 传送，但在实现了 DMA 方式的系统中，DMA 传送结束时需要用中断方式来通知 CPU 进行后处理；当有紧急情况发生时，也需要中断方式来进行处理，故 D 错误。26.下列各选项是采用奇偶校验码编码的 ASCII
35、码，所有编码都未发生错误，采用偶校验的是( )。（分数：2.00）A.01001101 B.0011001C.10101101D.1101000解析：编码未发生错误，故编码中 1 的个数为偶数的就是采用偶校验编码的，只有 A 选项符合。27.某通讯线路每 20ms 采样一次，每一个信号共有 64 种不同的状态，那么这个线路的传输速率是( )。（分数：2.00）A.100bpsB.200bpsC.300bps D.400bps解析：300bps，每次采样可得到 6 比特，每秒采样 50 次，那么线路传输速率为 300bps。28.在( )的情况下，系统出现死锁。（分数：2.00）A.计算机系统发
36、生重大故障B.有多个封锁的进程同时存在C.若干进程因竞争资源而无休止地相互等待对方释放已占有的资源 D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数解析：本题考查死锁的概念。29.如下图所示一棵二叉排序，其不成功的平均查找长度为( )。（分数：2.00）A.21/7B.28/7 C.15/6D.21/6解析：不带数字的结点均为查找不成功的位置(如下图所示)，其平均查找长度为(3*2+4*3+5*2)7=287。30.如果 I/O 设备和存储设备之间的数据交换不经过 CPU 来完成，则这种交换方式是( )。（分数：2.00）A.程序查询方式B.中断方式C.DMA 方式 D.外部总线
37、方式解析：本题考查 DMA 方式。31.浮点运算结果满足下列哪个条件时，需做中断处理( )。（分数：2.00）A.尾数双符号位为“01”B.尾数双符号位为“10”C.阶码双符号位为“01” D.阶码双符号位为“10”解析：尾数双符号位为“01”或“10”时，说明尾数溢出，需要右规；阶码双符号位为“10”时，说明浮点数下溢，作机器零处理；阶码双符号位为“01”时，说明阶码上溢，需中断处理。32.如果对含有 n(n1)个元素的线性表的运算只有 4 种：删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后个元素的后面插入新元素，则最好使用( )。（分数：2.00）A.只有尾结点指针没
38、有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环单链表C.只有头结点指针没有尾结点指针的循环单链表 D.既有头结点指针也有尾结点指针的循环单链表解析：对于 A 的链表，删除最后一个结点 p 时，需要找到 p 的前一个结点，其时间复杂度为 O(n)；对于B 的链表，删除第一个结点的 p 时，需找到头结点，这里没给出头结点指针，故无法实现这种操作。对于C 的链表，这 4 种操作的时间复杂度都为 O(1)，对于 D 的链表，删除最后一个结点 p 时，需要找到 p 的前一个结点，其时间复杂度为 O(n)。33.一个 TCP 连接总是以 1KB 的最大段发送 TCP 段，发送方有足够多的
39、数据要发送。当拥塞窗口为 16KB 时发生了超时，如果接下来的 4 个 RTT(往返时间)时间内的 TCP 段的传输都是成功的，那么当第 4 个 RTT 时间内发送的所有 TCP 段都得到肯定应答时，拥塞窗口大小是( )。（分数：2.00）A.7KBB.8KBC.9KB D.16KB解析：在拥塞窗口为 16KB 时发生了超时，那么拥塞窗口就被设为 1KB，而阀值就被设为 8KB。在接下来的4 个成功的 TCP 段传输中，拥塞窗口先在前三次传输后安装指数增长到 8，而第四次成功传输后拥塞窗口只增长 1KB，所以最后大小是 9KB。34.对包含 n 个关键码的散列表进行检索，平均检索长度为( )。
40、（分数：2.00）A.O(log n)B.O(n)C.O(nlog n)D.不直接依赖于 n 解析：对散列表进行检索，平均检索长度仅与装填因子 a 有关，而与关键字个数 n 无关。35.下列只读存储器中，可编程且可以实现字擦除的是( )。（分数：2.00）A.掩模 ROMB.PROMC.EPROMD.EEPROM 解析：掩模 ROM 和 PROM 一旦写入就无法擦除；EPROM 擦除采用紫外线照射方式，只能实现全部擦除；EEPROM 可以使用电擦除，能够实现字擦除或者页擦除，选 D。36.如果二叉树 T2 是由有序树 T1 转换而来的二叉树，那么 T1 中结点的后序就是 T2 中结点的( )。
41、（分数：2.00）A.先序B.中序 C.后序D.层次序解析：一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为 B。37.一个分段存储管理系统中，地址长度为 32 位，其中段号占 8 位，则最大段长是( )。（分数：2.00）A.28字节B.216字节C.224字节 D.232字节解析：段内偏移为 24 位，所以最大长度为 224 字节。38.定点数采用模 4 补码，即变形补码进行加减运算时，判断溢出的方法是( )。（分数：2.00）A.符号位进位与最高数值位进位相异时表明溢出B.实际参与运算的两数符号位相同，结果又与原操作数符号不同
42、时表明溢出C.双符号位不同时表明溢出D.以上都正确 解析：采用模 4 补码进行加减运算时，直接通过判断双符号位是否相同来判断溢出最为方便。39.下列交换方式中，( )一次连接沿着一条路由路径发送所有的数据。（分数：2.00）A.分组交换B.报文交换C.电路交换 D.以上都不是解析：电路交换在数据传送之前需要建立一条物理通路，然后所有数据都沿着这条建立的通路发送。40.以下关于 UNIX 操作系统的叙述中，( )是错误的。（分数：2.00）A.UNIX 对实时系统是不合适的，因为进程在核心态不可抢占B.UNIX 终究会在市场上消失的 C.UNIX 是目前最流行的操作系统之一D.UNIX 比较适用
43、于高档计算机系统和网络环境，它不能用于普通的微机解析：UNIX 比较适用于大型机，市场上有它的位置，B 太片面了。二、B综合应用题/B(总题数：5，分数：70.00)41.设算术表达式由字符串 b 表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“( )( )”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。（分数：10.00）_正确答案：()解析：设 tag 为括号是否正确配对的标志，用 0 表示不正确的配对，1 表示正确的配对。另设一个栈 S。若当前处理字符为左括号，就将对应的右括号进栈。当遇到右括号时，直接与栈顶元素进行比较，若相等，则退栈；否则返
44、回不正确配对标志。当整个算术表达式检测完毕且栈为空时，表示括号正确配对，否则括号不正确配对。算法描述如下： #define MAX 1000 int JudgeExp(char*b) char SMAX; inti，top=0，tag=1； for(i=0；tag bi!=/0；i+) switch(bi) case(:stop+=);break; case:Stop+=;break; case:Stop+=; break; case): case: case: if(top=0 | bi!=S-top) tag=0； break： return top=0 tag bi=/0; 42.带权图
45、(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点； 选择离 u 最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点 u=v; 重复步骤，直到 u 是目标顶点时为止。 请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。（分数：15.00）_正确答案：()解析：该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从 A到 C 的最短路径为 ABC，事实上其最短路径为 ADC。43.某计算机字长 16 位，采用 16 位
