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

《【考研类试卷】考研计算机学科专业基础综合-5-2及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】考研计算机学科专业基础综合-5-2及答案解析.doc（15页珍藏版）》请在麦多课文档分享上搜索。

1、考研计算机学科专业基础综合-5-2 及答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.银行家算法在解决死锁问题中是用于( )的。（分数：2.00）A.预防死锁B.避免死锁C.检测死锁D.解除死锁2.假设有一个信道的带宽是 3000Hz，其信噪比为 20dB，那么这个信道可以获得的理论最大传输速率是( )。（分数：2.00）A.1KbpsB.32KbpsC.20KbpsD.64Kbps3.完全二叉树高度为 h则最左边的叶子结点序号为( )。（分数：2.00）A.2h-1+1B.2h-1C.2h+1-1D.2h+14.在 OSI 参考模

2、型中，自下而上第一个提供端到端服务的层次是( )。（分数：2.00）A.数据链路层B.传输层C.会话层D.应用层5.某浮点机字长 8 位，尾数和阶码都采用补码形式，且运算过程中数符和阶符都采用双符号位。基数为2。则浮点加减运算过程中，当出现下列哪种情况时，需要左规?( )（分数：2.00）A.尾数相加后，数符为“01”B.尾数相加后，数符为“10”C.尾数相加结果为“00.1xxxxxx”D.尾数相加结果为“11.1xxxxxx”6.一个十进制数真值为-100，按补码形式存放在一个 16 位寄存器中，该寄存器的内容用十六进制表示为( )。（分数：2.00）A.FF9CHB.009CHC.9C0

3、0HD.0064H7.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，198.一个使用 CSMA/CA 的网络上，计算机 A 的帧际间隔是 2 时槽，计算机 B 的帧际间隔是 6 时槽，如果计算机 C 使用( )帧际间隔可以获得最高优先级。（分数：2.00）A.8 时槽B.5 时槽C.3 时槽D.1 时槽9.给

4、定二叉树图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，7，5，6，1，2，4，则其遍历方式是( )。（分数：2.00）A.LRNB.NRLC.RLND.RNL10.用 PCM 对语音进行数字量化，如果将声音分为 128 个量化级，采样频率为 8000 次/秒，那么一路话音需要的数据传输率为( )。（分数：2.00）A.56KbpsB.64KbpsC.128KbpsD.1024Kbps11.某公司 C 有一台主机 h，该主机具有的 Internet 域名应该为( )。（分数：2.00）AB.com.c.hC.com.h.cD12.在分页

5、式储存管理中，需将逻辑地址转换成物理地址，在分页式地址转换中地址字为 16 位，页长为212字节(4KB)，现有一逻辑地址为 2F6AH，则相应物理地址为( )。页表如下：（分数：2.00）A.页号B.块号(十进制)C.0D.5E.1F.10G.2H.1113.执行一次磁盘输入输出操作所花费的时间包括( )。（分数：2.00）A.寻道时间、延迟时间、传送时间和等待时间B.寻道时间、等待时间、传送时间C.等待时间、寻道时间、延迟时间、读写时间D.寻道时间、延迟时间、传送时间14.设有五个进程共享一个互斥段，如果最多允许两个进程同时进入互斥段，则所采用的互斥信号量初值应该是( )。（分数：2.00

6、）A.5B.2C.1D.015.某 DRAM 芯片内部存储元排列成 10241024 的矩阵，且已知其存取周期为 0.1s，最大刷新间隔为2ms。当采用异步刷新方式时，死时间( )。（分数：2.00）A.=2msB.0.1msC.-0.2sD.-0.1s16.某计算机的指令系统中有“先基址后间址”的寻址方式，基址寄存器为 BR，形式地址为 A，则有效地址为( )。（分数：2.00）A.(BR)+AB.(BR+A)C.(BR)+A)D.(BR)+A17.某图像显示器的分辨率为 1024768，共可显示 256 种灰度，则显示存储器的容量为( )。（分数：2.00）A.256KBB.768KBC.

7、1MBD.2MB18.通道又称 I/O 处理机，它用于实现( )之间的信息传输。（分数：2.00）A.主存和外设B.CPU 与外设C.主存与外设D.CPU 与外存19.某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间)分别是 90ns、80ns、70ns 和 60ns，则该计算机的 CPU 时钟周期至少是( )。（分数：2.00）A.90nsB.80nsC.70nsD.60ns20.当( )时，进程从执行状态转变为就绪状态。（分数：2.00）A.进程被调度程序选中B.时间片到C.等待某一事件D.等待的事件发生21.物理层、数据链路层和网络层的 PDU 分

