计算机专业(基础综合)模拟试卷11(题后含答案及解析)

计算机专业（基础综合）模拟试卷11 (题后含答案及解析)

题型有：1. 单项选择题 2. 综合应用题

单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1． 如果对含有n(n＞1)个元素的线性表的运算只有4种：删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用( )。

A．只有尾结点指针没有头结点指针的循环单链表 B．只有尾结点指针没有头结点指针的非循环单链表 C．只有头结点指针没有尾结点指针的循环单链表 D．既有头结点指针也有尾结点指针的循环单链表

正确答案：C

解析：对于A的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为O(n)；对于B的链表，删除第一个结点的p时，需找到头结点，这里没给出头结点指针，故无法实现这种操作。对于C的链表，这4种操作的时间复杂度都为O(1)，对于D的链表，删除最后一个结点p时，需要找到p的前一个结点，其时间复杂度为O(n)。

2． 在一个顺序循环队列中删除元素时，首先需要( )。 A．前移队首指针 B．后移队首指针

C．取出队首指针所指位置上的元素 D．取出队尾指针所指位置上的元素

正确答案：B

3． 如果二叉树T2是由有序树T1转换而来的二叉树，那么T1中结点的后序就是T2中结点的( )。

A．先序 B．中序 C．后序 D．层次序

正确答案：B 解析：一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为B。

4． 前序遍历和中序遍历结果相同的二叉树为( )。 A．根结点无左孩子的二叉树

B．根结点无右孩子的二叉树 C．所有结点只有左子树的二叉树 D．所有结点只有右子树的二叉树

正确答案：D

解析：前序遍历是根结点，左子树，右子树；中序遍历是左子树，根结点，右子树。易知，如果没有左子树，则两者相同。

5． 对包含n个关键码的散列表进行检索，平均检索长度为( )。 A．O(log n) B．O(n)

C．O(nlog n)

D．不直接依赖于n

正确答案：D

解析：对散列表进行检索，平均检索长度仅与装填因子a有关，而与关键字个数n无关。

6． A． B． C． D．

正确答案：B

7． A． B． C． D．

正确答案：B

8． 下面关于图的存储结构的叙述中正确的是( )。

A．用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关 B．用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点无关 C．用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关

D．用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关

正确答案：A

9． 下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。

A．冒泡排序 B．希尔排序

C．直接选择排序 D．直接插入排序

正确答案：C

解析：A、C每一趟都能选出一个元素放在最终位置上，但只有C是不稳定的。

10． 下列排序算法中，时间复杂度为O(nlog n)且占用额外空间最少的是( )。

A．堆排序 B．冒泡排序 C．快速排序 D．希尔排序

正确答案：A

11． 条件转移指令执行时所依据的条件来自( )。 A．指令寄存器IR B．程序计数器PC

C．程序状态字寄存器PSWR D．主存地址寄存器MAR

正确答案：C

解析：程序状态字寄存器PSWR用来保存根据运算结果设置的各种状态位，这些状态位可以被测试；条件转移指令正是通过测试这些状态位来决定是否跳转。

12． 某计算机字长8位，采用补码表示小数。若某数真值为-0．1001，则它在该计算机中的机器数形式为( )。

A．10111 B．10110111 C．10111000 D．10110000

正确答案：C

解析： -0．1001=-0．1001000，将-0．1001000连符号位在内取反加1即可

得-0．1001000的补码形式：1．0111000。

13． 定点数采用模4补码，即变形补码进行加减运算时，判断溢出的方法是( )。

A．符号位进位与最高数值位进位相异时表明溢出

B．实际参与运算的两数符号位相同，结果又与原操作数符号不同时表明溢出

C．双符号位不同时表明溢出 D．以上都正确

正确答案：D 解析：采用模4补码进行加减运算时，直接通过判断双符号位是否相同来判断溢出最为方便。

14． 浮点运算结果满足下列哪个条件时，需做中断处理( )。 A．尾数双符号位为“01” B．尾数双符号位为“10” C．阶码双符号位为“01” D．阶码双符号位为“10”

正确答案：C

解析：尾数双符号位为“01”或“10”时，说明尾数溢出，需要右规；阶码双符号位为“10”时，说明浮点数下溢，作机器零处理；阶码双符号位为“01”时，说明阶码上溢，需中断处理。

