【考研类试卷】计算机专业（基础综合）-试卷5及答案解析.doc

1、计算机专业（基础综合）-试卷 5 及答案解析(总分：98.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.一个栈的入栈序列是 1，2，3，4，5，则栈的不可能的输出序列是( )。（分数：2.00）A.5，4，3，2，1B.4，5，3，2，1C.4，3，5，1，2D.1，2，3，4，53.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a 1，1 为第一元素，其存储地址为1，每个元素占一个地址空间，则 a 8，5 的地址是( )。（分数

2、：2.00）A.13B.33C.18D.404.在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于( )。（分数：2.00）A.nB.n1C.n1D.2n5.在常用的描述二叉排序树的存储结构中，关键字值最大的结点是( )。（分数：2.00）A.左指针一定为空B.右指针一定为空C.左右指针均为空D.左右指针均不为空6.由权值为 9、2、5、7 的四个叶子构造一棵哈夫曼树，该树的带权路径长度为( )。（分数：2.00）A.23B.37C.44D.467.若一个具有 n 个结点、k 条边的非连通无向图是一个森林(nk)，则该森林中必有树的数目是( )。（分数：2.00）A.kB.nC.nkD

3、.nk8.采用邻接表存储的图的广度优先遍历算法类似于树的( )。（分数：2.00）A.中根遍历B.先根遍历C.后根遍历D.按层次遍历9.在有向图 G 的拓扑序列中，若顶点 V i 在顶点 V j 之前，则下列情形不可能出现的是( )。（分数：2.00）A.G 中有弧 i，v j B.G 中有一条从 V i 到 V j 的路径C.G 中没有弧 i，V j D.G 中有一条从 V i 到 V j 的路径10.假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，至少要进行的探查次数是( )。（分数：2.00）A.k1B.kC.k1D.k(k1)211.下列序列中，满足堆定义的是(

4、)。（分数：2.00）A.(100，86，48，73，35，39，42，57，66，21)B.(12，70，33，65，24，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)12.对于一个长度为 n 的任意表进行排序，至少需要进行的比较次数是( )。（分数：2.00）A.O(n)B.O(n 2 )C.O(logk)，则该森林中必有树的数目是( )。（分数：2.00）A.kB.nC.nk D.nk解析：解析：因为一棵具有 n 个顶点的树有 n1 条边，因此设题

5、目中的森林有 m 棵树，每棵树具有顶点数为 V i (1im)，则 V 1 V 2 V m N 及(V 1 1)(V 2 1)(V m 1)K，所以，2mk。8.采用邻接表存储的图的广度优先遍历算法类似于树的( )。（分数：2.00）A.中根遍历B.先根遍历C.后根遍历D.按层次遍历 解析：解析：深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。广度优先搜索遍历类似于树的按层次遍历的过程。或者说，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。9.在有向图 G 的拓扑序列中，若顶点 V i 在顶点 V j 之前，则下列情形不可能出现的是( )。（分数：2.00）

6、A.G 中有弧 i，v j B.G 中有一条从 V i 到 V j 的路径C.G 中没有弧 i，V j D.G 中有一条从 V i 到 V j 的路径 解析：解析：选项 A、B、C 都是有可能出现的，但是选项 D 是不可能出现的，因为若是 G 中有一条从 V j 到 V i 的路径，则在图的拓扑序列中顶点 V i 应该在顶点 V i 之前。10.假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，至少要进行的探查次数是( )。（分数：2.00）A.k1B.kC.k1D.k(k1)2 解析：解析：假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，探查次数最少

7、的情况是第 1 个关键字通过 1 次比较后插入，第 2 个关键字通过 2 次比较后插入，第 k 个关键字通过 k 次比较后插入。总的比较次数12kk(k1)2。11.下列序列中，满足堆定义的是( )。（分数：2.00）A.(100，86，48，73，35，39，42，57，66，21) B.(12，70，33，65，24，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)解析：解析：依据堆的定义，将选项中的每个数列分别看成是一棵完全二叉树，则堆或是空树或是满足

8、下列特性的完全二叉树：其左、右子树分别是堆，并且当左右子树不空时，根结点的值小于(或大于)左右子树根结点的值。12.对于一个长度为 n 的任意表进行排序，至少需要进行的比较次数是( )。（分数：2.00）A.O(n)B.O(n 2 )C.O(log0；i) longpathipathi； longpathlenpathlen； else path：pathlenbdata； 将当前结点放入路径中 pathlen； 路径长度增 l Longpath(bIchil dpath，pa 七hlen，longpath，longpathlen)； 递归扫描左子树 Longpath(brchil dpath

9、，pathlen，longpath，longpathlen)； 递归扫描右子树 pathen； 环境恢复 )解析：解析：采用 path 数组保存扫描到当前结点的路径，pathlen 保存扫描到当前结点的路径长度，longpath 数组保存最长的路径，longpathlen 保存最长路径长度。当 b 为空时，表示当前扫描的一个分支已扫描完毕，将 pathlen 与 longpathlen 进行比较，将较长路径及路径长度分别保存在 longpath 和longpathlen 中。45.某微机的寻址范围为 64KB，其存储器选择器信号为 M，接有 8 片 8KB 的存储器，试完成下列问题。 (1)画

