2017年广东技术师范学院J235数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． （1）判定起泡排序的结束条件是什么？
（2）请简单叙述希尔排序的基本思想。 （3）将下列序列调整成堆（堆顶为最小值）。
（4）在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。
【答案】（1）至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。
（2）希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将，从而减少参与直接插入排序的数据量，当经过几次分待排序的记录划分成几组（缩小增量分组）
组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。
（3）13，24，33，65，70，56，48，92，80，112
（4）采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次（两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15次。将冠军的叶结点改为最大值，均与兄弟比较，共4次选出亚军）。
2． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。
图 存储映像7K 意图
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】
（1）算法的基本设计思想：
①分别求出strl 和str2所指的两个链表的长度m 和n ;
第 2 页，共 38 页
请设计一
个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字
或JA V A 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度。
②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第
个结点；若
则使q 指向链表中的第
表尾的长度相等。
则使p 指向链
个结点，即使指针p 和q 所指的结点到
③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。
（2）用C 语言算法描述如下：
两个指针同步向后移动
（3）参考答案的时间复杂度为：
或
其中m 、n 分别为两个链表的
长度。
3． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
4． 阅读下面的算法，说明算法实现的功能。
【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。
5． 对下面的关键字集若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。
【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为
第 3 页，共 38 页
返回共同C 缀的起始点
用除留余数法设计
哈希函数，哈希函数为
（2）哈希表如表所示：
表 哈希表
（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，
当其哈希地址为
时的查找次数。本例中
（4）算法如下：
6． 系统中有多个生产者进程和消费者进程，，共享用一个可以存1000个产品的缓冲区（初始为空）当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量
求写出完整的过程；并指出所用信号量的含义和初值
【答案】设置5个信号量
empty :表示缓冲区是否为空，初值为1000 full ：
表示缓冲区是否为满，初值为0
mutex 1：生产者之间的互斥信号，初值为1 mutex2：消费者之间的互斥信号，初值为1 available :当前消费者能否访问缓冲区，初值为1
定义变量in , out 分别为生产者和消费者进程所要使用的指针，指向下一个可用的缓冲区单元，MaXNum= 1000 为缓冲区的大小，count 标志当前消费者已经取的产品的数量，初值为0
生产者进程：
第 4 页，共 38 页
故查找失败和查找成功时的平均查找长度分别为：
操作实现进程间的互斥和同步，要