8、别是( )。（分数：2.00）A.报文、帧、比特B.报文、分组、比特C.比特、分组、帧D.比特、帧、分组22.假设某系统总线在一个总线周期中并行传输 4 字节信息，一个总线周期占用 2 个时钟周期，总线时钟频率为 10MHz，则总线带宽是( )。（分数：2.00）A.10MB/sB.20MB/sC.40MB/sD.80MB/s23.长度为 10km、数据传输率为 10Mbps 的 CSMA/CS 以太网，信号传播速度为 200m/s。那么该网络的最小帧长为( )。（分数：2.00）A.20bitB.200bitC.100bitD.1000bit24.以下动态路由算法中，使用距离-矢量路由算法的

9、是( )。（分数：2.00）A.RIP 协议B.OSPF 协议C.BGP 协议D.ICMP 协议25.系统总线中地址线的功能是用于选择( )。（分数：2.00）A.主存单元B.I/O 端口C.磁盘数据块D.A 或 B26.关于 B-树，下列说法不正确的是( )。（分数：2.00）A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3 树中，所有非叶子结点有 1 或者 3 个孩子结点D.通常情况下，B-树不是二叉树27.从下面关于虚拟设备的论述中，选择一条正确的论述( )。（分数：2.00）A.虚拟设备是指允许用户使用比系统中具有的物理设备更多的设备B.虚拟设备是指允许用户以标准化方式来

10、使用物理设备C.虚拟设备是把一个物理设备变换成多个对应的逻辑设备D.虚拟设备是指允许用户程序不必全部装入内存便可使用系统中的设备28.下列算法中用于磁盘移臂调度的是( )。（分数：2.00）A.时间片轮转法B.LRU 算法C.最短寻找时间优先法D.优先级高者优先法29.在一棵高度为 h 的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。（分数：2.00）A.2h 2h-1B.2h-1 2hC.2h+1 2h-1D.2h-1 2h-130.微型计算机中，主机和高速磁盘交换数据适合采用( )方式。（分数：2.00）A.程序查询控制B.程序中断控制C.直接存储器存取(DMA)D.通道控

11、制31.设用数组 A1，n作为两个栈 S1、S2 的共用存储空间，对任一个栈，只有当数组 A1，n全满时才不作入栈操作，则分配这两个栈空间的最佳方案是( )。（分数：2.00）A.S1 的栈底位置设为 1，S2 的栈底位置设为 nB.S1 的栈底位置设为 n/2，S2 的栈底位置设为 n/2+1C.S1 的栈底位置设为 1，S2 的栈底位置设为 n/2D.S1 的栈底位置设为 n/2，S2 的栈底位置设为 132.在 AOE 网络中关键路径叙述正确的是( )。（分数：2.00）A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间B.从开始顶点到完成顶点的具有最

12、小长度的路径，关键路径长度是完成整个工程所需的最短时间C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间33.在下列文件中，不便于文件增、删操作的是( )。（分数：2.00）A.索引文件B.连续文件C.Hash 文件D.串联文件34.下列有关数据存储结构的叙述中，正确的是( )。（分数：2.00）A.顺序存储方式只能用于存储线性结构B.顺序存储方式的优点是占用存储空间小，插入、删除等操作效率高C.链表的每个结点中都恰好含有一个指针D.Hash 存储的基本思想是由关键词的值决

13、定数据的存储地址35.下列的叙述不正确的个数是( )。 (1) 9 阶 B-树，除根以外的任一结点的关键字个数不少于 4 (2) 理想情况下，在散列表中查找一个元素的时间复杂度为 O(1) (3) 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻 (4) 在索引顺序表的查找中，对索引表既可以采用顺序查找方法，也可采用二分查找方法（分数：2.00）A.1B.2C.3D.436.以下说法中错误的是( )。（分数：2.00）A.与 DRAM 相比，SRAM 的集成度低，存取速度快B.PC 机的主存储器常由 DRAM 构成C.RAM 需要刷新，且断电后信息会丢失D.ROM 是一种非易失性存储器