10、出选片译码逻辑图。 (2)写出每片 RAM 的寻址范围。 (3)如果运行时发现不论往哪片存储器存放 8KB 数据，以 4000H 起始地址的存储芯 片都有与之相同的数据，分析故障原因。 (4)如果运行时发现以 0000H 为起始地址的一片存储芯片不能读写，分析故障原因。 (5)若发现译码器中的地址线 A 13 与 CPU 断线，并搭接到低电平的故障，问后果如何? (6)如果发现只能对第 l4 片 RAM 进行读写，试分析故障原因。（分数：2.00）_正确答案：(正确答案：(1)选片译码逻辑如下图所示。 (2)8 片 RAM 的寻址范围分别是：0000H1FFFH、2000H3FFFH、4000

11、H5FFFH、6000H7FFFH、8000H9FFFH、A000HBFFFH、C000HDFfFH 和 E000HFFFFH。 (3)说明译码器有误， 输出始终为低。因该输出接至第 3 片 RAM 的 端，该片对应的地址范围是 4000H5FFFH，故不论往哪片 RAM 存放 8K 数据，该存储芯片始终被选中，所以都有与之相同的数据。 (4)说明 y0 输出始终为高。因 RAM 的片选信号时低电平有效，故用 作片选信号的存储芯片(对应 0000H1FFFH 地址范围)不能读写，而其他芯片可以读写。 (5)若发现 A 13 与 CPU 断线，并搭接到低电平的故障，则 )解析：解析：(3)(6)

12、中出现的问题都是由于译码器连接上的问题(短路或断路)造成的，使得某些片选信号始终被选中或始终不被选中。 归纳总结全译码法将除片内寻址外的全部高位地址线都作为地址译码器的输入，译码器的输出作为各芯片的片选信号，将它们分别接到存储芯片的片选端，以实现对存储芯片的选择。全译码法的优点是每片(或组)芯片的地址范围是唯一确定的，而且是连续的，也便于扩展，不会产生地址重叠的存储区。 解题技巧首先确定片选电路以及各个芯片的地址分配，然后分析各种出错情况，分别找出出错的原因。46.某模型机的通路结构如下图所示，用寄存器传送语句(如 PCMAR)，拟出下列指令从读取到执行的完整流程。 (1)数据传送指令 MOV

