文档内容
2014 年计算机学科专业基础综合试题参考答案
一、单项选择题
BBCABA CCADD DCCCC CDBBD ABAAD AACBD D
1. C 2. 3. 4. 5. 6. 7. 8.
9. D 10. 11. 12. 13. 14. 15. 16.
17. A 18. 19. 20. 21. 22. 23. 24.
25. D 26. 27. 28. 29. 30. 31. 32.
33. C 34. 35. 36. 37. 38. 39. 40.
1. 解析：
内层循环条件j<=n 与外层循环的变量无关，每次循环j 自增 1, 每次内层循环都执行n 次。
外层循环条件为 k<=n, 增量定义为 k*=2, 可知循环次数为 2k<=n, 即 k<=log2n。所以内层循环
的时间复杂度是 O(n), 外层循环的时间复杂度是 O(log2n)。对千嵌套循环，根据乘法规则可知，
该段程序的时间复杂度 T(n)= T1(n)T2(n) = O(n)O(log2n) = O(nlog2n), 选C。
2. 解析：
将中缀表达式转换为后缀表达式的算法思想如下：
从左向右开始扫描中缀表达式；
遇到数字时，加入后缀表达式；
遇到运算符时：
a. 若为＇（＇，入栈；
BDD
b. 若为＇）＇，则依次把栈中的运算符加入后缀表达式中，直到出现＇（＇，从栈中删除＇（＇；
C. 若为除括号外的其他运算符，当其优先级高于除＇（＇以外的栈顶运算符时，直接入栈；
否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比
它优先级低的或者遇到了一个左括号为止。
当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。
待处理序列 栈 后缀表达式 当前扫描元素 动作
alb+(c*d-e*f)/g a a加入后缀表达式
lb+(c*d-e*t)/g a / ／入栈
b+(c*d-e*f)/g / a b b加入后缀表达式
+(c*d-e*f)/g I ab + ＋优先级低千栈顶的/, 弹出／
+(c*d-e*f)/g ab/ + ＋入栈
(c*d-e*f)/g + ab/ ( （入栈
c*d-e*f)/g +( ab/ C c加入后缀表达式
*d-e*f)/g +( able * 栈顶为（，＊入栈
d-e*t)/g +(* able d d加入后缀表达式
-e*f)/g +(* ab/cd －优先级低于栈顶的＊，弹出＊
-e*f)/g +( ab/cd* 栈顶为（，－入栈（续表）
待处理序列 栈 后缀表达式 当前扫描元素 动作
e*t)/g +(- ab/cd* e e加入后缀表达式
*f)/g ＋（－ ab/cd*e ＊ ＊优先级高于栈顶的－， ＊入栈
f)/g +(-* ab/cd*e f f加入后缀表达式
)/g +(-* ab/cd*ef ） 把栈中（之前的符号加入表达式
/1! ＋ ab/cd*ef"- I I优先级高于栈顶的+, I入栈
＋／ ab/cd*ef*- g g加入后缀表达式
j1;
十／ ab/cd*ef*-g 扫描完毕，运算符依次退栈加入表达式
ab/cd*ef*-g/+ 完成
由此可知，当扫描到 的时候，栈中的元素依次是＋（－＊，选B。
f
在此，再给出中缀表达式转换为前缀或后缀表达式的手工做法，以上面给出的中缀表达式
为例：
第一步：按照运算符的优先级对所有的运算单位加括号。
式子变成 。
((alb)+(((c*d)-(e*f))/g))
第二步：转换为前缀或后缀表达式。
前缀：把运算符号移动到对应的括号前面，则变成
+(/(ab)/(-(*(cd)*(ef))g))
。
把括号去掉： 前缀式子出现。
+/ab/-*cd*efg
后缀：把运算符号移动到对应的括号后面，则变成
((ab)/(((cd)*(ef)*)-g)/)+
。
把括号去掉： 后缀式子出现。
ab/cd*ef*-g/+
当题目要求直接求前缀或后缀表达式时，这种方法会比上一种快捷得多。
3. 解析：
指向队头元素，那么可知出队的操作是先从 读数，然后 再加 。 指向
endl A[endl] endl 1 end.2
队尾元素的后一个位置，那么可知入队操作是先存数到 然后 再加 。若把 储存
A[end.2], end.2 1 A[O]
第一个元素，当队列初始时，入队操作是先把数据放到 然后 自增，即可知 初值为
A[O], end.2 end.2
o, o,
0; 指向的是队头元素，队头元素的在数组 中的下标为 所以得知 初值也为 可知
endl A endl
队空条件为 。然后考虑队列满时，因为队列最多能容纳 个元素，假设队列存储在
endl=end.2 M-1
下标为 到下标为 的 个区域队头为 队尾为 此时队列满，考虑在这
0 M-2 M-1 A[O]; A[M-2],
种情况下 和 的状态， 指向队头元素，可知 指向队尾元素的后一个位
endl end.2 endl endl=O, end.2
置，可知 所以可知队满的条件为 选 。
end.2=M-2+1 =M-1, endl=(end.2+ 1) modM, A
注意：考虑这类具体问题时，用一些特殊情况判断往往比直接思考问题能更快地得到答案，
并可以画出简单的草图以方便解题。
4. 解析：
线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先
写出二叉树的中序遍历序列 中序遍历中在 左边和右边的字符，就是它在中序线索化
debxac, x
的左、右线索，即b、a, 选D。
5. 解析：
将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。 在变化过程中，原森林某结点
的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。 那么森林中的叶结点由千没有
孩子结点，那么转化为二叉树时，该结点就没有左结点，所以 中叶结点的个数就等于 中左
F T
孩子指针为空的结点个数，选 。此题还可以通过一些特例来排除 、 、 选项。
C A B D6. 解析：
前缀编码的定义是在一个字符集中，任何一个字符的编码 都不是另一个字符 编码的前缀。
选项D中编码 110 是编码 1100的前缀，违反了前缀编码的规则，所以D不是前缀编码。
7. 解析：
按照拓扑排序的算法，每次都选择入度为0的结点从图中删去，此图中一开始只有结点3
的入度为0; 删掉结点3后，只有结点1的入度为0; 删掉结点1后，只有结点4的入度为O;
o,
删掉结点4后， 结点2和结点6的入度 都为 此时选择删去不同的结点， 会得出不同的拓扑
序列 ， 分别处理完毕后可知可能的拓扑序列为3,1, 4, 2, 6,5 和3,1,4,6,2,5, 选D。
8. 解析：
产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平
均查找长度 会因为堆积现象而增大，选D。
9. 解析：
关键字数量不变，要求结点数量 最多，那么即每个结点中含关键字的数最最少。根据4 阶
B树的定义，根 结点最少含l个关键字，非根结点中最少含「4/27-1=1个关键字 ，所以每个结
点中，关键字数量最少都为1个，即每个结点都 有2个分支，类似于排序 二叉树，而15个结点
正好可以构造一个4层的4阶B树，使得叶结点全在第四层 ，符合B树定义，因此选D。
10. 解析：
首先，第二个元素为1, 是整个序列中的最小元素，所以可知该希尔排序为从小到大排 序 。
然后考虑增量问题， 若增量为2, 第1+2个元素4明显比第1个元素9要大，A排除；若增量
为3, 第八i+ 3、i+ 6个元素都为有序序列Ci= 1, 2, 3), 符合希尔排序的定义；若增量为4,
第1个元素9比第1+4个元素7要大，C排除；若增量为5, 第1个元素9比第1 + 5个元素8
要大，D排除，选B。
11. 解析：
快排的阶段性排序 结果的特点是，第i趟完成时， 会有l个以上的数出现在它最终将要出
现的位置，即它左边的数 都比它小，它右边的数 都比它大。题目问第二趟排序的结果，即要找
不存在两个这样的数的选项。A选项中2、3、6、7、9均符合，所以A排除；B选项中，2、9
均符合，所以B排除；D选项中5、9均符合，所以D选项排除；最后看C选项，只有9一个
数符合，所以C不可能 是快速排序第二趟的结果。
12. 解析：
不妨设原来指令条数为X, 那么原CPI就为20/x, 经过编译优化后， 指令条数减少到原来
的70%, 即指令条数为0.7x, 而CPI增加到原来的1.2倍，即24/x, 那么 现在P 在M上的执行
时间就为指令条数xCPI= 0.7x x 24/x = 24x0.7 = 16.8s, 选D。
13. 解析：
8位定点补码表示的数据范围为-12s�121, 若运算结果超出这个范围则会溢出，A选项x+
y = 103-25 = 78, 符合范围，A排除；B选项-x+y= -103-25 = -128, 符合范围，B排除；D选
项寸-y= -103 + 25 = -78, 符合范围，D排除；C选项x-y= 103 + 25 = 128, 超过了127, 选C。
该题也可按照二进制写出两个数进行运算，观察运算的进位信息得到 结果，不过这种方法
更为麻烦和耗时，在实际考试中并不推荐。
14. 解析：
(fl)和位）对应的二进制分别是(110011001001…)2和(101100001100…2) , 根据IEEE754浮点
数标准，可知(fl)的数符为1, 阶码为10011001,尾数为1.001,而(f2的) 数符为1, 阶码为01100001,尾数为1.1, 则可知两数均为负数， 符号相同， B、 D排除。 (fl)的绝对值为 l.001x226, (f2)的绝
对值为 l.lx2-30, 则(fl)的绝对值比(f2)的绝对值大， 而符号为负， 真值大小相反， 即(fl)的真值
比(f2)的真值小， 即xlchild == NULL && root->rchild NULL)
II若为叶子结点，累积wpl
wpl +"". deep*root->wei9ht;
if"(root->].child != NULL) II若左子树不空，对左子树递归遍历
wpl_PreOrder(root->lchilct,·cteep+l);
if(root rchild != NULL) ／／若右子树不空，对右子树递归遍历
今
wpl_PreOrder(root
今
rchild, deep+l);return, wpl;
｝
＠基于层次遍历的算法：
#define MaxSize 100 //设置队列的最大容量
;int wpl_J;,�:velOrder(BiTree roo七）｛
BiTree q[MaxSize]; //声明队列，endl为头指针，end2为尾指针
ijlt erid,l, end2; , • //队列最多容纳MaxSize-1个元素
·
eridl = end2 ;,,, 0; II头指针指向队头元素，尾指针指向队尾的后一个元素
ir;i:t wp�= 0�deep = 0; . • I I初始化wpl和深度
BiTree• lastNode; ·.
. . . .· ·.. ·,
/ / lastNode用来记录当前层的最后一个结点
B.iTree newlastNode; . .. //newlastNode用来记录下一层的最后一个结点
la.stNocie = root; . .. · / /lastNode初始化为根结点
newlastNode = NULL; . //newlastNode初始化为空
q[end2++] = root; II根结点入队
while(endl != end2) { II层次遍历，若队列不空则循环
眨Tree·t = q[endl++];·..• · II拿出队列中的头一个元素
if(t一>lchild == NULL & 七一>lchild == NULL){
wpl +=; deep*七一>weight;
} . I I若为叶子结点，统计wpl
if;:lchil.d. != NULL){.. I I若非叶子结点把左结点入队
q[end2++] = t->lchild;
newlcistNo.de = t->lchild;
,
II并设下一层的最后一个结点为该结点的左结点
if (t->rchild ! = NULL) { I I处理叶结点
q[end2++] = t.:.>rchild;
newlastNode =,t->rchild;
if(t == lastNode) { ／／若该结点为本层最后一个结点，更新lastNode
las七Node··= newlas七Node;
deep+= l; //层数加1
} //while
return:,wpl; II返回wpl
【评分说明】
＠若考生给出能够满足题目要求的其他算法且正确，可同样给分。
＠考生答案无论使用C或者C++语言，只要答案正确同样给分。
＠若对算法的基本设计思想和主要数据结构描述不十分准确， 但在算法实现中能够清晰
反映出算法思想且正确，参照＠的标准给分。
＠若考生给出的二叉树结点的数据类型定义和算法实现中，使用的是除整型之外的其他
数值，可视同使用整型类型。
＠若考生给出的答案中算法主要设计思想或算法中部分正确，可酌情给分。
注意： 上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，读者应当选取自
己最擅长的书写方式。 直观看去，先序遍历代码行数少，不用运用其他工具，书写也更容易，
希望读者能掌握。
在先序遍历的算法中，static是一个静态变量，只在首次调用函数时声明wpl并赋值为o,
以后的递归调用并不会使得wpl为o, 具体用法请参考相关资料中的关键字static说明，也可以
在函数之外预先设置一个全局变量，并初始化。 不过考虑到历年真题算法答案通常都直接仅由一个函数构成， 所以参考答案使用stati。c 若对stati不c 熟悉的同学可以使用以下形式的递归：
int wpl_PreOrder(BiTree root,int deep) {
int lwpl,rwpl; II用千存储左子树和右子树的产生的wpl
lwpl=rwpl=O;
if(root->lchild==NULL&&root->lchild==NULL)
II若为叶结点，计算当前叶结点的wpl
return deep*root-'->weight;
if(root->lchild!=NULL) · II若左子树不空， 对左子树递归遍历
lwpl = wpl_PreOrder(root->lchild, deep+l);
if(root今rchild!=NULL) II若右子树不空， 对右子树递归遍历
rwpl=wpl_PreOrder(root"">rchild,deep;tl);
return lwpl+rwpl;
CIC++语言基础好的同学可以使用以下更简便的形式：
int wpl_PreOrder(BiTree root,in七 deep){
if(roo七一>lchild==NULL&&roo1:->lchild==NULL) ／／若为叶子结点， 累积�pl
re七urn deep*root->weight;
re七urn (root->lchild!=NULL ?, wpl_PreOrder(root->lchild, deep+l) :0)
+ (roo七->rchild!=NULL? wpl_PreOrder(root->rchild, deep+l) :O);
这个形式只是上面方法的简化而已，本质是一样的，而这个形式的代码更短， 在时间有限
的情况下更具优势，相比写层次遍历能节约很多时间，所以读者应当在保证代码正确的情况下，
尽量写一些较短的算法， 为解答其他题目赢得更多的时间。 但是， 对于基础不扎实的考生， 还
是建议使用把握更大的方法， 否则可能会得不偿失。 例如在上面的代码中， 考生容易忘记三元
式(x?y:z)两端的括号，若不加括号， 则答案就会是错误的。
在层次遍历的算法中， 读者要理解lasNt ode和newlasNt do e的区别，lastNode指的是当前
遍历层的最后一个结点，而en wlasNt doe指的是下一层的最后一个结点，是动态变化的， 直到遍
历到本层的最后一个结点， 才能确认下层真正的最后一个结点是哪个结点，而函数中入队操作并
没有判断队满，若考试时用到，读者最好加上队满条件， 这里队列的队满条件为edn l=(end2+1 )
mdo M。 同时， 考生也可以尝试使用记录每层的第一个结点来进行层次遍历的算法， 这里不再
给出代码， 请考生自行练习。
42. 解答：
很多考生乍看之下以为是网络的题目， 其实该题本身并没有涉及太多的网络知识点， 只是
应用了网络的模型， 实际上考查的还是数据结构的内容。
(1)图(1分）
题中给出的是一个简单的网络拓扑图， 可以抽象为无向图。
【评分说明】
” ”
只要考生的答案中给出与图含义相似的描述， 例如，“网状结构 “非线性结构 等， 同样
给分。
(2)链式存储结构的如下图所示。
弧结点的两种基本形态
表头结点
结构示总其数据类型定义如下： (3分）
七ypedef struc七｛
unsigned int ID, IP;
}LinkNode; / /Link 的结构
typedef struct{
.
unsigned int.Prefix, Mask;
}NetNode; / /Net 的结构
typedef struct Node{
int Flag; //Flag=l为Link;Flag=2为Net
union{
LinkNode Lnode;
NetNode Nnode
} LinkORNet;
unsigned int Metric;
struct Node *next;
}ArcNode; / /弧结点
typedef struct HNode{
unsigned int RouterID;
ArcNode *LN_link;
struct HNode *next;
, ,
}HNODE; I I表头结点
对应上述链式存储结构的示意图如下。(2分）
Flag=2 I A
I 92.1.1.0
255.255.255.0
Flag=2 I A
192.1.6.0
255.255.255.0
Flag=2 I A
I 92.1.5.0
255.255.255.0
＾
Fiag=t �Flag=! I ·Flag=2 I
1
10.1.1.5 10.1.1.2 192.1.7.0
10.1.1.6 10.l.l.14 255.255.255.0
6 4 I
【评分说明】
一 一
＠若考生给出的答案是将链表中的表头结点保存在 个 维数组中（即采用邻接表形
式）， 同样给分。
＠若考生给出的答案中，弧结点没有使用 union定义，而是采用两种不同的结构分别表示
Link 和 Net, 同时在表头结点中定义了两个指针， 分别指向由这两种类型的结点构成的两个链
表， 同样给分。＠考生所给答案的弧结点中，可以在单独定义的域中保存各直连网络IP地址的前缀长度，
也可以与网络地址保存在同一个域中。
＠数据类型定义中，只要采用了可行的链式存储结构 ，并保存了题目中 所给的LSI信息，
如各网络抽象为一类结点，写出含8个表头结点的链式存储结构，均可参照＠～＠的标准给分。
＠若考生给出的答案中，图示部分与其数据类型定义部分一致，图示只要能够体现链式
存储结构和网络连接关系（可以不给出结点内细节信息），即可给分。
＠若解答不完全正确，酌情给分。
(3) 计算结果如下表所示。(4分）
目的网络 路径 代价（费用）
步骤l 192.1.1.0/24 直接到达 I
步骤2 192.1.5.0/24 RI-R3-192.1.5.0/24 3
步骤3 192.1.6.0/24 RI-R2-192.l.6.0/24 4
步骤4 192.1.7.0/24 RI-R2-R4-192.1.7.0/24 8
【评分说明】
O若考生给出的各条最短路径的结果部分正确， 可酌情给分。
＠若考生给出的从Rl到达子网192.1.x.x的最短路径 及代价正确，但不完全符合代价不减
的次序， 可酌情给分。
43. 解答：
(1)因为题目要求路由表中的路由项尽可能少，所以这里可以把子网 192.1.6.0/24和
192. 1. 7 .0/24聚合为子网192.1.6.0/23。其他网络照常， 可得到路由表如下： (6分）
目的网络 下一条 接口
192.1. 1.0/24 EO
192.1.6.0/23 10.1.J.2 LO
192.1.5.0/24 10.1.1.10 LI
【评分说明】
O每正确解答一个路由项，给 2分，共6分。
＠路由项解答不完全正确，或路由项多于3条， 可酌情给分。
(2)通过查路由表可知： RI通过LO接口转发该 IP分组。(I分）因为该分组要经过3个
路由器(RI,R2, R4), 所以主机192.1.7.211收到的IP分组的TTL是64-3= 61。(I分）
(3) RI的LSI需要增加一条特殊的直连网络，网络前缀Prefix为"0.0.0.0/0", Metric为
10。(I分）
【评分说明】
考生只要回答： 增加前缀Prefix为"0.0.0.0/0", Metric为10, 同样给分。
44. 解答：
该题涉及指令系统、存储管理以及CPU三个部分内容，考生应注意各章节内容之间的联系，
才能更好地把握当前考试的趋势。
I)已知计算机M采用32位定长指令字，即一条指令占4B, 观察表中各指令的地址可知，
每条指令的地址差为4个地址单位，即4个地址单位代表4B, 一个地址单位就代表了1B, 所
以该计算机是按字节编址的。(2分）
2)在二进制中某数左移两位相当于乘以4, 由该条件可知，数组间的数据间隔为4个地址单位，而计算机按字节编址， 所以数组A中每个元素占4B。(2分）
3)由表可知，bne指令的机器代码为1446FFFAH,根据题目给出的指令格式， 后2B的内
容为OFFSET字段， 所以该指令的OFFSET字段为FFFAH, 用补码表示，值为-6(1分）。 当
系统执行到bne指令时，PC自动加4,PC的 内容就为08048118H, 而跳转的目标是08048100H,
两者相差了18H,即24个单位的地址间隔， 所以偏移址的 一位即是真实跳转地址的-24/-6= 4
位(1分）。 可知bne指令的转移目标地址计算公式为(PC)+ 4 + OFFSET x4 (1分）。
4)由于数据相关而发生阻塞的 指令为第2、 3、 4、 6条， 因 为第2、 3、 4、 6条指令都与
各自前一条指令发生数据相关。(3分）
第6条指令会发生控制冒险。(1分）
当前循环的第五条指令与下次循环的第一条指令虽然有数据相关，但由于第6条指令后有
3个时钟周期的阻塞， 因而消除了该数据相关。(1分）
【评分说明】
对于第1问，若考生回答： 因 为指令l和2、 2和3、 3和4、 5和6发生数据相关， 因 而
发生阻塞的 指令为第2、 3、 4、 6条， 同样给 3分。 答对3 个以上给 3分， 部分正确酌情给分。
45. 解答：
1) R2里装的是i的值，循环条件是区N(1000), 即当i自增到不满足这个条件时跳出循
环， 程序结束， 所以此时i的值为1000。(1分）
2) Cache共有16块， 每 块32字节，所以Cache数据区的容量为16x32B = 512B。(1分）
P共有6条指令， 占24字节， 小于主存块大小C32B),其起始地址为08048100H, 对应一
块的开始位置， 由此可知所有指令都在一个主 存块内。 读取第一条指令时会发生Cache缺失， 故
将P 所在的主存块调入Cache某一块， 以后每次读取指令时，都能在指令Cache中命中。 因此在
1000次循环中，只会发生1次指令访问缺失， 所以指令Cache的命中率为(lOOOx6-1/) (1O OOx6) =
99.98%。(2分）
【评分说明】若考生给出正确的命中率， 而未说明原因和过程， 给 1分。 若命中率计算错
误，但解题思路正确， 可酌情给分。
3) 指令4 为加法指令，即对应sum+=A[i],当数组A中元素的值过大时，则会导致这条加
法指令发生溢出异常；而指令2、5虽然都是加法指令，但它们分别为数组地址的 计算指令和存
储变量i的寄存器进行自增的指令，而i最大到达1000,所以它们 都不会产生溢出异常。(2分）
只有访存指令可能产生缺页异常， 即指令3 可能产生缺页异常。(1分）
因为数组A在磁盘的 一页上，而一开始数组并不在主存中，第一次访问数组时会导致访盘，
把A调入内存，而以后数组A的元素都在内存中，则不会导致访盘，所以该程序一共访盘一次。
(2分）
每 访问一次内存数据就会查TLB 一次，共访问数组1000次，所以此时又访问TLBlOOO次，
还要考虑到第一次访问数组A,即访问AO[ ]时，会多访问一次TLB(第一次访问A O[ ]会先查一
次TLB,然后产生缺页，处理完缺页中断后，会重新访问AO[ ],此时又查TLB),所以访问TLB
的次数一共是1001次。(2分）
【评分说明】
＠对于第1问， 若答案中除指令4外还包含其他运算类指令（即指令1 、 2 、 5), 则给l
分，其他情况， 则给 0分。
＠对于第2问， 只要回答"load指令”，即可得分。
＠对于第3问，若答案中给出的 读TLB 的次数为1002, 同样给分。若直接给出正确的TLB及磁盘的访问次数，而未说明原因，给3分。若给出的TLB及磁盘访问次数不正确，但解
题思路正确， 可酌情给分。
46. 解答：
I)系统采用顺序分配方式时， 插入记录需要移动其他的记录块， 整个文件共有200条记
录，要插入新记录作为第30条，而存储区前后均有足够的磁盘空间，且要求最少的访问存储块
数， 则要把文件前29条记录前移， 若算访盘次数移动一条记录读出和存回磁盘各是一次访盘，
29条记录共访盘58次， 存回第30条记录访盘1次， 共访盘59次。(1分）
F的文件控制区的起始块号和文件长度的内容会因此改变。(I分）
2)文件系统采用链接分配方式时， 插入记录并不用移动其他记录， 只需 找到相应的记录，
修改指针即可。 插入的记录为其第30条记录， 那么需要找到文件系统的第29块， 一共需要访
盘29次， 然后把第29 块的下块地址部分赋给新块， 把新块存回内存会访盘1次， 然后修改内
存中第29块的下块地址字段， 再存回磁盘(I分）， 一共访盘31次。(I分）
4字节共32位，可以寻址232=4G 块存储块，每块的大小为IKB, 即1024B, 其中下块地址
部分占4B, 数据部分占1020B, 那么该系统的文件最大长度是4GxI0 20B =4 080GB。(2分）
【评分说明】
0第1)小题的第2小问 ， 若答案中不包含文件的起始地址和文件大小， 则 不给分。
＠若按I024x232B = 4096GB计算最大长度， 给1分。
47. 解答：
这是典型的生产者和消费者问题， 只对典型问题加了一个条件， 只需在标准模型上新加一
个信号最， 即可完成指定要求。
设置四个变量mutexl、mutex2、empty和full, mutex1 用于一个控制一个消费者进程一个
周期(IO次）内对于缓冲区的控制， 初值为I; mutex2用于进程单次互斥的访问缓冲区， 初值
为I; empty代表缓冲区的空位数， 初值为0; full代表缓冲区的产品数， 初值为1000, 具体进
程的描述如下：
semaphore mutexl=l;
semaphore mutex2=1;
semaphore empty=n;
semaphore full=O;
producer() {
while (1) {
生产一个产品；
P(empty); II判断缓冲区是否有空位
P(mutex2); ／／互斥访问缓冲区
把产品放入缓冲区；
V(mutex2); ／／互斥访问缓冲区
V (full); ／／产品的数量加1
consumer() {
while (1) {
P (mutexl) ／／连续取10次
for(int i = 0; i < 10; ++i){
P(full); //判断缓冲区是否有产品
P(mutex2); //互斥访问缓冲区从缓冲区取出一件产品；
V(mu七ex2); II互斥访问缓冲区
V(em ty); II腾出一个空位
p
消费这件产品；
【评分说明】
O信号量的初值和含义都正确给2分。
＠生产者之间的互斥操作正确给l分；生产者与消费者之间的同步操作正确给2分；消
费者之间互斥操作正确给l分。
＠控制消费者连续取产品数量正确给2分。
＠仅给出经典生产者－消费者问题的信号量定义和伪代码描述最多给3分。
＠若考生将题意理解成缓冲区至少有10件产品，消费者才能开始取，其他均正确，得
6分。
＠部分完全正确，酌情给分。
