[考研类试卷]计算机专业（基础综合）模拟试卷48及答案与解析.doc

1、计算机专业（基础综合）模拟试卷 48 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 将 5 个字母“ooops”按此顺序人栈，则有 ( )种不同的出栈顺序可以仍然得到“ooops”。（A）1（B） 3（C） 5（D）62 设有 10 阶矩阵 A，其对角线以上的元素 aijj10，1（A）45（B） 46（C） 55（D）563 一棵二叉树的后序遍历序列为 DABEC，中序遍历序列为 DEBAC，则先序遍历序列为( ) 。（A）ACBED（B） DECAB（C） DEABC（D）CEDBA4 以下叙述不正确的

2、是( )。（A）后序线索二叉树是不完善的，要对它进行遍历，不需使用栈（B）任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈（C）任何一棵二叉树都可以不用栈实现先序线索树的先序遍历（D）任何一棵二叉树都可以不用栈实现中序线索树的中序遍历5 如果一棵完全二叉树共有 26 个结点，则必定有( )个结点的度为 1。（A）0（B） 1（C） 3（D）136 在散列表中，当装填因子非常接近 1 时，线性探测类似于( )查找。（A）二分（B）随机（C）顺序（D）分块7 高度为 7 的 AVL 树最少有( )个结点。（A）31（B） 32（C） 33（D）348 如右图所示的有向图 G 的深度优先搜索得到

3、的结点序列是 ( )。（A）abcfdeg（B） abcgfde（C） abcdefg（D）abcfgde9 设有关键字序列 F=Q，G，M，Z，A，N，P，X ，H) ，下面( )序列是从上述序列出发建堆的结果。（A）A，G，H，M，N，P，Q，X，Z（B） A，G，M，H，Q，N，P，X，Z（C） G，M ，Q，A，N，P，X，H，Z（D）H，G，M，P ，A，N，Q，X，Z10 若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。（A）起泡排序（B）插入排序（C）选择排序（D）二路归并排序11 使用海明码来

4、检出并纠正一位错，当有效代码长度为 8 位时，至少需要( )位校验位。（A）3（B） 4（C） 5（D）612 下列关于加法器的说法错误的是( )。（A）实现 n 位的串行加法器只需 1 位全加器（B）实现 n 位的并行加法器需要 n 位全加器（C）影响并行加法器速度的关键因素是加法器的位数的多少（D）加法器是一种组合逻辑电路13 某 2561 位的存储芯片内部结构为 1616 的存储元矩阵，且采用“重合法”的译码驱动方式来选择存储元，则该芯片引脚中地址线的数目为( )。（A）256（B） 32（C） 16（D）814 下列四种存储器中，存取速度最快的是( )。（A）DRAM（B） SRAM（

5、C）掩模式 ROM（D）EPROM15 下列关于一地址指令的说法正确的是( )。（A）可能是数据传送指令（B）可能是实现单目运算的运算指令（C）可能是实现双目运算的运算指令（D）以上都有可能16 堆栈(软堆栈) 寻址的寻址方式可看作是( ) 。（A）寄存器寻址（B）寄存器间接寻址（C）基址寻址（D）直接寻址17 关于基址寻址和变址寻址，下列说法中错误的是( )。（A）两者都可扩大指令的寻址范围（B）两者在取操作数之前都需要对有效地址进行计算（C）在程序执行过程中，基址寄存器的内容不可变，变址寄存器中的内容可变（D）基址寄存器和变址寄存器的内容都由用户确定18 指令流水线中出现数据相关时流水线将

6、受阻，( )可解决数据相关问题。（A）增加硬件资源（B）采用旁路技术（C）采用分支预测技术（D）以上都可以19 设 CPU 与 IO 设备以中断方式进行数据传送， CPU 响应中断时，该 IO 设备接口控制器送给 CPU 的中断向量表(中断向量表存放中断向量)指针是0800H，0800H 单元中的值为 1200H。则该 IO 设备的中断服务程序在主存中的入口地址为( ) 。（A）0800H（B） 0801H（C） 1200H（D）1201H20 CPU 的工作周期为 20ns，主存存取周期为 10ns，此时 DMA 接口适合采用( )方式与 CPU 共享主存。（A）停止 CPU 访问主存（B）