14、，断电后仍可保持记忆37.多道程序设计是指( )。（分数：2.00）A.在实时系统中并发运行多个程序B.在分布式系统中同一时刻运行多个程序C.在一台处理机上同一时刻运行多个程序D.在一台处理机上并发运行多个程序38.补码除法中，根据( )上商 0。（分数：2.00）A.余数为负B.余数的符号与被除数的符号相同C.余数的符号与被除数的符号不同D.余数的符号与除数的符号不同39.在基址寻址方式中，若基址寄存器 BR 的内容为 2D3C16，形式地址 A 的内容为 5316则有效地址 EA 为( )。（分数：2.00）A.5316B.2D3C16C.2D8F16D.803C1640.若用一个大小为

15、6 的一维数组来实现循环队列，且当前 front 和 rear 的值分别为 3，0，当从队列中删除一个元素，再加入两个元素后，front 和 rear 的值分别为( )。（分数：2.00）A.5，1B.4，2C.2，4D.1，5二、B综合应用题/B(总题数：7，分数：70.00)41.试编写一个非递归算法实现求以二叉链表存储的二叉树中 q 结点的祖先。（分数：10.00）_42.设计一个算法求图的中心点。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为： MAX从 w 到 v 的最短距离|w 属于 V(G) 如果 v 是有向图 G 中具有的最小偏心度的顶点，则称顶点 v 是 G 的中心

16、点。（分数：15.00）_43.在一个 8 级中断的系统中，硬件中断响应从高到低的优先顺序是 12345678，通过中断屏蔽技术，将中断处理优先顺序设置为 13572468，如果 CPU 在执行一个应用程序时有5、6、7、8 级的四个中断同时到达，CPU 在按优先顺序处理到第 3 个中断请求的过程中又有一个 3 级中断请求到达 CPU，试画出 CPU 响应这些中断的顺序示意图。（分数：13.00）_某计算机有 8 个主设备需要竞争总线的使用权，其设备号为 07。现欲设计其判优控制方法，试回答下述问题。（分数：8.00）(1).集中式总线判优控制与分布式总线判优控制的区别是什么?（分数：4.00

17、）_(2).若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，该计算机为实现判优控制所需的控制线种类及数量分别为多少?（分数：4.00）_44.三个进程 P1、P2、P3 互斥使用一个包含 N(N0)个单元的缓冲区。P1 每次用 produce()生成一个正整数并用 put()送入缓冲区某一空单元中；P2 每次用 getodd()从该缓冲区中取出一个奇数并用 countodd()统计奇数个数；P3 每次用 geteven()从该缓冲区中取出一个偶数并用 counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代

18、码描述。（分数：8.00）_45.在请求页式系统中，一程序的页面走向(访问串或引用串)为 2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为 m。试分别计算 m=3 和 m=4 时，FIFO 和 LRU 两种替换算法的缺页(页故障)数，并给出：结果说明了什么?（分数：7.00）_如下图所示为一个网络连接的示意图，主机 1 到主机 2 采用了 SLIP 网络连接，SLIP 网络可以传输的最大数据段是 296 字节，主机 2 和主机 3 使用了以太网连接。 请问：（分数：9.00）(1).为了使 IP 不分片，主机 1 可以在 TCP 包中承载多少数据?（分数：3.00）_

