1、计算机专业（基础综合）模拟试卷 2 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在顺序表中删除一个元素的时间复杂度为( )。（A）O(1)（B） O(log n)（C） O(n)（D）O(n 2)2 设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是( )。（A）1（B） 2（C） 3（D）43 设 A 是一个已有 10 个元素的栈，栈中依次是 A1，A2，A10，栈顶是A10；
2、B 是一个已有 10 个元素的循环队列，队列中元素依次为B1，B2， ，B10，队头元素为 B1。A、B 均采用顺序结构，现要将栈中元素全部移入队列中，需( ) 次基本操作才能使得队列中元素与栈中元素交替排列，即 B中排列后的元素为 B1，A1，B2，A2，B10，A10。(不必考虑存储空间)（A）100（B） 1 000（C） 50（D）204 设高度为 H 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为( ) 。（A）2*H（B） 2*H-1（C） 2*H+1（D）H+15 设有 13 个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有( )个结点。（A）13（
3、B） 12（C） 26（D）256 已知 10 个数据元素为(54，28，16，34，73，62，95，60，23，43)，按照依次插入结点的方法生成一棵二叉排序树后，查找值为 62 的结点所需比较的次数为( )。（A）2（B） 3（C） 4（D）57 当向一棵 m 阶的 B 一树做插入操作时，若一个结点中的关键字个数等于( ) ，则必须分裂成两个结点，当向一棵 m 阶的 B-树做删除操作时，若一个结点中的关键字个数等于( ) ，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。（A）m，m2-2（B） m-1，m2-1（C） m+1，m2（D）m2，m2+18 下面关于 Prim 算法和 K
4、ruskal 算法的时间复杂度正确的是 ( )。（A）Prim 算法的时间复杂度与网中的边数有关，适合于稀疏图（B） Prim 算法的时间复杂度与网中的边数无关，适合于稠密图（C） Kruskal 算法的时间复杂度与网中的边数有关，适合于稠密图（D）Kruskal 算法的时间复杂度与网中的边数无关，适合于稀疏图9 数据序列 F=2，1，4， 9，8，10，6，20)只能是下列排序算法中的 ( )的两趟排序后的结果。（A）快速排序（B）冒泡排序（C）选择排序（D）插入排序10 在含有 n 个关键字的大顶堆中，关键字最小的记录有可能存储在( )位置上。（A）n2（B） n2-1（C） 1（D）n2
5、+211 冯.诺依曼机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是( )。（A）指令操作码的译码结果（B）指令和数据的寻址方式（C）指令周期的不同阶段（D）指令和数据所在的存储单元12 IEEE754 标准浮点数的尾数采用( )机器数形式。（A）原码（B）补码（C）移码（D）反码13 字长 16 位的补码定点小数的表示范围是( )。（A）01-2 -15（B） -(1-2-15)1-2 -15（C） -11-2 -15（D）-1 114 补码定点小数除法中，被除数和除数应满足( )。（A）0被除数除数（B） 0被除数除数（C） 0除数被除数（D）0被除数除数15 某机器采
6、用四体低位交叉存储器，现分别执行下述操作：(1)读取 6 个连续地址单元中存放的存储字，重复 80 次；(2)读取 8 个连续地址单元中存放的存储字，重复 60 次。则(1)、(2) 所花时间之比为 ( )。（A）1：1（B） 2：1（C） 4：3（D）3：416 下列说法中错误的是( )。（A）虚拟存储器的引入主要是为了解决主存容量的问题（B）虚拟存储器通过页表来实现虚实地址的映射（C）虚拟存储器是一个容量很大的逻辑模型，不是任何实际的存储器（D）虚拟存储器完全由硬件实现17 在指令格式中，采用扩展操作码设计方案的目的是( )。（A）缩短指令字长（B）增加指令字长（C）保持指令字长不变的基础
7、上增加指令数量（D）保持指令字长不变的基础上扩大指令寻址空间18 磁盘的平均存取时间是指平均寻道时间和平均等待时间之和。若磁盘的转速提高一倍，则( ) 。（A）平均存取时间减半（B）平均寻道时间减半（C）平均等待时间减半（D）以上都正确19 下列说法正确的是( ) 。（A）取指周期一定等于机器周期（B）指令字长等于机器字长的前提下，取指周期等于机器周期（C）指令字长等于存储字长的前提下，取指周期等于机器周期（D）取指周期与机器周期没有必然联系20 下列说法中正确的是( )。（A）微处理器的程序称为微程序（B）微指令控制器的执行速度比硬布线控制器快（C）存放微程序的控制存储器可用 ROM 或 E
8、PROM 来实现（D）在微程序控制器中，微指令使用机器指令来解释执行21 同步通信比异步通信数据传输率高的原因是( )。（A）同步通信不需要应答信号（B）同步通信使用公共时钟进行同步（C）同步通信中，通信双方的速度相近（D）以上都包括22 CPU 在中断周期要完成的任务不包括( )。（A）保护断点（B）关中断（C）保护现场（D）向量地址送 PC23 实时系统中的进程调度，通常采用( )算法。（A）先来先服务（B）时间片轮转（C）抢占式的优先数高者优先（D）响应比高者优先24 进程由就绪态转换为运行态是由( )引起的。（A）中断事件（B）进程状态转换（C）进程调度（D）为程序创建进程25 以下(
9、 ) 不是产生死锁的原因。（A）资源共享（B）并发执行的进程数太多（C）系统资源不足（D）进程推荐顺序非法26 把程序地址空间中使用的逻辑地址变成内存中物理地址称为( )。（A）加载（B）物理化（C）重定位（D）逻辑化27 下面关于虚拟存储器的论述中，正确的是( )。（A）在段式系统中以段为单位管理用户的逻辑空间，以页为单位管理内存的物理空间；有了虚拟存储器才允许用户使用比内存更大的地址空间（B）为了提高请求分页系统中内存的利用率，允许用户使用不同大小的页面（C）为了能让更多的作业同时运行，通常只装入 1030的作业即启动运行（D）最佳适应算法是实现虚拟存储器的常用算法28 在下列文件的物理结
10、构中，( )不利于文件长度的动态增长。（A）连续结构（B）链接结构（C）索引结构（D）哈希结构29 设文件 F1 的当前引用计数值为 1，先建立 F1 的符号链接(软链接)文件 F2，再建 F1 的硬链接文件 F3，然后删除 F1。此时，F2 和 F3 的引用计数值分别是( )。（A）0、1（B） 1、1（C） 1、2（D）2、130 如果 IO 设备与存储设备间的数据交换不经过 CPU 来完成，则这种数据交换方式是( ) 。（A）程序查询方式（B）中断方式（C） DMA 方式（D）无条件存取方式31 驱动调度算法中，( )算法可能会随时改变移动臂的运动方向。（A）电梯调度（B）最短寻找时间优
11、先（C）扫描（D）单向扫描32 某虚存系统有 3 页初始为空的页框，若采用先进先出的页面淘汰算法，则在下列的页面需求提出时，会产生( )次缺页中断? 设页面走向为：4 3 2 1 4 3 5 4 3 2 1 5。（A）7（B） 8（C） 9（D）1033 传输线上的位流信号同步，应该属于下列 OSI 的( )层处理。（A）物理层（B）数据链路层（C）网络层（D）传输层34 测得一个以太网数据的波特率是 40 Mbps，那么其数据率是( )。（A）10 Mbps（B） 20 Mbps（C） 40 Mbps（D）80 Mbps35 数据链路层采用了后退 N 帧(GBN)协议，发送方已经发送了编号为
12、 07 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是( )。（A）2（B） 3（C） 4（D）536 一个 C 类地址，采用了 255255255240 作为子网掩码，那么这个 C 类地址可以划分为( ) 个子网。（A）16（B） 32（C） 64（D）12837 下列地址中，不属于多播地址的是( )。（A）22518912343（B） 239146889（C） 240322212（D）2240025538 下列的网络协议中，( )的运输层协议是使用 TCP 的。（A）TFTP（B） DNS（C） RIP（D）TELNEI 、39 一个 FTP 的用户
13、，发送了 LIS27、命令来获取服务器的文件列表，这时候服务器应该通过( ) 端口来传输该列表。（A）21（B） 20（C） 22（D）1940 UDP 的报文头部不包括( )。（A）目的地址（B）报文长度（C）目的 UDP 端 H（D）源 UDP 端口二、综合应用题41-47 小题，共 70 分。41 42 给定集合 S=0，1，2 ，3，4)，以及优先关系 R=01，14，12，23，24，40)。(1)R 是偏序关系吗?(2)证明你的结论。43 下图所示为双总线结构机器的数据通路，IR 为指令寄存器，PC 为程序计数器(具有自增功能) ，M 为主存(受 RW 信号控制) ，AR 为地址寄
14、存器，DR 为数据缓冲寄存器，ALU 由加、减控制信号决定完成何种操作，控制信号 G 控制的是一个门电路。另外，线上标注有小圈表示有控制信号，例中 yi 表示 y 寄存器的输入控制信号，R1 o 为寄存器 R1 的输出控制信号，未标字符的线为直通线，不受控制。 (1)“ADD R2，R0”指令完成(R0)+(R2)R0 的功能操作，画出其指令周期流程图，假设该指令的地址已放入 PC 中。并列出相应的微操作控制信号序列。 (2)若将“取指周期”缩短为一个 CPU 周期，请先画出修改数据通路，后画出指令周期流程图。 (3)在(2)的基础上，将“执行周期”也缩短为一个 CPU 周期，先修改运算器数据
15、通路，后画出指令周期流程图。此时加法指令速度比(1)提高几倍?44 有两部计算机 M1 和 M2，指令系统相同。它们的操作频率频率分别是 400 MHz 和 200 MHz。指令分成 A、B 和 C 三类，在 M1 上执行分别需 4、6 和 8 个周期；在 M2 上执行分别需 2、4 和 3 个周期。现有一程序在两机器上执行，其中A、B 和 C 三类指令依次占 30、50和 20。请问哪一部机器较快完成，快几倍?45 某会议有 n 个参与者，等大家到齐后会议才能开始，利用 P、V 原语操作实现会议参与者进程。46 完成以下各小题。(1)什么是 Belady 现象?为什么会产生这种现象?(2)页
16、面置换算法 FIFO 为什么会出现 Belady 现象?简述理由。(3)页面置换算法 LRU 为什么不会出现 Belady 现象? 简述理由。47 假定 A 和 B 是试图在一个以太网上发送的两个站。每个站都有一个稳定的帧的队列准备发送，A 的帧编号是 A1，A2 和 A3 等，B 的帧编号是 B1，B2 和 B3 等。再假定指数后退的基本单元时间是 T=512 微秒。现在 A 和 B 同时尝试发送 1 号帧，碰撞，并且刚好分别选择了 0T 和 1T 的退避时间，也就是说，A 赢得了这一次竞争，发送 A1，B 需要等待。在这次传送结束时，B 尝试再发送 B1，而 A 则尝试发送 A2。这一轮的
17、首次尝试产生碰撞，此时，A 的退避时间从 0T 和 1T 中选择，而 B 则从 0T，3T 中选择。(1)给出 A 赢得第 2 次退避竞争的概率。(2)假定 A 已赢得了第 2 次退避竞争。A 在成功发送 A2 后，接着尝试发送 A3。当 B 再次尝试发送 B1 时，A 和 B 再次碰撞。给出 A 赢得这第 3 次退避竞争的概率。(3)给出 A 赢得所有其余后退竞争的概率的合理下限值。计算机专业（基础综合）模拟试卷 2 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 删除顺序表中第
18、 i 个元素，将顺序表第 i 个元素以后元素均向前移动一个位置。因此时间复杂度为 O(n)。2 【正确答案】 C3 【正确答案】 A【试题解析】 操作如下：(1)先将栈中所有元素出栈(10 次) ，入队列(10 次 )，栈为空，队列中的元素为B1，B2， ，B10，A10 ，A9，A1；(2)将 B1，B2，B3，B10 出队列(10 次)，人队列(10 次)，则队列变为A10，A2，A1，B1，B2，B10；(3)将 A10， A9，A1 出队列(10 次)，入栈(10 次)，栈中自栈底至栈顶依次为A10，A3，A2，A1，队列中剩下 B1，B2，B10；(4)重复执行 10 次 Bi 出队
19、列(1 次)，入队列(1 次)，Ai 出栈(1 次)，入队(1 次)，则最终得到 B1，A1，B2，A2，B10，A10。4 【正确答案】 B5 【正确答案】 D【试题解析】 具有 n 个叶子结点的哈夫曼树共有 2*n-1 个结点。6 【正确答案】 B【试题解析】 参考二叉排序树的建立。将这 10 个元素按照依次插入结点的方法生成一棵二叉排序树后，62 位于这棵二叉排序树的第三层，查找值为 62 的结点所需要的次数恰好是从二叉排序树的根到被查结点的树的深度。7 【正确答案】 A【试题解析】 参见 B-树基本插入与删除操作。8 【正确答案】 B【试题解析】 Prim 算法的时间复杂度为 O(n2
20、)，与网中的边数无关，适合于稠密图；而 Kruskal 的算法复杂度为 O(elog e)，与网中的边数有关，适合于稀疏图。9 【正确答案】 A【试题解析】 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列不满足。10 【正确答案】 D【试题解析】 大顶堆中关键字最小的记录只能在叶子结点上，不可能在小于或等于 n2 的结点上。11 【正确答案】 C【试题解析】 冯.诺依曼机中根据指令周期的不同阶段来区分从存储器取出的是指令还是数据：取指周期取出的是指令；执行周期取出的是数据。此外，也可根据取数和取指令时的地址来源不同来区分：指令地址来源于程序计数器 PC
21、；数据地址来源于地址形成部件。12 【正确答案】 A【试题解析】 IEEE754 标准浮点数的尾数采用原码表示，选 A。13 【正确答案】 C【试题解析】 表示定点小数时，补码可比原码、反码多表示一个-1，选 C。14 【正确答案】 B【试题解析】 n 位补码定点小数的表示范围是 -1 1-2-(n-1)，故被除数的绝对值应小于等于除数的绝对值，否则结果会溢出；此外应避免被除数为 0，因为此时结果一定为 0，这个除法没有意义，浪费了机器时间。15 【正确答案】 C【试题解析】 假设存储器的存取周期为 T，(1)的情况下，连续读取 6 个存储字需时 T+(6-1)(T4)=225T，但存放连续字
22、中第一个字的存储器需到 3T 时间后才能进行下一轮读取，故(1)共需时 3T(80-1)+225T=23975T；(2) 的情况同理，一轮读取需时 T+(8-1)(T4)=275T，但开始下一轮读取需 3T 时间后，故(2)共需时 3T(60-1)+275T=17975T ；综合上述分析，(1)、(2) 所花时间之比约为4：3。16 【正确答案】 D【试题解析】 虚拟存储器的实现需要软硬件的共同支持，D 为错误选项。17 【正确答案】 C【试题解析】 扩展操作码技术使操作码的长度随着地址码个数的减少而增加，从而在保持指令字长不变的基础上增加指令数量。18 【正确答案】 C【试题解析】 磁盘平均
23、等待时间一磁盘旋转一周所需时间2 一(1转速)2；故磁盘转速提高一倍，平均等待时间减半；但平均寻道时间与磁盘转速无关。故选C。19 【正确答案】 C【试题解析】 指令字长一般取存储字长的整数倍，当指令字长等于存储字长时，取指周期可看作机器周期。20 【正确答案】 C【试题解析】 A 选项所述显然错误；机器指令使用微指令构成的微程序来解释执行，D 错误；硬布线控制器的速度要比微程序控制器快， B 错误；微程序控制器根据其指令是否可以修改，分为静态微程序控制器和动态微程序控制器，分别可用ROM、EPROM 来实现。故 C 为正确选项。21 【正确答案】 D【试题解析】 A、B、C 三个选项都是同步
24、通信数据传输率高于异步通信的原因，同步通信比异步通信数据传输率高正是这些原因综合作用的结果。22 【正确答案】 C【试题解析】 保护现场包括保护断点和保护 CPU 内其他相关寄存器的内容，其中包括断点的任务在中断周期由中断隐指令完成，保护其他寄存器内容的任务由中断服务程序完成，而不是在中断周期由中断隐指令完成，选 C。23 【正确答案】 C【试题解析】 实时系统为了满足用户实时交互以及对重要事件的迅速反应，所以采取抢占式的优先数高者优先。24 【正确答案】 C【试题解析】 进程由就绪态转换为运行态是由进程调度引起的。25 【正确答案】 B【试题解析】 A、C、D 都是产生死锁的原因，死锁与进程
25、数的太多无关。26 【正确答案】 C27 【正确答案】 C28 【正确答案】 A【试题解析】 连续结构不适合删除和插入操作，即不利于文件的动态增长。29 【正确答案】 B【试题解析】 建立链接时，文件的引用数值相当于复制。30 【正确答案】 C【试题解析】 在 DMA(直接内存存储) 控制器控制下，外设直接与内存交换成批数据而不用 CPU 干预。故选 C。31 【正确答案】 B【试题解析】 最短寻找时间优先可能根据新的请求做出方向改变。32 【正确答案】 C【试题解析】 本题考查对在先进先出的淘汰算法缺页中断是如何发生的。33 【正确答案】 A【试题解析】 物理层涉及在通信信道上传输的原始数据
26、位，在设计时需要保证传输线上的位流同步。34 【正确答案】 B【试题解析】 以太网采用了曼彻斯特编码，意味着每发送一位就需要两个信号周期，那么波特率就是数据率的两倍，即波特率为 40 Mbps、数据率为 20 Mbps。35 【正确答案】 C【试题解析】 根据后退 N 帧协议，接收方的窗口为 “1”，如果发送方收到了 3 号帧的确认，则说明 O、1、2、3 号帧都已经发送成功，所以只需要重发4、5、6、7 号帧即可。36 【正确答案】 A【试题解析】 先将子网掩码转换成二进制得到 1111 11111111 11111111 11111111000。C 类的主机号是 8 位的，现在用高 4 位
27、来表示子网，因此可以得到 16 个子网。37 【正确答案】 C【试题解析】 多播地址的格式是 1110+28 位的多播地址。用 10 进制点分范围表示是 224000 到 239255255255。所以选项 C 不在这个范围之内。38 【正确答案】 D【试题解析】 其他三项都是使用 UDP 来传输的，只有 TELNET 是使用 TCP 的。39 【正确答案】 B【试题解析】 FTP 中数据传输端口是 20，而文件的列表是通过数据连接来传输的。40 【正确答案】 A【试题解析】 UDP 是传输层的协议，不需要包括目的地址，寻址是网络层的功能。二、综合应用题41-47 小题，共 70 分。41 【
28、正确答案】 link NODE(int item，link 1，link r)lnik t=malloc(sizeof*t)；t-item=item；t-1=1；t-r=r；return t；link max(int a，int 1，int r)int m=(1+r)2；int u，v；link x=NODE(am，NULL，NULL)；x- 1=max(a，1，m) ；x-r=max(a，m+1，r)；u=x-1- item；v=x- r-item；if(uv)x-item=u；else x-item=v；return x；42 【正确答案】 43 【正确答案】 44 【正确答案】 设程序的
29、指令条数为 s 指令周期： M1：10 9ns400 M=25 ns、M2：10 9ns200 M=5 ns。 CPl ： 一条指令的平均周期为： M1：4*03+6*0 5+8*0 2=58、M2：2*03+4*05+3*02=32。 执行时间(设程序共有 S 条指令)： M1：S*58*25=14 5 S M2：S*3 2*5=16 S M1 机器较快完成。n=16/14.5=11，故 m1 较 m245 【正确答案】 semaphore mutex=1semaphore barrier=0；int meetings=0；void meeting()P(mutex)；meetings+；V
30、(mutex)；if(meetings=n)V(barrler)；P(barrier)；V(barrier)；begin_meeting()；46 【正确答案】 分述如下：(1)如果某种换页算法，在增加页框数之后反而可能导致更多缺页，这种反常情形称为 Belady 现象。(2)FIFO 换页策略将最早换入页框的页面换出，而不考虑该页面是否最近使用过，这违背了局部性原理。当页框数较大时，由于包含的页面更多，历史记录更全面，就有可能使最近频繁使用但较早进入页框的页面被换出，从而出现 Belady 异常。(3)LRU 换页策略将最近最长时间未使用的页面换出，符合局部性原理。当页框数较大时，最近最长未
31、使用的情况更全面，因此缺页数不会增加。47 【正确答案】 (1)A 可以选择 KA=0 或 1；B 可以选择 KB=0，1，2，3。如果(KA，KB)选择(0 ，1)，(0，2)，(0，3)，(1，2)，(1，3)中的一个组合，那么将是A 赢得这第 2 次竞争，其概率是 58。(2)现在 A 是在一次成功发送之后，可以选择 KA=0 或 1；KB 是在它的第 3 次碰撞之后，可能的选择是 0，1，2，7。如果 KA=0，那么 KB 中有 7 种选择使得A 赢；如果 KA=1，那么 KB 中有 6 种选择使得 A 赢。所以 A 赢得这第 3 次竞争的概率是 1316。(3)A 赢得第 2 次竞争的概率 =5812A 赢得第 3 次竞争的概率=131634类似地，A 赢得第 4 次竞争的概率78一般地，A 赢得第 i 次竞争的概率(1-12i-1)因此，假定 A 已经赢得第 1 至第 3 次竞争，那么 A 赢得所有其余的后退竞争的概率将不低于：(1-18)(1-116)(1-132)(1-164)1-18-116-132-164-=6 8=3 4