7、周期挪用（C） DMA 与 CPU 交替访存（D）以上无正确选项21 假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失( 未命中)50 次，则 Cache 的命中率是( )。（A）5（B） 95（C） 50（D）9522 关于 DMA 方式和通道方式，下列说法中错误的是( )。（A）DMA 的数据传送全部由硬件控制，而通道方式通过执行通道程序来传送数据（B）一个 DMA 控制器连接多台外设时，这些外设只能串行工作（C）一个通道可连接多台外设，且可使这些外设并行工作（D）DMA 控制器和通道都可以连接各种高低速设备23 分时系统中，

8、为使多个用户能够同时与系统交互，最关键的问题是( )。（A）计算机具有足够的运行速度（B）内存容量应足够大（C）系统能及时地接收多个用户输入（D）能在一短的时间内，使所有用户程序都能运行24 计算机操作系统中，若 WAIT、SIGNAL 操作的信号量 S 初值为 3，当前值为一 2，则表示当前有( ) 个等待信号量 S 的进程。（A）1（B） 2（C） 3（D）025 假定系统拥有某类资源 10 个。在该系统上运行的所有作业，其对该类资源的需求量不会超过 2 个。为了提高资源利用率，我们打算对这种资源采用动态分配，但用限制系统中并发执行的作业数来防止发生死锁。你认为作业调度允许并发执行的最大作

9、业数应是( ) 。（A）1（B） 8（C） 9（D）1026 设某进程的访问串为 1、3、1、2、4，驻留集为 3 块，当访问 4 号页面时，按LRU 页面替换算法，应淘汰( )号页面。（A）1（B） 2（C） 3（D）427 文件系统的主要目的是( )。（A）实现对文件的按名存取（B）实现虚拟存储器（C）提高外围设备的输入输出速度（D）用于存储系统文档28 虚拟存储管理系统的基于程序的局部性理论，( )是指最近被访问的存储单元可能马上被访问。（A）数据局部性（B）空间局部性（C）时间局部性（D）空间全局性29 我们把一段时间内，只允许一个进程访问的资源，称为临界资源，因此，我们可以得出以下论

10、述，请选择一条正确的论述( )。（A）对临界资源是不能实现资源共享的（B）对临界资源，应采取互斥访问方式，来实现共享（C）为临界资源配上相应的设备控制块后，便能被共享（D）对临界资源应采取同时访问方式，来实现共享30 有关设备管理概念的下列叙述中，( )是不正确的。（A）通道是处理输入、输出的软件（B）所有外围设备的启动工作都由系统统一来做（C）来自通道的 IO 中断时间由设备管理负责处理（D）编制好的通道程序是存放在主存储器中的31 驱动调度算法中，( )算法可能会随时改变移动臂的运动方向。（A）电梯调度（B）最短寻找时间优先（C）扫描（D）单向扫描32 对于一个文件的访问，常由( )共同限

11、制。（A）用户访问权限和文件属性（B）用户访问权限和用户优先级（C）优先级和文件属性（D）文件属性和口令33 为了使数据在网络中的传输延迟最小，首选的交换方式是( )。（A）电路交换（B）报文交换（C）分组交换（D）信元交换34 假定有一条通带为 100kHz 的信道，每路信号的带宽为 32kHz，各路信号间的防护带宽为 08kHz 。若采用频分多路复用，那么最多可以同时传输( )路信号。（A）10 路（B） 20 路（C） 25 路（D）40 路35 一个 ATM 网络的源端点和目的端点之间有三个 ATM 交换机，现在要建立一条虚电路，一共需要发送( )个报文。（A）12（B） 15（C）