19、(2).主机 3 可以在 TCP 包中承载多少数据?（分数：3.00）_(3).先在主机 1 和主机 3 建立起了一条 TCP 连接，请问这条 TCP 连接的 mss 值是多少? （分数：3.00）_考研计算机学科专业基础综合-5-2 答案解析(总分：150.00，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.银行家算法在解决死锁问题中是用于( )的。（分数：2.00）A.预防死锁 B.避免死锁C.检测死锁D.解除死锁解析：本题考查银行家算法在分配资源时采用安全性检查，从而预防死锁。2.假设有一个信道的带宽是 3000Hz，其信噪比为 20dB，那么这个信道可

20、以获得的理论最大传输速率是( )。（分数：2.00）A.1KbpsB.32KbpsC.20Kbps D.64Kbps解析：SNR=10log10(S/N)，题目中 SNR=20dB，因此 S/N=10O。再使用香农定理可以得到信道的理论速率上限C=Wlog2(1+S/N)=3000log2(1+100)20(Kbps)。3.完全二叉树高度为 h则最左边的叶子结点序号为( )。（分数：2.00）A.2h-1+1B.2h-1 C.2h+1-1D.2h+1解析：可知前 h-1 层为满二叉树，共有结点 2h-1-1，因此最左边叶子结点的序号为 B。4.在 OSI 参考模型中，自下而上第一个提供端到端服

21、务的层次是( )。（分数：2.00）A.数据链路层B.传输层 C.会话层D.应用层解析：传输层是第一个提供端到端服务的层次，它使用端口来区分不同的应用程序。5.某浮点机字长 8 位，尾数和阶码都采用补码形式，且运算过程中数符和阶符都采用双符号位。基数为2。则浮点加减运算过程中，当出现下列哪种情况时，需要左规?( )（分数：2.00）A.尾数相加后，数符为“01”B.尾数相加后，数符为“10”C.尾数相加结果为“00.1xxxxxx”D.尾数相加结果为“11.1xxxxxx” 解析：当尾数运算结果为非规格化形式时，需要左规；基数为 2 的补码的规格化形式下最高数值位应与符号位相反，故当尾数相加结

22、果为“11.1xxxxxx”时，尾数需要左规。6.一个十进制数真值为-100，按补码形式存放在一个 16 位寄存器中，该寄存器的内容用十六进制表示为( )。（分数：2.00）A.FF9CH B.009CHC.9C00HD.0064H解析：100 的 16 位二进制形式为 0000 0000 0110 0100，将其连符号位在内取反加 1，即可得-100 的 16位二进制形式为 1111 11111 1001 1100，写为十六进制为 FF9CH。7.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3

23、，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，19解析：8.一个使用 CSMA/CA 的网络上，计算机 A 的帧际间隔是 2 时槽，计算机 B 的帧际间隔是 6 时槽，如果计算机 C 使用( )帧际间隔可以获得最高优先级。（分数：2.00）A.8 时槽B.5 时槽C.3 时槽D.1 时槽 解析：在 CSMA/CA 中，帧际间隔值可以用来分配发送方的优先级，如果一个设备被分配一个较小的帧际优先级，那么它就会有更多的机会得到对传输介质访问的机会。9.给定

24、二叉树图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，7，5，6，1，2，4，则其遍历方式是( )。（分数：2.00）A.LRNB.NRLC.RLND.RNL 解析：10.用 PCM 对语音进行数字量化，如果将声音分为 128 个量化级，采样频率为 8000 次/秒，那么一路话音需要的数据传输率为( )。（分数：2.00）A.56Kbps B.64KbpsC.128KbpsD.1024Kbps解析：声音信号需要 128 个量化级别，那么每采样一次需要 7bit 来表示，每秒采样 8000 次，那么一路话音需要的数据传输率为 56Kbps

25、。11.某公司 C 有一台主机 h，该主机具有的 Internet 域名应该为( )。（分数：2.00）A B.com.c.hC.com.h.cD解析：根据 DNS 域名的命名规则，层次越高的域名应该安排在靠后的位置，所以 A 是正确答案。12.在分页式储存管理中，需将逻辑地址转换成物理地址，在分页式地址转换中地址字为 16 位，页长为212字节(4KB)，现有一逻辑地址为 2F6AH，则相应物理地址为( )。页表如下：（分数：2.00）A.页号B.块号(十进制)C.0 D.5E.1F.10G.2H.11解析：逻辑地址的最高四位为 2，即页号为 2，根据页表映射，块号为 11，即 B(H)，加

26、上页内偏移 F6AH为 BF6AH。13.执行一次磁盘输入输出操作所花费的时间包括( )。（分数：2.00）A.寻道时间、延迟时间、传送时间和等待时间B.寻道时间、等待时间、传送时间 C.等待时间、寻道时间、延迟时间、读写时间D.寻道时间、延迟时间、传送时间解析：本题考查磁盘操作时间的概念。14.设有五个进程共享一个互斥段，如果最多允许两个进程同时进入互斥段，则所采用的互斥信号量初值应该是( )。（分数：2.00）A.5B.2 C.1D.0解析：因为最多允许两个进程同时进入互斥段，所以信号量为 2。15.某 DRAM 芯片内部存储元排列成 10241024 的矩阵，且已知其存取周期为 0.1s

27、，最大刷新间隔为2ms。当采用异步刷新方式时，死时间( )。（分数：2.00）A.=2msB.0.1msC.-0.2sD.-0.1s 解析：当采用异步刷新方式时，将对 DRAM 芯片内 1024 行的刷新均匀分布在 2ms 内的不同时间，每次刷新一行；这样每次刷新只需停止一个存取周期，即“死时间”为一个存取周期0.1s，故选 D。16.某计算机的指令系统中有“先基址后间址”的寻址方式，基址寄存器为 BR，形式地址为 A，则有效地址为( )。（分数：2.00）A.(BR)+AB.(BR+A)C.(BR)+A) D.(BR)+A解析：先基址，即基址寄存器内容加形式地址，(BR)+A；再间址，即 E

