1、计算机专业（基础综合）模拟试卷 5 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下列有关数据存储结构的叙述中，正确的是( )。（A）顺序存储方式只能用于存储线性结构（B）顺序存储方式的优点是占用存储空间小，插入、删除等操作效率高（C）链表的每个结点中都恰好含有一个指针（D）Hash 存储的基本思想是由关键词的值决定数据的存储地址2 以数组 Datam+1作为循环队列 SQ 的存储空间，front 为头指针，rear 为队尾指针，则执行出队操作的语句是( )。（A）front=front+1（B） fron
2、t=(front+1)m（C） Iront=(front+1)(m+1)（D）rear=(rear+1)m3 设 n、m 为一棵二叉树上的两个结点，在中序遍历时， n 在 m 前的条件是( )。（A）n 在 m 右方（B） n 是 m 祖先（C） n 在 m 左方（D）n 是 m 子孙4 前序遍历和后序遍历结果相同的二叉树为( )。（A）只有根结点的二叉树（B）根结点无左孩子的二叉树（C）根结点无右孩子的二叉树（D）所有结点只有左子树的二叉树5 已知一个线性表为(38，25，74，63，52，48)，假定采用 H(K)=K mod 7 计算散列地址进行散列存储，若利用线性探测的开放定址法处理冲
3、突，则在该散列表上进行查找的平均查找长度为( )；若利用链地址法处理冲突，则在该散列上进行查找的平均查找长度为( ) 。（A）15，1（B） 17，32（C） 2，43（D）23，766 关于 AVL(平衡二叉树) ，下列说法错误的是( )。（A）左子树与右子树高度差最多为 1（B）插入操作的时间复杂度为 O(log n)（C）平衡二叉树是二叉排序树中的一种（D）使用平衡二叉树的目的是为了节省空间7 下面关于对图的操作的说法不正确的是( )。（A）寻找关键路径是关于带权有向图的操作（B）寻找关键路径是关于带权无向图的操作（C）连通图的生成树不一定是唯一的（D）带权无向图的最小生成树不一定是唯一
4、的8 在文件局部有序或文件长度较少的情况下，最佳的内部排序方法是( )。（A）直接插入排序（B）冒泡排序（C）简单选择排序（D）堆排序9 下列( ) 是一个堆。（A）19，75，34，26，97，56（B） 97，26，34，75，19，56（C） 19，56，26，97，34，75（D）19，34，26，97，56，7510 以下有关二叉树的描述中正确的是( )。 (1)二叉树按某种右岸序线索化后，任一结点均有指向其前驱和后继的线索(2)二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面（A）只有(1)（B）只有 (2)（C） (1)和(2)（D）以上全不对11 某定点机字长 n 位
5、，其中包含一位符号位。若采用补码一位乘(Booth 算法) 实现乘法运算，则最多需要做( )次移位运算。（A）n-1（B） n（C） n+1（D）n+212 若某浮点机基数为 4，尾数采用补码表示，则该浮点机的规格化尾数形式为( )。（A）最高两位数值位与符号位相反（B）最高两位数值位与符号位相同（C）最高两位数值位至少有一位与符号位相反（D）最高两位数值位至少有一位与符号位相同13 用 74181和 74182 芯片构成小组内并行进位，小组间并行进位，大组间串行进位的 32 位 ALU，需要 74182 芯片的片数为( )。（A）0（B） 1（C） 2（D）314 某机字长 32 位，它的存
6、储容量为 256 MB，按字节编址，则它的寻址范围大小为( )。（A）256 MB（B） (256-1)MB（C） 64 MB（D）(64-1)MB15 采用了虚拟存储器的计算机系统中，逻辑地址与物理地址相比( )。（A）两者位数相等（B）逻辑地址位数多（C）物理地址位数多（D）无法判断16 下列关于 RISC 的叙述中，错误的是 ( )。（A）RISC 普遍采用微程序控制器（B） RISC 大多数指令在一个时钟周期内完成（C） RISC 的内部通用寄存器数量相对 CISC 多（D）RISC 的指令数、寻址方式和指令格式种类相对 CISC 少17 下列寻址方式中，执行速度最快的是( )。（A）
7、立即数寻划（B）直接寻址（C）间接寻址（D）寄存器间接寻址18 CPU 在响应中断的过程中，保护现场的工作由( )完成。（A）中断隐指令（B）中断服务程序（C） A 或 B 之一完成（D）A 和 B 共同完成19 CPU 的中断周期前可能是( )。（A）取指周期（B）间址周期（C）执行周期（D）以上都有可能20 数据总线、地址总线、控制总线是根据总线( )来划分的。（A）传送内容的不同（B）所处位置的不同（C）连接部件的不同（D）所使用标准的不同21 采用 DMA 方式传送数据时，每传送一个数据要占用( )。（A）一个指令周期（B）一个机器周期（C）一个存取周期（D）一个时钟周期22 中断系统
8、中，中断屏蔽字的作用是( )。（A）暂停对所有中断源的响应（B）暂停对所有可屏蔽中断源的响应（C）暂停对某些可屏蔽中断源的响应（D）暂停对主存的访问23 分页式虚拟存储管理系统中，一般来说页面的大小与可能产生缺页中断的次数( )。（A）成正比（B）成反比（C）无关（D）成固定比值24 请求分页存储管理方案中，如果所需的页面不在内存中，则产生缺页中断，它属于( )中断。（A）硬件故障（B） IO（C）外（D）程序中断25 页式虚拟存储管理的主要特点是( )。（A）不要求将作业装入到主存的连续区域（B）不要求将作业同时全部装入到主存的连续区域（C）不要求进行缺页中断处理（D）不要求进行页面置换26
9、 分区分配内存管理方式的主要保护措施是( )。（A）界地址保护（B）程序代码保护（C）数据保护（D）栈保护27 在存储系统管理中，采用覆盖与交换技术的目的是( )。（A）节省主存空间（B）物理扩充主存容量（C）提高 CPU 效率（D）实现主存共存28 既考虑作业等待时间又考虑作业执行时间的调度算法是( )。（A）响应比高者优先（B）短作业优先（C）优先级调度（D）先来先服务29 下列死锁的论述中，正确的论述是( )。（A）由于产生死锁的基本原因是系统资源不足，因而预防死锁最常用方法，是根据系统规模，配置足够的系统资源（B）由于产生死锁的另一个基本原因是进程推进顺序不当，因而预防死锁的常用方法，
10、是使进程的推进顺序合法（C）因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的常用方法，是防止系统进入不安全状态（D）可以通过破坏产生死锁的四个必要条件之一或其中几个方法，来预防发生死锁30 设 m 为同类资源数，n 为系统中并发进程数。当 n 个进程共享 m 个互斥资源时，每个进程的最大需求是 w，则下列情况会出现系统死锁的是 ( )。（A）m=2 ， n=1，w=2（B） m=2，n=2，w=1（C） m=4，n=3，w=2（D）m=4 ， n=2，w=331 MS-DOS 中的文件物理结构采用 ( )。（A）连续结构（B）链接结构（C）索引结构（D）哈希表32 通过硬件和软件的功
11、能扩充，把原来独占的设备改造成若干用户共享的设备，这种设备称为( ) 。（A）系统设备（B）存储设备（C）用户设备（D）虚拟设备33 ICMP 在 TCPIP 协议集中属于( )。（A）数据链路层（B）传输层（C）网络层（D）应用层34 采用 8 种相位，每种相位各有两种幅度的 QAM 调制方法，在 4 800 波特率的信号传输速率下能达到的数据传输速率为( )。（A）4 800 bps（B） 9 600 bps（C） 19 200 bps（D）38 400 bps35 两个网段在物理层进行互联时要求( )。（A）数据传输率和数据链路层协议都不相同（B）数据传输率和数据链路层协议都相同（C）数
12、据传输率相同，数据链路层协议可不同（D）数据传输率可不同，数据链路层协议相同36 一条线路带宽为 1 Mbps，往返时延为 45 ms，假设数据帧的大小为 1 000 字节。若采用停一等协议，实际的数据率是( )。（A）15 Kbps（B） 15 Kbps（C） 151 Kbps（D）1 510 Kbps37 若数据链路层采用回退 N 滑动窗口字而已，发送帧的序列号用 7 bit 表示，发送窗口的最大值为( ) 。（A）7（B） 64（C） 127（D）12838 以下地址中的( ) 和 86320012 匹配。（A）8633224123（B） 867965216（C） 865811974（D
13、）866820615439 在 TCP 连接中，如果已经接收了 1 000 字节的数据，那么在发送回的数据包头中，确认号为( ) 。（A）1 000（B） 1 001（C） 999（D）99840 FTP 客户和服务器间传递 FTP 命令时，使用的连接是 ( )。（A）建立在 TCP 之上的控制连接（B）建立在 TCP 之上的数据连接（C）建立在 UDP 之上的控制连接（D）建立在 UDP 之上的数据连接二、综合应用题41-47 小题，共 70 分。41 42 图的 D 搜索类似于 BFS，不同之处在于使用栈代替 BFS 中的队列，入出队列的操作作为入出栈的操作，即当一个顶点的所有邻接结点被搜
14、索后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构，写一个 D 搜索算法；(2)用 D 搜索方法搜索下图，设初始出发的结点为 1，写出顶点的访问次序，当从某顶点出发搜索它的邻接点时，请按邻接点序号递增顺序搜索，以使答案唯一。43 某计算机采用 Cache 一主存一磁盘三级存储系统。Cache 的访问时间为 t1ns，命中率为 p1；若 Cache 未命中，CPU 需直接访问主存，访问时间为 t2ns，主存命中率为 p2；若所需数据字不在主存中，则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需时 t3ns。 (1)若不考虑主存未命中的情况，则 Cache 一
15、主存系统的平均访问时间为多少? (2)Cache 一主存一磁盘系统的平均访问时间为多少?44 某计算机采用微程序控制方式，微指令字长 32 位，采用字段直接编码的控制方式，共有 55 个微命令，可分为 6 个互斥组，分别包含 1、3、7、8、12、24 个微命令。另外，该机共有 5 个可判定的外部条件，采用断定方式形成后续微指令地址。(1)设计该机微指令的格式，要求给出各字段的位数。(2)结合(1)的微指令格式，计算该机控制存储器的最大容量。45 试就 Mutual Exclusion、Progress、Bounded Waiting 论述以下解决双进程临界区问题的算法是错误的：Process
16、 PO：doflag0=true；While(flag1)；Critical sectionFlag0=false；Remainder section；while(1)；process P1：doflag1=true；While(flag0)；Critical sectionFlag1=false；Remainder section；while(1)；46 Demand paging 算法是 paging 算法在虚拟存储空间管理的扩展。其主要的改进是：仅当需要访问某页面时，如果它不在内存，把它调入内存。按照这个思路，将segmentation 算法(段式存储管理算法 )扩展到虚拟存储空间管理，
17、也可以产生类似的算法，不妨称之为 demand segmentation。(1)请给出相应算法，并简要说明。(2)Demand paging 算法一般都用 TLB。请问 demand segmentation 算法需要类似的装置吗?为什么 ?47 如下图所示为一个带宽为 50 kbps 的卫星信道，它的往返传播延时为 500 ms。现在有一个网络架设在该信道上，网络使用 1 000 bit 长度的帧和停止一等待协议，请回答如下问题： (1)该网络发送一帧的发送延时和传输延时分别是多少? (2)网络的利用率是多少? (3)为了使网络的利用率达到 100，需要使用窗口是多大的回退N 帧协议? (4
18、)使用回退 N 帧协议的网络中，如果发送了 07 号帧，而发送端只收到了 0、3 号帧的回复，需要重新发送哪些帧?计算机专业（基础综合）模拟试卷 5 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 顺序存储方式除了用于存储线性结构外，还能存储数组或完全二叉树等非线性结构。插入、删除操作时，由于要移动大量的数据，执行效率低，链表的形式有单链表、双链表和多重链表，除了单链表外，其他链表中的结点需要两个以上的指针。2 【正确答案】 C3 【正确答案】 C【试题解析】 中序遍历时，先访问左
19、子树，再访问根结点。n 在 m 前，则 n 必须在 m 的左子树中。因此本题答案为 C。4 【正确答案】 A【试题解析】 使用特值法，排除 B、C、D 选项。5 【正确答案】 C【试题解析】 若利用线性探测的开放定址法处理冲突，发生 0 次冲突的关键字有3 个，1 次冲突的 1 个，2 次冲突的 1 个，3 次冲突的 1 个，因而在该散列表上进行查找的平均查找长度为 ASL=(3*1+1*2+1*3+1*4)6=2；若利用链地址法处理冲突，同一链表上有 1 个元素的线性链表有 2 个，有 2 个元素的线性链表有 2 个，因此ASL=(4*1+2*2)6=43。6 【正确答案】 D【试题解析】
20、平衡二叉树没有节省空间，引入其目的是防止排序二叉树左、右子树高度失衡。7 【正确答案】 B8 【正确答案】 A9 【正确答案】 D【试题解析】 完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树来判断答案为 D。10 【正确答案】 B11 【正确答案】 A12 【正确答案】 C13 【正确答案】 C【试题解析】 74181 是内部并行进位的 4 位 ALU 芯片，74182 是 4 位先行进位芯片，故 4 片 74181 和 l 片 74182 可构成小组内并行进位，小组间并行进位的 16 位ALU；又题目要求构成小组内并行进位，大组内
21、串行进位的 32 位 ALU，故只需将2 个前述 16 位 ALU 串联即可，共需 2 片 74182 芯片，选 C。14 【正确答案】 A【试题解析】 该机存储容量为 256 MB，又按字节编址，故其寻址范围为 0256 M-1，寻址空间大小为 256 MB。15 【正确答案】 B【试题解析】 虚拟存储器主要是为了解决存储系统的容量问题，引入虚拟存储器后，程序员编程可使用的虚拟空间要远大于物理内存容量，故逻辑地址位数要大于物理地址位数，选 B。16 【正确答案】 A【试题解析】 与 CISC 相比，RISC 的特点是：指令数量和寻址方式少，指令格式简单，大多数指令在一个时钟周期内完成；CPU
22、 内部通用寄存器数量多；控制器多采用硬布线逻辑，且多采用流水线技术，执行速度较快。故 A 选项错误。17 【正确答案】 A【试题解析】 四个选项中，只有立即数寻址不需要访存，故其执行速度最快。18 【正确答案】 D【试题解析】 保护现场包括保护程序断点和保护 CPU 内部各寄存器内容，其中，保护程序断点的任务由中断隐指令完成；而保护 CPU 内部其他寄存器的任务由中断服务程序来完成，故 D 为正确选项。19 【正确答案】 C【试题解析】 CPU 在一个指令周期结束，即一条指令的执行周期结束后检查是否有中断请求，如果有则进入中断周期，故中断周期前只可能是执行周期。20 【正确答案】 A【试题解析
23、】 根据总线上传输内容的不同，可将总线分为数据总线、地址总线和控制总线。21 【正确答案】 C【试题解析】 采用 DMA 方式传送数据时，每传送一个数据需要占用 CPU 一个存取周期，即在该存取周期内，CPU 不能访存。22 【正确答案】 C【试题解析】 CPU 通过设置中断屏蔽字来中断对某些可屏蔽中断源的响应。23 【正确答案】 B【试题解析】 页面越小发生缺页中断次数的可能性越大。24 【正确答案】 D25 【正确答案】 B26 【正确答案】 A【试题解析】 界地址寄存器来保护内存管理方式的主要措施。27 【正确答案】 A【试题解析】 覆盖和交换是虚拟上扩充内存的技术。28 【正确答案】
24、A【试题解析】 响应比=(等待时间+执行时间)执行时间。29 【正确答案】 D【试题解析】 A：不可能根据系统的规模，配置足够的系统资源，因为系统的资源是有限的。B：这种方法不能保证死锁不发生，而且进程推进过程很复杂，实现合理的顺序不太可能。C：系统进入不安全状态不一定会产生死锁，防止系统进入不安全状态不太可能，故不是常用的方法。30 【正确答案】 D【试题解析】 当 2 个进程已经拥有 2 个资源，都申请第 3 个资源时，导致死锁。31 【正确答案】 B32 【正确答案】 D33 【正确答案】 C【试题解析】 ICMP 在 TCPIP 协议集中是属于 IP 层的，即属于网络层。34 【正确答
25、案】 C【试题解析】 QAM 调制是一种多元制的振幅相位混合调制方法。题目中有 8 种相位，每种相位各有两种幅度的 QAM 调制方法，共有 16 种状态，所以每个 Baud为 4 位。由于是 4 800 波特率的信号传输速率，因此数据传输速率是 19 200 bps。35 【正确答案】 C【试题解析】 数据传输率是物理层的重要参数，两个网段在物理层进行互联，数据传输率必须相同。如果在数据链路层互联，则要求数据链路层协议也相同。36 【正确答案】 C【试题解析】 往返时延为 45 ms，发送一帧的时间是 810001 000 000s。实际的数据率是 81 000(81 0001000 000+
26、450001)=150 943(bps)151(Kbps)。37 【正确答案】 C【试题解析】 7 位的发送序列号，最大可以有 128 个序列，采用回退 N 帧的协议，发送窗口的最大值应该是最大序列号减 1，即 127。38 【正确答案】 A【试题解析】 观察地址的第二个字节 032=010 0000，前缀 12 位，说明第二个字节的前 4 位在前缀中。给出的 4 个地址的第二字节的前 4 位分别是：0010，0100，OO11 和 0100，故只有 A 是匹配的。39 【正确答案】 B【试题解析】 确认号表示接下来希望接收数据的序列号，成功接收 1 000 字节之后，TCP 连接希望接收 1
27、 001 号字节，所以答案是 1 001。40 【正确答案】 A【试题解析】 TCP 的控制连接用来传输控制命令，数据连接用来传输文件。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 (1)算法基本思想如下：从头至尾遍历单链表，并用指针 p 指向当前结点的前 k 个结点。当遍历到链表的最后一个结点时，指针 p 所指向的结点即为所查找的结点。(2)详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针 p1 指向当前遍历的结点，指针 p 指向 p1 所指向结点的前 k 个结点，如果p1 之前没有 k 个结点，那么 p 指向表头结点。用整型变量 i 表示当前遍历
28、了多少个结点，当 ik 时，指针 p 随着每次遍历，也向前移动一个结点。当遍历完成时，p 或者指向表头结点，或者指向链表中倒数第 k 个位置上的结点。(3)算法描述：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(“dn“，p- data)；return 1；42 【正确答案】 (1)void D_Traverse(Graph
29、G)int i，v；ArcNode*arc；Stack S：int visitedvexnum；for(i=0；i vexnum；i+)visitedi=0；InitStack(S)；for(i=0；i vexnum；i+)if(!visitedi)如果结点 i 未访问push(S，i)；结点 i 入栈while(!StackEmpty(S)pop(S，v)；visitedv=1；Visit(v)；出栈，将栈顶元素赋值给 vfor(arc=Gifirstarc；arc!=NULL ；arc=arc- nextarc)if(!visitedarc-adjvex)对于结点 v 的所有邻接结点，若未
30、访问，就入栈push(S，arc-adjvex) ；visitedv=1； (2)访问的顺序为： 143276543 【正确答案】 (1)若不考虑主存未命中的情况，则 Cache 一主存系统的平均访问时间为 T=t 1+t2(1-p1) 注意：若 Cache 失配后 CPU 才开始访存，则平均访问时间计算如上；若 CPU 访问 Cache 和访问主存同时开始，Cache 命中时中断主存访问，则 T=t1p1+t2(1-p1)，根据题意，本题应属于前者。 (2)若 Cache 命中，则访问时间为 t1，其概率为 p1； 若 Cache 未命中，主存命中，则访问时间为 t1+t2，其概率为(1-p
31、1)p2；若主存未命中，则访问 Cache 用时 t1；主存未命中，并将所需数据块装入主存用时 t3；然后又需一次主存访问来得到所需数据字，用时 t2；总的访问时间为 t1+t2+t3；其概率为 (1-p1)(1-p2)。 故 Cache主存磁盘系统的平均访问时间为 T=t1p1+(t1+t2)(1-p1)p2+(t1+t2+t3)(1-p1)(1-p2)=t1+t2(1-p1)+t3(1-p1)(1-p2)44 【正确答案】 (1)微程序采用字段直接编码方式时，应注意操作控制字段中每个互斥组需要额外的一个状态来表示“不发出任何微命令” ，故该机微指令格式中操作控制字段需要 log 2(1+1
32、)+log2(3+1)+log2(7+1)+log2(8+1)+log2(12+1)+log2(24+1) =1+2+3+4+4+5 =19 此外，该机有 5 个可判定的外部条件，采用编码方式需要 3 位比特位来表示，余下的 32-19-3=10 位为下地址字段，综上，该机微指令格式如下：(2)根据下地址字段长 10 位可知最多有 210=1 024 条微指令，故该机控制存储器的最大容量为 32 bit1 024=32 Mb=4 MB45 【正确答案】 (1)进程 P0，P1 通过 flagi实现互斥。因为不管 flag0、flag1的初值如何，进程 i 获得 CPU 后，首先使 flagi为
33、 true，然后判断另一进程是否在临界区，这样至少有一个进程在 while 语句中等待，直到另一个进程退出临界区。(2)假设进程 0，先执行 flag0=true，然后 CPU 转去执行进程 1 中的 flag1=true，这样两个进程都在 while 循环中空转，系统进入死锁状态，所以不能满足有空让进。(3)由(2)可以看出，也不能保证有限等待。46 【正确答案】 (1)一个作业的所有分段的副本都保存在辅存上。当其执行时，首先把需要的段装入主存，其他段在调用到时才装入。假设访问段 s 中的 b 单元，首先访问段表，如果段不存在，则进入缺段中断从辅存中调入该段，如果主存中没有空间，还要采取一定
34、置换算法进行置换。如果 b 在段容量之内，且对段有访问权限，则访问位置 1，根据段地址和段内偏移，算出真正主存地址，最终返回访问地址。(类似于分区分配)(2)需要 TLB，因为段表是定长的，这样可以避免二次寻址，增加访存速度。47 【正确答案】 (1)信道的带宽为 50 kbps，那么发送 1 000 字节的帧需要 20 ms，而传输延时为 250 ms。(2)信号在 20 ms 被发送出去，在 270 ms 到达接收端，然后在 520 ms 时发送端收到确认。那么信号的利用率 E=205204。(3)发送窗口应该为 52020=26 ，这样就可以保证在任何时候只要信道空闲，就有数据可以发送。(4)需要重发 4、5、6、7 号帧，因为回退 N 帧的协议中，接受窗口为 1，那么如果返回了 3 号帧的确认，则说明之前的所有帧都发送成功，因此只需要重发之后的几帧即可。
