2018年北京联合大学软件工程803软件基础之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0’
2． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
3． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
4． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
5． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
第 2 页，共 50 页
，
left 指向其前驱；，
right 指向其右孩子，，
，
right 指向其后继。
【答案】
二、单项选择题
6． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps ，电缆中的信号传播速度是200000km/s.若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）.
A. 增加160m B. 增加80m C. 减少160m D. 减少80m 【答案】D
【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度＝碰撞窗口大小×报文发送速率，本题最小数据帧长度
89
减少800b , 那么碰撞的窗口也要减少，因此距离也要减少，从而(800×2×l0)/(l×l0) ＝160m ，由于
时间延时存在两倍的关系，因此减少的距离为80m 。
7． 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3, 这些资源总数分别为18、6、22。
时刻的资源分配情况如下表所示, 此时存在的一个安全序列是（ ）。
表 资源分配情况表
A.P0, P2, P4, P1, P3 B.P1, P0, P3, P4, P2 C.P2, P1, P0, P3, P4 D.P3, P4, P2, P1, P0P0 【答案】D 。
【解析】典型的死锁避免算法、银行家算法的应用。分析一下下表, 可以看到, P3, P4, P2, P1, P0运行是可以的。
第 3 页，共 50 页
表
本题也可以排除法,
时刻可用资源是R1, R2, R3分别为2, 3, 3, 此时刻, P0需要R1, R2, R3
分别为2, 3, 7, 故排除A , P1需要R1, R2, R3分别为1, 3, 3, P2还需要资源R1, R2, R3分别为0, 0, 6, 故C 排除, P3需要R1, R2, R3分别为2, 2, 1。所以正确答案在B , D 之间。
看B 选项, P1之后的可用资源R1, R2, R3分别变为6, 3, 6, 而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。
8． 某字长为8位的计算机中, 已知整型变量x 、y 的机器数分别为
,
A.11000000 B.00100100 C.10101010 D. 溢出 【答案】A
【解析】将x 左移一位, y 右移一位, 两个数的补码相加的机器数为11000000, 故答案选择A 。
9． 两台主机之间的数据链路层采用后退N 帧协议(GBN)传输数据, 数据传输速率为16kbps , 单向传播时延为270ms , 数据帧长度范围是
字节, 接收方总是以与数据帧等长的帧进行确认。
为使信道利用率达到最高, 帧序号的比特数至少为（ ）。
A.5 B.4 C.3 D.237
【答案】B 。
【解析】GBN 的工作原理如下图所示, 本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧, 要尽可能多发送帧, 应以短的数据帧计算, 注意帧的单位是字节, 因此首先计算出发送一帧的时
间为
;
,
这段时间总共可以发送
, 故发送一帧到收到确认为止的总时间
(帧) , 为了保证发送帧序号和确认帧
。若整型变量
, 则z 的机器数为（ ）
序号在此期间不重复, 因此桢序号的比特数至少为4, 答案为B
第 4 页，共 50 页