15． 下列各选项是采用奇偶校验码编码的ASCII码，所有编码都未发生错误，采用偶校验的是( )。

A．01001101 B．0011001 C．10101101 D．1101000

正确答案：A 解析：编码未发生错误，故编码中1的个数为偶数的就是采用偶校验编码的，只有A选项符合。

16． 下列只读存储器中，可编程且可以实现字擦除的是( )。 A．掩模ROM B．PROM C．EPROM D．EEPROM

正确答案：D

解析：掩模ROM和PROM一旦写入就无法擦除；EPROM擦除采用紫外线

照射方式，只能实现全部擦除；EEPROM可以使用电擦除，能够实现字擦除或者页擦除，选D。

17． 下列关于机器字长与指令字长的说法正确的是( )。 A．指令字长等于机器字长

B．指令字长一定是机器字长的整数倍 C．两者长度没有必然关系 D．以上说法都不对

正确答案：C 解析：指令字长取决于操作码的长度、操作数地址的长度和操作数地址的个数，与机器字长没有必然的联系；但为了硬件设计方便，指令字长一般取字节或存储字长的整数倍。

18． 某机器指令字长12位，有零地址、一地址、二地址三种指令，地址码长4位，采用扩展操作码技术。若二地址指令和一地址指令条数都取最大值，则该机指令条数最多为( )。

A．16 B．46 C．48 D．4 366

正确答案：B

解析：根据题意，二地址指令的操作码长度为12-4×2=4，留一个编码用于扩展，故最多可定义15条二地址指令；一地址指令扩展长度为4位，留一个编码用于扩展，故最多可定义15条一地址指令；零地址指令可在一地址指令的基础上扩展4位，故最多可定义16条零地址指令，根据题意，该机指令条数最多为(15+15+16=)46条。

19． 下列哪个选项不可能是微指令格式中的组成部分( )。 A．操作码字段 B．操作控制字段 C．外部条件字段 D．下地址字段

正确答案：A 解析：操作码字段是机器指令的组成部分，垂直型微指令中可能有微操作码字段，水平型微指令中无相应字段，故选A。

20． 某机中，设备号小的主设备在总线判优时具有较高的优先级，其总线判优方式可能是( )。

A．链式查询方式

B．计数器定时查询方式 C．独立请求方式

D．以上都有可能

正确答案：D

解析：三种集中仲裁方式都有可能，其实现方式分别为：链式请求方式下，将总线同意线上靠近仲裁中心的设备分配较小的设备号；计数器定时方式下，计数器从0开始计时；独立请求方式下，通过程序设置赋予设备号较少的主设备较高的优先级。

21． 中断向量表中保存的是( )。 A．被中断程序的返回地 B．中断服务程序入口地址

C．中断服务程序入口地址的地址 D．中断优先级

正确答案：B

解析：中断向量表中保存的是各中断服务程序的入口地址，CPU响应中断时，由硬件生成中断向量(又称中断向量表指针)，CPU通过访问该中断向量指出的主存单元就可得到中断服务程序入口地址。

22． 下列说法中错误的是( )。

A．程序查询方式下，CPU与I／O设备串行工作 B．程序中断方式下，CPU与I／O设备并行工作

C．DMA方式下，主程序可与I／O数据传送并行工作

D．实现了DMA方式的系统中，程序中断方式没有存在的必要

正确答案：D

解析：DMA方式比较适合成块数据的I／O传送，但在实现了DMA方式的系统中，DMA传送结束时需要用中断方式来通知CPU进行后处理；当有紧急情况发生时，也需要中断方式来进行处理，故D错误。

23． 为了保证操作系统本身的安全，( )是必须加以保护的。 A．从内核模式转换到用户模式

B．从存储操作系统内核的空间读取数据 C．从存储操作系统内核的空间读取指令 D．打开定时器

正确答案：D

解析：打开定时器会影响系统的时间。

24． 以下关于UNIX操作系统的叙述中，( )是错误的。 A．UNIX 对实时系统是不合适的，因为进程在核心态不可抢占 B．UNIX终究会在市场上消失的

C．UNIX是目前最流行的操作系统之一

D．UNIX 比较适用于高档计算机系统和网络环境，它不能用于普通的微机

正确答案：B

解析：UNIX比较适用于大型机，市场上有它的位置，B太片面了。

