数据结构试卷三．阅读下面的算法(10分)LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL

Question

数据结构试卷
三．阅读下面的算法(10分)
LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L；L=L－>next；p=L；
S1：while(p－>next) p=p－>next；
S2：p－>next=q；q－>next=NULL；
}
return L；
}
请回答下列问题：
（1）说明语句S1的功能；
（2）说明语句组S2的功能；
（3）设链表表示的线性表为（a1,a2,...,an）,写出算法执行后的返回值所表示的线性表.
四、应用题（每题10分）
1．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG.
(1)画出该二叉树并给出其二叉链表及顺序存储结构表示.
(2)画出与（1）求得的二叉树对应的森林.
2．已知带权图的邻接表如下所示,其中边表结点的结构为：
依此邻接表从顶点C出发进行深度优先遍历.
（1）画出由此得到的深度优先生成树；
（2）求网的最小生成树
3．设散列表的长度m=13；散列函数为H(K)=K mod m,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试画出用线性探查法解决冲突时所构造的散列表.并求出在等概率的情况下,这种方法的搜索成功时的平均搜索长度和搜索不成功时的平均搜索长度.
4.（1）已知一组键值序列（3,6,8,9,2,7,4）,试采用快速排序法对该组序列作升序排序,并给出每一趟的排序结果.
（2）已知一组键值序列（28,47,35,42,53,60,34,22）,试给出采用直接插入排序法对该组序列作升序排序的每一趟结果.

Answer 1

请回答下列问题：
（1）说明语句S1的功能；——查找表尾元素
（2）说明语句组S2的功能； ——把第一个元素插入表尾
（3）设链表表示的线性表为（a1,a2, ...,an）,写出算法执行后的返回值所表示的线性表.（a2, ...,an,a1）,
1．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG.
(1)画出该二叉树并给出其二叉链表及顺序存储结构表示.
(2)画出与（1）求得的二叉树对应的森林.
H
D G
A C F
B E 连接情况是,D,G连接H ,A,C 连接D,B连接C,E连接F,F连接G
3．设散列表的长度m=13；散列函数为H(K)=K mod m,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试画出用线性探查法解决冲突时所构造的散列表.并求出在等概率的情况下,这种方法的搜索成功时的平均搜索长度和搜索不成功时的平均搜索长度.
0 1 2 3 4 5 6 7 8 9 10 11 12
14 01 68 27 55 9 20 84 23 11
4.（1）已知一组键值序列（3,6,8,9,2,7,4）,试采用快速排序法对该组序列作升序排序,并给出每一趟的排序结果.
(2)3(8 9 6 7 4)
2 3 （4 6）8（7 9）
2 3 4 （6）8 7（9）
23 4 6 8 7 9
（2）已知一组键值序列（28,47,35,42,53,60,34,22）,试给出采用直接插入排序法对该组序列作升序排序的每一趟结果.
（28,47,35,42,53,60,34,22）,
（28,47,35,42,53,60,34,22）,
（28,35,47,42,53,60,34,22）,
（28,35,42,47,53,60,34,22）,
（28,35,42,47,53,60,34,22）,
（28,35,42,47,53,60,34,22）,
（28,34,35,42,47,53,60,22）,
（22,28,34,35,42,47,53,60）,