1、计算机专业（基础综合）模拟试卷 38 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下面程序段中，执行 S 语句的次数为( )。for(inti=1；inext)if(rand( )+m=0)x=t；（A）13（B） 110（C） 17（D）123 若一个栈的输入序列为 1，2，3，n，输出序列的第一个元素为 i，则第 j 个输出元素为( ) 。（A）ij1（B） ij（C） Ji+1（D）不确定4 一个循环队列 Q 最多可存储 m 个元素，已知其头尾指针分别是 front 和 rear，则判定该循环队列为
2、满的条件是( )。（A）Qrear Qfront=一 m（B） Qrear!=Qfront（C） Qfront=(Q rear+1)m（D）Qfront=Qrearm+15 已知有一维数组 AEom*n1，若要对应为 m 行 n 列的矩阵，则下面的对应关系()可将元素 AEk(00 时，H i=(H(key)+di)m 当 dii=(H(key)+di+m)m 散列表如下表所示，试回答下面的问题：42 对表中每个关键字进行查找时，各需要进行的比较次数；43 在等概率情况下查找时，查找成功的平均查找长度。43 已知某 32 位二进制机器数为 110000000000000000000000000
3、00000，试计算在下列各种编码方式下其代表的真值。44 原码定点小数；45 补码定点小数；46 反码定点小数；47 IEEE754 标准短实数。【注】题中机器数中间加空格是为了读写方便，并非机器数的一部分，答题时如有需要可类似表示。47 某机字长 32 位，主存容量 32MB，按字节编址；该机的 Cache 采用 4 路组相联映射方式，Cache 容量为 16KB，块长为 4 个字，试回答下列问题：48 主存地址位数为多少?49 画出主存地址格式示意图，注明各字段名称及位数。50 设该 Cache 的命中率为 98，如果 Cache 的速度是主存的 5 倍，则该机采用Cache 时存储系统的
4、速度是不采用 Cache 时的多少倍(设 CPU 访存时同时访问Cache 和主存，若 Cache 命中则中断主存访问)?51 桌上有一空盘，只允许放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子，女儿专等着吃盘中的苹果，儿子专等着吃盘中的橘子。试用 P，V 原语实现爸爸、妈妈、儿子和女儿间能同步的程序。51 关于分页系统，回答下列问题：52 在页表中，哪些数据项是为实现换页而设置的?53 设某系统为每个作业进程分配 3 个内存块，某作业进程在运行访问中的轨迹为1，4，3，1，6，8，1，且每一页都是按请求装入的。问：先进先出页面置换算法(FIFO)和最近未使用页面置换算法(LRU)下，产
5、生缺页的次数各是多少 ?(画出必要的数据图)54 在什么情况下，上述两种页面淘汰算法执行效果是一样的?为什么?54 某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A ：B(1)，D(3)B：A(1) ，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E：D(2)，B(5)问：55 经过计算后 A 到各个顶点的最短距离是多少?56 A 到各个顶点的最短路径是什么?57 如果此时 B 到 D 的链路长度更新为 3，那么 A 到各个结点的最短路径有什么变化?计算机专业（基础综合
6、）模拟试卷 38 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 分析易知当 i=1 时 s 语句执行 1 次，当 i 一 2 时 s 语句执行 2 次，当 i=n 时 s 语句执行 n 次，故 s 语句共执行 1+2+n=n(n+1)2 次。2 【正确答案】 B【试题解析】 x 存放表中任意一个结点指针的概率是一样的，故存放第 7 个结点指针的概率是 110，选 B。3 【正确答案】 D【试题解析】 由于此题 i，j 的值均未指定，故我们不能判断第 j 个元素是什么。4 【正确答
7、案】 C【试题解析】 考查循环队列判满的条件。5 【正确答案】 C【试题解析】 数组和矩阵的行和列都从 0 开始，Ak前有 k 个元素，矩阵每行有n 个元素，故行数 i=kn，列数 j=k96n 。6 【正确答案】 B【试题解析】 根据题意有 215=n0+n2=n0+(n01)=2n0 一 1；因此 n0=108，即可得到 108 个码字，因为待编码的字符均保存在叶子节点里。7 【正确答案】 C【试题解析】 由先序和中序遍历构造出二叉树，易知选 C。8 【正确答案】 D【试题解析】 n 个顶点在邻接矩阵中有 n2 个元素，由于每条边会产生两个相同的元素，故 e 条边产生 2e 个非零元素，故
8、共有 n2 一 2e 个零元素。9 【正确答案】 A【试题解析】 12 个元素进行二分查找在查找成功的情况下有 1 个元素需查找 1 次，2 个元素需查找 2 次，4 个元素需查找 3 次，5 个元素需查找 4 次；故查找成功所需的平均比较次数=(11+22+43+54)12=37 12；选 A。10 【正确答案】 C【试题解析】 归并排序所需内存量最大。9811 【正确答案】 A【试题解析】 机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。汇编语言是机器语言便于记忆和理解的符号形式，汇编语言必须转化为机器语言才能被计算机识别和执行。高级语言必须要转化为低级语言如汇编语
9、言或其他低级语言，再进一步转化为机器语言才能被计算机识别和执行。12 【正确答案】 C【试题解析】 计算机使用补码的最大优点是可以在加法或减法处理中，不需因为数字的正负而使用不同的计算方式。只要一种加法电路就可以处理各种有号数加法，而且减法可以用一个数加上另一个数的二进制补码来表示，因此只要有加法电路及二进制补码电路即可完成各种有号数加法及减法，在电路设计上相当方便。从而简化了计算机的设计。13 【正确答案】 A【试题解析】 移码的取值范围和补码是相同的，故选 A。一 128 对应的二进制移码为 00000000；0 对应的二进制移码为：10000000；127 对应二进制移码为：011111
10、11。14 【正确答案】 B【试题解析】 RISC 指令系统的特点有：指令长度固定、指令格式种类少、寻址方式种类少，配备大量通用寄存器，较多的采用硬布线逻辑实现，指令功能简单、只有取数和存数指令访问存储器，其余指令都在寄存器之间进行，使用频率高的简单指令，很有用且不复杂的指令系统和优化的编译程序。故 B 错。15 【正确答案】 B【试题解析】 速度快慢排序如下：寄存器Cache内存外存。16 【正确答案】 D17 【正确答案】 C18 【正确答案】 B【试题解析】 时钟周期是由 cPu 时钟定义的定长时间间隔，是计算机主频的周期，是 CPU 工作的最小时间单位，也称节拍脉冲。CPU 周期又称机
11、器周期，由于CPU 访问一次内存所花的时间较长，因此通常用从内存读取一条指令字的最短时间来规定 CPU 周期。指令周期是取出并执行一条指令的时间，一个指令周期常常由若干个 CPU 周期组成。存储器进行一次“读”或“写”操作所需的时间称为存储器的访问时问(或读写时间) ，而连续启动两次独立的“读”或“写”操作(如连续的两次“读”操作)所需的最短时间，称为存取周期(或存储周期)。19 【正确答案】 B【试题解析】 直接表示法是在微指令的控制字段中，每一位代表一个微命令。但在某些复杂的计算机中，微命令甚至可多达三四百个，这使微指令字长达到难以接受的地步，故提出了编码表示法。编码表示法有字段直接编码法
12、和字段间接编码法。选出互斥的微命令，并将这些微命令编成一组，成为微指令字的一个字段，用二进制编码来表示，就是字段直接编译法。例如，将 7 个互斥的微命令编成一组，用三位二进制码分别表示每个微命令，那么在微指令中，该字段就从 7 位减成 3 位，缩短了微指令长度。而在微指令寄存器的输出端，为该字段增加一个译码器，该译码器的输出即为原来的微命令。字段间接编码法是在字段直接编码法的基础上，进一步缩短微指令字长的一种编码法。20 【正确答案】 B【试题解析】 多级存储体系由 Cache、主存和辅存构成，故 B 错。21 【正确答案】 B【试题解析】 A、C、D 都只是某种存储体而非存储结构。由多重中断
13、的特点始终响应的是最近的一次中断请求，故它符合堆栈的后进先出的特点。22 【正确答案】 A【试题解析】 多体交叉存储器把主存储器分成几个能独立读写的、字长为一个主存字的存储体，分别对每一个存储体进行读写；还可以使几个存储体协同运行，由存储器控制部件控制它们分时使用数据总线进行信息传递，这是一种并行存储器结构，从而提供出比单个存储体更高的读写速度。23 【正确答案】 B【试题解析】 多道程序设计系统的定义。24 【正确答案】 C【试题解析】 考查银行家算法。25 【正确答案】 B【试题解析】 因每次允许 3 个进程进入程序段故 S 最大值为 3，则最小值为一(43)=一 1；故选 B。26 【正
14、确答案】 B【试题解析】 进程被唤醒后首先进入就绪队列的队尾，当获得时间片时从就绪状态变为运行状态。进程控制块(PCB)是进程存在的唯一标识，所谓进程进入就绪队列队尾即 PCB 移至就绪队列的队尾。27 【正确答案】 D【试题解析】 最不理想的情况下每个进程都需要 2 个该类资源才能执行并且每个进程都以申请到 1 个资源同时申请第二个资源，而此时还有一个资源可供使用，3个进程中任意一个进程再获得 1 个资源都可执行完毕释放自己的资源供其他进程使用，故必然不会出现死锁现象。28 【正确答案】 C【试题解析】 虚拟存储器的实现需要软硬件的共同支持，它的引入是为了解决主存容量的问题。29 【正确答案
15、】 D【试题解析】 理想页面置换算法是每次调换出的页面是所有内存页面中最迟将被使用的，可惜的是这种算法是无法实现的。为了尽量减少与理想算法的差距产生了最近最少未使用页面置换算法，它是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的儿条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这就是著名的局部性原理一一比内存速度还要快的 Cache，也是基于同样的原理运行的。30 【正确答案】 A【试题解析】 3 一个磁盘块可以放 n=1kB64B=16 个目录，现某一文件又能3200 个目录项，总共需 320016=200 个磁盘块，又采用 1 级目
16、录结构，故查找一个文件平均启动盘块的次数为 2002=100 次。31 【正确答案】 B【试题解析】 SPOOLing 是 SimultaneotlsPeripheralOperationOnLine(即外部设备联机并行操作)的缩写。在 SPOOLing 系统中，实际上并没有真正的把设备分配给该进程，而只是在输入井和输出井中，为进程分配一存储区和建立一张 IO请求表。这样，便把独占设备改造为共享设备。32 【正确答案】 B【试题解析】 设备独立性是指用户不指定特定的设备，而指定逻辑设备，使得用户作业和物理设备独立开来，再通过其他途径建立逻辑设备和物理设备之间的对应关系的特性；即用户程序独立于具
17、体使用的物理设备的一种特性。33 【正确答案】 A【试题解析】 根据网络的作用范围可以把计算机网络分为广域网、城域网和局域网；根据网络的拓扑结构可以把网络分为总线型、环形、星形等结构。根据网络的通信方式可以把计算机网络分为点对点传输网络、广播式传输网络。根据网络的传输介质可以把计算机网络分为有线网、光纤网、无线网等。34 【正确答案】 C【试题解析】 集线器(Hub)是局域网的基本连接设备，是一种特殊的中继器，工作在物理层，可以对接收到的信号进行衰减补偿从而放大信号。集线器接收到某个结点发送的广播信息时便会将接收到的数据转发到每个端口。35 【正确答案】 D【试题解析】 促进 ATM 技术发展
18、的因素主要有：用户对网络带宽与对带宽高效、动态分配需求的不断增长；用户对网络实时应用需求的提高；网络的设计与组建进一步走向标准化的需要。由于 ATM 技术简化了交换过程，去除了不必要的数据校验，采用易于处理的固定信元格式，所以 ATM 交换速率大大高于传统的数据网。多媒体应用及实时通信要求网络传输的高速率与低延迟，目前存在的传统的线路交换与分组交换都很难胜任这种综合数据业务的需要，而 ATM 技术能满足此类应用的要求。36 【正确答案】 C【试题解析】 C 类地址前 24 位是网络地址不可用于划分子网，后 8 位主机号可供划分子网要分成 8 个子网须 3 位，后 5 位作为每个子网的 IP 地
19、址；故掩码为255255255224，选 C。37 【正确答案】 D【试题解析】 只有路由器可用于连接多个网络，中继器、网桥、网卡都不能实现多个网络的互联。38 【正确答案】 A【试题解析】 TCP 提供的是可靠的、全双工的面向连接的服务。39 【正确答案】 C【试题解析】 物理层、数据链路层和网络层组成的通信子网为网络环境中的主机提供点到点的服务，而传输层为网络中的主机提供端到端的通信。直接相连的节点对等实体的通信叫点到点通信。它只提供一台机器到另一台机器之间的通信，不会涉及到程序或进程的概念。同时点到点通信并不能保证数据传输的可靠性，也不能说明源主机与目的主机之间是哪两个进程在通信，这些工
20、作都由传输层来完成的。40 【正确答案】 C【试题解析】 FTP(文件传输协议)，主要功能有：(1)把本地计算机上的一个或多个文件传送到远程计算机，或从远程计算机上获取一个或多个文件。(2)提供对本地计算机和远程计算机的目录操作功能。(3)客户端在一定的范围内对文件进行改名、删除、显示文件内容等。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 逐个检测顺序表中值在 x 和 y 之间的元素，并计数于 k，再将其值大于 y 的元素向前移动 k 个元素。算法描述如下： void DeleteXY(SList*1a，int x，int y)int k=0：for(int i=0； i
21、size；i+)if(a_datai一 x&a-dataidataik=a 一datai；a 一n=a-n-k；42 【正确答案】 查找成功的比较次数分为：21：2,57：2,45：3,37：1,50：243 【正确答案】 查 找成功的平均查找长度为(2+2+3+1+2)5=2 。44 【正确答案】 该 32 位二进制机器数为原码定点小数时，其真值为一 12-1=一05；45 【正确答案】 该 32 位二进制机器数为补码定点小数时，根据其符号位为 1 可知其为负数，为方便计算，将其连符号位在内取反加 1，得其相反数的补码机器数为01000000000000000000000000000000
22、相反数真值为 12-1=05，故原机器数真值为一 05；46 【正确答案】 该 32 位二进制机器数为反码定点小数时，根据其符号位为 1 可知其为负数，故将其数值位取反即可得其真值对应的原码机器数为10111111111111111111111111111111 其真值为一(02 -1+12-2+12-31)=一(2 -1一 2-31)；47 【正确答案】 该 32 位二进制机器数表示 IEEE754 标准短实数时，根据IEEE754 标准的格式，知其为负数，写出隐藏位，得其尾数的形式如下一100000000000000000000000 尾数真值为一 1，又 IEEE754 标准短实数阶码采
23、用偏移量为 7FH 的移码，故其阶码真值为 100000002011111112=000000012=110，又基数为 2，故题目所求真值为一 121=一 2。48 【正确答案】 主存按字节编址，容量为 32MB=225B，故主存地址位数为 25。49 【正确答案】 主 存字长 32 位，按字节编址，块长为 4 个字，即 4 字4B字=16B=224B，故字块内地址需 4 位；Cache 采用四路组相联映射，故每组容量为16B4=64B，Cache 共分 16KB64B=256=2 8。组，故组地址需 8 位；主存字块标记位数为 2548=13 位。主存地址格式如下表所示：50 【正确答案】
24、设 Cache 访问时间为 t，则主存访问时间为 5t，采用 Cache 时存储系统的平均访问时间 T=t098+5t(1 098)=108t 故采用 Cache 存储系统的速度是不采用 Cache 时的 510846 倍。51 【正确答案】 在本题中，应设置 3 个信号量：empty，apple ，orange 。其中empty 表示盘中是否为空，初始值为 1；apple 表示盘中是否有苹果，初始值为0；orange 表示盘中是否有橘子，初始值为 0。爸爸、妈妈、儿子和女儿间的同步描述如下：Fatherwhile(true)P(empty)；将苹果放入盘中；V(apple)；Mather：w
25、hile(true)P(empty)；将橘子放入盘中；52 【正确答案】 在页表中，访问位和修改位是为请求页面调度设置的。访问位来跟踪页的使用，修改位来跟踪页的写入。53 【正确答案】 F IFO 算法：缺页次数是 6，具体如下：LRU 算法：缺页中断次数为 5，具体如下：54 【正确答案】 当 最先进入内存的页面又是最近最久没有使用的页面时，上述两种页面淘汰算法执行的效果一样。55 【正确答案】 根据 Dijkstra 算法，可以算得 A 到各个顶点的最短距离如下表所示：56 【正确答案】 可 以得到 A 到各个顶点的最短路径如下表：57 【正确答案】 B D 距离变为 3 之后各个顶点的最短距离和路径如下表：