13、 X(R 0 )，Y(R 1 )，源和目的操作数地址均采用变址寻址，第 1 个参数 X为源操作数的形式地址，第 2 个参数为目的操作数的形式地址，分别位于指令的第 2 个和第 3 个存储字。 (2)数据求反指令 COM(R 0 )，采用自减型寄存器间接寻址，结果送回自减后的地由 E 单元。 （分数：2.00）_正确答案：(正确答案：(1)MOV X(R 0 )，Y(R 1 ) PCMAR，Read ；取指令 MMDRIR PC1PC PCMAR，Read ；取源操作数形式地址 MMDRC PC1PC CR 0 MAR，Read ；形成源操作数有效地址，并取源操作数 MMDRC ；源操作数暂存

14、C 中 PCMAR，Read ；取目的操作数形式地址 MMDRD PC1PC DR 1 MAR ；形成目的操作数有效地址 CMDR ；将源操作数送存储器数据寄存器 MDRM，write ；将源操作数写入目的有效地址中 (2)COM(R 0 ) PCMAR，Read ；取指令 MMDRIR PClPC R 0 1R 0 ，R 0 1MAR，Read ；修改 R 0 的内容(源和目的操作数地址) MMDRD ；取出源操作数 DMDR ；将源操作数取反 MDRM，write ；写入目的地址中)解析：解析：数据传送指令占 3 个字，第 1 个字是操作码和寄存器编号；第 2 个字是参数 X，为源操作数的

15、形式地址；第 3 个字是参数 Y，为目的操作数的形式地址，源和目的操作数地址均采用变址寻址，指令的含义是：(R 0 )X)(R 1 )Y。 求反指令仅占 1 个字，自减型寄存器寻址是先修改寄存器的内容(1)，再取数。 归纳总结(1)MOV X(R 0 )，Y(R 1 ) 指令执行流程中的前 3 步是完成取指令的操作公操作；接下来的 5 步是去主存中取源操作数，把取出的数放在暂存器 C 中；然后的 4 步是形成目的操作数地址；最后 2 步完成传送操作。 (2)COM(R 0 ) 指令执行流程中的前 3 步是取指令公操作；接下来的 2步是去主存中取源操作数，把取出的数放在暂存器 D 中；然后将 D

16、 的内容取反，写入目的地址中。 解题技巧根据数据通路，写出指令执行的微操作序列。使用寄存器传送语句(如 PC MAR)，比较直观。47.某工厂有一个仓库可以存放甲、乙两种零部件，甲零件可以存放 m 件，乙零件可以存放 n 件，车间 A专门生产甲零件，每次 1 件，每生产 1 件存放进仓库 1 件；车间 B 专门生产零件乙，每次 1 件，每生产 1件存放进仓库 1 件。总装车间每次从仓库取出 2 件甲零件、l 件乙零件组装成成品，车间 A、B 和总装车间必须互斥进入仓库。当仓库内甲、乙零件分别达到 m、n 件时，车间 A、B 分别停止生产。而仓库内任何一种零件为 0 时，总装车间停产。根据上述规

17、则，请利用信号量机制，没计一个可以让车间 A、B 和总装车间协调运转的程序，并说明各个信号量的意义，用类 c 语言写出整个过程。（分数：2.00）_正确答案：(正确答案：设信号量 mutex 用于车间的互斥，positionA、positionB 和 partA，partB 为资源信号量，分别表示仓库中零件甲、乙的空位数和满位数，positionApartAm；positionBpartBn；编程如下： deftype int semaphore； 定义信号量 semaphore mutexl； 进入仓库的互斥信号量 semaphore positionAm，positionBn； 车间 A、

18、B 生产的零件甲、乙存放的位置 semaphore partA0，partB0； 零件甲、乙的信号量 void workshopA ( ) 车间 A 进程 while(TRUE) 并发调度 int item； 仓库货架指针 itemproduce(甲)； 生产零件甲 P(positionA)； 查有无零件甲的货位 P(mutex)； 仓库可以进入吗? puton(item)； 放置零件甲 V(mutex)； 释放仓库互斥量 V(partA)； 增加零件甲的资源信号量 离开 void workshopB( ) 车间 B 进程 while(TRUE) 并发调度 int item； 仓库货架指针 i

19、temproduce(乙)； 生产零件乙 P(positionB)； 查有无零件乙的货位 P(mutex)； 仓库可以进入吗? puton(item)； 放置零件乙 V(mutex)； 释放仓库互斥量 V(partB)； 增加零件乙的资源信号量 ) 离开 ) void assembleshop( ) 总装车间进程 while(TRUE) 并发调度 int iteml，item2； 仓库货架指针 P(partA)； 查第一个零件甲是否有? P(partA)； 查第二个零件甲是否有? P(partB)； 查第一个零件乙是否有? P(mutex)； 仓库可以进入吗? itemlget(甲，2)； 取