12、18（D）2136 下列设备中，可以分割广播域的是( )。（A）集线器（B）网桥（C）以太网交换机（D）路由器37 路由器采用( ) 方式来发送 IP 分组。（A）存储转发机制（B）直通交换机制（C）分组交换机制（D）分组检测机制38 TCP 是采用 ( )来控制流量的。（A）设定拥塞窗口（B） TCP 首部中的接收窗口（C）设定拥塞阀值（D）通过标志位来通知39 一个 UDP 用户的数据报的数据部分长为 8192 字节。那么通过以太网来传播该UDP 数据报时，最后一个 IP 分片的数据长度是( )。（A）1500（B） 1480（C） 800（D）60040 在使用浏览器打开某个网页时，用户

13、输入网址后，浏览器首先要进行( )。（A）域名到 IP 地址的解析（B）和服务器建立 TCP 连接（C）发送 UDP 分组到服务器（D）发 GET、的 HTTP 命令来获得网页内容二、综合应用题41-47 小题，共 70 分。40 已知一个带有表头结点的单链表，结点结构为： 假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点(k 为正整数)。若查找成功，算法输出该结点的 data 值，并返回 1；否则，只返回 0。要求：41 描述算法的基本设计思想；42 描述算法的详细实现步骤；43 根据设计思想和实现步骤，采用程序设计语

14、言描述算法 C 使用 C 或 C+或JAVA 语言实现)，关键之处请给出简要注释。43 图的 D 搜索类似于 BFS。不同之处在于使用栈代替 BFS 中的队列，入出队列的操作作为入出栈的操作，即当一个顶点的所有邻接结点被搜索后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。44 用邻接表作为存储结构，写一个 D 搜索算法；45 用 D 搜索方法搜索下图，设初始出发的结点为 1，写出顶点的访问次序，当从某顶点出发搜索它的邻接点时，请按邻接点序号递增顺序搜索，以使答案唯一。45 某计算机采用 Cache 一主存一磁盘三级存储系统。Cache 的访问时间为 t1ns，命中率为 p1；若 Cache

15、未命中，CPU 需直接访问主存，访问时间为 t2ns，主存命中率为 p2；若所需数据字不在主存中，则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需时 t3ns。46 若不考虑主存未命中的情况，则 Cache 一主存系统的平均访问时间为多少?47 Cache 一主存一磁盘系统的平均访问时间为多少?47 某计算机采用微程序控制方式，微指令字长 32 位，采用字段直接编码的控制方式，共有 55 个微命令，可分为 6 个互斥组，分别包含 1、3、7、8、12、24 个微命令。另外，该机共有 5 个可判定的外部条件，采用断定方式形成后续微指令地址。48 设计该机微指令的格式，要求给出各字段的位

16、数。49 结合(1)的微指令格式，计算该机控制存储器的最大容量。50 试就 MutualExclusion、 Progress、BoundedWaiting 论述以下解决双进程临界区问题的算法是错误的：Process PO：doflagO=true；While(flag1)；Critical sectionFlagO=false；Remaindersection；while(1)；process P1：doflag1=true；While(flagO)；Critical sectionFlagr1=false；Remainder section；while(1)；50 Demandpaging

17、 算法是 paging 算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation 算法(段式存储管理算法 )扩展到虚拟存储空间管理，也可以产生类似的算法，不妨称之为 demandsegmentation。51 请给出相应算法，并简要说明。52 Demandpaging 算法一般都用 TLB。请问 demandsegmentation 算法需要类似的装置吗?为什么 ?52 如下图所示为一个带宽为 50kbps 的卫星信道，它的往返传播延时为 500ms。现在有一个网络架设在该信道上，网络使用 1000bit 长度的

18、帧和停止一等待协议，请回答如下问题：53 该网络发送一帧的发送延时和传输延时分别是多少?54 网络的利用率是多少?55 为了使网络的利用率达到 100，需要使用窗口是多大的回退 N 帧协议?56 使用回退 N 帧协议的网络中，如果发送了 0 7 号帧，而发送端只收到了 0、3号帧的回复，需要重新发送哪些帧?计算机专业（基础综合）模拟试卷 48 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C2 【正确答案】 D【试题解析】 考查矩阵压缩存储，由于对角线以下均为一 3，不与其他元素重复，可知这 4