25． 关于临界区问题(critical section problem)是一个算法(假设只有进程P0和P1可能进入该临界区)，算法如下(i为0或1)，该算法( )。 repeat retry：if(turn≠-1)turn：=i； if(turn≠i)go to retry； turn：=-1； critical Section(临界区) turn=0； remainder Section(其他区域)until false；

A．不能保证进程互斥进入临界区，且会出现“饥饿”(Starvation) B．不能保证进程互斥进入临界区，但不会出现“饥饿” C．保证进程能互斥进入临界区，但会出现“饥饿” D．保证进程互斥进入临界区，不会出现“饥饿”

正确答案：A

解析：例如当PO执行完语句turn=-1；进入临界区时，CPU调度P1执行，P1顺利进入临界区，不能满足互斥。当P0执行完临界区时，CPU调度P1执行，P1在retry循环，CPU调度P0执行，P0继续执行，重复以上过程，会导致P1饥饿。

26． 系统功能调用是( )。 A．用户编写的一个子程序 B．高级语言中的库程序 C．操作系统中的一条命令

D．操作系统向用户提供的接口

正确答案：D

27． 在( )的情况下，系统出现死锁。 A．计算机系统发生重大故障 B．有多个封锁的进程同时存在

C．若干进程因竞争资源而无休止地相互等待对方释放已占有的资源 D．资源数大大小于进程数或进程同时申请的资源数大大超过资源总数

正确答案：C

28． 通常对文件系统来说，文件名及其属性可以集中在( )。 A．目录 B．索引 C．字典

D．作业控制块

正确答案：A

29． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最

大段长是( )。

A．28字节 B．216字节 C．224字节 D．232字节

正确答案：C

30． 如果I／O设备和存储设备之间的数据交换不经过CPU来完成，则这种交换方式是 ( )。

A．程序查询方式 B．中断方式 C．DMA方式 D．外部总线方式

正确答案：C

31． 假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，( )可能发生死锁。情况序号系统中进程数资源总量

A． 1 2 B． 2 1 C． 2 2 D． 2 3

正确答案：C

32．

A．进程A B．进程B

C．进程A和进程B同时 D．不一定

正确答案：A

33． 下列交换方式中，( )一次连接沿着一条路由路径发送所有的数据。 A．分组交换 B．报文交换 C．电路交换 D．以上都不是

正确答案：C 解析：电路交换在数据传送之前需要建立一条物理通路，然后所有数据都沿着这条建立的通路发送。

34． 某通讯线路每20 ms采样一次，每一个信号共有64种不同的状态，那么这个线路的传输速率是( )。

A．100 bps B．200 bps C．300 bps D．400 bps

正确答案：C

解析：300 bps，每次采样可得到6比特，每秒采样50次，那么线路传输速率为300 bps。

35． RS-232-C的电气特性规定逻辑“1”的电平范围为( )。 A．+5～+15 V B．-5～-15 V C．0～+5 V D．0～-5 V

正确答案：B

解析：RS-232-C关于电气信号特性的要求，规定逻辑“1”的电平为低于-3 V，为了表示一个逻辑1或MARK条件，驱动器必须提供-5 V～-15 V之间的电压；为了表示一个逻辑0或SPACE条件，驱动器必须给出+5 V～+15 V之间韵电压。

36． 一个16端口的二层以太网交换机，冲突域和广播域的个数分别是( )。

A．1，1 B．16，16 C．1，16 D．16，1

正确答案：D

解析：二层以太网交换机的每个端口都是冲突域的终止点，但LAN交换机不隔离广播，所以本题中，冲突域和广播域的个数分别是16和1。

37． 假定一台主机的IP地址是222．205．74．56，子网掩码为255．255．240．0，该子网地址为 ( )。

A．222．205．0．0 B．222．205．64．0 C．222．205．72．0 D．222．205．74．0

正确答案：B

解析：240的二进制表示是1111 0000，74的二进制表示是0100 1010，子网

地址的第3字节是二进制0100 0000，即64。

38． 以下( )协议完成了从网卡到IP地址的映射。 A．ARP协议 B．RARP协议 C．IGMP协议 D．ICMP协议

正确答案：A

解析：地址解析协议ARP用来在局域网上从目的IP地址得到目的MAC地址。

39． 一个TCP连接总是以1 KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16 KB时发生了超时，如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是( )。

A．7 KB B．8 KB C．9 KB D．16 KB

