# 2011年全国硕士研究生入学统一考试计算机科学与技术学科联考 # 计算机学科专业基础综合 (科目代码: 408) # 一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一项符合题目要求的。请在答题卡上将所选项的字母涂黑。） 1. 设 $n$ 是描述问题规模的非负整数, 下面程序片段的时间复杂度是 ```latex $\mathbf{x} = 2$ while $(x < n / 2)$ $\mathrm{x} = 2^{\star}\mathrm{x};$ ``` A. $0\left(\log_2 n\right)$ B. $0(\mathrm{n})$ C. $0(\mathrm{n} \log_2 \mathrm{n})$ D. $0\left(\mathrm{n}^{2}\right)$ 解答：A。程序中，执行频率最高的语句为“ $x = 2 * x$ ”。设该语句执行了t次，则 $2^{t + 1} = n / 2$ 故 $t = \log_2(n / 2) - 1 = \log_2n - 2 = 0 (\log_2n)$ 。 2. 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 A. 3 B. 4 C. 5 D. 6 解答：B。出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。 3. 已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是 A. 0,0 B. 0, n-1 C. n-1,0 D. n-1, n-1 解答：B。插入元素时，front不变，rear+1. 而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1, front为0。 4. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是 A. 257 B. 258 C. 384 D. 385 解答：C。叶结点数为n，则度为2的结点数为n-1, 度为1的结点数为0或1，本题中为1（总结点数为偶数），故而即 $2n = 768$ 。 5. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是 A. 1,2,3,4 B. 2,3,4,1 C. 3,2,4,1 D. 4,3,2,1 解答：C。由前序和后序遍历序列可知3为根结点，故（1,2）为左子树，（4）为右子树，C不可能。或画图即可得出结果。 6. 已知一棵有2011个结点的树, 其叶结点个数为 116 , 该树对应的二叉树中无右孩子的结点个数是 A. 115 B. 116 C. 1895 D. 1896 解答：D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子。 ![](https://408.foreverlink.love/images/9875f757330da832e9621c49836eefc6.jpg) 共1895个中间结点 共116个叶结点 7. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是 A. 95, 22, 91, 24, 94, 71 B. 92, 20, 91, 34, 88, 35 C. 21,89,77,29,36,38 D. 12, 25, 71, 68, 33, 34 解答：A。选项A中，当查到91后再向24查找，说明这一条路径之后查找的数都要比91小，后面的94就错了。 8. 下列关于图的叙述中，正确的是 I.回路是简单路径 II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列, 则该图不存在回路 A. 仅 II B. 仅 I、II C. 仅III D. 仅 I、III 解答：C。I.回路对应于路径，简单回路对应于简单路径；II．刚好相反；III．拓扑有序的必要条件。故选C。 9. 为提高散列（Hash）表的查找效率，可以采取的正确措施是 I. 增大装填（载）因子 II．设计冲突（碰撞）少的散列函数 III. 处理冲突（碰撞）时避免产生聚集（堆积）现象 A. 仅 I B. 仅 II C. 仅 I、II D. 仅 II、III 解答：B。III错在“避免”二字。 10. 为实现快速排序算法，待排序序列宜采用的存储方式是 A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 解答：A。内部排序采用顺序存储结构。 11. 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是 A. 1 B. 2 C. 4 D. 5 解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。 12. 下列选项中，描述浮点数操作速度指标的是 A. MIPS B. CPI C. IPC D. MFLOPS 解答：D。送分题。 13. float型数据通常用IEEE 754单精度浮点数格式表示。若编译器将float型变量x分配在一个32位浮点寄存器FR1中，且 $x = -8.25$ ，则FR1的内容是 A. C104 0000H B. C242 0000H C. C184 0000H D. C1C2 0000H 解答：A。x的二进制表示为-1000.01 = -1.000 01 × 211 根据IEEE754标准隐藏最高位的“1”，又E-127=3，所以E=130=1000 0010 (2) 数据存储为1位数符+8位阶码（含阶符）+23位尾数。 故FR1内容为1 10000 0010 0000 10000 0000 0000 0000 000 即1100000100000100000000000000，即C104000H 14. 下列各类存储器中，不采用随机存取方式的是 A. EPROM B. CDROM C. DRAM D. SRAM 解答：B。光盘采用顺序存取方式。 15. 某计算机存储器按字节编址，主存地址空间大小为64MB，现用 $4\mathrm{M} \times 8$ 位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是 A. 22位 B. 23位 C. 25位 D. 26位 解答：D。64MB的主存地址空间，故而MAR的寻址范围是64M，故而是26位。而实际的主存的空间不能代表MAR的位数。 16. 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是 A. 间接寻址 B. 基址寻址 C. 相对寻址 D. 变址寻址 解答：A。间接寻址不需要寄存器， $\mathrm{EA} = (\mathrm{A})$ 。基址寻址： $\mathrm{EA} = \mathrm{A}+$ 基址寄存器内同；相对寻址： $\mathrm{EA} = \mathrm{A} + \mathrm{PC}$ 内容；变址寻址： $\mathrm{EA} = \mathrm{A}+$ 变址寄存器内容。 17. 某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是 A. $CF + OF = 1$ B. $\overline{SF} + ZF = 1$ C. $\overline{CF + ZF} = 1$ D. $\overline{CF + SF} = 1$ 解答：C。无符号整数比较，如A>B，则A-B无进位/借位，也不为0。故而CF和ZF均为0。 18. 下列给出的指令系统特点中，有利于实现指令流水线的是 I. 指令格式规整且长度一致 II. 指令和数据按边界对齐存放 III. 只有Load/Store指令才能对操作数进行存储访问 A. 仅 I、II B. 仅 II、III C. 仅 I、III D. I 、II 、III 解答：D。指令定长、对齐、仅Load/Store指令访存，以上三个都是RISC的特征。均能够有效的简化流水线的复杂度。 19. 假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是 A. 每个指令周期中CPU都至少访问内存一次 B. 每个指令周期一定大于或等于一个CPU时钟周期 C. 空操作指令的指令周期中任何寄存器的内容都不会被改变 D. 当前程序在每条指令执行结束时都可能被外部中断打断 解答：C。会自动加1，A取指令要访存、B时钟周期对指令不可分割。 20. 在系统总线的数据线上，不可能传输的是 A. 指令 B. 操作数 C. 握手（应答）信号 D. 中断类型号 解答：C。握手（应答）信号在通信总线上传输。 21. 某计算机有五级中断 $\mathrm{L}_4 \sim \mathrm{L}_0$ ，中断屏蔽字为 $\mathrm{M}_4\mathrm{M}_3\mathrm{M}_2\mathrm{M}_1\mathrm{M}_0$ ， $\mathrm{M_i} = 1$ （ $0 \leqslant i \leqslant 4$ ）表示对 $\mathrm{L_i}$ 级中断进行屏蔽。若中断响应优先级从高到低的顺序是 $\mathrm{L}_4 \rightarrow \mathrm{L}_0 \rightarrow \mathrm{L}_2 \rightarrow \mathrm{L}_1 \rightarrow \mathrm{L}_3$ ，则 $\mathrm{L_i}$ 的中断处理程序中设置的中断屏蔽字是 A. 11110 B. 01101 C. 00011 D. 01010 解答：D。高等级置0表示可被中断，比该等级低的置1表示不可被中断。 22. 某计算机处理器主频为 $50 \mathrm{MHz}$ , 采用定时查询方式控制设备A的 $\mathrm{I} / \mathrm{O}$ , 查询程序运行一次所用的时钟周期数至少为 500。在设备A工作期间, 为保证数据不丢失, 每秒需对其查询至少 200 次, 则CPU用于设备A的 $\mathrm{I} / \mathrm{O}$ 的时间占整个CPU时间的百分比至少是 A. $0.02\%$ B. $0.05\%$ C. $0.20\%$ D. $0.50\%$ 解答：C。每秒200次查询，每次500个周期，则每秒最少 $200 \times 500 = 10000$ 个周期，10000÷50M=0.20%。 23. 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是 A. 先来先服务 B. 高响应比优先 C. 时间片轮转 D. 非抢占式短任务优先 解答：B。响应比 $=$ 作业响应时间/作业执行时间 $=$ （作业执行时间 $+$ 作业等待时间)/作业执行时间。高响应比算法，在等待时间相同情况下，作业执行时间越少，响应比越高，优先执行，满足短任务优先。随着等待时间增加，响应比也会变大，执行机会就增大，所以不会产生饥饿现象。先来先服务和时间片轮转不符合短任务优先，非抢占式短任务优先会产生饥饿现象。 24. 下列选项中，在用户态执行的是 A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序 解答：A。缺页处理程序和时钟中断都属于中断，在核心态执行。进程调度属于系统调用在核心态执行，命令解释程序属于命令接口，它在用户态执行。 25. 在支持多线程的系统中，进程P创建的若干个线程不能共享的是 A. 进程P的代码段 B. 进程P中打开的文件 C. 进程P的全局变量 D. 进程P中某线程的栈指针 解答：D。进程中某线程的栈指针，对其它线程透明，不能与其它线程共享。 26. 用户程序发出磁盘I/O请求后，系统的正确处理流程是 A. 用户程序 $\rightarrow$ 系统调用处理程序 $\rightarrow$ 中断处理程序 $\rightarrow$ 设备驱动程序 B. 用户程序 $\rightarrow$ 系统调用处理程序 $\rightarrow$ 设备驱动程序 $\rightarrow$ 中断处理程序 C. 用户程序 $\rightarrow$ 设备驱动程序 $\rightarrow$ 系统调用处理程序 $\rightarrow$ 中断处理程序 D. 用户程序 $\rightarrow$ 设备驱动程序 $\rightarrow$ 中断处理程序 $\rightarrow$ 系统调用处理程序 解答：B。输入/输出软件一般从上到下分为四个层次：用户层、与设备无关软件层、设备驱动程序以及中断处理程序。与设备无关软件层也就是系统调用的处理程序。所以争取处理流程为B选项。 27. 某时刻进程的资源使用情况如下表所示。
进程已分配资源尚需分配可用资源
R1R2R3R1R2R3R1R2R3
P1200001021
P2120132
P3011131
P4001200
此时的安全序列是 A. P1, P2, P3, P4 B.P1,P3,P2,P4 C. P1, P4, P3, P2 D. 不存在 解答：D。使用银行家算法得，不存在安全序列。 28. 在缺页处理过程中，操作系统执行的操作可能是 I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I、II B. 仅 II C. 仅III D. I 、II 和III 解答：D。缺页中断调入新页面，肯定要修改页表项和分配页框，所以I、I I I可能发生，同时内存没有页面，需要从外存读入，会发生磁盘I/O。 29. 当系统发生抖动（thrashing）时，可用采取的有效措施是 I. 撤销部分进程 II. 增加磁盘交换区的容量 III. 提高用户进程的优先级 A. 仅 I B. 仅 II C. 仅III D. 仅 I、II 解答：A。在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。抖动现象是指刚刚被换出的页很快又要被访问为此，又要换出其他页，而该页又快被访问，如此频繁的置换页面，以致大部分时间都花在页面置换上。撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都与抖动无关。 30. 在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是 A. 编辑 B. 编译 C. 链接 D. 装载 解答：B。编译过程指编译程序将用户源代码编译成目标模块。源地址编译成目标程序时，会形成逻辑地址。 31. 某文件占 10 个磁盘块, 现要把该文件磁盘块逐个读入主存缓冲区, 并送用户区进行分析, 假设一个缓冲区与一个磁盘块大小相同, 把一个磁盘块读入缓冲区的时间为 $100 \mathrm{us}$ , 将缓冲区的数据传送到用户区的时间是50us，CPU对一块数据进行分析的时间为50us。 在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是 A. 1500us、1000us B. 1550us、1100us C. 1550us、1550us D. 2000us、2000us 解答：B。单缓冲区下当上一个磁盘块从缓冲区读入用户区完成时下一磁盘块才能开始读入，也就是当最后一块磁盘块读入用户区完毕时所用时间为 $150 \times 10 = 1500$ 。加上处理最后一个磁盘块的时间50为1550。双缓冲区下，不存在等待磁盘块从缓冲区读入用户区的问题，也就是 $100 \times 10 + 100 = 1100$ 。 32. 有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。 // 加1操作 //减1操作 load R1, x // 取x到寄存器R1中 load R2, x inc R1 dec R2 store x，R1 // 将R1的内容存入x store x，R2 两个操作完成后，x的值 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 解答：C。将P1中3条语句变为1,2,3，P2中3条语句编为4，5，6。则依次执行1,2,3,4,5得结果1，依次执行1,2,4,5,6,3得结果2，执行4，5，1，2，3，6得结果0。结果-1不可能得出，选C。 33. TCP/IP参考模型的网络层提供的是 A. 无连接不可靠的数据报服务 B. 无连接可靠的数据报服务 C. 有连接不可靠的虚电路服务 D. 有连接可靠的虚电路服务 解答：A。TCP/IP的网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。此外考察IP首部，如果是面向连接的，则应有用于建立连接的字段，但是没有；如果提供可靠的服务，则至少应有序号和校验和两个字段，但是IP分组头中也没有（IP首部中只是首部校验和）。因此网络层提供的无连接不可靠的数据服务。有连接可靠的服务由传输层的TCP提供。 34. 若某通信链路的数据传输速率为2400bps，采用4相位调制，则该链路的波特率是 A. 600波特 B. 1200波特 C. 4800波特 D. 9600波特 解答：B。有4种相位，则一个码元需要由 $\log_24 = 2$ 个bit表示，则波特率 $=$ 比特率/2=1200波特。 35. 数据链路层采用选择重传协议（SR）传输数据，发送方已发送了 $0 \sim 3$ 号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是 A. 1 B. 2 C. 3 D. 4 解答：B。选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择ACK分组进行确认。因此选择重传协议中的ACK分组不再具有累积确认的作用。这点要特别注意与GBN协议的区别。此题中只收到1号帧的确认，0、2号帧超时，由于对于1号帧的确认不具累积确认的作用，因此发送方认为接收方没有收到0、2号帧，于是重传这两帧。 36. 下列选项中，对正确接收到的数据帧进行确认的MAC协议是 A. CSMA B. CDMA C. CSMA/CD D. CSMA/CA 解答：D。可以用排除法。首先CDMA即码分多址，是物理层的东西；CSMA/CD即带冲突检测的载波监听多路访问，这个应该比较熟悉，接收方并不需要确认；CSMA，既然CSMA/CD是其超集，CSMA/CD没有的东西，CSMA自然也没有。于是排除法选D。CSMA/CA是无线局域网标准802.11中的协议。CSMA/CA利用ACK信号来避免冲突的发生，也就是说，只有当客户端收到 网络上返回的ACK信号后才确认送出的数据已经正确到达目的地址。 37. 某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将 IP分组正确地路由到图中所有子网，则在R1中需要增加的一条路由（目的网络，子网掩码，下一跳）是 ![](https://408.foreverlink.love/images/326756aa7a20e87bfadb3bd6978c9734.jpg) A. 192.168.2.0 255. 255. 255. 128 192. 168. 1. 1 B. 192.168.2.0 255.255.255.0 192. 168. 1. 1 C. 192.168.2.0 255. 255. 255. 128 192. 168. 1. 2 D. 192.168.2.0 255.255.255.0 192. 168. 1. 2 解答：D。此题主要考察路由聚合。要使R1能够正确将分组路由到所有子网，则R1中需要有到192.168.2.0/25和192.168.2.128/25的路由。观察发现网络192.168.2.0/25和192.168.2.128/25的网络号的前24位都相同，于是可以聚合成超网192.168.2.0/24。从图中可以看出下一跳地址应该是192.168.1.2。 38. 在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的IP分组的最大主机数是 A. 0 B. 1 C. 2 D. 4 解答: C。首先分析 192.168.4.0/30 这个网络。主机号占两位, 地址范围 $192.168.4.0 / 30 \sim$ 192.168.4.3/30, 即可以容纳 (4-2=2) 个主机。主机位为全 1 时, 即 192.168.4.3, 是广播地址, 因此网内所有主机都能收到, 因此选 C。 39. 主机甲向主机乙发送一个 $(\mathrm{SYN} = 1, \mathrm{seq} = 11220)$ 的TCP段，期望与主机乙建立TCP连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP段可能是 A. $(\mathrm{SYN} = 0$ ，ACK $= 0$ ，seq $= 11221$ ，ack $= 11221)$ B. $(\mathrm{SYN} = 1$ ，ACK=1，seq=11220，ack=11220) C. $(\mathrm{SYN} = 1$ ，ACK=1，seq=11221，ack=11221) D. $(\mathrm{SYN} = 0$ ，ACK $= 0$ ，seq $= 11220$ ，ack $= 11220)$ 解答：C。主机乙收到连接请求报文后，如同意连接，则向甲发送确认。在确认报文段中应把SYN位和ACK位都置1，确认号是甲发送的TCP段的初始序号seq=11220加1，即为ack=11221，同时也要选择并消耗一个初始序号seq，seq值由主机乙的TCP进程确定，本题取seq=11221与确认号、甲请求报文段的序号没有任何关系。 40. 主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是 A. 300 B. 500 C. 1200 D. 1400 解答：B。TCP段首部中的序号字段是指本报文段所发送的数据的第一个字节的序号。第三个段的序号为900，则第二个段的序号为 $900 - 400 = 500$ 。而确认号是期待收到对方下一个报文段的第一个字节的序号。现在主机乙期待收到第二个段，故甲的确认号是500。 # 二、综合应用题： $41\sim 47$ 小题，共70分。请将答案写在答题纸指定位置上。 41.（8分）已知有6个顶点（顶点编号为 $0\sim 5$ ）的有向带权图G，其邻接矩阵A为上三角 矩阵，按行为主序（行优先）保存在如下的一维数组中。
46∞∞∞5∞∞∞43∞∞33
要求： （1）写出图G的邻接矩阵A。 （2）画出有向带权图G。 （3）求图G的关键路径，并计算该关键路径的长度。 # 解答： （1）图G的邻接矩阵A如下所示。 $$ A = \left( \begin{array}{c c c c c c} 0 & 4 & 6 & \infty & \infty & \infty \\ \infty & 0 & 5 & \infty & \infty & \infty \\ \infty & \infty & 0 & 4 & 3 & \infty \\ \infty & \infty & \infty & 0 & \infty & 3 \\ \infty & \infty & \infty & \infty & 0 & 3 \\ \infty & \infty & \infty & \infty & \infty & 0 \end{array} \right) $$ （2）有向带权图G如下图所示。 ![](https://408.foreverlink.love/images/cfe62de729ffa128e0c88dad864026e2.jpg) （3）关键路径为 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ （如下图所示粗线表示），长度为 $4 + 5 + 4 + 3 = 16$ 。 ![](https://408.foreverlink.love/images/a2933b897b314e3ea618ca40b1b465dc.jpg) 42.（15分）一个长度为 $\mathrm{L}(\mathrm{L}\geqslant 1)$ 的升序序列S，处在第 $\left\lfloor L / 2\right\rfloor$ 个位置的数称为S的中位数。 例如，若序列 $S1 = (11, 13, 15, 17, 19)$ ，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 $S2 = (2, 4, 6, 8, 20)$ ，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求： （1）给出算法的基本设计思想。 （2）根据设计思想，采用C或 $\mathrm{C + + }$ 或JAVA语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。 # 解答： （1）算法的基本设计思想如下。 分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数过程如下： 1）若 $a = b$ ，则a或b即为所求中位数，算法结束。 2) 若 $a < b$ , 则舍弃序列 $A$ 中较小的一半, 同时舍弃序列 $B$ 中较大的一半, 要求舍弃的长度相等; (3) 若 $a > b$ , 则舍弃序列 $A$ 中较大的一半, 同时舍弃序列 $B$ 中较小的一半, 要求舍弃的 长度相等； 在保留的两个升序序列中，重复过程1)、2)、3)，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。 （2）算法的实现如下： ```txt int M_Search(int A[], int B[], int n) { int s1 = 0, d1 = n - 1, m1, s2 = 1, d2 = n - 1, m2; //分别表示序列A和B的首位数、末位数和中位数 while (s1 != d1 || s2 != d2) { m1 = (s1 + d1) / 2; m2 = (s2 + d2) / 2; if (A[m1] == B[m2]) return A[m1]; //满足条件1) if (A[m1] < B[m2]) { //满足条件2) if ((s1 + d1) % 2 == 0) { //若元素个数为奇数 s1 = m1; //舍弃A中间点以前的部分且保留中间点 d2 = m2; //舍弃B中间点以后的部分且保留中间点 } else { //元素个数为偶数 s1 = m1 + 1; //舍弃A中间点及中间点以前部分 d2 = m2; //舍弃B中间点以后部分且保留中间点 } } else { //满足条件3) if ((s1 + d1) % 2 == 0) { //若元素个数为奇数 d1 = m1; //舍弃A中间点以后的部分且保留中间点 s2 = m2; //舍弃B中间点以前的部分且保留中间点 } else { //元素个数为偶数 d1 = m1 + 1; //舍弃A中间点以后部分且保留中间点 s2 = m2; //舍弃B中间点及中间点以前部分 } } } ``` （3）算法的时间复杂度为 $0(\log_2n)$ ，空间复杂度为 $O(1)$ 。 43.（11分）假定在一个8位字长的计算机中运行如下类C程序段： ```txt unsigned int $x = 134$ unsigned int $\mathrm{y} = 246$ int $\mathbf{m} = \mathbf{x}$ int $\mathrm{n} = \mathrm{y}$ unsigned int $\mathrm{z1} = \mathrm{x - y};$ unsigned int $\mathrm{z2} = \mathrm{x + y};$ int $\mathrm{k1} = \mathrm{m - n};$ int $\mathrm{k2} = \mathrm{m + n};$ ``` 若编译器编译时将8个8位寄存器 $\mathrm{Rl}\sim \mathrm{R8}$ 分别分配给变量x、y、m、n、z1、z2、k1和k2。请回答下列问题。（提示：带符号整数用补码表示） (1) 执行上述程序段后, 寄存器 R1、R5 和 R6 的内容分别是什么? (用十六进制表示) (2) 执行上述程序段后, 变量 m 和 k1 的值分别是多少? (用十进制表示) (3) 上述程序段涉及带符号整数加/减、无符号整数加/减运算, 这四种运算能否利用同一个加法器辅助电路实现? 简述理由。 （4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？ 解答： (1) $\mathbf{R} 1 = 134 = 86 \mathrm{H}, \mathrm{R} 5 = 90 \mathrm{H}, \mathrm{R} 6 = 7 \mathrm{CH}$ ; 134=1000 0110B=86H；x-y=1000 0110B-1111 0110B=1001 0000B=90H；x+y=1000 0110B+1111 0110B=0111 1100B（溢出） (2) $\mathbf{m} = -122, \mathbf{k1} = -112$ $\mathrm{m = 10000110B}$ ，做高位为符号位，则 $\mathfrak{m}$ 的原码为 $11111010\mathrm{B} = -122$ ； $\mathrm{n = 11110110B}$ n的原码为 $10001001 = -10$ ； $\mathrm{k1 = m - n = -112}$ 。 （3）无符号数和有符号数都是以补码的形式存储，加减运算没有区别（不考虑溢出情况时），只是输出的时候若是有符号数的最高位是符号位。 减法运算求 $[-x]_{\text{补}}$ 的时候，是连同符号位一起按位取反末位加1，但是如果有溢出情况，这两者是有区别的，所以可以利用同一个加法器实现，但是溢出判断电路不同。 （4）判断方法是如果最高位进位和符号位的进位不同，则为溢出；“int k2=m+n；”会溢出；三种方法可以判断溢出，双符号位、最高位进位、符号相同操作数的运算后与原操作数的符号不同则溢出 44.（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB；Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b图所示，图中页框号及标记字段的内容为十六进制形式。 题44-a图页表的部分内容
虚页号有效位页框号...
0106...
1104...
2115...
3102...
40-...
512B...
60-...
7132...
题44-b图Cache的部分内容
行号有效位标记...
01020...
10-...
2101D...
31105...
41064...
5114D...
60-...
7127A...
请回答下列问题。 （1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？ (2) 使用物理地址访问 Cache 时, 物理地址应划分成哪几个字段? 要求说明每个字段的位数及在物理地址中的位置。 (3) 虚拟地址 001C60H 所在的页面是否在主存中? 若在主存中, 则该虚拟地址对应的物理地址是什么? 访问该地址时是否 Cache 命中? 要求说明理由。 (4) 假定为该机配置一个 4 路组相联的 TLB 共可存放 8 个页表项, 若其当前内容 (十六进制) 如题 44-c 图所示, 则此时虚拟地址 024BACH 所在的页面是否存在主存中? 要求说明理由。 组号有效位标记页框号有效位标记页框号有效位标记页框号有效位标记页框号 题44-c图TLB的部分内容
010--1001150--10121F
10132D0--10087E0--
# 解答： # （1）24位、前12位；20位、前8位。 $16\mathrm{M} = 224$ 故虚拟地址24位， $4\mathrm{K} = 212$ ，故页内地址12位，所以虚页号为前12位； $1\mathrm{M} = 220$ 故物理地址20位， $20 - 12 = 8$ ，故前8位为页框号。 (2) # 主存字块标记（12bit）、cache字块标记（3bit）、字块内地址（5bit） 物理地址20位，其中，块大小为 $32\mathrm{B} = 25\mathrm{B}$ 故块内地址5位；cache共8行， $8 = 23$ ，故字块标记为3位； $20 - 5 - 2 = 12$ ，故主存字块标记为12位。 # (3) 在主存中, 04C60H, 不命中, 没有 04C 的标记字段 001C60H中虚页号为 $001\mathrm{H} = 1$ ，查页表知其有效位为1，在内存中；该物理地址对应的也表项中，页框号为04H故物理地址为04C60H；物理地址04C60H在直接映射方式下，对应的行号为4，有效位为1但是标记位为 $064\mathrm{H}\neq 04\mathrm{CH}$ 故不命中。 # （4）在，012 的那个标记是对的。 思路：标记11位组地址1位页内地址12位，前12位为000000100100，组地址位为0，第0组中存在标记为012的页，其页框号为1F，故024BACH所在的页面存在主存中。 # 45.（8分）某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下： ```txt cobegin {process顾客i{从取号机获取一个号码；等待叫号；获取服务；}process营业员while（TRUE）{叫号；为客户服务；} }coend ``` 请添加必要的信号量和 P、V（或 wait()、signal()）操作，实现上述过程中的互斥与同步。 要求写出完整的过程，说明信号量的含义并赋初值。 # 解答： ```txt semaphoreseets $= 10$ ，//有10个坐位的资源信号量 mesh $= 1$ ，//取号机互斥信号量 haveCustom $= 0$ ；//顾客与营业员同步，无顾客时营业员休息 process顾客 {P(seets)；//等空位P(mutex)；//申请使用取号机从取号机上取号；V(mutex)；//取号完毕V(haveCustom)；//通知营业员有新顾客到来等待营业员叫号；V(seets)；//离开坐位接受服务; } process营业员 {while(True){P(haveCustom)；//没有顾客则休息叫号；为顾客服务；} ``` 46.（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。 （1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要FCB中设计哪些相关描述字段？ (2) 为快速找到文件, 对于 FCB, 是集中存储好, 还是与对应的文件数据块连续存储好? 要求说明理由。 # 解答： (1) 连续更合适,因为一次写入不存在插入问题,连续的数据块组织方式完全可以满足一次性写入磁盘。同时连续文件组织方式减少了其他不必要的空间开销, 而连续的组织方式顺序查找读取速度是最快的。 (2) FCB 集中存储好。目录是存在磁盘上的，所以检索目录的时候需要访问磁盘，速度很慢；集中存储是将文件控制块的一部分数据分解出去，存在另一个数据结构中，而在目录中仅留下文件的基本信息和指向该数据结构的指针，这样一来就有效地缩短减少了目录的体积，减少了目录在磁盘中的块数，于是检索目录时读取磁盘的次数也减少，于是就加快了检索目录的次数。 47.（9分）某主机的MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100（私有地址）。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80个 字节的十六进制及 ASCII 码内容。 ![](https://408.foreverlink.love/images/c5ab2e5f3ba72a4212a890a10bedd4f6.jpg) 图47-a图网络拓扑
00000021272151ee0015c5c15e2808004500. !||Q... . . .^ (.E.
001001ef113b40008006ba9d0a02806440aa. . .@ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0020622004ff0050e0e200fa7bf9f8055018b . . .P. . . .{..}P. . . .
0030faf01ac40000474554202f7266632e68. . . .GE T /rfc.h
0040746d6c20485454502f312e310d0a4163tmI HTTP /1.1..Ac
请参考图中的数据回答以下问题。 （1）Web 服务器的 IP 地址是什么？该主机的默认网关的 MAC 地址是什么？ (2) 该主机在构造题 47-b 图的数据帧时, 使用什么协议确定目的 MAC 地址? 封装该协议请求报文的以太网帧的目的 MAC 地址是什么? (3) 假设 HTTP/1.1 协议以持续的非流水线方式工作, 一次请求-响应时间为 RTT, rfc.html 页面引用了 5 个 JPEG 小图像, 则从发出题 47-b 图中的 Web 请求开始到浏览器收到全部内容为止, 需要多少个 RTT? (4) 该帧所封装的 IP 分组经过路由器 R 转发时, 需修改 IP 分组头中的哪些字段? 注：以太网数据帧结构和IP分组头结构分别如题47-c图、题47-d图所示。
6B6B2B46-1500B4B
目的MAC地址源MAC地址类型数据CRC
![](https://408.foreverlink.love/images/0bd519f8e17083b53e1a33242b965c41.jpg) 题47-b图以太网数据帧（前80字节） 题47-c图以太网帧结构 题47-d IP分组头结构 # 解答： (1) 64.170.98.32 00-21-27-21-51-ee 以太网帧头部 $6 + 6 + 2 = 14$ 字节，IP数据报首部目的IP地址字段前有 $4*4 = 16$ 字节，从以太网数据帧第一字节开始数 $14 + 16 = 30$ 字节，得目的IP地址40aa6220(十六进制)，转换为十进制得64.170.98.32。以太网帧的前六字节00-21-27-21-51-ee是目的MAC地址，本题中即为主机的默认网关10.2.128.1端口的MAC地址。 (2) ARP FF-FF-FF-FF-FF-FF ARP协议解决IP地址到MAC地址的映射问题。主机的ARP进程在本以太网以广播的形式发送ARP请求分组，在以太网上广播时，以太网帧的目的地址为全1，即FF-FF-FF-FF-FF。 (3） 6 HTTP/1.1协议以持续的非流水线方式工作时，服务器在发送响应后仍然在一段时间内保持这段连接，客户机在收到前一个响应后才能发送下一个请求。第一个RTT用于请求web页面，客户机收到第一个请求的响应后(还有五个请求未发送)，每访问一次对象就用去一个RTT。故共 $1 + 5 = 6$ 个RTT后浏览器收到全部内容。 (4) 源IP地址0a 02 80 64改为650c7b0f 生存时间(TTL)减1 校验和字段重新计算 私有地址和Internet上的主机通信时，须有NAT路由器进行网络地址转换，把IP数据报的源IP地址(本题为私有地址10.2.128.100)转换为NAT路由器的一个全球IP地址(本题为101.12.123.15)。因此，源IP地址字段0a 02 80 64变为65 0c 7b 0f。IP数据报每经过一个路由器，生存时间TTL值就减1，并重新计算首部校验和。若IP分组的长度超过输出链路的MTU，则总长度字段、标志字段、片偏移字段也要发生变化。 注意，图47-b中每行前4bit是数据帧的字节计数，不属于以太网数据帧的内容。