19、5 个元素只需用一个值来表示，故该矩阵只需用(100 一 45)+1=56 个元素来表示。3 【正确答案】 D【试题解析】 由后序序列必定最后一个访问根结点，故 C 为根结点。在先序遍历中首先访问根结点，故可选 D。4 【正确答案】 B【试题解析】 不需要使用栈。5 【正确答案】 B【试题解析】 26 个结点，可知该二叉树有 5 层。由于前 4 层组成一棵满二叉树，共 15 个结点，则共有 11 个叶子结点，可知只有 1 个结点的度为 l。6 【正确答案】 C【试题解析】 由于线性探测在关键词同义时解决冲突的办法是线性的向后查找，当整个表几乎装满时，它就很类似于顺序查找了。7 【正确答案】 C

20、【试题解析】 平衡二叉树中含有的最少结点数有如下关系：N 0=0N1=1Nh=Nh-1+Nh-2+1 所以： N7=33。8 【正确答案】 A【试题解析】 参考深度优先算法。9 【正确答案】 B【试题解析】 参考堆建立算法。10 【正确答案】 B11 【正确答案】 B【试题解析】 当使用海明码来检出并纠正一位错时，有效代码位数 n 和校验代码位数 k 应满足 2kn+k+1；具体计算时，可采用“试凑法”。本题中。有效代码长度为 8，易知校验位至少应大于 3 位，故取 k=4，代人公式，得：2 4=168+4+1=13，满足要求，故选 B。12 【正确答案】 C【试题解析】 n 位的并行加法器有

21、 n 位的全加器，可同时对数据的各位相加，但低位运算所产生的进位会影响高位的运算结果，所以并行加法器的运算时间主要由进位信号的传递时间决定，而不是加法器位数的多少，选 C。13 【正确答案】 D【试题解析】 当采用“重合法”时，存储芯片内行、列各使用 16 根选择线便可选中 1616 矩阵中的任一位；又采用译码器时，4 根地址线即可对应 16 根选择线，故该芯片引脚中地址线数目为 4+4=8。注意，当行地址与列地址分两次传送时，可将芯片引脚中地址线数减少到 4，但题中未给出相关说明，且无对应选项，故选D。14 【正确答案】 B【试题解析】 由于电容充放电以及刷新需要一定的时间，所以 DRAM

22、的存取速度比 SRAM 慢；掩模式 ROM 只可读，不可写入； EPROM 采用紫外线照射擦去信息，读写时间比 RAM 长得多。故选 B。15 【正确答案】 D【试题解析】 一地址指令可能是实现单目运算的运算指令，也可能是数据传送指令或者实现双目运算的运算指令，其中一个操作数由指令地址码给出，另一个操作数为隐含寻址，通常由累加器 AC 提供。16 【正确答案】 B【试题解析】 软堆栈是指用主存空间的一部分实现的堆栈，只可对栈顶进行存取，堆栈指针 SP 本质上是一个寄存器，其中存放着操作数的有效地址，故堆栈寻址可看作是寄存器间接寻址。17 【正确答案】 D【试题解析】 基址寄存器常用来实现多道程

23、序，其内容一般由操作系统确定，故D 选项错误。18 【正确答案】 B【试题解析】 旁路技术指 Ng,等待某条指令的执行结果写回到寄存器后，再从寄存器取出结果，而是直接将执行结果通过专用通路送至需要该结果的地方，可用来解决流水线的数据相关问题。19 【正确答案】 C【试题解析】 中断向量即是中断服务程序的入口地址。20 【正确答案】 C【试题解析】 由于 CPU 工作周期为主存周期的 2 倍，故可将其分为两个分周期，其中一个供 DMA 接口访存，另一个供 CPU 访存，即 DMA 与 CPU 交替访存，这样可以在不影响 CPU 效率的前提下充分利用主存带宽。21 【正确答案】 D【试题解析】 C

