1、计算机专业（基础综合）模拟试卷 15 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下面说法错误的是( ) 。(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低（A）-1（B） (1)，(2)（C） (1)，(4)（D） -32 若线性表最常用的运算是查找第 i 个元素及其前驱的值，则采用 ( )存储方式
2、节省时间。（A）单链表（B）双链表（C）单循环链表（D）顺序表3 设计一个判别表达式中左右括号是否配对出现的算法，采用( )数据结构最佳。（A）顺序表（B）队列（C）链表（D）栈4 设 n 阶方阵是一个上三角矩阵，则需存储的元素个数为( )。（A）n（B） nn（C） nn2（D）n(n+1) 25 在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，采用三叉链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节，若采用顺序存储，最后一个结点下标为 k(起始下标为 1)，那么( )时
3、采用顺序存储更节省空间。（A）d12n(k-n)（B） d12n(k-n)（C） d12n(k+n)（D）d12n(k+n)6 中缀表达式 A-(B+CD)*E 的后缀形式是( )。（A）AB-C+D E*（B） ABC+D-E*（C） ABCDE*+-（D）ABCD+E*-7 有 m 个叶子结点的哈夫曼树所具有的结点数为( )。（A）m（B） m+1（C） 2m（D）2m-18 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其邻接矩阵为 A1n，1n，且压缩存储在 B1k，则 k 的值至少为( )。（A）n(n+1) 2（B） n22（C） (n-1)(n
4、+1)2（D）n(n-1)29 设顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为( )。（A）21（B） 23（C） 41（D）6210 快速排序最易发挥其长处的情况是( )。（A）被排序的数据中含有多个相同排序码（B）被排序的数据已基本有序（C）被排序的数据完全无序（D）被排序的数据中的最大值和最小值相差悬殊11 在机器数中，正数的符号位用“1” 表示的是( ) 。（A）原码（B）补码（C）反码（D）移码12 IEEE 754 标准规定的 64
5、位浮点数格式中，符号位为 1 位，阶码为 11 位，尾数为 52 位。则它所能表示的最小规格化负数为( )。（A） -(2-2 52)2-1023（B） -(2-2-52)2+1023（C） -12-1024（D） -(1-2 52)2+204713 按其数据流的传递过程和控制节拍来看，阵列乘法器可认为是( )。（A）全串行运算的乘法器（B）全并行运算的乘法器（C）串一并行运算的乘法器（D）并啊一串行运算的乘法器14 字长相同的两种浮点数，第一种阶码位数较多，尾数位数少，第二种阶码位数少，尾数位数多，阶的底数都是 2，则( )。（A）表示的数的范围与精度相同（B）第一种数的范围大，但精度低（C
6、）第二种数的范围大，精度高（D）第一种数的范围大，精度高15 4 片 74181ALU 和 1 片 74182CLA 器件相配合，具有( )进位传递功能。（A）串行进位（B）组内并行进位，组间并行进位（C）组内并行进位，组间串行进位（D）组内串行进位，组间并行进位16 需要刷新的存储器是( )。（A）SRAM（B） DRAM（C） ROM（D）上述三种17 双端口存储器在( ) 情况下会发生读写冲突。（A）左端口与右端口的地址码不同（B）左端口与右端口的地址码相同（C）左端口与右端口的数据码相同（D）左端口与右端口的数据码不同18 操作数地址存放在寄存器的寻址方式叫( )。（A）相对寻址方式（
7、B）变址寄存器寻址方式（C）寄存器寻址方式（D）寄存器间接寻址方式19 在微程序控制中，机器指令和微指令的关系是( )。（A）每一条机器指令由一条微指令解释执行（B）每一条机器指令由一段微程序解释执行（C）每一条微指令由一条机器指令解释执行（D）每一段微程序由若干条机器指令解释执行20 直接映射 Cache 的主要优点是实现简单。这种方式的主要缺点是( )。（A）它比其他几利 Cache 组织类型更贵（B）如果使用中的 2 个或多个 block 映射到 Cache 的同一行，命中率将下降（C）它的存取时间大于其他类型（D）Cache 中的 Block 数随着主存的容量线性增加21 由于 CPU
8、 内部的操作速度较快，而 CPU 访问一次主存所花的时间较长，因此机器周期通常用( ) 来规定。（A）主存中读取一个指令字的最短时间（B）主存中读取一个数据字的最长时间（C）主存中写入一个数据字的平均时间（D）主存中取一个数据字的平均时间22 DMA 方式是在( )之间建立直接的数据通路。（A）CPU 与外部设备（B）外部设备与外部设备（C）主存与外部设备（D）主存与外部设备23 在设计实时操作系统中，首先要考虑的是( )。（A）灵活性和可靠性（B）实时性和可靠性（C）交互性和实时性（D）资源利用率24 ( )进程调度算法综合考虑到了 CPU 密集型进程和 IO 密集型进程。（A）时间片轮转（
9、B）优先级（C）多重队列（D）彩票25 信号量 S 的初值定义为 5，在 S 上调用了 10 次 wait 操作和 8 次 signal 操作后，S 的值应为( )。（A）2（B） 3（C） 7（D）1326 临界区是指并发进程中访问共享变量的( )段。（A）管理信息（B）信息存储（C）数据（D）程序27 死锁的预防是通过破坏产生死锁的四个必要条件来实现的。下列方法中，破坏了“循环等待 ”条件的是( )。（A）资源按序分配策略（B）银行家算法（C）一次性分配资源策略（D）资源分配图化简法28 系统“抖动 ”现象的发生是由 ( )引起的。（A）置换算法选择不当（B）交换的信息量过大（C）内存容量
10、不足（D）请求页式管理方案29 两个进程 P、Q 都需要三个资源 1，2，3，系统中有资源 1、2、3 各一个，如果 P 请求资源的顺序是 1、2、3，Q 请求资源的顺序任意，共有 3!=6 种排列，其中共有( ) 个排列可能导致死锁。（A）3（B） 4（C） 5（D）630 对于三级文件目录，若主目录、用户目录及子目录各级分别最多有 3、4、5 个目录项，则为找到一指定文件的目录项(绝对路径名方式)，最多只需检索的目录项数是( )。（A）12 个（B） 17 个（C） 23 个（D）60 个31 在文件系统中，文件的不同物理结构有不同的优缺点。在下列文件的物理结构中，( )具有直接读写文件任
11、意一个记录的能力，又提高了文件存储空间的利用率。（A）顺序结构（B）链接结构（C） Hash 结构（D）索引结构32 启动磁盘执行一次输入输出操作时，( )是硬件设计时就固定的。（A）寻找时间（B）传送时间（C）延迟时间（D）一次 IO 操作的总时间33 在网络中计算机接收的信号是( )。（A）数字信号（B）模拟信号（C）广播信号（D）脉冲信号34 通常通信信道的带宽越大，在数据传输中失真将会( )。（A）严重（B）不变（C）越大（D）越小35 在共享介质的以太网中，采用的介质访问控制方法是( )。（A）并发连接（B） CSMACD（C）时间片（D）令牌36 IP 层的功能不包括( )。（A）
12、差错处理（B）数据报路由选择（C）无连接的数据报传输（D）提供可靠连接37 路由器在 ISOOSI 开放系统参考模型中对应于( )。（A）物理层（B）数据链路层（C）网络层（D）表示层38 TCP 使用 ( )机制来进行流量控制。（A）三次握手（B）二次握手（C） Windows 窗口（D）滑动窗口39 下列应用层协议中，( )协议是基于 UDP 传输的。（A）DNS（B） SMTP（C） HTTP（D）FTP40 在 OSI 参考模型中，同一结点内相邻层之间通过( )来进行通信。（A）协议（B）接口（C）进程（D）应用程序二、综合应用题41-47 小题，共 70 分。41 给定单链表的结点结
13、构typedef struct node *link；struct nodeint item，link next；) ；将两个升序单链表归并为一个升序单链表。42 某中央处理器的数据通路如图所示。MDR 为内存数据寄存器，PC 为程序计数器，IR 为指令寄存器。所有的单线箭头为控制微命令。 (1)请说明图中部件 X 的名称和功能、寄存器 Y 的名称和功能。 (2)请解释：为什么要设置 T 暂存器? (3)假定指令格式为 RS 型指令，其中 “SUB R，A” 指令的操作为：RR-A ，A为内存地址 A 所存储的内容。请画出 SUB 指令的指令周期流程图，并给出每个微操作对应的微命令。43 设某
14、系统有两种磁盘配置：一种单磁盘结构，一种 4 磁盘组阵列结构。每个磁盘每磁道 64 个扇区，每扇区 1 024字节，转速为 10 000 rpm。找道时间为 6 ms。两种结构的磁盘控制器每次访问的延迟时间均为 1 ms。设 IO 系统的性能只与磁盘和控制器有关，单磁盘中连续访问的扇区在磁盘组中将尽量分布在不同磁盘中。设扇区可以按照任意顺序读写。问：A若从单盘结构的顺序排列的扇区中读取 4 KB，每次 IO 操作用时多少?B若从阵列结构的顺序排列的扇区中读取4 KB，每次 IO 操作用时多少?C设读请求是随机的，其中一半的请求从顺序排列的扇区中读取 4KB，另一半的请求从顺序排列的扇区中读取
15、16 KB。请比较两种组织结构的 IO 性能。44 某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V 原语操作实现读者进程。45 给定页面请求序列 RS=cadbebabcd，页框为 4，起始为空，写出 LRU 页面置换过程。46 如图所示一台路由器连接 3 个以太网。请根据图中给出的参数回答如下问题： (1)该 TCPIP 网络使用的是哪一类 IP 地址? (2)写出该网络划分子网后所采用的子网掩码。 (3)系统管理员将计算机 D 和 E 按照图中所示结构连入网络并使用所分配的地址对 TCPIP 软件进行常规配置后，发现这两台机器上的网络应用程序不能够正常通信。这是
16、为什么? (4) 如果你在主机 C 上要发送一个 IP 分组，使得主机 D和主机 E 都会接收它，而子网 3 和子网 4 上的主机都不会接收它，那么该 IP 分组应该填写什么样的目标 IP 地址?计算机专业（基础综合）模拟试卷 15 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 A2 【正确答案】 D3 【正确答案】 D4 【正确答案】 D5 【正确答案】 A6 【正确答案】 D【试题解析】 将中缀表达式转换为后缀表达式需要一个运算符栈，假设中缀表达式本身合法且在字符数组 A 中，转换后的后缀表
17、达式存储在字符数组 B 中。具体做法：从左到右扫描表达式，遇到运算对象顺序向存储后缀表达式的 B 数组中存放，遇到运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则运算符出栈，并将其送人数组 B 中存放。其实中缀表达式和后缀表达式中操作数出现的次序是相同的，只是运算符的出现次序不同。在后缀表达式中，运算符出现的次序就是实际应计算的顺序。一种方法是把中缀表达式中所有的计算顺序都按照计算规则用嵌套括号形式表示出来，然后将每对括号中的运算符移到相应括号的后面，在删去所有括号，便得到等价的后缀表达式。A-(B+C D)*E 表示为：(A-(B+(CD)*E)转换为：
18、ABCD +E*- 故选 D。7 【正确答案】 D【试题解析】 由哈夫曼树的特点易知哈夫曼树结点总数=2m-1 ，m 为叶子节点个数。8 【正确答案】 D【试题解析】 简单无向图的邻接矩阵是对称的，且对角线元素均是 0(因简单无向图不存在自己到自己的环路)，故压缩存储只须存储下三角或上三角(均不包括对角线)即可。故 k 值至少为 1+2+3+(n-1)=n(n-1)2；故选 D。9 【正确答案】 B【试题解析】 分块查找成功的平均查找长度为 ASL=(s2+s+n)2s(s 为每块记录数，n 为记录总数 )。在本题中，n=123 ，s=1233=41，故平均查找长度为 23。10 【正确答案】
19、 C【试题解析】 当待排数据基本有序时快速排序需 0(n2)次比较，只有当数据完全无序时才能发挥快速排序的长处(此时时间复杂度接近 O(nlogn)。11 【正确答案】 D【试题解析】 只有移码表示法中正数的符号位为“1”，原码、反码和补码中正数的符号位均为“0”。12 【正确答案】 B13 【正确答案】 B14 【正确答案】 B【试题解析】 阶码位数越多能表示数的范围越大，尾数位数越多能表示的数的精度越高；故选 B。C 错，因为第二种阶码位数少，所以其表示的数的范围小。15 【正确答案】 B【试题解析】 74181ALU 设置了 P 和 G 两个本组先行进位输出端。如果将四片74181 的
20、P，G 输出端送入到 74182 并行进位部件(CLA)，又可实现第二级的并行进位，即组与组之间的并行进位。16 【正确答案】 B【试题解析】 SRAM 是易失性存储器，无需刷新；DRAM 也是易失性存储器，需刷新；ROM 无需刷新。17 【正确答案】 B【试题解析】 双端口存储器采用了两套相互独立的读写电路，两套读写电路可以同时访问共同的存储体，当左右端口访问的地址一样时就会产生读写冲突问题，需要避免。18 【正确答案】 D19 【正确答案】 B【试题解析】 在微程序控制中一条机器指令对应一个微程序，每一个微程序包含若干条微指令，每一条微指令对应一个或几个微操作命令。当计算机运行时，逐条执行
21、微程序中的每一条微命令，就相应的完成了一条机器指令的全部操作。20 【正确答案】 B【试题解析】 直接映射 Cache 规则：主存储器中一块只能映象到 Cache 的一个特定的块中。(1)主存与缓存分成相同大小的数据块。(2) 主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的块数与缓存的总块数相等。(3)主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。优点：地址映象方式简单，数据访问时，只需检查区号是否相等即可，因而可以得到比较快的访问速度，硬件设备简单。缺点：替换操作频繁，命中率比较低。21 【正确答案】 A【试题解析】 机器周期又 CPU 周期：内存中读取
22、一个指令字的最短时间；指令周期(Instruction Cycle) ：取出并执行一条指令的时间；总线周期(BUS Cycle) ：也就是一个访存储器或 IO 端口操作所用的时间；时钟周期(Clock(2ycle)：又称节拍周期，是处理操作的最基本单位。22 【正确答案】 C【试题解析】 C DMA(存储器直接访问) 。这是指一种高速的数据传输操作，允许在外部设备和存储器之间直接读写数据，既不通过 CPU，也不需要 CPU 干预，是在主存和外设之间建立的直接数据通路。23 【正确答案】 B【试题解析】 实时操作系统是保证在一定时间限制内完成特定功能的操作系统。实时操作系统是指当外界事件或数据产
23、生时，能够接受并以足够快的速度予以处理，其处理的结果又能在规定的时间之内来控制生产过程或对处理系统作出快速响应，并控制所有实时任务协调一致运行的操作系统。因而，提供及时响应和高可靠性是其主要特点。24 【正确答案】 C【试题解析】 多级反馈队列调度算法描述：(1)进程在进入待调度的队列等待时，首先进入优先级最高的 Q1 等待。(2)首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1，Q2，Q3 三个队列，只有在 Q1 中没有进程等待时才去调度 Q2，同理，只有 Q1，Q2 都为空时才会去调度 Q3。(3)对于同一个队列中的各个进程，按照时
24、间片轮转法调度。比如 Q1 队列的时间片为 N，那么 Q1 中的作业在经历了 N 个时间片后若还没有完成，则进入 Q2 队列等待，若 Q2 的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。(4)在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU 马上分配给新到达的作业(抢占式 )。故多级反馈队列调度算法综合考虑了 CPU 密集型和 IO 密集型进程。25 【正确答案】 B【试题解析】 s 初值为 5，每调用一次 wait 操作 s 减一，每执行一次 signal 操作s 加 1，故调用了 10 次 wait 操作和 8 次 signal 操作后 s
25、 值为 5-10+8=3。26 【正确答案】 D27 【正确答案】 A【试题解析】 B 错，银行家算法是死锁避免算法而非死锁预防策略；C 错，一次性分配资源策略是打破死锁的请求并保持条件；D 错，资源分配图化简法可以用来发现循环等待现象，用于死锁的检测，它不能破坏循环等待条件。28 【正确答案】 A【试题解析】 在请求分页存储管理中，从主存中刚刚移走某一页面后，根据请求马上又调进该页，这种反复调进调出的现象，称为系统抖动。原因是调度的算法不科学。系统抖动大大降低系统效率。29 【正确答案】 B30 【正确答案】 A【试题解析】 分析知首先在主目录检索，最不理想的情况下检索到第 3 个目录项才检
26、索到文件所在的主目录(此时检索了 3 个目录项)，以此类推在用户目录和子目录中最多各需检索 4 个和 5 个目录项；故最多只需检索 3+4+5=12 个目录项。31 【正确答案】 D【试题解析】 文件的逻辑结构有流式结构和记录式结构。文件的物理结构有：顺序结构、链式结构和索引结构等。文件的索引结构是为每个文件分配一个索引块，有效索引表登记其各逻辑块与外存物理块的对应关系，并在文件 FCB 中登记该文件索引块的地址。索引结构的特点：既适合顺序存取，也方便随机存取；容易实现记录的增、删和插入；缺点是由于索引表的建立而增加了存储空间的开销。32 【正确答案】 B33 【正确答案】 A【试题解析】 计
27、算机只能够识别和处理数字信号，只认识 0 和 1 两个二进制数组成的数字编码。所以一般计算机网络中的信号，也是以数字信号表示的。34 【正确答案】 D35 【正确答案】 B【试题解析】 以太网采用带冲突检测的载波帧听多路访问(CSMACD)机制。以太网中节点都可以看到在网络中发送的所有信息；所以，以太网是一种广播网络。当以太网中的一台主机要传输数据时，它将按如下步骤进行：(1)侦听信道上收否有信号在传输。如果有的话，表明信道处于忙状态，就继续侦听，直到信道空闲为止。(2)若没有侦听到任何信号，就传输数据。(3)传输的时候继续侦听，如发现冲突则执行退避算法，随机等待一段时间后，重新执行步骤 1(
28、当冲突发生时，涉及冲突的计算机会发送一个拥塞序列，以警告所有的节点)。(4)若未发现冲突则发送成功，计算机会返回到帧听信道状态。36 【正确答案】 D【试题解析】 A、B、C 都是网络层(IP 层)需提供的服务，而提供可靠的连接是传输层提供的服务。37 【正确答案】 C【试题解析】 中继器是局域网互连的最简单设备，工作于 OSI 的物理层；网桥工作在 OSI 的数据链路层；路由器工作在 OSI 的网络层。38 【正确答案】 D【试题解析】 TCP 采用面向连接的三次握手实现可靠对象传输。TCP 使用滑动窗口协议进行流量控制，TCP 连接的每一方都有固定大小的缓冲空间，TCP 的接收端只允许另一
29、端发送接收端缓冲区所能接纳的数据，防止较快主机发送过多数据致使较慢主机的缓冲区溢出。39 【正确答案】 A40 【正确答案】 B二、综合应用题41-47 小题，共 70 分。41 【正确答案】 算法描述如下：link merge(link t1，link t2)link x，t=malloc(sizeof*t) ；while(t1!=NULL&t21=NULL)if(t1-item t2-item)t-next=t1；t=t-next；t1=t1-next；elset-next=t2；t=t-next；t2=t2-next；if(t1!=NULL)t-next=t1；if(t2!=NULL)t
30、-next=t2；x=t； t=t-next；free(x)；return t；42 【正确答案】 43 【正确答案】 旋转时间=(60*1 000) 10 0002=6 ms2=3 ms读一个扇区的传输时间=6 ms64=0 093 ms读四个连续扇区的传输时间=(6 ms64)*4=0 375 ms访问时间=6+3+1+0375=10375 msB 同时从四个盘各自读取一个扇区：旋转时间=(60*1 000)10 0002=6 ms2=3 ms从一个磁盘读一个扇区的传输时间=6 ms64=0 093 ms同时从四个磁盘读四个连续扇区的传输时间=0093 ms访问时间=6+3+1+0093=
31、10093 msC 单盘结构：读四个连续扇区的传输时间=(6 ms64)*4=0 375 ms访问时间=6+3+1+0375=10375 ms读 16 个连续扇区的传输时间=(6 ms64)*16=1 5 ms访问时间=6+3+1+15=115 ms阵列结构：同时从四个磁盘读四个连续扇区的传输时间=0093 ms访问时间=6+3+1+0093=10093 ms读 16 个连续扇区的传输时间=0093*4=0 375 ms访问时间=6+3+1+0375=10375 ms44 【正确答案】 semaphore mutex=1；int readers=0；void reader()P(mutex)；if(+readers=1)turn_on(light)；V(mutex)；reading()；P(mutex)；if(-readers=0)turn_off(light)；V(mutex)；45 【正确答案】 46 【正确答案】 (1)该 TCPIP 网络使用的是 B 类 IP 地址。(2)该网络划分子网后所采用的子网掩码是 2552552550。(3)这两台机器上的网络应用程序不能够正常通信，那是因为在一个以太网上不能使用不同的子网号。在这种配置情况下，IP 软件会试图将 IP 分组送往网关，而不会直接投递。最终 IP 分组将会被该网关丢弃。(4)255255 255255
