2017年湖南师范大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 已知一个带有表头结点的单链表，结点结构为datalink , 假设该链表只给出了头指针list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1; 否则，只返回0。要求：
（1）描述算法的基本设计思想； （2）描述算法的详细实现步骤；
（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C 或，关键之处请给出简要注释。 现）
【答案】（1）算法的基本设计思想定义两个指针变量p 和q ，初始时均指向头结点的下一个结点。p 指针沿链表移动；当p 指针移动到第k 个结点时，q 指针开始与p 指针同步移动；当p 指针移动到链表最后一个结点时，因为p 和q 相隔k ，故q 指针所指元素为倒数第k 个结点。以上过程对链表仅进行一遍扫描。
（2）算法的详细实现步骤
①count=0, p 和q 指向链表表头结点的下一个结点； ②若p 为空，转⑤; ，
③若count 等于k ，则q 指向下一个结点；否则，count=count+l; ④p 指向下一个结点，转步骤②；
⑤若count 等于k ，则查找成功，输出该结点的data 域的值，返回1; 否则，查找失败，返回0;
⑥算法结束。 （3）算法实现
第 2 页，共 37 页
或JA V A 语言实
2． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :
假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。
（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ （2）数组数据号从0开始）？
（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？
【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache 块号为log28=3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28-6-3=19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为
（2）数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示：
和
各自所在的主存块对应的Cache 行号分别是多少（Cache 行
图
数组按行优先方式存放，首地址为320, 数组元素占4个字节。
第 3 页，共 37 页
所在的主存块对应的
Cache 行号
为
（3）数组a 的大小为逐行访问数
组a ，共需访问的次数为A 的数据访问命中率为
所在的主存块对应的Cache 行号
为占用
个主存块，按行优先存放，程序A
次，程序
次，每个字块的第一个数未面中，因此未面中次数为
Cache 总容量为
数组a —行的大
小为1KB 正好是Cache 容量的2倍，可知不同行的同一列数组元素使用的是同一个Cache 单元，而程序B 逐列访问数组a 的数据时，都会将之前的字块置换出，也即每次访问都不会面中，故程序B 的数据访问命中率是0, 因此程序A 的执行过程更短。
3． 某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许个通过。参观者的活动描述如下：
参观者进程i :
进门；
参观;
出门；
coend
请添加必要的信号量和P 、
V 的互斥与同步。
要求写出完整的过程，说明信号量含义并赋初值。 【答案】 定义两个信号量
博物馆可以容纳的最多人数
用于出入口资源的控制
参观者进程i :
进门；
第 4 页，共 37 页
操作，以实现上述操作过程中