24、ache 的命中率=命中次数总访存次数 =(100050)1000100=95 。22 【正确答案】 D【试题解析】 通道可连接各种高低速外设，而 DMA 控制器只用于高速外设成组数据的传送，D 为错误选项。23 【正确答案】 D【试题解析】 本题考查分时系统的特点。24 【正确答案】 B【试题解析】 若信号量为正则表示资源数，若为负则其绝对值表示等待的进程数。25 【正确答案】 C【试题解析】 因为最大需求量不会超过 2 个，所以最大作业数为 9，保证不会死锁。26 【正确答案】 C【试题解析】 根据 LRU 算法规则淘汰 3。27 【正确答案】 A【试题解析】 本题考查文件系统的主要目的。

25、28 【正确答案】 C【试题解析】 时间局部性是指一段时间内访问的相同的一段存储单元。29 【正确答案】 B【试题解析】 临界资源是指被多个进程共享的资源，需要互斥访问。30 【正确答案】 A【试题解析】 通道是一种特殊用途的处理器，是硬件。31 【正确答案】 B【试题解析】 除了最短寻找时间优先之外的其余三种算法在移动到磁道的尽头前都是单向移动。32 【正确答案】 A【试题解析】 本题考查文件保护的概念。33 【正确答案】 A【试题解析】 电路交换需要在传输之前建立一个固定的连接，因此其传输的延迟最短。34 【正确答案】 C【试题解析】 频分复用指的是所有用户按同样的时间占用不同的带宽资源，

26、所以复用信号的路数为(10010 3(32+08)10 3=)25 路。35 【正确答案】 B【试题解析】 让 SETUP 报文到达目的地需要四个跳段，除了最后一个跳段外，每个跳段都要被确认，这样就共有 7 个报文。类似地，CONNECT 报文也经历 4个跳段，并且有 4 个确认，共有 8 个报文。这样全部加在一起，总共需要发送 15个报文。36 【正确答案】 D【试题解析】 路由器是网络层的设备，而广播是网络层的功能，而其他三个项都属于网络层以下的设备，所以都不能分割广播域。37 【正确答案】 A【试题解析】 路由器在向输出链路传输分组的第一个比特之前，必须先接收整个分组，这种方式称为存储转

27、发机制。38 【正确答案】 B【试题解析】 TCP 首部中的接收窗口是用来标识接收方的缓冲能力的，避免快速的发送方淹没慢速的接收方。39 【正确答案】 C【试题解析】 UDP 头部长为 8 字节，因此该 UDP 数据报总长度为 8200 字节，以太网帧的最大数据域为 1500，再减去 20 的 1P 头部，得到每个 IP 分片的最大数据域长度应该是 1480，则最后一个数据分片的长度应该是(820051480=)800 字节。40 【正确答案】 A【试题解析】 首先需要将域名解析成 IP 地址，才能利用 IP 地址来建立 TCP 连接，并进行之后的一系列活动。二、综合应用题41-47 小题，共

28、 70 分。41 【正确答案】 算 法基本思想如下：从头至尾遍历单链表，并用指针 p 指向当前结点的前 k 个结点。当遍历到链表的最后一个结点时，指针 p 所指向的结点即为所查找的结点。42 【正确答案】 详 细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针 p1 指向当前遍历的结点，指针 p 指向 pl 所指向结点的前 k 个结点，如果 p1 之前没有 k 个结点，那么 p 指向表头结点。用整型变量 i 表示当前遍历了多少个结点，当 ik 时，指针 p 随着每次遍历，也向前移动一个结点。当遍历完成时，p 或者指向表头结点，或者指向链表中倒数第 k 个位置上的结点。43

