1、计算机专业（基础综合）模拟试卷 16 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 一个栈的入栈序列是 1，2，3，4，5，则栈的不可能的输出序列是( )。（A）5，4，3，2，1（B） 4，5，3，2，：1（C） 4，3，5，1，2（D）1，2，3，4，52 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储， a1,1 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a8,5 的地址是( )。（A）13（B） 33（C） 18（D）403 在一棵具有 n 个结点的二叉树中，所有
2、结点的空子树个数等于( )。（A）n（B） n-1（C） n+1（D）2n4 在常用的描述二叉排序树的存储结构中，关键字值最大的结点是( )。（A）左指针一定为空（B）右指针一定为空（C）左右指针均为空（D）左右指针均不为空5 由权值为 9、2、5、7 的四个叶子构造一棵哈夫曼树，该树的带权路径长度为( )。（A）23（B） 37（C） 44（D）466 若一个具有 n 个结点、k 条边的非连通无向图是一个森林(nk)，则该森林中必有树的数目是( ) 。（A）k（B） n（C） n-k（D）n+k7 采用邻接表存储的图的广度优先遍历算法类似于树的( )。（A）中根遍历（B）先根遍历（C）后根遍
3、历（D）按层次遍历8 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是( )。（A）G 中有弧 i，V j（B） G 中有一条从 Vi 到 Vj 的路径（C） G 中没有弧 i，V j（D）G 中有一条从 Vj 到 Vi 的路径9 假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，至少要进行的探查次数是( ) 。（A）k-1（B） k（C） k+1（D）k(k+1) 210 下列序列中，满足堆定义的是( )。（A）(100 ，86，48，73，35，39，42，57，66，21)（B） (12，70，33，65，24，56，48，92，
4、86，33)（C） (103，97，56，38，66，23，42，12，30，52，6，26)（D）(5 ，56，20，23，40，38，29，61，36，76，28，100)11 对于一个长度为 n 的任意表进行排序，至少需要进行的比较次数是( )。（A）O(n)（B） O(n2)（C） O(logn)（D）O(nlogn)12 哈佛(Harvard)结构的基本特点是 ( )。（A）采用多指令流单数据流（B）程序和数据在不同的存储空间（C）堆栈操作（D）存储器按内容选择地址13 若二进制定点小数真值是一 01101，机器中表示为 10010，则该数采用的编码方法是 ( ) 。（A）原码（B）
5、补码（C）反码（D）移码14 描述流水线 CPU 基本概念中，正确表述的句子是( )。（A）流水线 CPU 是以空间并行性为原理构造的处理（B）流水线 CPU 一定是 RISC 机器（C）流水线 CPU 一定是多媒体 CPU（D）流水线 CPU 是一种非常经济而实用的时间并行技术15 原码乘法时，符号位单独处理，乘积的符号是( )。（A）两个操作数符号相“与”（B）两个操作数符号相“或”（C）两个操作数符号相“异或”（D）两个操作数中绝对值较大数的符号16 页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如下图所示。假定页面的大小为 8K，图中所示的十进制逻辑地址 9612 经
6、过地址变换后，形成的物理地址 a(十进制 )是( )。 （A）42380（B） 25996（C） 9612（D）819217 在指令系统的各种寻址方式中，获取操作数最快的方式是( )。（A）直接寻址（B）立即寻址（C）寄存器寻址（D）间接寻址18 在计算机体系结构中，CPU 内部包括程序计数器 PC、存储器数据寄存器MDR、指令寄存器 IR 和存储器地址寄存器 MAR 等。若 CPU 要执行的指令为：MOV R0，#100(即将数值 100 传送到寄存器 R0 中 )，则 CPU 首先要完成的操作是( )。（A）100R0（B） 100MDR（C） PCMAR（D）PCIR19 在微指令的编码
7、方式中，若微命令数相同，下列叙述中正确的是( )。I直接控制方式与编码控制方式的微指令长度相等最短编码控制和直接控制方式不影响微指令字长编码控制方式的微指令比直接控制方式的微指令短直接控制的微指令比字段编码的微指令长V字段直接编码的微指令与字段间接编码的微指令长度相等字段间接编码的微指令比字段直接编码的微指令长（A）和 PC（B） I 和 111（C） 和（D）、和20 下列计算机总线属于串行总线的是( )。（A）PCI（B） 1394（C） EISA（D）ISA21 某数码相机内置 128MB 的存储空间，拍摄分辨率设定为 1 6001 200 像素，颜色深度为 24 位，若不采用压缩存储技
8、术，使用内部存储器最多可以存储的照片数是( )。（A）12（B） 25（C） 13（D）2322 中断向量表中保存的是( )。（A）被中断程序的返回地址（B）中断服务程序入口地址（C）中断优先级（D）中断源编码23 对于设计实时操作系统，不是其设计目标的是( )。（A）安全可靠（B）处理机效率（C）及时响应输入（D）快速处理请求24 并发进程在运行时，其推进的相对速度是( )。（A）由进程的程序结构决定（B）由进程自己的代码控制（C）与进程调度策略有关（D）在进程创建时确定的25 两个旅行社甲和已为旅客到某航空公司订飞机票，形成互斥资源的是( )。（A）旅行社（B）航空公司（C）飞机票（D）旅
9、行社与航空公司26 在进程通信中，消息的一般形式为四个部分组成。是( )。（A）发送进程名、接收进程名、消息标示符、消息正文（B）发送进程名、消息标示符、消息长度、消息正文（C）发送进程名、接收进程名、消息长度、消息当前状态（D）发送进程名、接收进程名、消息长度、消息正文27 某计算机系统中内存保护采用基址、限长寄存器的方法来实现，那么，判断是否越界的判别式是( )。（A）0被访问的逻辑地址BCD。下表列出了执行每级中断服务程序所需的时间。 如果以执行中断服务程序的时间作为确定中断优先级的尺度：时间越短优先级越高。 (1)请指出如何为各级中断服务程序设置屏蔽码? (2)如果 A、B、C、D 分
10、别在6s、8s、10s、0s 时刻发出中断请求，请画出 CPU 执行中断服务程序的序列。 (3)基于上题，请计算上述四个中断服务程序的平均执行时间。45 某大学的阅览室共有 300 个座位，同学进入时必须先在管理处用学生证换取座位牌，若座位满了，同学就要在阅览室外等候。当有同学离开时，要到管理处用座位牌换回学生证。请画出流程图，试用一种类语言，利用信号量和 P、V 操作，描述同学进入和离开阅览室的过程。46 某虚拟存储系统中有一个进程共有 6 页(05)，其中代码占 3 页(02)，数据占1 页(3)，数据堆占 1 页(4)，用户栈占 1 页(5)。它们依次存放在外存的22，23，25，26
11、存储块。当前，代码页已经分配在物理内存的 66，67，87 页，数据页为 31，并已经进行了修改。数据堆页还没有分配内存，用户栈分配在 01 页。请问： (1)页表中应该包含哪些项目? 请填写此页表(见下表)。 (2)若内存堆申请内存，因无分配物理内存而产生缺页中断，此时内存无空闲页面，则采用 LRU 页面淘汰算法选中内存的那个页面?操作系统作何处理? 页表又如何变化 ?设当前时刻为虚拟时间 1256。 。 47 主机 A 向主机 B 连续发送了两个 TCP 报文段，其序号分别为 70 和 100。试问：(1)第一个报文段携带了多少个字节的数据?(2)主机 B 收到第一个报文段后发回的确认中的
12、确认号应当是多少?(3)如果主机 B 收到第二个报文段后发回的确认中的确认号是 180，试问 A 发送的第二个报文段中的数据有多少字节?(4)如果 A 发送的第一个报文段丢失了，但第二个报文段到达了 B。B 在第二个报文段到达后向 A 发送确认。试问这个确认号应为多少 ?计算机专业（基础综合）模拟试卷 16 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 此类问题是常见题型。解答的基本原理是：一串数据依次通过一个栈，并不能保证出栈数据的次序总是倒置，可以产生多种出栈序列。一串数据通
13、过一个栈后的次序由每个数据之间的进栈、出栈操作序列决定，只有当所有数据“全部进栈后再全部出栈”才能使数据倒置。事实上，存在一种操作序列“进栈、出栈、进栈、出栈”可以使数据通过栈后仍然保持次序不变。2 【正确答案】 B【试题解析】 这里数组下标从 1 开始，只存储其下三角形元素，在 a8,5 的前面有 7行，第 1 行有 1 个元素，第 2 行有 2 个元素，第 7 行有 7 个元素，这 7 行共有(1+7)72=2 8 个元素，在第 8 行中，a 8,5 的前面有 4 个元素，所以，a 8，5 前有28+4=32 个元素，其地址为 33。3 【正确答案】 C【试题解析】 在一棵具有 n 个结点
14、的二叉树中，每个结点可有两棵子树，共有2n 个子树。其中二叉树的总分支数等于总结点数减 1，即有 n 一 1 棵不空的子树。所以在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于 n+1。4 【正确答案】 B【试题解析】 在二叉排序树的存储结构中，每个结点由三部分构成，其中左(或右)指针指向比结点的关键值小(或大)的结点。关键字值最大的结点位于二叉排序树的最右位置上，因此它的右指针一定为空。5 【正确答案】 C【试题解析】 由权值为 9、2、5、7 的四个叶子构造的哈夫曼树可如下图所示。 该树的带权路径长度=91+72+23+53=44 。6 【正确答案】 C【试题解析】 因为一棵具有
15、 n 个顶点的树有 n 一 1 条边，因此设题目中的森林有m 棵树，每棵树具有顶点数为 Vi(1im)，则 V1+V2+Vm=N 及(V 1 一 1)+(V2 一 1)+(Vm 一 1)=K，所以 n=m+k。7 【正确答案】 D【试题解析】 深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。广度优先搜索遍历类似于树的按层次遍历的过程。或者说，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。8 【正确答案】 D【试题解析】 选项 A、B、C 都是有可能出现的，但是选项 D 是不可能出现的，因为若是 G 中有一条从 Vj 到 Vi 的路径，则在图的拓扑序列中顶点
16、Vj 应该在顶点Vi 之前。9 【正确答案】 D【试题解析】 假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，探查次数最少的情况是第 1 个关键字通过 1 次比较后插入，第 2 个关键字通过2 次比较后插入，第 k 个关键字通过 k 次比较后插入。总的比较次数=1+2+k=k(k+1)2。10 【正确答案】 A【试题解析】 依据堆的定义，将选项中的每个数列分别看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左右子树不空时，根结点的值小于(或大于)左右子树根结点的值。11 【正确答案】 D【试题解析】 在排序过程中，每次比较会有两
17、种情况出现，若整个排序过程中至少需要 t 次比较，则显然会有 2t 种情况，由于 n 个记录总共有 n!种不同的排列，因而必须有 n!种不同的比较路径，于是有：2 tn!，即 tlog2(n!)。因为 log2(n!)nlog2n，所以 tnlog2n。12 【正确答案】 B【试题解析】 哈佛结构的指令和数据是完全分开的，存储器分为两部分，一个是程序存储器，用来存放指令，另一个是数据存储器，用来存放数据。13 【正确答案】 C【试题解析】 真值一 01101，对应的原码表示为 11101，补码表示为10011，反码表示为 10010。移码通常用于表示阶码，不用来表示定点小数。14 【正确答案】
18、 D【试题解析】 在 4 个选项中唯有选项 D 是正确的。选项 A 是指超标量处理机。RISC 机器一定采用流水线技术，而流水线 CPU 不一定就是 RISC 机器。流水线CPU 也不一定是多媒体 CPU。15 【正确答案】 C【试题解析】 原码的符号位为“1”表示负数，为“0”表示正数。原码乘法时，符号位单独处理，乘积的符号是两个操作数符号相“异或”，同号为正，异号为负。16 【正确答案】 B【试题解析】 由于页面大小为 8K，则十进制逻辑地址 9612 处于第 1 虚页中，页内地址一 1420，其对应的实页为第 3 页，故 a=381 92+1420=25996。17 【正确答案】 B【试
19、题解析】 立即寻址是一种特殊的寻址方式，指令中在操作码字段后面的部分不是通常意义上的地址码，而是操作数本身，也就是说数据就包含在指令中，只要取出指令，也就取出了可以立即使用的操作数，不必再次访问存储器，从而提高了指令的执行速度。18 【正确答案】 C【试题解析】 无论运行什么类型的指令，CPU 首先需要取指令，取指令阶段的第一个操作就是将指令地址(程序计数器 PC 中的内容)送往存储器地址寄存器。19 【正确答案】 A【试题解析】 微指令的操作控制字段可分为直接控制法、最短编码法和字段编码法，字段编码法中又可以进一步分为字段直接编码法和字段间接编码法。若微命令数相同，微指令操作控制字段的长度由
20、短至长依次为：最短编码一字段间接编码一字段直接编码一直接控制。操作控制字段短则相应的微指令字长就短。20 【正确答案】 B【试题解析】 1394 是高性能的串行总线。21 【正确答案】 D【试题解析】 颜色深度为 24 位(3 个字节)，每张照片的存储量为160012003B55MB， 128MB55 MB 一 233，所以内置的存储空间最多可存储 23 张照片。22 【正确答案】 B【试题解析】 中断向量表是用来存放中断服务程序的入口地址的。23 【正确答案】 B【试题解析】 本题考查实时操作系统的设计目标。实时操作系统要求能对用户的请求在规定的时间内完成，同时需要保证进程运行的安全性和高可
21、靠性。而处理机的效率不是实时操作系统设计所关心的。24 【正确答案】 C【试题解析】 在进程的一次运行过程中，其代码的执行序列是确定的，即使有循环或转移，对于进程来讲，其运行的轨迹也是确定的，所以对于这样一个确定的运行轨迹，进程自身是可以控制自身前进或停止的，例如可以休眠 10 秒再唤醒等，但是，当这样的进程存在于一个并发系统中时，这种确定性就被打破了。由于系统中存在有大量的可运行的进程，操作系统为了提高计算机的效率，会根据用户的需求和系统资源的数量来自动地进行调度和切换，以保证系统高效地运行。此时，进程由于被调度，打破了原来的固有执行速度，走走停停，因此，进程的相对速度就不受进程自己的控制，
22、而是取决于进程调度的策略。不确定性也是并发系统的一个特征。25 【正确答案】 C【试题解析】 本题考查互斥资源的问题，一张飞机票不能售给不同的旅客，因此飞机票是互斥资源，其它因素只是为完成飞机票订票的中间过程，与互斥资源无关。26 【正确答案】 D【试题解析】 在消息传递系统中，进程间的数据交换是以消息(在计算机网络中又称为报文)为单位的。消息的一般结构形式有发送进程名、接收进程名、消息长度、消息正文。故正确答案为选项 D。27 【正确答案】 A【试题解析】 本题考查存储保护的方法。考查基址、限长寄存器方式下是如何进行越界判断的。在基址、限长寄存器的保护方式下，系统为每个并发进程设置一个基址寄
23、存器和一个限长寄存器，限长寄存器保存的是进程的长度，所以有关系式：逻辑地址next=la； 置三个循环链表为空表ld 一next=ld；lo 一rlext=lo；while(L!=NULL) 分解原链表r=L；L=L 一next ； L 指向待处理结点的后继if(r 一data=a&r 一datadata=A&r 一datanext=la 一next； 处理字母字符la 一next=r；else if(r 一data=0&r 一datanext=ld 一next； 处理数字字符ld 一next=r；else r 一next=lo 一next； 处理其它符号lo 一next=r；【试题解析】 将
24、一个结点数据域为字符的单链表，分解成含有字母字符、数字字符和其它字符的三个循环链表，首先要构造分别含有这三类字符的表头结点。然后从原链表第一个结点开始，根据结点数据域是字母字符、数字字符和其它字符而分别插入到三个链表之一的链表。注意：不要因结点插入新建链表而使原链表断链。另外，题目并未要求链表有序，插入采用“头插法”，每次插入的结点均成为所插入链表的第一元素的结点即可。43 【正确答案】 (1)PC=14 位，IR=18 位 AC 0=AC1=16 位，R 0R 3=16 位 IAR=14位，IDR=18 位 DAR=16 位，DDR=16 位 (2)加法指令“ADD X(Ri)”是一条一地址
25、指令，其中一个操作数来自 AC0，另一个操作数在 DM 中，其地址由通用寄存器的内容(Ri)加上指令格式中的 X 量值决定。其指令周期流程图如下图所示，相应的微程序控制信号标在框图外面。 【试题解析】 (1)由于指令存储器 IM 的容量为 16384*18，数据存储器 DM 的容量为 65536*16，可以推出相应寄存器的位数。(2)根据数据通路，可以写出加法指令的微操作控制信号。44 【正确答案】 (1)如果以执行中断服务程序的时间长短来确定中断优先级(时间越短优先级越高)，可知中断处理的次序为：CADB。中断服务程序屏蔽码见下表。(2)根据各级中断源发出的中断请求信号的时刻，画出 CPU
26、执行中断服务程序的序列，如下图所示。 中断处理的优先级别是 CADB。0s 时， D 请求来到，由于没有其他的中断请求，所以开始执行中断服务程序 D。第 6s 时，A 请求来到，A 的优先级高于 D，转去执行中断服务程序 A。第 8s 时，B 请求来到，由于 B 的优先级低于 A，所以不响应 B 请求，继续执行中断服务程序 A。第 10s 时，C 请求来到，C 的优先级最高，虽然此时中断服务程序 A 还没有结束，也必须暂停转去执行中断服务程序 C。中断服务程序 C 所需时间为 3s，当第 13s 时，中断服务程序 C 执行完毕，返回执行中断服务程序 A。第 14s 时，中断服务程序 A 执行完
27、毕(总共执行时间 5s)，返回执行中断服务程序 D。第 20s 时中断服务程序 D 执行完毕(总共执行时间 12s)，返回现行程序。因为 B 请求还存在，所以此时开始执行中断服务程序 B，直至第 3 5s 时结束(总共执行时间 3 5s)。 (3)由于在 35s 时间内，完成了 4 级中断的处理，所以平均执行时间=354=875s。【试题解析】 硬件排队电路次序又称中断响应次序，它是不可以改变的，在不改变硬件排队电路的前提下，通过改变中断屏蔽字可以改变中断处理的优先级，使原级别较低的中断源变成较高的级别，这便称为中断升级。实际上中断升级是一种动态改变优先级的方法。45 【正确答案】 同学进入阅
28、览室的同步算法如下流程图所示。 typedef int semaphore； semaphore mutex=1； semaphore sit=300 ； void student() P(sit)； P(mutex)； mark_sit() ； V(mutex)； reading() ； P(mutex) ； release_sit() ； V(mutex)；V(sit)； leave()； 【试题解析】 本题考查进程间同步的问题。用信号量是可以解决同步问题的。假设同学有很多，晚自习时都希望在图书馆的阅览室占到一个座位，但是，阅览室的座位数是有限的，我们不妨设该数值为一个资源信号量，用它来控
29、制进入阅览室的同学的数量。另外设互斥量 mutex，代表在管理处换取座位牌时，管理处的临界资源，初始值为 1，用来防止两个及以上的同学同时换取座位牌而造成混乱。46 【正确答案】 (1)页表填写见下： (2)当内存堆申请内存，产生缺页中断，采用 LRU 页面淘汰算法选中数据页，操作系统根据页表的指示，该页已经被改写了，所以首先要将该页写回外存块中，修改该页表，然后将该页分配给数据堆页，重新修改数据堆页的页表，返回到缺页中断的那条指令，继续执行。修改的页表如下： 逻辑 4、5 页只要从来没有被换出到交换区，就没有外存块号。【试题解析】 内存计算的变化很多，本题主要考查考生对内存管理的理解。根据题
30、意，本系统采用的是虚拟存储系统，因此立即可以想到，进程一定是部分调入。从题目给出的条件中可知，进程共有 6 页(05)，其中代码占 3 页(02)，数据占1 页(3)，数据堆占 1 页(4)，用户栈占 1 页(5)。这个条件显然是虚拟存储管理的实际情况，进程的逻辑页有 6 页，因此分配的虚拟空间也是 6 页。按题意，页面依次存放在外存的 22，23，25，26 存储块。这个条件告诉我们，进程对应的外存是 4块，显然，有 2 页是进程运行过程中产生的，一般数据堆和栈是在运行过程中产生的，在虚拟存储管理中，数据堆和栈对应的外存应该在对换区上，而且，只有在换出时才分配，所以在外存地址中一般是不包括堆
31、和栈的。题目还提供了当前代码页已经分配在物理内存的 66，67，87 页，数据页为 31，并已经进行了修改。此信息说明虚拟存储管理已经分配了物理内存页框，而且，数据页还被修改了，那么应该在页表中表现出来。题目还告诉我们数据堆页还没有分配内存，显然还没有使用。用户栈分配在 01 页。表示栈也已经分配内存页框了。据此就可以填写表格了。上面已经提到，数据堆还没有分配，当用到该页时，由于不在内存故产生缺页中断，题目的意思是在本进程内进程页面置换。当采用 LRU 算法时，考虑 LRU 算法是最近最久未使用的页面淘汰掉，从给定的条件看，数据页 3 被引用的时间为1020，最久未使用，而且，记录的时间为引用
32、时间，所以该页还是最近未使用，故这页被选中淘汰，该页框被分配给数据堆页，解答如下，存在位表示是否在内存，修改位根据题意，只有数据页修改了，故为 1，引用位表示该页的使用情况，在没有特别说明的情况下，只要该页面被调入内存，对虚拟存储管理来说，该页一定被引用。保护方式代码页只能读和运行，数据页可以读写，栈可以读写，外存块号和内存页框号由题目给出，填写如下。47 【正确答案】 (1)第一个报文段携带了 30 个字节的数据。(2)主机 B 收到第一个报文段后发回的确认中的确认号应当是 100。(3)如果主机 B 收到第二个报文段后发回的确认中的确认号是 180，A 发送的第二个报文段中的数据有 80
33、字节。(4)如果 A 发送的第一个报文段丢失了，但第二个报文段到达了 B。B 在第二个报文段到达后向 A 发送确认。这个确认号应为 70。【试题解析】 本题考查 TCP 的可靠连接，重点是报文段的确认字段：(1)第二个报文段的开始序号是 100，说明第一个报文段的序号是 70 到 99，故第一个报文段携带了 30 个字节的信息。(2)由于主机已经收到第一个报文段，即最后一个字节的序号应该是 99，故下一次应当期望收到第 100 号字节，故确认中的确认号是 100。(3)由于主机 B 收到第二个报文段后发回的确认中的确认号是 180，说明已经收到了第 1 79 号字节，也就说明第二个报文段的序号
34、是从 100 到 179，故第二个报文段有 80 字节。(4)确认的概念就是前面的序号全部收到了，只要有一个没收到，都不能发送更高字节的确认，所以主机 B 应该发送第一个报文段的开始序号，即 70。特别注意在使用 TCP 传输数据时，如果有一个确认报文段丢失了，是不是一定会引起与该确认报文段对应的数据的重传?答案是不一定，例如某个确认丢失了，但是在该报文的重传计时器到时之前，却收到了更高序号的确认，因为如果接收方没有收到低号的报文是不可能会发出高序号的确认的，所以说发送方此时不会在重传那个丢失确认的报文了。例如主机 A 连续发送两个报文段： (SEQ=92，共 8 字节的数据)和(SEQ=100 ，共 20 字节的数据)，均正确达到主机 B。B 连续发送两个确认：(ACK=100)和(ACK=120)，但是前者在传送时丢失了。假如 A 在第一个报文段超时之前收到了对第二个报文段的确认，此时 A 知道，120 号之前的所有字节(当然包括第一个报文段中的所有字节)均已被 B 正确接收，因此 A 不会再重传第一个报文段。
