二叉树中 计算机考研408真题及答案(6)

27.段号占 8 位，则段内地址 24 位。也就是 2^24 位，即 2^21 字节。 29.SCAN 调度算法就是电梯调度算法，顾名思义就是如果开始时磁头往外就一直要到最外 面，然后再返回向里（磁头编号一般是最外面为 0 号往里增加） ，就像电梯若往下则一直要 下到最底层才会再上升一样。 32.无论有多少物理设备都要映射为逻辑设备使用。这些设备在程序员看来是没有差别的。 33.传输层和应用层都是端到端的。自下而上次一个端到端的是传输层。 35.在后退N协议式ARQ中，接收方应以正确的顺序把沙鸥到的报文递交到主机。发送方在不 等待确认就连续发送许多帧的情况下，有可能发了N个帧以后，才发现尚未收到对前面帧的 确认信息，也许某个帧在传输过程中出错了。接收方因这一帧出错，查出后不会交给本地主 机，对后面再发送来的N个帧也可能均不接收而丢弃。换句话说，接收方只能按顺序接收。 36.以太网交换机工作在物理层，所以进行交换决策时使用的是物理地址。 38. 主机乙发送给主机甲的确认序列号是期待接收到的数据的序列号 39.拥塞控制是指节制沿着一条通路的分组流以保持网络部件免于变得过量拥挤所采用的控 制规程。

二． 综合应用题 41.该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的 原则，从 A 到 C 的最短路径为 A→B→C，事实上其最短路径为 A→D→C。42. （1）算法基本思想如下：从头至尾遍历单链表，并用指针 P 指向当前节点的前 K 个节点。 当遍历到链表的最后一个节点时，指针 P 所指向的节点即为所查找的节点。 （2）详细实现步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针 P1 指向当前遍历的节点， 指针 P 指向 P1 所指向节点的前 K 个节点， 如果 P1 之前没有 K 个节点， 那么 P 指向表头节点。用整型变量 i 表示当前遍历了多少节点，当 i>k 时，指针 p 随着每次 遍历，也向前移动一个节点。当遍历完成时，p 或者指向表头就节点，或者指向链表中倒数第 K 个位置上的节点。 （3）算法描述： Int LocateElement(linklist list,int k) { P1=list->link; P=list; i=1; while(P1) { P1=P1->link; i++; if(i>k) p=p->next; //如果 i>k,则 p 也往后移 } if(p==list)return 0; //说明链表没有 k 个结点 else { printf(“%d\n“,p->data); return 1; } }43. （1）在中断方式下，每 32 位（4B）被中断一次，故每秒中断 0.5MB/4B=0.5×106/4=12.5×104 次 要注意的是，这里是数据传输率，所以 1MB=106B。

因为中断服务程序包含 18 条指令，中断 服务的其他开销相当于 2 条指令的执行时间，且执行每条指令平均需 5 个时钟周期，所以， 1 秒内用于中断的时钟周期数为 （18+2）×5×12.5×104=12.5×106 （2）在 DMA 方式下，每秒进行 DMA 操作 5MB/5000B=5×106/5000=1×103 次因为 DMA 预处理和后处理的总开销为 500 个时钟周期， 所以 1 秒钟之内用于 DMA 操作的时钟周期数为 500×1×103=5×105 故在 DMA 方式下，占整个 CPU 时间的百分比是 （ （5×105）/（500×106） ）×100%=0.1% 44.指令执行阶段每个节拍的功能和有效控制信号如下所示 时钟 C5 C6 C7 C8 C9 C10 功能 MAR←(R1) MDR←M(MAR) A←(R0) AC←(MDR)+(A) MDR←(AC) M(MAR) ←MDR 有效控制信号 PCout,MARin MemR,MDRinE R0out,Ain MDRout,Addr,ACin ACout,MDRin MDRoutE,MemW45.定义信号量 S1 控制 P1 与 P2 之间的同步； S2 控制 P1 与 P3 之间的同步； empty 控制生产 者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区。