1、计算机专业（基础综合）模拟试卷 31 及答案与解析一、单项选择题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） n1 （C） n1 （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） nk （D）nk7 采用邻接表存储的图的广度优先遍历算法类似于树的( )。（A）中根遍历 （B）先根遍
3、历（C）后根遍历 （D）按层次遍历8 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是( )。（A）G 中有弧 i，v j （B） G 中有一条从 Vi 到 Vj 的路径（C） G 中没有弧 i，V j （D）G 中有一条从 Vi 到 Vj 的路径9 假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，至少要进行的探查次数是( ) 。（A）k1 （B） k （C） k1 （D）k(k 1)210 下列序列中，满足堆定义的是( )。（A）(100 ，86，48，73，35，39，42，57，66，21)（B） (12，70，33，65，24
4、，56，48，92，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(log 0；i)longpathipathi；longpathlenpathlen；elsepath：pathlenbdata； 将当前结点放入路径中pathlen； 路径长度增 lLongpath(bIchil dpath，pa 七 hlen，longpath，longpath
5、len)； 递归扫描左子树Longpath(brchil dpath，pathlen，longpath，longpathlen) ； 递归扫描右子树pathen； 环境恢复【试题解析】 采用 path 数组保存扫描到当前结点的路径，pathlen 保存扫描到当前结点的路径长度，longpath 数组保存最长的路径，longpathlen 保存最长路径长度。当 b 为空时，表示当前扫描的一个分支已扫描完毕，将 pathlen 与longpathlen 进行比较，将较长路径及路径长度分别保存在 longpath 和 longpathlen中。43 【正确答案】 (1)选片译码逻辑如下图所示。 (2
6、)8 片 RAM 的寻址范围分别是：0000H1FFFH 、2000H 3FFFH、4000H5FFFH 、6000H 7FFFH、8000H 9FFFH、A000HBFFFH、C000H DFfFH 和 E000HFFFFH 。(3)说明译码器有误，输出始终为低。因该输出接至第 3 片 RAM 的 端，该片对应的地址范围是4000H5FFFH ，故不论往哪片 RAM 存放 8K 数据，该存储芯片始终被选中，所以都有与之相同的数据。(4)说明 y0 输出始终为高。因 RAM 的片选信号时低电平有效，故用 作片选信号的存储芯片(对应 0000H1FFFH 地址范围)不能读写，而其他芯片可以读写。
7、(5)若发现 A13 与 CPU 断线，并搭接到低电平的故障，则信号均不可能输出 0，故第 2、4、6、8 片 RAM 始终不被选中。(6)说明译码器的 C 输入端始终为低，可以检查一下 A15 是否搭接到低电平上。【试题解析】 (3)(6) 中出现的问题都是由于译码器连接上的问题(短路或断路)造成的，使得某些片选信号始终被选中或始终不被选中。归纳总结 全译码法将除片内寻址外的全部高位地址线都作为地址译码器的输入，译码器的输出作为各芯片的片选信号，将它们分别接到存储芯片的片选端，以实现对存储芯片的选择。全译码法的优点是每片(或组)芯片的地址范围是唯一确定的，而且是连续的，也便于扩展，不会产生地
8、址重叠的存储区。解题技巧 首先确定片选电路以及各个芯片的地址分配，然后分析各种出错情况，分别找出出错的原因。44 【正确答案】 (1)MOV X(R 0)，Y(R 1) PCMAR，Read ；取指令 MMDRIR PC1PC PCMAR，Read ；取源操作数形式地址 MMDRC PC1PC CR 0MAR， Read ；形成源操作数有效地址，并取源操作数 MMDRC ；源操作数暂存 C 中 PCMAR ，Read ；取目的操作数形式地址 MMDRD PC1PC DR 1MAR ；形成目的操作数有效地址 CMDR ；将源操作数送存储器数据寄存器 MDRM，write ；将源操作数写入目的有效
9、地址中 (2)COM(R 0) PCMAR，Read ；取指令 MMDRIR PClPC R01R 0，R 01MAR，Read ；修改 R0 的内容(源和目的操作数地址) MMDRD ；取出源操作数 DMDR ；将源操作数取反 MDRM，write ；写入目的地址中【试题解析】 数据传送指令占 3 个字，第 1 个字是操作码和寄存器编号；第 2 个字是参数 X，为源操作数的形式地址；第 3 个字是参数 Y，为目的操作数的形式地址，源和目的操作数地址均采用变址寻址，指令的含义是：(R 0)X)(R 1)Y。 求反指令仅占 1 个字，自减型寄存器寻址是先修改寄存器的内容(1)，再取数。 归纳总结
10、(1)MOV X(R 0)，Y(R 1) 指令执行流程中的前 3 步是完成取指令的操作公操作；接下来的 5 步是去主存中取源操作数，把取出的数放在暂存器 C 中；然后的 4 步是形成目的操作数地址；最后 2 步完成传送操作。 (2)COM(R 0) 指令执行流程中的前 3 步是取指令公操作；接下来的 2 步是去主存中取源操作数，把取出的数放在暂存器 D 中；然后将 D 的内容取反，写入目的地址中。 解题技巧根据数据通路，写出指令执行的微操作序列。使用寄存器传送语句(如 PC MAR)，比较直观。45 【正确答案】 设信号量 mutex 用于车间的互斥， positionA、positionB
11、和partA，partB 为资源信号量，分别表示仓库中零件甲、乙的空位数和满位数，positionApartAm；positionBpartBn；编程如下：deftype int semaphore； 定义信号量semaphore mutexl； 进入仓库的互斥信号量semaphore positionAm，positionBn； 车间 A、B 生产的零件甲、乙存放的位置semaphore partA0，partB0； 零件甲、乙的信号量void workshopA ( ) 车间 A 进程 while(TRUE) 并发调度 int item； 仓库货架指针itemproduce(甲)； 生产零
12、件甲P(positionA)； 查有无零件甲的货位P(mutex)； 仓库可以进入吗?puton(item)； 放置零件甲V(mutex)； 释放仓库互斥量V(partA)； 增加零件甲的资源信号量 离开void workshopB( ) 车间 B 进程 while(TRUE) 并发调度 int item； 仓库货架指针itemproduce(乙)； 生产零件乙P(positionB)； 查有无零件乙的货位P(mutex)； 仓库可以进入吗?puton(item)； 放置零件乙V(mutex)； 释放仓库互斥量V(partB)； 增加零件乙的资源信号量) 离开)void assemblesho
13、p( ) 总装车间进程 while(TRUE) 并发调度 int iteml，item2； 仓库货架指针P(partA)； 查第一个零件甲是否有?P(partA)； 查第二个零件甲是否有?P(partB)； 查第一个零件乙是否有 ?P(mutex)； 仓库可以进入吗?itemlget(甲，2)； 取出 2 个零件甲item2get(乙)； 取出 1 个零件乙V(mutex)； 释放仓库互斥量v(positionA)； 增加零件甲的第一空位信号量V(positionA)； 增加零件甲的第二空位信号量V(positionB)； 增加零件乙的空位信号量assemble(iteml，item2) ；
14、总装 离开【试题解析】 本题考查的是生产者和消费者问题的变形。本题中的生产者有两个，所对应的缓冲区(即仓库) 是一个，但是，它们各自有自己的零件货位，甲、乙零件可以分别存放 m、n 件，所以可以考虑设置一个仓库的互斥量，作为车问 A、B 和总装车间的互斥信号量。由于已知甲、乙货架的数量分别为 m、n，因此可以为车间 A、B 设置资源信号量 positionA、positionB ，它们的初值分别为 m、n ，表示货架为空、可以分别存放的零件数量。对于总装车间来讲，它是一个消费者，与普通消费者不同的是，它每次要取零件甲 2 件和零件乙 1 件来生产，因此可以设置资源信号量 partA 和 partB，它们的初值为 0，代表仓库中零件甲、乙的数量。总装车间每次消费 2 个零件甲，可以对信号量 partA 作 2 次 P 操作，消费零件乙 1 件则只作 1 次 P 操作，从而完成三个车间的同步。