20、出 2 个零件甲 item2get(乙)； 取出 1 个零件乙 V(mutex)； 释放仓库互斥量 v(positionA)； 增加零件甲的第一空位信号量 V(positionA)； 增加零件甲的第二空位信号量 V(positionB)； 增加零件乙的空位信号量 assemble(iteml，item2)； 总装 离开 )解析：解析：本题考查的是生产者和消费者问题的变形。本题中的生产者有两个，所对应的缓冲区(即仓库)是一个，但是，它们各自有自己的零件货位，甲、乙零件可以分别存放 m、n 件，所以可以考虑设置一个仓库的互斥量，作为车问 A、B 和总装车间的互斥信号量。由于已知甲、乙货架的数量分别

21、为 m、n，因此可以为车间 A、B 设置资源信号量 positionA、positionB，它们的初值分别为 m、n，表示货架为空、可以分别存放的零件数量。对于总装车间来讲，它是一个消费者，与普通消费者不同的是，它每次要取零件甲 2 件和零件乙 1 件来生产，因此可以设置资源信号量 partA 和 partB，它们的初值为 0，代表仓库中零件甲、乙的数量。总装车间每次消费 2 个零件甲，可以对信号量 partA 作 2 次 P 操作，消费零件乙 1 件则只作 1 次 P 操作，从而完成三个车间的同步。48.某个页式存储管理系统，接收了一个大小一共 7 页的程序，其依次访问的页为：1、2、3、4

22、、2、1、5、6、2、1、2、3、7。若分配给该程序的内存空间为 4 页，并一次预装入，请用先进先出(FIFO)调度算法和最近最少用(LRU)凋度算法计算，程序执行时会产牛多少次缺页中断?依次写出被淘汰的页号并计算缺页率。（分数：2.00）_正确答案：(正确答案：采用 FIFO 的算法： 被淘汰的页号次序为 1、2、3、4、5、6；缺页率为71070 采用 LRU 的算法： )解析：解析：本题考查页面置换算法。49.如图所示一台路由器连接 3 个以太网。 （分数：2.00）_正确答案：(正确答案：(1)该 TCPIP 网络使用的是 B 类 IP 地址。 (2)该网络划分子网后所采用的子网掩码是

23、 2552552550。 (3)这两台机器上的网络应用程序不能够正常通信，那是因为在一个以太网上不能使用不同的子网号。在这种配置情况下，IP 软件会试图将 IP 分组送往网关，而不会直接投递。最终 IP 分组将会被该网关丢弃。 (4)255255255255)解析：解析：本题考查 IP 地址的概念，子网划分和路由原理，首先明确该路由器连接着四个子网，即130130110120160200，要注意 190 和 200 在物理上是在一个链路上的。 问题 1考查 IP 地址的分类，用于单播地址的是 A 类到 C 类，其中 A 类地址(1000126255255255)，B 类地址(128000191

24、255255255)和 C 类地址(192000223255255255)，因此这四个子网均属于 B 类地址。 问题 2 给出子网划分的子网掩码，从比较这四个子网可以看出，不同之处在于第三个字节，因此可以知道掩码是 24 位，或者从 130130200 出发，这代表一个网络，前三个字节是网络号，因此掩码是 24 位。 问题 3 主要考查主机基本路由的过程，即使两台主机处于同一个物理链路，在通信之前要判断是否是同一个网段，如果是就直接通信，否则把数据报发送给该主机的网关，由于该拓扑图中只有 130130190 的网关，191，因此不能完成 D 和 E 的通信。 问题 4 主要考查对广播报的认识，广播报是同一个链路上主机都必须接收，不管其是属于哪个网络；其次考查路由器一个功能，就是隔断广播报；因此只有广播报能够满足题目的要求。