1、计算机专业（基础综合）模拟试卷 90 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下面是有关 DRAM 和 SRAM 存储器芯片的叙述：I DRAM 芯片的集成度比 SRAM 高 DRAM 芯片的成本比 SRAM 高 DRAM 芯片的速度比 SRAM 快 DRAM 芯片工作时需要刷新，SRAM 芯片工作时不需要刷新通常情况下，错误的是( )。（A）I 和（B） 和（C） 和（D）I 和2 有 2 个优先级相同的并发进程 P1 和 P2，它们的执行过程如下图所示， x、y 和z 是共享变量。假设，当前信号量
2、 s10，s20，进程运行结束后， x、y 和 z 的值分别为( ) 。进程 P1 进程 P2 y：20； x：10；y：y1； x：x1；z：y1 ； P(s1) ；V(s1)； x：xy；P：(s2)； z：xz ；y：zy； V(s2)；（A）33，42，22 （B） 11，42，33 （C） 33，76，55 （D）33，76，333 一个支持并发的操作系统在运行过程中，调度模块会不断地选择新进程投入运行。在非抢先式操作系统中，下面不是引起操作系统重新选择新进程的直接原因是( )。（A）分配的时间片用完（B）运行着的进程要等待某一信号到来（C）正在运行的进程出错（D）有新进程进入就绪队
3、列4 下面包含在 TCP 头中而不包含在 UDP 头中的信息是( )。（A）目标端口号（B）序号（C）源端口号（D）校验号5 计算机硬件系统中“ 主机 ”是指( )。（A）主机箱及其内部硬件设备（B）运算器和控制器（C） CPU 和主存储器（D）CPU 、主存和输入输出设备6 对于一个长度为 n 的任意表进行排序，至少需要进行的比较次数是( )。（A）O(n)（B） O(n2)（C） O(log n)（D）O(nlog n)7 下面关于作为 PC 机内存使用的 ROM 和 RAM 的叙述中，错误的是( )。（A）ROM 和 RAM 都是半导体存储器（B） PC 机关机后，存储在 PC 机 CM
4、OS RAM 中的内容一般不会丢失（C） RAM 芯片掉电后，存放在芯片中的内容会丢失（D）Flash ROM 芯片中的内容经一次写入后再也无法更改8 CPU 在响应中断的过程中，保护现场的工作由( )完成。（A）中断隐指令（B）中断服务程序（C） A 或 B（D）A 和 B 共同 9 一台主机的 IP 地址为 1111100，子网掩码为 255000。现在用户需要配置该主机的默认路由。经过观察发现，与该主机直接相连的路由器具有如下 4个 IP 地址和子网掩码：IIP 地址：11111，子网掩码：2550 00IP 地址：11121，子网掩码：2550 00IP 地址：12111，子网掩码：2
5、550 00IP 地址：13121，子网掩码：2550 00那么 IP 地址和子网屏蔽码可能是该主机的默认路由的是 ( )。（A）I 和（B） I 和 I II（C） I和（D）和10 表示浮点数时，若要求机器零在计算机中的表示为全“0”，则阶码应采用的编码是( )。（A）原码（B）反码（C）补码（D）移码11 磁盘的平均存取时间是指平均寻道时间和平均等待时间之和。若磁盘的转速提高一倍，则( ) 。（A）平均存取时间减半（B）平均寻道时间减半（C）平均等待时间减半（D）以上都正确12 设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储， a1,1 为第一元素，其存储地址为 1，
6、每个元素占一个地址空间，则 a8,5 的地址是( )。（A）13（B） 33（C） 18（D）4013 磁盘和磁带是两种存储介质，他们的特点是( )。（A）二者都是顺序执行的（B）二者都是随机存取的（C）磁盘是顺序存取的，磁带是随机存取的（D）磁带是顺序存取的，磁盘是随机存取的14 多重中断方式下，开中断的时间应选择在( )之后。（A）保护断点（B）保护现场（C）中断周期（D）恢复现场15 中断向量的地址是( )。（A）子程序入口地址（B）中断服务例行程序入口地址（C）中断服务例行程序入口地址的地址（D）例行程序入口地址16 流水计算机中，下列语句发生的数据相关类型是( )。ADD R1，R2
7、，R3 ；(R2)+(R3)R1ADD R4，R1，R5 ；(R1)+(R5)R4（A）写后读（B）读后写（C）写后写（D）读后读17 DNS 作为一种分布式系统，所基于的网络应用模式是( ) 。（A）CS 模式（B） BS 模式（C） P2P 模式（D）以上均不正确18 在一条无条件跳转指令的指令周期内，程序计数器(PC)的值被修改了( )次(注：指令均为单字长指令，且按字寻址)。（A）1（B） 2（C） 3（D）不能确定19 某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为实现总线判优控制需要的控制线数为( )。（A）3（B） 16（C） 5（D）无法确定
8、20 对输入输出系统产生决定性影响的基本要求是( )。I异步性；同步性；分时性；实时性；V设备相关性；设备无关性；（A），V（B） I，（C） ，（D） I，V21 如果二叉树 T2 是由有序树 T1 转换而来的二叉树，那么 T1 中结点的后序就是T2 中结点的( )。（A）先序（B）中序（C）后序（D）层次序22 进程处于下列哪个等待状态时，它是处于非阻塞状态( )。（A）等待从键盘输入数据（B）等待协作进程的一个信号（C）等待操作系统分配 CPU 时间（D）等待网络数据进入内存23 适合多道程序运行的存储管理方法中，存储保护主要是( )。（A）防止一个进程占用一个分区（B）防止非法访问磁盘
9、文件（C）防止非法访问临界区（D）防止各道进程相互干扰24 RS 一 232 一 C 的电气特性规定逻辑“1” 的电平范围为 ( )。（A）+5+15V（B）一 5一 15V（C） 0+5V（D）05V25 计算机系统的层次结构，下列五个级别机器由下到上的顺序是( )。机器语言机器汇编语言机器高级语言机器微程序控制机器操作系统机器（A）（B） （C） （D）26 OSI 模型中完成路径选择功能的层次是( )。（A）物理层（B）数据链路层（C）网络层（D）传输层27 一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树的结点数是( )。（A）2 k1 1 （B） 2k1 （C
10、） 2k1 1 （D）2 k1 128 在虚拟存储系统中，若进程在内存中占 3 位(开始时为空)，采用先进先出页面淘汰算法，当执行访问页号序列为 1，2，3，4，1，2，5，1，2，3，4，5，6 时，将产生( ) 次缺页中断。（A）7（B） 8（C） 9（D）1029 对于硬盘上存放的信息，物理上读写的最小单位是一个( )。（A）二进制（B）字节（C）物理块（D）逻辑记录30 交叉存储器实质上是( )。（A）一种模块式存储器，能并行执行多个独立的读写操作（B）一种模块式存储器，能串行执行多个独立的读写操作（C）一种整体式存储器，能并行执行多个独立的读写操作（D）一种整体式存储器，能串行执行多
11、个独立的读写操作31 信号量 S 的初值定义为 5，在 S 上调用了 10 次 wait 操作和 8 次 signal 操作后，S 的值应为( )。（A）2（B） 3（C） 7（D）1332 二叉树的先序遍历和中序遍历的遍历结果如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是( )。（A）E（B） F（C） G（D）H33 操作系统中的 SPOOLing 技术，实质是将( )转化为共享设备的技术。（A）虚拟设备（B）独占设备（C）脱机设备（D）块设备34 对于 100Mbps 的以太网交换机，当输出端口无排队，以直通交换(cutthroughswitching
12、)方式转发一个以太网帧 (不包括前导码)时，引人的转发延迟至少是（A）0s（B） 048s（C） 512s（D）12144s35 对如下有向带权图，若采用迪杰斯特拉(I)ijkstra)算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是（A）d，e， f（B） e，d，f（C） f，d，e（D）f，e，d36 下列关于 USB 总线特性的描述中，错误的是（A）可实现外设的即插即用和热插拔（B）可通过级联方式连接多台外没（C）是一种通信总线，可连接不同外没（D）同时可传输 2 位数据，数据传输
13、率高37 38 39 下列有关 RAM 和 ROM 的叙述中，正确的是_。IRAM 是易失性存储器，ROM 是非易失性存储器RAM 和 ROM 都采用随机存取方式进行信息访问RAM 和 ROM 都可用作 CacheRAM 和 ROM 都需要进行刷新（A）仅 I 和（B）仅 和（C）仅 I、和（D）仅、和40 主机甲和主机乙之间已建立了一个 TCP 连接，TCP 最大段长度为 1000B。若主机甲的当前拥塞窗口为 4000B，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的第一个段的确认段，确认段中通告的接收窗口大小为 2000B，则此时主机甲还可以向主机乙发送的最大字节数是_。（A）
14、1000（B） 2000（C） 3000（D）4000二、综合应用题41-47 小题，共 70 分。41 已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序遍历访问的第一个结点，是否可不用递归且不用栈来完成?请简述原因。42 下图是某存储芯片的引脚图，请回答： (1)这个存储芯片的类型(是 RAM 还是ROM)?这个存储芯片的容量? (2) 若地址线增加一根，存储芯片的容量将变为多少 ? (3)这个芯片是否需要刷新? 为什么?刷新和重写有什么区别。 (4)如果需要刷新，请指出芯片刷新一遍需要的时间(设存取周期为 05s)及你准备选择的刷新方式，需说明理由。 43 并发使得处理机的利用率
15、得到提高，其主要原因是处理机与 IO 可以同时为多个进程服务，也即处理机与 IO 设备真正地并行。但是处理机的利用率提高并不是简单地将两个进程的处理机利用率相加，而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发，调度算法采用时间片轮转，时间片很小可以不计进程并发时的次序。忽略计算机系统的开销，请计算并填写下表以及甘特图的空缺内容：假设进程创建时间和完全占有 CPU 运行的确切时间如下表所示。已知其 IO繁忙率为 80，处理机的利用率为 20。 请计算并填写下列空格(填百分率) 和图表空格处(填时间) 。44 设有一个由正整数组成的无序(后向)单链表，编写能够完成下列功能的算法
16、：(1)找出最小值结点，且打印该数值。(2)若该数值为奇数，则将其与直接后继结点的数值交换。(3)若该数值为偶数，则将其直接后继结点删除。45 什么是单重分组和双重分组跳跃进位链?一个按 3，5，3，5 分组的双重分组跳跃进位链(最低位为第 0 位)，试问大组中产生的是哪几位进位?与 4，4，4，4 分组的双重分组跳跃进位链相比，试问产生全部进位的时间是否一致?为什么?46 已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key 1(key2n)； (2)关键字自大到小逆序
17、(key1key2keyn)； (3)奇数关键字顺序有序，偶数关键字顺序有序(key13，key 24212m，key m+1keym+2keyn，m 为中间位置)。47 采用敞列函数 H(k)=3kMOD13 并用线性探测开放地址法处理冲突，在散列地址空间0 ，12 中对关键字序列 22，41，53，46，30，13，1，67，51；(1)构造散列表；(2)计算装填因子；(3)等概率情况下查找成功的平均奄找长度；(4)等概率情况下查找失败的平均查找长度。计算机专业（基础综合）模拟试卷 90 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一
18、个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 DRAM 的集成度高于 SRAM，SRAM 的速度高于 DRAM，可以推出 DRAM 的成本低于 SRAM，SRAM 芯片工作时不需要刷新，DRAM 芯片工作时需要刷新。2 【正确答案】 C【试题解析】 本题考查并发进程的特点，并结合信号量进行同步的原理。由于进程并发，所以，进程的执行具有不确定性，在 P1、P2 执行到第一个 PV 操作前，应该是相互无关的。现在考虑第一个对 s1 的 PV 操作，由于进程 P2 是 P(s1)操作，所以，它必须等待 P1 执行完 V(s1)操作以后才可继续运行，此时的 xyz 值分别为11，21，2
19、2，当进程 P1 执行完 V(s1)以后便在 P(s2)上阻塞，此时 P2 可以运行直到 V(s2)，此时的 xyz 值分别为 33，21，55，进程 P1 继续运行直到结束，最终的xyz 值分别为 33，76，55 。在此需注意，xyz 应该是共享变量，若是私有变量，则进程 P1、P2 就各自独立对：xyz 操作。3 【正确答案】 D【试题解析】 本题考查进程调度的时机。在所列出的四个选项中，A 、B 和 C 的情况一旦发生，处理机空闲，操作系统必须立即调度其他进程，而 D 选项有新的进程进入就绪状态，如果操作系统采用的是抢先式调度，则立即激活调度模块，进行进程调度，进程调度的结果可能引起进
20、程切换，也可能维持当前进程运行而不切换；而当操作系统采用非抢先式调度方式时，当新进程进入就绪状态，若此时处理机正在忙于处理当前运行进程的请求，则不会激活调度模块。这里需要了解进程调度的细节问题。4 【正确答案】 B【试题解析】 本题主要考查 TCP 报文段和 UDP 报文段结构。TCP 数据报和UDP 数据报都包含目标端口、源端口、校验号。但是由于 UDP 是不可靠的传输，故数据报不需要编号，所以不会有序号这一字段，而 TCP 是可靠的传输，故需要设置序号这一字段，答案是 B。5 【正确答案】 C【试题解析】 CPU 和主存储器合称主机。6 【正确答案】 D【试题解析】 在排序过程中，每次比较
21、会有两种情况出现，若整个排序过程中至少需要 t 次 比较，则显然会有 2种情况，由于 n 个记录总共有 n!种不同的排列，因而必须有 n!种不同的比较路径，于是有：2 tn!，即 tlog2(n!)。因为 log2(n!)nlog2n，所以 tnlog2n。7 【正确答案】 D【试题解析】 ROM 和 RAM 都是半导体存储器，但 RAM 具有易失性但 CM()s RAM 不具有易失性，。Flash 中的内容可以多次改写。归纳总结(2M()S RAM 一般用来存储计算机系统每次开机时所需的重要信息，例如计算机存储容量、键盘类型、鼠标、监视器以及磁盘驱动器的有关信息。它与RAM 的区别在于，在
22、PC 机关机后其存储的信息不会丢失；它与 ROM 的区别在于，其内容随着计算机系统配置的改变或用户的设置可以发生变化。闪速存储器(Flash)是一种快擦写型存储器，它的主要特点是既可在不加电的情况下长期保存信息，又能在线进行快速擦除与重写，兼备了 EEPR()M 和 RAM 的优点。8 【正确答案】 D【试题解析】 保护现场包括保护程序断点和保护 CPU 内部各寄存器内容，其中，保护程序断点的任务由中断隐指令完成；而保护 CPU 内部其他寄存器的任务由中断服务程序来完成，故 D 为正确选项。9 【正确答案】 A【试题解析】 本题考查默认路由的配置，主机地址是一个标准的 A 类地址，其网络地址为
23、 11000。选项 I 的网络地址为 11 000，选项的网络地址为11000，选项的网络地址为 1200O ，选项的网络地址为13000，因此和主机在同一个网络是选项 I 和，因此答案为 A。10 【正确答案】 D【试题解析】 移码全为 0 时，它所对应的真值最小(绝对值最大的负数)。所以当阶码为全 0，尾数也为全 0 时，表示机器零。11 【正确答案】 C【试题解析】 磁盘平均等待时间一磁盘旋转一周所需时间2 一(1转速)2；故磁盘转速提高一倍，平均等待时间减半；但平均寻道时间与磁盘转速无关。故选C。12 【正确答案】 B【试题解析】 这里数组下标从 1 开始，只存储其下三角形元素，在 a
24、8,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。13 【正确答案】 D【试题解析】 本题主要考查磁盘和磁带的工作方式的区别。14 【正确答案】 B【试题解析】 多重中断方式下，为了能够及时响应其他更高优先级的中断，且保证能在响应更高优先级的中断后正确返回原中断服务程序，开中断的时间应选择在保护现场之后。15 【正确答案】 C【试题解析】 中断向量包括两个字：一个是中断处理程序的入口地址
25、；另一个是中断处理程序的程序状态字。那么显然，中断向量地址就是中断处理程序的入口地址的地址了。16 【正确答案】 A【试题解析】 数据相关包括写后读相关(RAW)、写后写相关(WAW)、读后写相关(WAR)。在这两条指令中，都对 R1 进行操作，其中前面对 R1 写操作，后面对R1 读操作，因此发生写后读相关。17 【正确答案】 A【试题解析】 本题考查网络应用模型，DNS 作为分布式应用，是一种典型的CS 模式。B S 模式又称 BS 结构，是随着 Internet 技术的兴起，对 CS 模式应用的扩展。因此答案为 A。18 【正确答案】 B【试题解析】 (1)取指周期结束后，PC 的值自动
26、加 1(因为指令为单字长指令，且按字寻址，故 PC+1)。(2)在执行周期中， PC 的值修改为要跳转到的地址。综上所述，在一条无条件跳转指令的指令周期内，程序计数器(PC)的值被修改了两次。可能考生会问，如果 PC 的值修改为跳转的指令，不是还要自增 1 吗?应该是 3次才对。其实不是这样的，无条件跳转指令的功能就是使得 PC 的内容改为所需跳转到的地址，PC 再自增已经不在这条指令的指令周期内。19 【正确答案】 A【试题解析】 链式请求方式下，为实现总线判优控制，需要一根总线请求线、一根总线忙线、一根总线同意线，共三根控制线。而 B 和 C 选项分别对应独立请求方式和计数器查询方式所需要
27、的线数。20 【正确答案】 B【试题解析】 输入输出系统的特点集中反映在异步性、实时性和设备无关性三项基本要求上，它们对输入输出系统的组织产生决定性的影响。21 【正确答案】 B【试题解析】 一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为 B。22 【正确答案】 C【试题解析】 进程有三个基本状态，处于阻塞状态的进程是由于某个事件不满足需求而等待的。这样的事件一般是 10 操作，例如键盘，磁盘等，或者是因互斥或同步数据引起的等待，例如等待信号或等待进入互斥临界区代码段等，等待网络数据进入内存是为了进程同步。而等待 CPU 调度的进
28、程是处于就绪态，只有它是非阻塞状态。23 【正确答案】 D【试题解析】 本题考查存储保护的目的。在多道程序设计的环境中，要保证各道进程只能在自己的存储区中活动，不能对别的程序产生干扰和破坏，尤其不能破坏操作系统的核心区。因此，必须对存储的信息采取各种保护措施，其目的是防止各道进程相互之间的干扰，甚至破坏。一个分区一般只分给一个进程独占使用，即使有空闲的空间，若是内碎片则一般也不能分给其它进程使用。磁盘和临界区访问不属于存储管理的范围。24 【正确答案】 B【试题解析】 RS 一 232 一 C 关于电气信号特性的要求，规定逻辑 “1”的电平为低于一 3V，为了表示一个逻辑 1 或 MARK 条
29、件，驱动器必须提供一 5V一 15V之间的电压；为了表示一个逻辑 0 或 SPACE 条件，驱动器必须给出+5V+15V之间的电压。25 【正确答案】 B【试题解析】 现代计算机系统是一个硬件与软件组成的综合体，可以把它看成是按功能划分的多级层次结构。26 【正确答案】 C【试题解析】 本题考查 OSI 模型中各个层次功能，完成路径选择，也就是路由功能的是网络层，答案是 C。27 【正确答案】 D【试题解析】 一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为0，也就是说每个非终端结点都有左子树和右子树且高度相等。因此，这样的平衡二叉树即为满二叉树，而高度为 k 的满二叉树的结点数是
30、 2k1。28 【正确答案】 D29 【正确答案】 C【试题解析】 硬盘的读取是以块为单位的。30 【正确答案】 A【试题解析】 多体交叉存储器把主存储器分成几个能独立读写的、字长为一个主存字的存储体，分别对每一个存储体进行读写；还可以使几个存储体协同运行，由存储器控制部件控制它们分时使用数据总线进行信息传递，这是一种并行存储器结构，从而提供出比单个存储体更高的读写速度。31 【正确答案】 B【试题解析】 s 初值为 5，每调用一次 wait 操作 s 减一，每执行一次 signal 操作s 加 1，故调用了 10 次 wait 操作和 8 次 signal 操作后 s 值为 5-10+8=3
31、。32 【正确答案】 C【试题解析】 由先序和中序遍历构造出二叉树，易知选 C。33 【正确答案】 B【试题解析】 SPOOLing 是 SimultaneotlsPeripheralOperationOnLine(即外部设备联机并行操作)的缩写。在 SPOOLing 系统中，实际上并没有真正的把设备分配给该进程，而只是在输入井和输出井中，为进程分配一存储区和建立一张 IO请求表。这样，便把独占设备改造为共享设备。34 【正确答案】 B【试题解析】 直通交换方式是指以太网交换机可以在各端口问交换数据。它在输入端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相
32、应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前 14个字节，由于不需要考虑前导码，只需要检测目的地址的 6B，所以最短的传输延迟是 048s。35 【正确答案】 C【试题解析】 根据迪杰斯特拉(Dijkstra) 算法，可以得到以下过程：从 a 出发，与其直接相邻的是 b(2)、c(5) ，因此可以得到第一条最短路径的目标顶点是 b。从a，h出发，与其相邻的是 c(3)、d(5)、e(6) ，因此可以得到第二条最短路径的目标顶点是 c。从 a,b，c出发，与其相邻的是 d(5)、e(6)、f(4)，因此可以得到第三条
33、最短路径的目标顶点是 f。从a，h，e，f 出发，与其相邻的是 d(5)、e(6)，因此可以得到第四、五条最短路径的目标顶点是 d、e。因此结点的顺序为 f、d、e，即C 选项。36 【正确答案】 D【试题解析】 USB 的全称是 universalSerialBus，最多可连接 127 台外设，由于USB 支持热插拔、即插即用的优点，所以 USB 接口已经成为计算机的标准接口。USB 没备之所以会被大量应用，主要具有以下优点： 可以热插拔。携带方便。标准统一。 可以连接多个没备。37 【正确答案】 A38 【正确答案】 B39 【正确答案】 A【试题解析】 考查半导体随机存取存储器。一般 C
34、ache 采用高速的 SRAM 制作，比 ROM 速度快很多，因此是错误的，排除法即可选 A。RAM 需要刷新，而ROM 不需要刷新。40 【正确答案】 A【试题解析】 考查 TCP 流量控制与拥塞控制。发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为min4000B，2000B)=2000B，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为 2000B1000B=1000B。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 可以。原因：后序遍历的顺序是“左子树右子树根结点” 。因此，二叉树
35、最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设 p 是二叉树根结点的指针)。if(p!=null)while(p-lchild!=nunll ll p-rchild!=null)while(p-lchild!=null)p=p-lchild；if(p-rehild!=null)p=p-rchild；return(p)； 返回后序序列第一个结点的指针42 【正确答案】 (1)芯片类型是 RAM，且为动态 RAM(DRAM)，芯片容量64K1。(2)由于地址线是复用的，若地址线增加一根，容量增加 4 倍，芯片的容量变为256K1。(3)需要刷新，因为是 DRAM 是用电容存储信
36、息的。重写是随机的，刷新是定时的。重写按存储单元进行，刷新按存储体一行行地进行。(4)64K1 芯片的内部为 256256 的矩阵，芯片刷新一遍需要的时间=25605s=128s 。采用异步刷新方式最好，死区小，刷新次数少。【试题解析】 第 43 题图中有地址线 8 根，输入输出数据线各 1 根，另有读写控制线丽和行、列选通线。从给出的芯片管脚可以看出，这是一个可读可写的动态随机存储 (DRAM)芯片。43 【正确答案】 根据题意，计算得到 U110 810220 U2 l 08 203636 U3108 304949 U4108 405959 【试题解析】 本题考查的是并发进程之间的计算。计
37、算机引入多道程序设计技术主要是为提高处理机的利用率。在多道程序并发的情况下，处理机的利用率呈现出如下的规律： U1p n 其中，U 为处理机利用率， p 为 IO 繁忙率，n 为并发进程数。据此，对题目给定的数据进行计算，并将结果填入表格中。 当 1 个进程运行时，处理机利用率为 20，这个进程独享该处理机，所以 20的利用率均被使用。在时刻 10：00 到 10：10 期间，进程 0 得到上述享受。这期间，进程 0 实际的处理机时间为 10 分202 分。 当 2 个进程运行时，根据公式计算得到处理机利用率为 36，2 个进程共享处理机，所以每个进程的处理机的利用率为 18。在时刻 10：1
38、0 到 10：15 期间，进程 0 和 1 共享处理机。这期间，进程 0 和 1 各自实际的处理机时间为 5 分36209 分。 当 3 个进程运行时，根据公式计算得到处理机利用率为 49，3 个进程共享处理机，所以每个进程的处理机的利用率为16。在时刻 10：15 到 10：20 期间，进程 0、1 和 2 共享处理机。这期间，进程0、1 和 2 各自实际的处理机时间为 5 分49308 分。 当 4 个进程运行时，根据公式计算得到处理机利用率为 59，4 个进程共享处理机，所以每个进程的处理机的利用率为 15。 从时刻 10：20 开始，4 个进程并发。那么，从图中可以看到，进程 0 已经
39、运行了 37 分，进程 1 运行了 17 分，进程 2 运行了 08 分，进程 3 刚运行，根据题目给出的个进程实际占有处理机的时间，我们可以看出，进程 0 还剩余时间 03 分，进程 1 还剩余 13 分，进程 2 还剩余 12 分，进程 3还剩余 2 分，显然，在并发并且平均使用处理机的情况下，进程结束的次序应该为0、2、1、3。 首先我们计算进程 0 还需要运行多少时间结束。经过刚才计算得知，进程 0 还剩余 03 分，那么，在 4 进程并发，处理机利用率为每进程 15的情况下，尚需要时间为 03152 分，由此得知，到 10：22 分时，进程 0 结束。 进程 0 退出以后，我们再计算
40、剩余进程的剩余时间为进程 1、2、3 分别为10、09、17 分，上面已经分析，下一个结束的进程是进程 2，所以，我们计算 091656 分，注意，此时是 3 个进程并发了，处理机的利用率为每进程 16，此处切记不可疏忽。到 10：276 分，进程 2 结束。 同理，进程 2 退出以后，我们再计算剩余进程的剩余时间为进程 1、3 分别为 01、08 分，上面已经分析，下一个结束的进程是进程 1，所以，我们计算 011806 分，再扫意，此时是 2 个进程并发了，处理机的利用率为每进程 18。到 10：282 分，进程 1 结束 同样计算，进程 1 退出以后，剩余进程 3 的剩余时间为 07 分
41、，我们计算得出 072035 分，而此时处理机的利用率为每进程 20。到10：317 分，进程 3 结束。 据此，填写下列各个表格和空格。44 【正确答案】 算法的思想是：采用从前向后扫描单链表的方法，边扫描边测试，根据测试结点执行相应的操作。算法描述如下：int Function(LinkList*la)int temp；LinkNode*p=L-next；单链表为空时返回LinkNode*q=p；if(p=NULL)return 0；*找到最小值结点*while(p!=NULL)if(p-dataq-data)q=p；p=p-next ；*打印最小值结点*printf(“Min：dn“，p
42、-data)；*功能点：若该数值为奇数，则将其与直接后继结点的数值交换*if(q-data2=1)temp=q- data；if(q-next=NULL)不存在直接后继结点return 0；q- data=q-next-data；q- next-data=temp；*功能点：若该数值为偶数，则将其直接后继结点删除*elseif(q-next=NULL)return 0；p=p-next ；q- next=p-next；free(p)；return 1；45 【正确答案】 单重分组即组内并行、组间串行的进位方式；双重分组即组内并行，组间也并行。双重分组跳跃进位链中一个按 3，5，3，5 分组，大
43、组中产生的进位输出是 C4、C 7、C 12 和 C15 而一个按 4，4，4，4 分组，大组中产生的进位输出是 C8、C 7、 C114 和 C15 虽然这两种方式小组内的位数不同，但产生全部进位的时间是一致的。因为两种方式都被分成 4 个小，假定一级“与门” 、“或门”的延迟时间定为 ty，则每一级进位的延迟时间为 2ty。C -1 经过 2ty 产生第 1 小组的进位及所有组进位产生函数 Gi*和组进位传递函数 Pi*；再经过 2ty，由大组产生相应的进位；再经过 2ty 后，才能产生第 2、3、4 小组内的其余的进位，所以最长的进位延迟时间都为 6ty。46 【正确答案】 依题意，最好
44、情况下的比较次数即为最少比较次数。(1)在这种情况下，插入第 i 个(2in)元素的比较次数为 1，因此，总的比较次数为 1+1+1+1=n 一 1。(2)在这种情况下，插入第 i 个(2in)元素的比较次数为 i，因此，总的比较次数为 2+3+4+n=(n 一 1)(n+2)2。(3)在这种情况下，比较次数最少的情况是所有纪录关键字均按升序排列，这时，总的比较次数为 n 一 1。(4)在这种情况下，后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少，此时前半部分的比较次数=m 一 1，后半部分的比较次数=(nm一 1)*(nm+2)2，因此，总的比较次数为 m 一 1+(nm
45、一 1)*(nm+2)2 一(n一 2)(n+8)8 (假设 n 偶数，m=n2)。【试题解析】 本题主要考查直接插入法的算法思想及性能分析。47 【正确答案】 用线性探测法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如下： (1)各关键字的散列函数值如下： H(22)=322 MOD 13=l； H(41)=341 MOD 13=6； H(53)=353 MOD 13=3； H(46)=346 MOD 13=8 ； H(30) ：330 MOD 13=12； H(13)=313 MOD 13=0； H(1)=31 MOD 13=3 ； H(67)=367 MOD 13：6： H(5
46、1)=351 MOD 13=10 。 采用线性探测法再散列法处理冲突，所构造的散列表为： (2)装填因子：关键字总数表长：913=0 7。(3) 设查找成功在每个关键字上是等概率的，则查找每个关键字的概率为 19，各关键字的比较次数分别为：所以 ASLsucc=(1+1+1+2+1+2+1+1+1)9=11 9(4)设不成功的查找在每个地址上发生的概率相同，平均概率为 113，对每个位置不成功查找的比较次数分别为：以散列地址在位置 2 的关键字为例，由于此处关键字为空，只需比较 1 次就可确定本次查找不成功；以散列地址在位置 3 的关键字为例，若该关键字不在散列表中，需要将它与从位置 3 开始向后直至位置 5 的关键字相比较。由于关键字 5 的关键字为空，所以不再向后比较，共比较 3 次，其他的类推得到。所以ASLsucc=(3+2+1+3+2+1+4+3+2+1+2+1+4)13=29 13
