https://hwpno1.blog.csdn.net/article/details/88634013?spm=1001.2014.3001.5502
预览：
2019 年全国硕士研究生招生考试
计算机科学与技术学科联考
计算机学科专业基础综合试题
一、 单项选择题： 1~40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项符合试题要求。
1.? ? ?设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是
x=0 ；
while ( n>= ( x+l ) * ( x+l ))
x=x+l ；
a.? o ( log n )? ? ?b.? o ( n 1/2 )? ? ?c.? o ( n )? ? ?d.? o ( n 2 )
2.? ? ?若将一棵树 t 转化为对应的二又树 bt ，则下列对 bt 的遍历中，其遍历序列与 t 的后根遍历序列相同的是
a.? 先序遍历? ? ?b.? 中序遍历? ? ?c.? 后序遍历? ? ?d.? 按层遍历
3.? ? ?对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是
a.? 56? ? b.? 57? ? c.? 58? ? d.? 60
4.? ? ?在任意一棵非空平衡二又树 ( avl 树 ) t 1 中，删除某结点 v 之后形成平衡二又树 t 2 ，再将 w 插入 t 2 形成平衡二又树 t 3 。下列关于 t 1 与 t 3 的叙述中，正确的是
i. 若 v 是 t 1 的叶结点，则 t 1 与 t 3 可能不相同
ⅱ. 若 v 不是 t 1 的叶结点，则 t 1 与 t 3 一定不相同
ⅲ. 若 v 不是 t 1 的叶结点，则 t 1 与 t 3 一定相同
a.? 仅 i? ? ? b.? 仅 i i? ? ? c.? 仅 i 、 ⅱ? ? ? d.? 仅 i 、 ⅲ
?5.? ? ?下图所示的 aoe 网表示一项包含 8 个活动的工程 。 活动 d 的最早开始时间和最迟开始时间分别是
a.? 3 和 7? ? ?b.? 12 和 12? ? ?c.? 12 和 14? ?d.? 15 和 15
6.? ? ?用有向无环图描述表达式 ( x+y ) * (( x+y ) /x ) ，需要的顶点个数至少是
a.? 5? ? ?b.? 6? ? ? ?c.? 8? ? ?d.? 9
7.? ? ?选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是
i . 数据的规模? ? ? ?ⅱ. 数据的存储方式? ? ?ⅲ. 算法的稳定性? ? ?v. 数据的初始状态
a.? 仅 ⅲ? ?b.? 仅 i 、 ⅱ? ? ? ?c.? 仅 ⅱ 、 ⅲ 、 iv? ? ?d.? i 、 ⅱ 、 ⅲ 、 ⅳ
8.? ? ?现有长度为 11 且初始为空的散列表 ht ，散列函数是 h ( key ) =key%7 ，采用线性探查 ( 线性探测再散列 ) 法解决冲突将关键字序列 87 ， 40 ， 30 ， 6 ， 11 ， 22 ， 98 ， 20 依次插入到 ht 后， ht 查找失败的平均查找长度是
a.? 4? ? ? ? ?b.? 5. 25? ? ? ? ? ?c.? 6? ? ? ? ? ?d.? 6. 29
9.? ? ?设主串 t=“abaabaabcabaabc” ，模式串 s=“abaab c ” ，采用 kmp 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是
a.? 9? ? ? ? ?b.? 10? ? ? ? ? ?c.? 12? ? ? ? ? ?d.? 15
10 .? ? 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一 “ 趟 ” 。下列序列中，不可能是快速排序第二趟结果的是
a.? 5 ， 2 ， 16 ， 12 ， 28 ， 60 ， 32 ， 72? ? ?b.? 2 ， 16 ， 5 ， 28 ， 12 ， 60 ， 32 ， 72
c.? 2 ， 12 ， 16 ， 5 ， 28 ， 32 ， 72 ， 60? ? ?d.? 5 ， 2 ， 12 ， 28 ， 16 ， 32 ， 72 ， 60
11 .? ? 设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是
a.? 1? b.? 2? c.? 3? d.? 4
12 .? ? 下列关于冯 · 诺依曼结构计算机基本思想的叙述中，错误的是
a.? 程序的功能都通过中央处理器执行指令实现
b.? 指令和数据都用二进制表示，形式上无差别
c.? 指令按地址访问，数据都在指令中直接给出
d.? 程序执行前，指令和数据需预先存放在存储器中
13 .? ? 考虑以下 c 语言代码：
unsigned short usi=65535 ；
short si=usi ；
执行上述程序段后， si 的值是
a.? -1? ? ? ? b.? -32767? ? ? ? c.? -32768? ? ? d.? -65535
14 .? ? 下列关于缺页处理的叙述中，错误的是
a.? 缺页是在地址转换时 cpu 检测到的一种异常
b.? 缺页处理由操作系统提供的缺页处理程序来完成
c.? 缺页处理程序根据页故障地址从外存读入所缺失的页
d.? 缺页处理完成后回到发生缺页的指令的下一条指令执行
15 .? ? 某计算机采用大端方式，按字节编址。某指令中操作数的机器数为 1234 ff00h ，该操作数采用基址寻址方式，形式地址 ( 用补码表示 ) 为 ff12h ，基址寄存器内容为 f000 0000h ，则该操作数的 lsb ( 最低有效字节 ) 所在的地址是
a.? f000 ff12h? ? ? ? b.? f000 ff15h? ? ? c.? efff ff12h? ? d.? efff ff15h
16.? ? ?下列有关处理器时钟脉冲信号的叙述中，错误的是
a.? 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成
b.? 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频
c.? 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准 确定
d.? 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令
17.? ? ?某指令功能为 r[r2] ← r[r1]+m[r[r0]] ，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是
i. 通用寄存器组 ( gprs )? ? ? ? ? ?ⅱ. 算术逻辑单元 ( alu )
ⅲ . 存储器 ( memory )? ? ? ? ?ⅳ. 指令译码器 ( id )
a.? 仅 i 、 ⅱ? ? b.? 仅 i 、 ⅱ 、 ⅲ? ? ?c.? 仅 ⅱ 、 ⅲ 、 iv? ? d.? 仅 i 、 ⅲ 、 ⅳ
18.? ? ?在采用 “ 取指、译码 / 取数、执行、访存、写回 ”5 段流水线的处理器中，执行如下指令序列，其中 s0 、 s1 、 s2 、 s3 和 t2 表示寄存器编号。
i1 ： add s2 ， s1 ， s0 //r[s2] ← r[s1]+r[s0]
i2 ： load s3 ， 0 ( t2 )? ? //r[s3] ← m[r[t2]+0]
i3 ： add s2 ， s2 s3 //r[s2] ← r[s2]+r[s3]
i4 ： store s2 ， 0 ( t 2 )? ? ? ?//m[r[t2]+0] ← r[s2]
下列指令对中，不存在数据冒险的是
a.? i1 和 i3? ? ? ? ? b.? i2 和 i3? ? ? c.? i2 和 i4? ? ? d.? i3 和 i4
19.? ? ?假定一台计算机采用 3 通道存储器总线，配套的内存条型号为 ddr3-1333 ，即内存条所接插的存储器总线的工作频率为 1333? ?mhz 、总线宽度为 64 位，则存储器总线的总带宽大约是
a. 10.? ?66 gb/s? ? ? b.? 32 gb/s? ? ? c.? 64 gb/s? ? ? d.? 96 gb/s
20.? ? ?下列关于磁盘存储器的叙述中，错误的是
a.? 磁盘的格式化容量比非格式化容量小
b.? 扇区中包含数据、地址和校验等信息
c.? 磁盘存储器的最小读写单位为一个字节
d.? 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成
21 .? ? 某设备以中断方式与 cpu 进行数据交换， cpu 主频为 1 ghz ，设备接口中的数据缓冲寄存器为 32 位，设备的数据传输率为 50kb/s 。若每次中断开销 ( 包括中断响应和中断处理 ) 为 1000 个时钟周期， 则 cpu 用于该设备输入 / 输出的时间占整个 cpu 时间的百分比最多是
a.? 1. 25%? ? ? ? ? ? ?b.? 2. 5%? ? ? ? ?c.? 5%? ? ? ? ?d.? 12.? 5%
22 .? ? 下列关于 dma 方式的叙述中，正确的是
i .? dma 传送前由设备驱动程序设置传送参数
i i
. 数据传送前由 dma 控制器请求总线使用权
ⅲ. 数据传送由 dma 控制器直接控制总线完成
i v .dma 传送结束后的处理由中断服务程序完成
a.? 仅 i 、 ⅱ? ? ? ? ?b.? 仅 ⅰ 、 ⅲ 、 ⅳ? ? ?c.? 仅 ⅱ 、 ⅲ 、 i v? ? ?d.? i 、 ⅱ 、 ⅲ 、 i v
23 .? ? 下列关于线程的描述中，错误的是
a.? 内核级线程的调度由操作系统完成
b.? 操作系统为每个用户级线程建立一个线程控制块
c.? 用户级线程间的切换比内核级线程间的切换效率高
d.? 用户级线程可以在不支持内核级线程的操作系统上实现
24.? ? ?下列选项中，可能将进程唤醒的事件是
i.? ?i/ o 结束? ? ? ? ? ? ?ⅱ.? ?某进程退出临界区? ? ? ? ?ⅲ .? ?当前进程的时间片用完
a.? 仅 i? ? ? ? ? ?b.? 仅 ⅲ? ? ? ? ? ?c.? 仅 i 、 ⅱ? ? ? ?d.? i 、 ⅱ 、 ⅲ
25.? ? ?下列关于系统调用的叙述中，正确的是
i. 在执行系统调用服务程序的过程中， cpu 处于内核态
ⅱ. 操作系统通过提供系统调用避免用户程序直接访问外设
ⅲ. 不同的操作系统为应用程序提供了统一的系统调用接口
i v . 系统调用是操作系统内核为应用程序提供服务的接口
a.? 仅 i 、 iv? ? ? ? b .? 仅 ii 、 iii? ? ? ? ?c.? 仅 i 、 ⅱ 、 iv? ? ?d.? 仅 i 、 ⅲ 、 ⅳ
26.? ? ?下列选项中，可用于文件系统管理空闲磁盘块的数据结构是
i. 位图? ? ? ? ?ⅱ. 索引节点? ? ? ?ⅲ . 空闲磁盘块链? ? ?ⅳ. 文件分配表 ( fat )
a.? 仅 i 、 ⅱ? ? ? ? ?b.? 仅 ⅰ 、 ⅲ 、 ⅳ? ? ? ?c.? 仅 l 、 ⅲ? d.? 仅 ⅱ 、 ⅲ 、 ⅳ
27.? ? ?系统采用二级反馈队列调度算法进行进程调度。就绪队列 q1 采用时间片轮转调度算法，时间片为 10ms ；就绪队列 q2 采用短进程优先调度算法；系统优先调度 q1 队列中的进程，当 q1 为空时系统才会调度 q2 中的进程；新创建的进程首先进入 q1 ； q1 中的进程执行一个时间片后，若未结束，则转入 q2 。若当前 q1 、 q2 为空，系统依次创建进程 pl 、 p2 后即开始进程调度 pl 、 p2 需要的 cpu 时间分别为 30ms 和 20ms ，则进程 p1 、 p2 在系统中的平均等待时间为
a.? 25 ms? ? ? ? b.? 20 ms? ? ? ? c.? 15 ms? ? ? d.? 10 ms
28.? ? ?在分段存储管理系统中，用共享段表描述所有被共享的段。若进程 p1 和 p2 共享段 s ，下列叙述中，错误的是
a.? 在物理内存中仅保存一份段 s 的内容
b.? 段 s 在 p1 和 p2 中应该具有相同的段号
c.? p1 和 p2 共享段 s 在共享段表中的段表项
d.? p1 和 p2 都不再使用段 s 时才回收段 s 所占的内存空间
29.? ? ?某系统采用 lru 页置换算法和局部置换策略，若系统为进程 p 预分配了 4 个页框，进程 p 访问页号的序列为 0 ， 1 ， 2 ， 7 ， 0 ， 5 ， 3 ， 5 ， 0 ， 2 ， 7 ， 6 ，则进程访问上述页的过程中，产生页置换的总次数是
a.? 3? ? ? ? ? ? b.? 4? ? ? ? ? ? c.? 5? ? ? ? ? d.? 6
30.? ? ?下列关于死锁的叙述中，正确的是
i .? ?可以通过剥夺进程资源解除死锁
i i .? ?死锁的预防方法能确保系统不发生死锁
i ii .? ?银行家算法可以判断系统是否处于死锁状态
ⅳ.? ?当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
a.? 仅 ii 、 ⅲ? ? ? ? b.? 仅 i 、 ⅱ 、 ⅳ? ? ? ?c.? 仅 i 、 ⅱ 、 ⅲ? ? d.? 仅 i 、 ⅲ 、 ⅳ
31 .? ? 某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示
页目录号 ( 10 位 )? ? ?页号 ( 10 位 )? ? ?页内偏移 ( 12 位 )
虚拟地址 2050? ?1225h 对应的页目录号、页号分别是
a.? 081h 、 101h? ? ? ?b.? 081h 、 401h? ? ? ? ?c.? 201h 、 101h? ? ?d.? 201h 、 401h
32 .? ? 在下列动态分区分配算法中，最容易产生内存碎片的是
a.? 首次适应算法? ? ? ? ?b.? 最坏适应算法? ? ? ? ?c.? 最佳适应算法? ? ? ?d.? 循环首次适应算法
33 .? ? osi 参考模型的第 5 层 ( 自下而上 ) 完成的主要功能是
a.? 差错控制? ? ? ? ?b.? 路由选择? ? ? ? ?c.? 会话管理? ? ? ?d.? 数据表示转换
34.? ? ?100baset 快速以太网使用的导向传输介质是
a.? 双绞线? ? ? ? ?b.? 单模光纤? ? ? ? ?c.? 多模光纤? ? ? ?d.? 同轴电缆
35.? ? ?对于滑动窗口协议，如果分组序号采用 3 比特编号，发送窗口大小为 5 ，则接收窗口最大是
a.? 2? ? ? ? ? ? ?b.? 3? ? ? ? ? ? ?c.? 4? ? ? ? ? ?d.? 5
36.? ? ?假设一个采用 csma/cd 协议的 100mbps 局域网，最小帧长是 128? ?b ，则在一个冲突域内两个站点之间的单向传播延时最多是
a.? 2. 56? μ s? ? ? ? ? ?b.? 5. 12? μ s? ? ? ? ? ? ?c.? 10. 24? μ s? ? ? ? ?d.? 20. 48? μ s
37.? ? ?若将 1 01.? ?2 00.? ?16.? ?0/20 划分为 5 个子网，则可能的最小子网的可分配 ip 地址数是
a.? 126? ? ? ? ? ?b.? 254? ? ? ? ? ?c.? 510? ? ? ? ?d.? 1022
?38.? ? ?某客户通过一个 tcp 连接向服务器发送数据的部分过程如题 38 图所示 。 客户在 t 0 时刻第一次收到确认序列号 ack_seq= 1 00 的段，并发送序列号 seq=100 的段，但发生丢失。若 tcp 支持快速重传，则客户重新发送 seq=100 段的时刻是
a.? t 1? ? ? ? ?b.? t 2? ? ? ? ?c.? t 3? ? ? ?d.? t 4
39.? ? ?若主机甲主动发起一个与主机乙的 tcp 连接，甲、乙选择的初始序列号分别为 2018 和 2046 ，则第三次握手 tcp 段的确认序列号是
a.? 2018? ? ? ?b.? 2019? ? ? ?c.? 2046? ? ?d.? 2047
40.? ? ?下列关于网络应用模型的叙述中，错误的是
a.? 在 p2p 模型中，结点之间具有对等关系
b.? 在客户 / 服务器 ( c/s ) 模型中，客户与客户之间可以直接通信
c.? 在 c/s 模型中，主动发起通信的是客户，被动通信的是服务器
d.? 在向多用户分发一个文件时， p2p 模型通常比 c/s 模型所需时间短
二、综合应用题： 41~47 小题，共 70 分。
41.? ?( 13 分 ) 设线性表 l= ( a1 ， a2 ， a… ， an-2 ， a-1 ， a 。 ) 采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node? {
int data ；
struct node*? ?next ；
}? node ；
请设计一个空间复杂度为 o ( 1 ) 且时间上尽可能高效的算法，重新排列 l 中的各结点，得到线性表 l= ( a 1 ， a n ， a 2 ， a n-1 ， a 3 ， a n-2 … ) 。
要求：
( 1 )? ?给出算法的基本设计思想
( 2 )? ?根据设计思想，采用 c 或 c++ 语言描述算法，关键之处给出注释。
( 3 )? ?说明你所设计的算法的时间复杂度。
42.? ?( 10 分 ) 请设计一个队列，要求满足： ① 初始时队列为空； ② 入队时，允许增加队列占用空间； ③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减； ④ 人队操作和出队操作的时间复杂度始终保持为 o ( 1 ) 。请回答下列问题：
( 1 )? ?该队列应该选择链式存储结构，还是顺序存储结构？
( 2 )? ?画出队列的初始状态，并给出判断队空和队满的条件
( 3 )? ?画出第一个元素 入 队后的队列状态。
( 4 )? ?给出入队操作和出队操作的基本过程。
43.? ?( 8 分 ) 有 n ( n≥3 ) 位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m ( m≥1 ) 个碗，每两位哲学家之间有 1 根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的 p 、 v 操作 ( wait () 、 signal () 操作 ) 描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
44.? ?( 7 分 ) 某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小为 512b 。文件系统的每个簇包含 2 个扇区。请回答下列问题：
( 1 )? ?磁盘的容量是多少？
( 2 )? ?假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为： 100260 、 60005 、 101660 和 110560 。若采用最短寻道时间优先 ( sstf ) 调度算法，则系统访问簇的先后次序是什么？
( 3 )? ?第 100530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 i/o 系统的什么程序完成的？
45.? ?( 16 分 ) 已知 f ( n ) =n ！ =n × ( n-l ) × ( n-2 ) × … × 2×1 ，计算 f ( n ) 的 c 语言函数 fl 的源程序 ( 阴影部分 ) 及其在 32 位计算机 m 上的部 分机器级代码如下：
??
?
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 m 按字节编址， int 型数据占 32 位。请回答下列问题：
( 1 )? ?计算 f ( 10 ) 需要调用函数 f 1 多少次？执行哪条指令会递归调用 f 1 ？
( 2 )? ?上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？
( 3 )? ?根据第 16 行 call 指令，第 17 行指令的虚拟地址应是多少？已 知第 16 行 call 指令采用相对寻址方式，该指令中的偏移量应是多少 ( 给出计算过程 ) ？已知第 16 行 call 指令的后 4 字节为偏移量， m 采用大端还是小端方式？
( 4 )? ?f ( 13 ) =6? ?227? ?020? ?800 ，但 f 1 ( 13 ) 的返回值为 1? ?932? ?053? ?504 ，为什么两者不相等？要使 f1 ( 13 ) 能返回正确的结果，应如何修改 f 1 源程序？
( 5 )? ?第 19 行 im ul eax,ecx 表示有符号数乘法，乘数为 r [eax] 和 r[ecx] ，当乘法器输出的高、低 32 位乘积之间满足什么条件时，溢出标志 of=1 ？要使 cpu 在发生溢出时转异常处理，编译器应在 imul 指令后加一条什么指令？
46.? ?( 7 分 ) 对于题 45 ，若计算机 m 的主存地址为 32 位，采用分页存储管理方式，页大小为 4kb ，则第 1 行 push 指令和第 30 行 ret 指令是否在同一页中 ( 说明理由 ) ？若指令 cache 有 64 行，采用 4 路组相联映射方式，主存块大小为 64b ，则 32 位主存地址中，哪几位表示块内地址？哪儿位表示 cache 组号？哪几位表示标记 ( tag ) 信息？读取第 16 行 call 指令时，只可能在指令 cache 的哪一组中命中 ( 说明理由 ) ？
47.? ?( 9 分 ) 某网络拓扑如题 47 图所示，其中 r 为路由器，主机 h1~h4 的 ip 地址配置以及 r 的各接口 ip 地址配置如图中所示。现有若干台以太网交换机 ( 无 vlan 功能 ) 和路由器两类网络互连设备可供选择。
请回答下列问题：
( 1 )? ?设备 1 、设备 2 和设备 3 分别应选择什么类型网络设备？
( 2 )? ?设备 1 、设备 2 和设备 3 中，哪几个设备的接口需要配置 ip 地址？并为对应的接口配置正确的 ip 地址。
( 3 )? ?为确保主机 h1~h4 能够访问 internet ， r 需要提供什么服务？
( 4 )? ?若主机 h3 发送一个目的地址为 192.168.1.127 的 ip 数据报，网络中哪几个主机会接收该数据报？
2019 年全国硕士研究生招生考试
计算机科学与技术学科联考
计算机学科专业基础综合试题参考答案
一、单项选择题
1.b? ? ?2.b? ? ?3.c? ? ?4.a? ? ?5.c
6.a? ? ?7.d? ? ?8.c? ? ?9.b? ? ?10.d
11.b? ? ?12.c? ? ?13.a? ? ?14.d? ? ?15.d
16.d? ? ?17.b? ? ?18.c? ? ?19.b? ? ?20.c
21.a? ? ?22.d? ? ?23.b? ? ?24.c? ? ?25.c
26.b? ? ?27.c? ? ?28.b? ? ?29.c? ? ?30.b
31.a? ? ?32.c? ? ?33.c? ? ?34.a? ? ?35.b
36.b? ? ?37.b? ? ?38.c? ? ?39.d? ? ?40.b
二、综合应用题
41. 【答案要点】
( 1 ) 算法的基本设计思想：
算法分 3 步完成。第 1 步，采用两个指针交替前行，找到单链表的中间结点；第 2 步，将单链表的后半段结点原地逆置；第 3 步，从单链表前后两段中依次各取一个结点，按要求重排。
( 2 ) 算法实现：
?
?
?
( 3 ) 算法的时间复杂度：
参考答案的时间复杂度为 o ( n ) 。
4 2 .? ?【答案要点】
( 1 ) 采用链式存储结构 ( 两段式单向循环链表 ) ，队头指针为 front ，队尾指针为 rear 。
( 2 ) 初始时，创建只有一个空闲结点的两段式单向循环链表，头指针 front 与尾指针 rear 均指向空闲结点。如下图所示。
?
队空的判定条件： front==rear 。
队满的判定条件： front==rear->next 。
( 3 ) 插 入 第一个元素后的队列状态：
?
( 4 ) 操作的基本过程：
?
4 3 .? ?【答案要点】
/ / 信号量
semaphore bowl ； // 用于协调哲学家对碗的使用
semaphore chopsticks[n] ； // 用于协调哲学家对筷子的使用
for ( int i=0 ； i<n ； i++ )
chopstick s[ i].value=1 ； // 设置两个哲学家之间筷子的数量
bowl.value=min ( n-1 ， m ) ； //bowl.value ≤ n-1 ，确保不死锁
cobegin?
while ( true ) {? ?/ / 哲学家 i 的程序
思考；
p ( bowl ) ； / / 取碗
p ( chopsti c ks[i] ) ； / / 取左边筷子
p ( chopsticks[ ( i+l ) mod? ?n] ) ； // 取右边筷子
就餐；
v ( chopstic k s[i] ) ；
v ( chopsticks[ ( i+1 ) mod? ?n] ) ；
v ( bowl ) ；
?}
coend
44. 【答案要点】
( 1 ) 磁盘容量 = ( 300×10×200×512/1024 ) kb=3×10 5? ?k
b
( 2 ) 依次访问的簇是 100 260 、 101 660 、 110 560 、 60 005 。
( 3 ) 第 100 530 簇在磁盘上的物理地址由其所在的柱面号、磁头号、扇区号构成
其所在的柱面号为 ? 100530/ ( 10×200/2 ) ? =100 。
100530% ( 10×200/2 ) =530 ，磁头号为 ? 530/ ( 200/2 ) ? =5 。
扇区号为 ( 530×2 ) %200=60 。
将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。
45. 【答案要点】
( 1 ) 计算 f ( l0 ) 需要调用函数 f1 共 10 次执行第 16 行 call? 指令会递归调用 f1 。
( 2 ) 第 12 行 jle 指令是条件转移指令。第 16 行 call 指令、第 20 行 jmp 指令、第 30 行 ret 指令一定会使程序跳转执行。
( 3 ) 第 16 行 call 指令的下一条指令的地址为 0040 1025h+5=0040 102ah ，故第 17 行指令的虚拟地址是 0040 102ah 。 call 指令采用相对寻址方式，即目标地址 = ( pc ) + 偏移量， call 指令的目标地址为 0040 1000h ，所以偏移量 = 目标地址 – ( pc ) =00401000h-0040 102ah=ffff ffd6h 。 根据第 16 行 call 指令的偏移量字段为 d6 ff ff ff ，可确定 m 采用小端方式。
( 4 ) 因为 f ( 13 ) =6? ?227? ?020? ?800 ，大于 32 位 int 型数据可表示的最大值，因而 f 1 ( 13 ) 的返回值是一个发生了溢出的结果。
为使 f 1 ( 13 ) 能返可正确结果，可将函数 f 1 的返回值类型改为 double ( 或 long long 或 long double 或 float ) 。
( 5 ) 若乘积的高 33 位为非全 0 或非全 l ，则 of=1
编译器应该在 imul 指令后加一条 “ 溢出自陷指令 ” ，使得 cpu 自动查询溢出标志 of ，当 of=1 时调出 “ 溢出异常处理程序 ” 。