28、A=(BR)+A)，选 C。17.某图像显示器的分辨率为 1024768，共可显示 256 种灰度，则显示存储器的容量为( )。（分数：2.00）A.256KBB.768KB C.1MBD.2MB解析：256 级灰度需要 log2256=8 个二进制位，即 1B 来表示，故显示存储器的容量为 1024768B=768KB。18.通道又称 I/O 处理机，它用于实现( )之间的信息传输。（分数：2.00）A.主存和外设B.CPU 与外设 C.主存与外设D.CPU 与外存解析：通道主要用于主存和外设的信息交换。19.某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓

29、存时间)分别是 90ns、80ns、70ns 和 60ns，则该计算机的 CPU 时钟周期至少是( )。（分数：2.00）A.90ns B.80nsC.70nsD.60ns解析：CPU 时钟周期必须保证能够在一个周期内完成最复杂的操作，故本题中 CPU 时钟周期至少应为90ns，选 A。20.当( )时，进程从执行状态转变为就绪状态。（分数：2.00）A.进程被调度程序选中B.时间片到 C.等待某一事件D.等待的事件发生解析：A：从就绪态到执行状态； C：从执行状态到阻塞状态； D：从阻塞状态到就绪状态。21.物理层、数据链路层和网络层的 PDU 分别是( )。（分数：2.00）A.报文、帧、

30、比特B.报文、分组、比特C.比特、分组、帧D.比特、帧、分组 解析：物理层的 PDU 是比特，数据链路层的 PDU 是帧，网络层的 PDU 是分组。22.假设某系统总线在一个总线周期中并行传输 4 字节信息，一个总线周期占用 2 个时钟周期，总线时钟频率为 10MHz，则总线带宽是( )。（分数：2.00）A.10MB/sB.20MB/s C.40MB/sD.80MB/s解析：总线时钟频率为 10MHz，一个总线周期占用 2 个时钟周期，故 1s 内共有 5M 个总线周期；每个周期并行传输 4 字节信息，故总线带宽为 5M/s4B=20.MB/s。23.长度为 10km、数据传输率为 10Mb

31、ps 的 CSMA/CS 以太网，信号传播速度为 200m/s。那么该网络的最小帧长为( )。（分数：2.00）A.20bitB.200bitC.100bitD.1000bit 解析：来回路程=100002m，RTT=100002(20010 6)=10-4。那么最小帧长度=WRTT=1000bit。24.以下动态路由算法中，使用距离-矢量路由算法的是( )。（分数：2.00）A.RIP 协议 B.OSPF 协议C.BGP 协议D.ICMP 协议解析：RIP 协议使用了距离-矢量路由算法。25.系统总线中地址线的功能是用于选择( )。（分数：2.00）A.主存单元B.I/O 端口C.磁盘数据块

32、D.A 或 B 解析：地址线既可用于选择主存单元，也可用于选择 I/O 端口；磁盘通过磁盘控制器与主机相连，故系统总线中的地址线只能用来选择磁盘控制器中的端口，而不能用来选择磁盘数据块。26.关于 B-树，下列说法不正确的是( )。（分数：2.00）A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3 树中，所有非叶子结点有 1 或者 3 个孩子结点 D.通常情况下，B-树不是二叉树解析：参见 B-树的定义。27.从下面关于虚拟设备的论述中，选择一条正确的论述( )。（分数：2.00）A.虚拟设备是指允许用户使用比系统中具有的物理设备更多的设备B.虚拟设备是指允许用户以标准化方式来使

