2016年兰州大学数学与统计学院综合考试之数据结构考研复试题库
● 摘要
一、选择题
1． 执行完下列语句段后，f 值为（ ）。
A.2
B.4
C.8
D. 无限递归
答:B
【解析】该程序使用了递归调用，由题知，所以结果为4。
2． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）
A.2
B.3
C.4
D.5
答:C
【解析】设校验位的位数为k ，数据位的位数为n ，根据海明码编码k 和n
应满足下述关系。
当k=4时， 符合要求，校验位至少是4位，故答案为C 。
3． 若X 是后序线索二叉树中的叶结点， 且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）
A.X 的父结点
B. 以Y 为根的子树的最左下结点
C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点
答:A
【解析】根据后续线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知X 结点的后继是其父结点，即其右线索指向的是父结点。
4． 下列选项中，降低进程优先级的合理时机是（ ）。
A. 进程的时间片用完
B. 进程刚完成1/0, 进入就绪队列
C. 进程长期处于就绪队列
D. 进程从就绪状态转为运行态
答:A
【解析】进程时间片用完可以降低其优先级，完成的进程应该提升其优先级，处于就绪队列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是
，时间片用完后降低其优独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机）
先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有
，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不优先权）
会随意改变。而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间。
5． 若用户1与用户2之间发送和接收电子邮件的过程如图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。
图 电子邮件发送接收示意图
A.SMTP 、SMTP 、SMTP
B.POP3、SMTP 、POP3
C.POP3、SMTP 、SMTP
D.SMTP 、SMTP 、POP3
答:D 。
【解析】题中电子邮件的工作过程如下：
①用户1调用用户代理来编辑要发送的邮件，用户代理用SMTP 将邮件传送给用户1的发送端邮件服务器。
②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中，等待发送。 ③运行在发送端邮件服务器的SMTP 客户进程，发现在邮件缓存中有待发送的邮件，就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP 服务器进程发起TCP 连接建立。当TCP 连接建立后，SMTP 客户进程开始向远程的SMTP 服务器发送邮件。当所有的待发邮件发完了，SMTP 就关闭所建立的TCP 连接。
④运行在接收端邮件服务器中的SMTP 服务器进程收到邮件后，将邮件放人收信人的用户邮箱中，等待收信人在他方便时进行读取。收信人在打算收信时，调用用户代理，使用POP 协议将自己的邮件从接收端邮件服务器的用户邮箱中取回（如果邮箱中有来信的话）。
因此题中1，2, 3阶段分别使用的应用层协议可以是SMTP ，SMTP , POP3, 因此答案是D 。SMTP 采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。