正确答案：C

解析：在拥塞窗口为16 KB时发生了超时，那么拥塞窗口就被设为1KB，而阀值就被设为8 KB。在接下来的4个成功的TCP段传输中，拥塞窗口先在前三次传输后安装指数增长到8，而第四次成功传输后拥塞窗口只增长1 KB，所以最后大小是9 KB。

40． 在HTTP协议中，一个以2开头的响应报文表示( )。 A．暂时性失败 B．永久性失败 C．重定向 D．成功

正确答案：D

解析：HTTP协议中以2开头的响应报文表示请求成功。

综合应用题41-47小题，共70分。

41． 在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(log n)的算法，确定树中第k个结点的位置。

正确答案：二叉排序树中第k个结点，即为二叉排序树中序序列中顺序号为k的结点，根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中

第k个结点，先需将k与根结点的顺序号进行比较，若相等，则找到；若k小于根结点的顺序号，k继续与根的左孩子结点的顺序号比较，依次类推。(注意，右孩子结点的顺序号等于根结点的顺序号与右孩子结点的Lsize域值之和。)由于查找过程中不超过树的高度，故其算法复杂度为O(log n)。 typedef struct Node{ int key； struct Node*lchild， *rchild； int Lsize }BSNode； BSNode* Locate(BSNode*T，int k) { int j，i=0； BSNode*p=T； while(p) { j=i+p-＞Lsize； if(j==k)return p；／／找到 if(j＞k)p=p-＞lchild； else{ i+=p-＞Lsize； p=p-＞rchild； } } return NULL；}

42．

