2009统考计算机考研试题

　　29.假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度(电梯调度)算法得到的磁道访问序列是

　　A.110，170，180，195，68，45，35，12

　　B.110，68，45，35，12，170，180，195

　　C.110，170，180，195，12，35，45，68

　　D.12，35，45，68，110，170，180，195

　　30.文件系统中，文件访问控制信息存储的合理位置是

　　A.文件控制块 B.文件分配表 C.用户口令表 D.系统注册表

　　31.设文件F1的当前引用计数值为1，先建立F1的符号链接(软链接)文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是

　　A.0、1 B.1、1 C.1、2 D.2、1

　　32.程序员利用系统调用打开I/O设备时，通常使用的设备标识是

　　A.逻辑设备名 B.物理设备名 C.主设备号 D.从设备号

　　33.在OSI参考模型中，自下而上第一个提供端到端服务的层次是

　　A.数据链路层 B.传输层 C.会话层 D.应用层

　　34.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是

　　A.12kbps B.24 kbps C.48 kbps D.96 kbps

　　35.数据链路层采用了后退N帧(GBN)协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是

　　A.2 B.3 C.4 D.5

　　36.以太网交换机进行转发决策时使用的PDU地址是

　　A.目的物理地址 B.目的IP地址 C.源物理地址 D.源IP地址

　　37.在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200 000km/s。若最小数据帧长度减少800比特，则最远的两个站点之间的距离至少需要

　　A.增加160m B.增加80m C.减少160m D.减少80m

　　38.主机甲和主机乙间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是 A.500 B.700 C.800 D.1000

　　39.一个TCP连接总是以1KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是

　　A.7KB B. 8KB C. 9KB D. 16KB

　　40.FTP客户和服务器间传递FTP命令时，使用的连接是

　　A.建立在TCP之上的控制连接 B. 建立在TCP之上的数据连接

　　C. 建立在UDP之上的控制连接 D. 建立在UDP之上的数据连接

　　二. 综合应用题。共70分。

　　41.(10分)带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

　　①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;

　　②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v;

　　③重复步骤②，直到u是目标顶点时为止。

　　请问上述方法能否求得最短路径?若该方法可行，请证明之;否则，请举例说明。

　　42.(15分)已知一个带有表头结点的单链表，结点结构为

　　假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data值，并返回1;否则，只返回0。要求：

　　(1) 描述算法的基本设计思想

　　(2) 描述算法的详细实现步骤

　　(3) 根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C++或JAVA语言实现)，关键之处请给出简要注释。

　　43.(8分)某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

　　(1)在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?

　　(2)当该外设的数据传输率达到5MB/s时，改用DMA方式传送数据。假设每次DMA传送大小为5000B，

　　且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?(假设DMA与CPU之间没有访存冲突)

　　44.(13分)某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR，MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状态。加法指令“ADD(R1)，R0”的功能为(R0)+((R1))→(R1)，即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。

　　数据通路结构

　　下表给出了上述指令取值和译码阶段每个节拍(时钟周期)的功能和有效控制信号，请按表中描

　　述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。

　　功能和控制信号

　　45.(7分)三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

　　46.(8分)请求分页管理系统中，假设某进程的页表内容如下表所示。

　　页面大小为4KB，一次内存的访问时间是100ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设

　　①TLB初始为空;

　　②地址转换时先访问TLB，若TLB未命中，再访问页表

　　(忽略访问页表之后的TLB更新时间);

　　③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列

　　2362H、1565H、25A5H，请问：