科目组合
数据结构 、计算机组成原理 、操作系统 、计算机网络
答题情况分析报告
。
假设4个作业到达系统的时刻和运行时间如下表所示。
系统在t=2时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是
A. J2、J3
B. J1、J4
C. J2、J4
D. J1、J3
某计算机按字节编址，其动态分区内存管理采用最佳适应算法，每次分配和回收内存后都对空闲分区链重新排序。当前空闲分区信息如下表所示。
回收起始地址为60K、大小为140KB的分区后，系统中空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是（ ）。
A. 3、20K、380KB
B. 3、500K、80KB
C. 4、20K、180KB
D. 4、500K、80KB
（单位：比特每秒 (bits per second, bps)）
，即
，将 SNR = 30 dB 代入，得
，再将
代入香农公式，解得 
。
，其中 M 为调制技术中可利用的符号数量。即
（单位：比特每秒 (bits per second, bps)）
，化简得 
， 取
。在下图所示的网络中，若主机H发送一个封装访问Internet的IP分组的IEEE 802.11数据帧F，则帧F的地址1、地址2和地址3分别是（ ）。
A. 00-12-34-56-78-9a, 00-12-34-56-78-9b, 00-12-34-56-78-9c
B. 00-12-34-56-78-9b, 00-12-34-56-78-9a, 00-12-34-56-78-9c
C. 00-12-34-56-78-9b, 00-12-34-56-78-9c, 00-12-34-56-78-9a
D. 00-12-34-56-78-9a, 00-12-34-56-78-9c, 00-12-34-56-78-9b
（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：
输出的中缀表达式分别为 (a+b)∗(c∗(−d)) 和 (a∗b)+(−(c−d)) 。
二叉树结点的定义如下：
typedef struct node{
char data[10]; // 存储操作数或操作符
struct node *left, *right;
}BTree;
要求：
⑴ 给出算法的基本设计思想。（5分）
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（10分）
1）通过二叉树的中序遍历，可以得出他的中缀表达式。如果一个结点有孩子且不是根节点，那就先输出“（”再访问他的左孩子。当一个结点没有孩子，输出该节点。接下来再遍历他的右子树。当右子树遍历到最后一个结点，说明这一段表达式结束，输出“）”。
2）
void expressionMid(BTree T, int depth){
if(T == NULL) return; //空树返回
if(depth > 0 && T->left != NULL || T->right != NULL) printf("(");
expressionMid(T->left, depth+1);
printf(T->data);
expressionMid(T->right, depth+1);
if(depth > 0 && T->left != NULL || T->right != NULL) printf(")");
}
评分及理由
（1）得分及理由（满分5分）
得分：3分
理由：学生基本理解了中序遍历的思想，提到了通过中序遍历输出表达式，并考虑了括号的添加。但是描述不够准确和完整：
- 没有明确说明根节点不需要加括号
- 对括号添加条件的描述比较模糊（"不是根节点"、"当右子树遍历到最后一个结点"等表述不准确）
- 没有清晰说明深度参数的作用
基本思路正确但表达不够严谨，扣2分。
（2）得分及理由（满分10分）
得分：6分
理由：代码实现了基本的中序遍历框架，但存在以下逻辑错误：
- 括号添加条件有误：`depth > 0 && T->left != NULL || T->right != NULL` 存在运算符优先级问题，应该是 `(depth > 0 && (T->left != NULL || T->right != NULL))`
- 缺少对叶子节点的特殊处理，标准答案中对叶子节点直接输出，不添加括号
- 函数参数应该是 `BTree*` 而不是 `BTree`
- `printf(T->data)` 语法错误，应该是 `printf("%s", T->data)`
- 缺少主调用函数
代码框架基本正确，但存在多处逻辑错误和语法问题，扣4分。
题目总分：3+6=9分
（8分）使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。
⑴ 对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。（4分）
⑵ 图G的MST是唯一的吗？（2分）
⑶ 对任意的带权连通图，满足什么条件时，其MST是唯一的？（2分）
1) A->D, D->E, E->C, C->B
2)是的
3)当一个连通图中环路没有相同权值的时候MST唯一。
评分及理由
（1）得分及理由（满分4分）
学生给出的边序列为：A→D, D→E, E→C, C→B。这与标准答案(A,D)、(D,E)、(C,E)、(B,C)在边的选择上完全一致，且顺序也正确。虽然学生使用了箭头符号表示，但表达的含义与标准答案相同。因此本题得满分4分。
（2）得分及理由（满分2分）
学生回答"是的"，表示认为图G的MST是唯一的，这与标准答案一致。因此本题得满分2分。
（3）得分及理由（满分2分）
学生回答"当一个连通图中环路没有相同权值的时候MST唯一"，这与标准答案"当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的"在含义上是一致的。虽然表述略有不同，但核心思想正确。因此本题得满分2分。
题目总分：4+2+2=8分
1）n=0时，f1会出现死循环，因为i是不断递增的，n-1所表示的是最大的无符号整数，无论怎么加都不可能超过他，所以会死循环。如果变成有符号整数，不会死循环，因为出现负数，直接就结束了。
2）float是浮点数，最大的表示范围是2^23，刚好不越界，所以相同。机器数分别是：00FF FFFFH和4B7F FFFFH
3) float在32位的时候最多有23位尾数，f2(24)已经溢出。
4）总共有32位，f1(31)则是有32个1，符号位是1，因此是负数。最大的n是30.
5）f2是float，尾数全为0，符号位是0，表示正无穷。最大的n是23。
评分及理由
（1）得分及理由（满分4分）
学生正确解释了n=0时死循环的原因：无符号整数n-1为最大值，条件永真。同时正确指出改为int后不会死循环，因为n-1=-1，条件不成立。但未明确说明无符号比较和带符号比较的区别，解释略显简略。扣1分。
得分：3分
（2）得分及理由（满分3分）
学生正确指出f1(23)和f2(23)返回值相等，并给出了正确的机器数。但解释部分“float最大的表示范围是2^23”表述不准确（应为23位尾数），不过不影响核心结论。扣0.5分。
得分：2.5分
（3）得分及理由（满分1分）
学生提到“float在32位时最多有23位尾数”正确，但将现象归因于“溢出”不准确（实际是舍入导致数值增大）。扣0.5分。
得分：0.5分
（4）得分及理由（满分2分）
学生正确解释f1(31)返回-1的原因（32位1解释为负数），并正确给出最大n=30。答案完整准确。
得分：2分
（5）得分及理由（满分3分）
学生正确解释7F80 0000H为正无穷，但未说明阶码全1、尾数全0的格式要求。第二问最大n=23错误（应为126），第三问最大n=23正确。第二问扣1分，第三问给满分。
得分：2分
题目总分：3+2.5+0.5+2+2=10分
。f1(23)为int类型，int占32位，没有溢出。f2(23)为float类型，float采用IEEE754单精度标准，float有1个符号位，8个指数位，23个尾数位，考虑小数点前面省略的1，float有24个有效数值位。阶码为 23+127=150=10010110B。所以两者返回值相等。
=4B7FFFFFH。
。f1(23)为int类型，int占32位，没有溢出。f2(23)为float类型，float采用IEEE754单精度标准，float有1个符号位，8个指数位，23个尾数位，考虑小数点前面省略的1，float有24个有效数值位。不满足25个有效数值位的要求，这里需要进行舍入，按0舍1入，f2(24)= 2^25 =33554432.0，比f1(24)= 2^25−1 =33554431大，即f1(24)和f2(24)返回值不相等。
且int型最大可表示数是符号位为0后面31个数值位全为1，即n+1=31，解得n=30，所以使f1(n)的返回值与f(n)相等的最大n值是30。
，阶码位全1，尾数位全0，表示无穷大，符号位为0，表示正无穷大，即 +∞ 。
。表示为浮点数
，括号内为需要舍入的部分，按0舍1入进行舍入后需要右规，阶码加1，得到 
，该浮点数表示 +∞ ，溢出。
。表示为浮点数 
，括号内为需要舍入的部分，按0舍1入进行舍入后需要右规，阶码加1，得到 
，阶码11111110B达到IEEE754单精度格式表示的最大阶码。
。f2(23)为float类型，float采用IEEE754单精度标准，float有1个符号位，8个指数位，23个尾数位，考虑小数点前面省略的1，float有24个有效数值位。所以不需舍入，结果精确。1）CICS，因为指令长度不同长度
2）
3）0
4）不能，因为f2是float浮点数，不能通过简单的位移进行计算。
评分及理由
（1）得分及理由（满分2分）
得2分。学生正确判断为CISC，理由"指令长度不同"符合标准答案中"指令长短不一"的描述，虽然表述不够完整但核心观点正确。
（2）得分及理由（满分2分）
得0分。学生未给出任何计算过程，也未得出具体字节数，完全缺失答案内容。
（3）得分及理由（满分3分）
得0分。学生仅给出结果"0"，但正确答案应为1。没有计算过程，且结果错误，属于逻辑错误。
（4）得分及理由（满分3分）
得2分。学生正确判断"不能"，理由"f2是float浮点数，不能通过简单的位移进行计算"基本正确，但解释不够详细，未提及阶码部分和无最高有效数位等关键点。
题目总分：2+0+0+2=4分
1）
2)
3）
评分及理由
（1）得分及理由（满分1分）
得分：0分
理由：学生未给出任何回答，完全空白，因此不得分。
（2）得分及理由（满分2分）
得分：0分
理由：学生未给出任何回答，完全空白，因此不得分。
（3）得分及理由（满分4分）
得分：0分
理由：学生未给出任何回答，完全空白，因此不得分。
题目总分：0+0+0=0分
，页目录号是00 0000 0001B=1，页表索引是000000 0001B=1，所以，取该指令时访问了页目录的第1（编号从0开始）个表项，在对应的页表中访问了第1（编号从0开始）个表项。
//复数的结构类型定义
typedef struct
{
float a;
float b;
}cnum;
cnum x,y,z; //全局变量
//计算两个复数之和
cnum add( cnum p,cnum q)
{
cnum s;
s.a=p.a+q.a;
s.b=p.b+q.b;
return s;
}
semaphore m_x=1, m_y=1, m_z=1;
semaphore mutex = 1;
thread1
{
wait(mutex);
wait(x);
wait(y);
cnum w;
w=add(x,y);
signal(x);
signal(y);
signal(mutex);
}
thread2
{
wait(mutex);
wait(z);
wait(y);
cnum w;
w=add(y,z);
signal(z);
signal(y);
signal(mutex);
}
thread3
{
wait(mutex);
wait(z);
wait(y);
cnum w;
w.a=1;
w.b=2;
z=add(z,w);
y=add(y,w);
signal(z);
signal(y);
signal(mutex);
}
评分及理由
（1）信号量定义得分及理由（满分3分）
学生定义了m_x=1, m_y=1, m_z=1和mutex=1四个信号量。但存在以下问题：
- m_x信号量是多余的，因为只有thread1访问x，且x是只读的
- 使用mutex作为全局互斥锁会严重降低并发性，不符合题目"最大程度地并发执行"的要求
- 没有按照标准答案的思路为y变量设置两个独立的互斥信号量
扣2分，得1分
（2）thread1代码得分及理由（满分1分）
thread1中：
- 使用了不必要的全局mutex和x信号量
- 对y的保护方式不正确
- 没有实现thread1与thread3对y的细粒度互斥访问
扣1分，得0分
（3）thread2代码得分及理由（满分2分）
thread2中：
- 使用了不必要的全局mutex
- 没有正确处理对y和z的访问顺序
- 没有实现thread2与thread3对y和z的细粒度互斥访问
扣2分，得0分
（4）thread3代码得分及理由（满分2分）
thread3中：
- 使用了不必要的全局mutex
- 没有正确处理对y和z的访问顺序，特别是对y的访问需要同时获得两个互斥锁
- 没有实现与thread1和thread2的细粒度互斥
扣2分，得0分
题目总分：1+0+0+0=1分
主要问题：学生使用了粗粒度的全局互斥锁，严重降低了并发性，没有实现题目要求的"最大程度地并发执行"。同时信号量的使用存在逻辑错误，对共享变量的保护方式不正确。
（9分）甲乙双方均采用后退N帧协议 (GBN) 进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000 B。 Sx,y 和 Rx,y 分别表示甲方和乙方发送的数据帧，其中：x是发送序号；y是确认序号（表示希望接收对方的下一帧序号）；数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100 Mbps，RTT = 0.96 ms。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中 t0 为初始时刻，此时甲方的发送和确认序号均为0， t1 时刻甲方有足够多的数据待发送。
请回答下列问题。
(1) 对于图(a)， t0 时刻到 t1 时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少？正确接收的是哪几个帧（请用 Sx,y 形式给出）？（3分）
(2) 对于图(a)，从 t1 时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个（请用 Sx,y 形式给出）？（3分）
(3) 对于图(b)，从 t1 时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧？重发的第一个帧是哪个（请用 Sx,y 形式给出）？（2分）
(4) 甲方可以达到的最大信道利用率是多少？（1分）
1）4个。(S0,0), (S1,0), (S2,0), (S3,0)
2）最多还可以发送2个。第一个帧是(S4,3)；最后一个是(S4,3)
3）2个
评分及理由
（1）得分及理由（满分3分）
学生回答4个帧（S0,0、S1,0、S2,0、S3,0），但标准答案为3个帧（S0,0、S1,0、S2,0）。在GBN协议中，甲方只能断定乙方正确接收了已被确认的帧。图中甲方收到R2,3，表示乙方期望接收序号3，说明乙方已正确接收序号0、1、2的帧，但未确认序号3。学生错误地将S3,0计入，属于逻辑错误。扣2分，得1分。
（2）得分及理由（满分3分）
学生回答最多发送2个帧，第一个和最后一个均为S4,3。标准答案为5个帧（第一个S5,2，最后一个S1,2）。GBN发送窗口大小由序号空间决定（3比特，窗口大小为7），甲方当前已发送到序号4，收到R2,3后确认序号2及之前的帧，发送窗口向前滑动，可用序号为3~7和0~1（模8），共5个帧。学生答案中帧数量、起始和结束帧均错误，且未理解窗口滑动机制。扣3分，得0分。
（3）得分及理由（满分2分）
学生回答重发2个帧，但未指定第一个重发帧。标准答案为重发3个帧（第一个S2,3）。图(b)中甲方在t1时刻收到R2,3，但之前已超时重发S2,0，表明序号2及之后的帧（S2,0、S3,0、S4,0）需重发。学生答案帧数量错误，且未给出第一个重发帧。扣2分，得0分。
（4）得分及理由（满分1分）
学生未回答此问题。扣1分，得0分。
题目总分：1+0+0+0=1分
，经过一个RTT = 0.96 ms，乙采用等长的数据帧进行捎带确认，接收乙发送一个数据帧的时延为 t2=t1=0.08 ms 。一个周期 T=t1+RTT+t2=1.12 ms 。
。
The road of your choice, you have to go on !
粤ICP备16082171号-1