29、【正确答案】 算 法描述：int LocateElement(Linklist list，int k)p1=list 一link；p=list；i=1：while(p1)p1=p1-link；i+；if(ik)p=p 一next； 如果 ik，则 p 也往后移if(p=list)return 0； 说明链表没有 k 个结点elseprintf(” d n”，p-44 【正确答案】 void D Traverse(Graph G)int i，v；AreNode*arcStack S：int visitedvexnum；for(i=0：ivexnum ；i+)visitedi=0：InitStac

30、k(S)；for(i=0：ivexnum ；i+)if(!visitedi)如果结点 i 未访问push(S，i)；结点 i 入栈whi45 【正确答案】 访问的顺序为：143276546 【正确答案】 若 不考虑主存未命中的情况，则 Cache 一主存系统的平均访问时间为 T=t1+t2(1 一 p1)注意：若 Cache 失配后 CPU 才开始访存，则平均访问时间计算如上；若 CPU 访问 Cache 和访问主存同时开始，Cache 命中时中断主存访问，则 T=t1p1+t2(1 一 p1)，根据题意，本题应属于前者。47 【正确答案】 若 Cache 命中，则访问时间为 t1，其概率为

31、p1；若 Cache 未命中，主存命中，则访问时间为 t1+t2，其概率为(1 一 p1)p2；若主存未命中，则访问(2ache 用时 t1；主存未命中，并将所需数据块装入主存用时 t3；然后又需一次主存访问来得到所需数据字，用时 t2；总的访问时间为 t1+t48 【正确答案】 微程序采用字段直接编码方式时，应注意操作控制字段中每个互斥组需要额外的一个状态来表示“不发出任何微命令” ，故该机微指令格式中操作控制字段需要 log2(1+1)+log2(3+1)+log2(7+1)+og2(8+1)+log2(12+1)+log2(24+1)=1+2+3+4+4+5=19 此外，该机有 5 个可

32、判定的外部条件，采用编码方式需要 3 位比特位来表示，余下的 321949 【正确答案】 根 据下地址字段长 10 位可知最多有 210=1024 条微指令，故该机控制存储器的最大容量为 32bit1024=32Mb=4MB50 【正确答案】 (1)进程 P0，P1 通过 flagi实现互斥。因为不管 flag0、flag1的初值如何，进程 i 获得 CPU 后，首先使 flagi为 true，然后判断另一进程是否在临界区，这样至少有一个进程在 while 语句中等待。直到另一个进程退出临界区。(2)假设进程 0，先执行 flag0=true，然后 CPIJ 转去执行进程 1 中的 flag1

33、=true，这样两个进程都在 while 循环中空转，系统进入死锁状态，所以不能满足有空让进。(3)由(2)可以看出，也不能保证有限等待。51 【正确答案】 一 个作业的所有分段的副本都保存在辅存上。当其执行时，首先把需要的段装入主存，其他段在调用到时才装入。假设访问段 s 中的 b 单元，首先访问段表，如果段不存在，则进入缺段中断从辅存中调入该段，如果主存中没有空间，还要采取一定置换算法进行置换。如果 b 在段容量之内，且对段有访问权限，则访问位置 1，根据段地址和段内偏移，算出真正主存地址，最终返回访问地址。(类似于分区分配)52 【正确答案】 需 要 TLB，因为段表是定长的，这样可以避免二次寻址，增加访存速度。53 【正确答案】 信道的带宽为 50kbps，那么发送 1000 字节的帧需要 20ms，而传输延时为 250ms。54 【正确答案】 信 号在 20ms 被发送出去，在 270ms 到达接收端，然后在 520ms时发送端收到确认。那么信号的利用率 E=205204 。55 【正确答案】 发 送窗口应该为 52020=26，这样就可以保证在任何时候只要信道空闲，就有数据可以发送。56 【正确答案】 需 要重发 4、5、6、7 号帧，因为回退 N 帧的协议中，接受窗口为 1，那么如果返回了 3 号帧的确认，则说明之前的所有帧都发送成功，因此只需要重发之后的几帧即可。