33、用物理设备C.虚拟设备是把一个物理设备变换成多个对应的逻辑设备 D.虚拟设备是指允许用户程序不必全部装入内存便可使用系统中的设备解析：本题考查虚拟设备的概念。28.下列算法中用于磁盘移臂调度的是( )。（分数：2.00）A.时间片轮转法B.LRU 算法C.最短寻找时间优先法 D.优先级高者优先法解析：其他三项都是进程调度算法。29.在一棵高度为 h 的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。（分数：2.00）A.2h 2h-1B.2h-1 2hC.2h+1 2h-1D.2h-1 2h-1 解析：由平衡二叉树的特性可知，一棵高度为 h 的理想平衡二叉树中含有结点数最少的情形

34、是：前 h-1 层为满二叉树，第 h 层只有一个结点，因而结点总数为(2 h-1-1)+1=2h-1；含有结点数最多的情形是：该树是一棵高度为 h 的满二叉树，因而结点总数为 2h-1。30.微型计算机中，主机和高速磁盘交换数据适合采用( )方式。（分数：2.00）A.程序查询控制B.程序中断控制C.直接存储器存取(DMA) D.通道控制解析：由于磁盘是高速设备，而程序控制方式(程序查询方式和程序中断方式)下，数据传送需要 CPU 的干预，这样会占用大量的 CPU 时间，甚至可能 CPU 时间全部用于数据传送都不能满足磁盘数据交换的要求；而通道控制方式一般见于大中型计算机中，微型机中基本不采用

35、，故 C 为正确选项。31.设用数组 A1，n作为两个栈 S1、S2 的共用存储空间，对任一个栈，只有当数组 A1，n全满时才不作入栈操作，则分配这两个栈空间的最佳方案是( )。（分数：2.00）A.S1 的栈底位置设为 1，S2 的栈底位置设为 n B.S1 的栈底位置设为 n/2，S2 的栈底位置设为 n/2+1C.S1 的栈底位置设为 1，S2 的栈底位置设为 n/2D.S1 的栈底位置设为 n/2，S2 的栈底位置设为 1解析：由于栈中元素个数不固定，因此如果将栈底设在中间位置时，固定了栈中元素的个数，不能满足只有当数组全满时才不作入栈操作的要求。32.在 AOE 网络中关键路径叙述正

36、确的是( )。（分数：2.00）A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间 B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间解析：关键路径的定义。33.在下列文件中，不便于文件增、删操作的是( )。（分数：2.00）A.索引文件B.连续文件 C.Hash 文件D.串联文件解析：因为连续文件是线性存储，每次增、删都要移动元素，代价较大。34.下列

37、有关数据存储结构的叙述中，正确的是( )。（分数：2.00）A.顺序存储方式只能用于存储线性结构B.顺序存储方式的优点是占用存储空间小，插入、删除等操作效率高C.链表的每个结点中都恰好含有一个指针D.Hash 存储的基本思想是由关键词的值决定数据的存储地址 解析：顺序存储方式除了用于存储线性结构外，还能存储数组或完全二叉树等非线性结构。插入、删除操作时，由于要移动大量的数据，执行效率低，链表的形式有单链表、双链表和多重链表，除了单链表外，其他链表中的结点需要两个以上的指针。35.下列的叙述不正确的个数是( )。 (1) 9 阶 B-树，除根以外的任一结点的关键字个数不少于 4 (2) 理想情况

38、下，在散列表中查找一个元素的时间复杂度为 O(1) (3) 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻 (4) 在索引顺序表的查找中，对索引表既可以采用顺序查找方法，也可采用二分查找方法（分数：2.00）A.1 B.2C.3D.4解析：(1)(2)(4)正确，(3)错误。因为如果发生多次冲突，则同义词在表中就不会相邻。36.以下说法中错误的是( )。（分数：2.00）A.与 DRAM 相比，SRAM 的集成度低，存取速度快B.PC 机的主存储器常由 DRAM 构成C.RAM 需要刷新，且断电后信息会丢失 D.ROM 是一种非易失性存储器，断电后仍可保持记忆解析：RAM 又可分为

39、SRAM 和 DRAM，其中，DRAM 需要刷新，而 SRAM 不用，故选 C。37.多道程序设计是指( )。（分数：2.00）A.在实时系统中并发运行多个程序B.在分布式系统中同一时刻运行多个程序C.在一台处理机上同一时刻运行多个程序D.在一台处理机上并发运行多个程序 解析：本题考查多道程序设计的概念。38.补码除法中，根据( )上商 0。（分数：2.00）A.余数为负B.余数的符号与被除数的符号相同C.余数的符号与被除数的符号不同D.余数的符号与除数的符号不同 解析：补码除法中，当余数的符号与除数的符号相同时，上商 1；当余数的符号与除数的符号不同时，上商 0。39.在基址寻址方式中，若基