正确答案：(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve(5)+1=16Ve(8)=ve(5)+4=19Ve(9)=max{ve(7)+5，ve(8)+2}=21Ve(10)=max{ve(6)+4，ve(9)+2}=23所有事件的最晚发生时间如下：Vl(10)=23Vl(9)=vl(10)-21VI(8)==vl(9)-2=19V1(7)=vl(9)-5=16Vl(6)=vl(10)-4=19Vl(5)=min{vl(7)-1，vl(8)-4)=15Vl(4)=rain{vl(6)-4，vl(5)-3}=12Vl(3)=rain{vl(4)-6，vl(5)-3)=6Vl(2)=vl(4)-3=9Vl(1)=min{vl(2)-5，vl(3)-6}=0因此，所有活动Ai的e( )，l( )，d( )如下：Al：e(1)=ve(1)=0，l(1)=vl(2)-5=4，d(1)=4A2：e(2)=ve(1)=0，l(2)=vl(3)-6=0，d(2)=0A3：e(3)=ve(2)=5，l(3)=vl(4)-3=8，d(3)=3A4：e(4)=ve(3)=6，l(4)=vl(4)-6=6，d(4)=0A5：e(5)=ve(3)=6，l(5)=vl(5)-3=12，d(5)=6A6：e(6)=ve(4)=12，1(6)=vl(5)-3=12，d(6)=0A7：e(7)=ve(4)=12，l(7)=vl(6)-4=15，d(7)=3A8：e(8)=ve(5)=15，l(8)=vl(7)-1=15，d(8)=0A9：e(9)=ve(5)=15，1(9)=vl(8)-4=15，d(9)=0A10：e(10)=ve(6)=16，l(10)=vl(9)-5=16，d(10)=0A11：e(11)=ve(7)=19，l(11)=vl(9)-2=19，d(10)=0A10：e(12)=ve(8)=16，l(12)=vl(10)-4=19，d(10)=3A10：e(13)=ve(9)=21，1(13)=vl(10)-2=21，d(10)=0 (2)完成此工程最少需要23天。 (3)从以上计算可知，关键活动为a2，a4，a6，a8，a9，a10，a11，a13。这些活动构成两条关键路径即：a2，a4，a6，a8，a10，a13和a2，a4，a6，a9，a11，a13。 (4)存在a2，a4，a6，a13活动，当其提高速度后能使整个工程缩短工期

43． 某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现该外设需要把一个非常大的数据块传送到内存。 (1)如果采用程序I／O方式，每传送一32位字宽的数据需要CPU执行2条指令。请计算最大数据传输率(单位：字／秒)。 (2)如果采用DMA方式，在DMA与CPU出现总线访问冲突时，CPU优先。请计算最大数据传输率(单位：字／秒)。

正确答案：(1)数据块非常大，可认为其执行时间远远大于1 s，故可用其1 s内的最大数据传输率来近似表示其整个传输过程中的最大数据传输率，(2)同

CPU每秒执行100条指令，且95％的时间内持续执行背景程序，故1 s内CPU可用来进行I／O传送的指令条数为 100×(1-95％)=5(条) 最大数据传输率为 5／2=2．5(字／秒) (2)CPU每秒内共有(100×5=)500个机器周期，其中执行“背景程序”时有(100×95％×3=)285个机器周期必须访问内存，由于DMA与CPU访存冲突时，CPU优先，故DMA控制器只能在余下的500-285=215个机器周期内访存；又内存读写需要一个机器周期，故采用DMA传输方式时，1s内可读写内存215次，即最大数据传输率为215字／秒。

44． 下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑，分取指周期、取第一操作数周期，取第二操作数周期、执行周期四个机器周期，每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADD R0，(R1) 完成功能(R0)+((R1))→R0

正确答案：各机器周期的微操作命令及节拍安排如下。 (1)取指周期 T0：PC→总线→MAR→主存，微操作命令形成部件发读信号到主存 T1：M(MAR)→MDR，微操作命令形成部件发+1信号到PC T2：MDR→总线→IR，OP(IR)→微操作命令形成部件 (2)取第一操作数周期 T0：R0总线→FIRST T1： T2： (3)取第二操作数周期 T0：R1→总线→MAR→主存，微操作命令形成部件发读信号到主存 T1：M(MAR)→MDR T2：MDR→总线→SECOND (4)执行周期 T0：FIRST→总线→YT1：微操作命令形成部件发Add信号到ALU，(Y)+(SECOND)→ALU→Z T2：Z→总线→R0

45． 设有一缓冲池P，P中含有10个可用缓冲区，一个输入进程将外部数据读入P，另有一个输出进程将P中数据取出并输出(如下图所示)。若进程每次操作均以一个缓冲区为单位，试用记录型信号量写出两个进程的同步算法，要求写出信号量的设置。 输入进程 输出进程 L：读入数据 L：从一满缓冲区中取出数据 将数据写入一空缓冲区 将数据输出 GnTOL GOTOL

正确答案：(1)设置信号量mutex，empty，full 初值，mutex=1，empty=10，full=0 (2)设置wait，signal操作如下。 输入进程 输出进程 L：读入数据 L：wait(full) wait(empty) wait(mutex) wait(mutex) 从一满缓冲区中取出数据 将数据写入一空缓冲区 signal(mutex) signal(mutex) signal(empty) signal(full) 将数据输出

46． 处理一次缺页的平均时间为108 ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设：①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表(忽略访问页表之后的TLB更新时间)；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问： (1)依次访问上述三个虚地址，各需多少时间?给出计算过程。 (2)基于上述访问序列，虚地址1565H的物理地址是多少?请说明理由。

正确答案：(1)根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4 KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下(十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号)：2362H：P=2，访问快表10 ns，因初始为空，访问页表100 ns得到页框号，合成物理地址后访问主存100 ns，共计10 ns+100 ns+100 ns=210 ns。1565H：P=1，访问快表10 ns，落空，访问页表100 ns落空，进行缺页中断处理108 ns，合成物理地址后访问主存100 ns，共计10 ns+100 ns+108 ns+100 ns≈318 ns。25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10 ns便可合成物理地址，访问主存100 ns，共计10 ns+100 ns=110 ns。(2)当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。

47．

正确答案：(1)根据无类IP地址的规则，每个网段中有两个地址是不分配的：主机号全0表示网络地址，主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2，即254台。该网络要划分为两个子网，每个子网要120台主机，因此主机位数X应该满足下面三个条件： X＜8，因为是在主机号位长为8位的网络进行划分，所以X一定要小于8位。2x＞120，因为根据题意需要容纳120台主机。X是整数。 解上述方程，得到X=7，子网掩码就是11111111 11111111 11111111 10000000， 即255．255．255．128。所以划分的两个网段是：202．118．1．0／25与202．118．1．128／25。(2)填写的路由表如下：(3)局域网1和局域网2的地址可以聚合为202．118．1．0／24，而R2去往局域网1和局域网2都是同一条路径。因此，路由表里面只需要填写到202．118．1．0／24网络的路由即可，如下表所示：