40、址寄存器 BR 的内容为 2D3C16，形式地址 A 的内容为 5316则有效地址 EA 为( )。（分数：2.00）A.5316B.2D3C16C.2D8F16 D.803C16解析：基址寻址方式下，EA=(BR)+A，结合题中条件，EA=(BR)+A=2D3C 16+5316=2D8F16，选 C。40.若用一个大小为 6 的一维数组来实现循环队列，且当前 front 和 rear 的值分别为 3，0，当从队列中删除一个元素，再加入两个元素后，front 和 rear 的值分别为( )。（分数：2.00）A.5，1B.4，2 C.2，4D.1，5解析：参考循环队列插入删除操作。二、B综合应

41、用题/B(总题数：7，分数：70.00)41.试编写一个非递归算法实现求以二叉链表存储的二叉树中 q 结点的祖先。（分数：10.00）_正确答案：()解析：该题可采用按后序遍历二叉树的非递归算法，当访问 q 结点时，结点栈中所有栈元素均为 q 结点的祖先。 #define MAX 1000 void Ancestor(BTTree*T，BTNode* q) BTNode* sMAX;/栈实现非递归 BTNode* P=T: int bMAX; int top=-1: do while(p) s+top=P; btop=0; p=p-lchild; if(top-1 btop=-1) P=sto

42、p; if(p=q) printf(“q 结点的祖先是:n“); for(inti=0；i=top;i+) printf(“%C“,si-data); return; else top-; if(top-1) P=stop-rchild; btop=1; while(top-1); 42.设计一个算法求图的中心点。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为： MAX从 w 到 v 的最短距离|w 属于 V(G) 如果 v 是有向图 G 中具有的最小偏心度的顶点，则称顶点 v 是 G 的中心点。（分数：15.00）_正确答案：()解析：设 C 是有向图 G 的邻接矩阵，求最小偏心度

43、的顶点的步骤如下： (1) 利用 Floyd 算法求出每对顶点之间的最短路径矩阵 A； (2) 对矩阵 A 求出每列 i 的最大值，得到顶点 i 的偏心度； (3) 在这 n 个顶点的偏心度中，求出最小偏心度的顶点 k，即为图 G 的中心点对应的算法如下： int Center(MGraph G) int AMAXVMAXV,BMAXV; int i,j,k,m; for(i=0;iG.n;i+)/将邻接矩阵赋给 A for(j=0;jG.n;j+) Aij=G.edgesij; for(k=0;kG.n;k+)/实现( )功能 for(i=0;iG.n;i+) for(j=0;jG.n;j+

44、) if(Aik+AkjAij) Aij=Aik+Akj; for(j=0;jG.n;j+)/实现( )功能，结果放在 B 数组中 Bj=A0j; for(i=1;iG.n;i+) if(BjAij) Bj=Aij; k=0; m=Bj;/实现( )功能，结果放在 k 中 for(i=1;iG.n;i+) if(Bim) m=Bi; k=i: return k;/返回 k 值 43.在一个 8 级中断的系统中，硬件中断响应从高到低的优先顺序是 12345678，通过中断屏蔽技术，将中断处理优先顺序设置为 13572468，如果 CPU 在执行一个应用程序时有5、6、7、8 级的四个中断同时到达

45、，CPU 在按优先顺序处理到第 3 个中断请求的过程中又有一个 3 级中断请求到达 CPU，试画出 CPU 响应这些中断的顺序示意图。（分数：13.00）_正确答案：()解析：硬件中断响应的优先顺序称为响应优先级，设置中断屏蔽字后实际处理中断的优先顺序称为处理优先级，分析如下： CPU 在执行现行程序时，有 5、6、7、8 级的四个中断请求同时到达，根据响应优先级，CPU 首先响应 5 级中断，设置中断屏蔽字后，由于 5 级中断的处理优先级高于 6、7、8 级中断，故 CPU 执行 5 级中断服务程序直至结束，返回原应用程序； 此时仍有 6、7、8 级三个中断请求，根据响应优先级，CPU 首先响应 6