数据结构期末复习（201512）
三、基本方法
1、算法的时间及空间复杂度的基本分析方法。 2、顺序栈的出入栈序列判断及求法。 3、循环队列的判空判满条件及求法。 4、二叉树的基本性质的计算及应用。
5、已知二叉树的遍历确定二叉树的形态求法。 6、线索二叉树的求法。
7、树的孩子兄弟链表结构的转换方法。 8、哈夫曼树及哈夫曼编码的求法。
9、邻接矩阵图、邻接表图、逆邻接表图的存储结构的相互转换。 10、图的深度优先、广度优先遍历的生成序列求法。
11、基于普利姆算法及克鲁斯卡尔算法的最小代价生成树求法。 12、拓扑排序的序列求法。 13、图的关键路径的求法。
14、基于线性探测再散列、链地址法的哈希表的生成求法。
15、二叉排序树、判定树、哈希表查找方法的平均查找长度求法。 16、平衡二叉树的类型判断及平衡方法。
17、希尔排序、快速排序、堆排序、归并排序的求法。
四、算法描述及算法设计
1、线性表基本算法的应用设计。
2、二叉树及孩子兄弟链表树的遍历算法应用设计。 3、图的遍历算法应用设计。
算法应用设计练习题举例（数据结构习题集）：
（1）2.15（单链表合并）2.19（单链表删除）2.24（有序单链表合并）2.29（多表删除）
2.33（分割循环单链表）
（2）6.39（不用栈非递归遍历）6.42（求结点数目）6.44（求子树深度）6.45（删除子树）
6.49（判断完全二叉树）
（3）7.14（创建邻接表）7.27（求长度为k的简单路径）7.30（求有向图的简单回路）
7.34（拓扑排序的序号应用）7.35（求有向无环图根的算法） 五、数据结构期末试题样题举例 三、应用题（30分）
.1. 已知一个哈希表如下图所示： 0 1 2 35 3 4 20 5 6 7 33 8 9 48 10 11 12 59 其哈希函数为 H(key)=key，处理冲突的方法为再散列法，散列函数为：
Hi=(H(key)+i*H1(key))%m i=0,1,…，m－1 其中：H1(key)=key+1 试求：（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数（要有计算过程）。（3，2，1，1）
—１—
（2）在等概率查找时查找成功的平均查找长度。（9.5）
2.已知一个无向图的顶点集V和边集E分别为
V={1,2,3,4,5,6,7};E={(2,1),(3,2),(3,6),(4,3),(4,5),(4,6),(5,1),(5,7),(6,1),(6,2),(6,5)};
若采用图的邻接表结构，并且邻接表中的边结点都是按照顶点编号从小到大的次序链接。 试求：（1）画出图的邻接表存储结构。
（2）画出 从顶点②出发的广度优先生成树。 3．假设初始关键字序列为（4, 2, 5, 8, 3）。根据堆排序算法，画出采用小根堆的堆排序过程。 （2,3,5,8,4）（3,4,5,8,2）（4,8,5,3,2）（5,8,4,3,2）（8,5,4,3,2）
四、算法设计题（12分）
设顺序表SqList中的数据元素递增有序。设计在有序顺序表中插入数据元素x的算法。 设函数原型定义：Sq_Insert(SqList L,int x) 参考答案：
void Sq_Insert(SqList L,int x) {//将x插入到有序顺序表中 int i,j;
if (L.length==L.listsize) exit(1);//溢出 else {
i= L.length-1;
for(;i>=0&&x
L.elem[j+1]== L.elem[j]; //元素后移
L.elem[i+1]=x; //插入x L.length++; //表长加1 }//else }// Sq_Insert
五、算法设计题（14分）
. 已知二叉树结点的存储结构为BiTree类型，单链表结点结构为LinkList类型。设计算法实现中序遍历二叉树，并使用叶子结点的数据域的值构建一个以L为头指针的无头结点的单链表。
函数原型定义： void Inorder_List(BiTree T, LinkList L ) 参考答案：
LinkList L=NULL；
void Inorder_List(BiTree T, LinkList L ){
//中序遍历二叉树，并按遍历叶子结点的值构建无头结点的单链表 if(T){
Inorder(T－>lchild，L)；//遍历左子树
if ((!T－>lchild)&&(!T－>rchild)){ //叶子结点
s=( LinkList )malloc(sizeof(ListNode))；//产生链表结点 s－>data=T－>data；//赋值 s－>next=L；//插入 L=s； }
Inorder(T－>rchild,L)；//遍历右子树 }//if
}//Inorder_List
—２—
六、算法设计题（14分）
已知图的邻接表结构定义如下： typedef struct Vnode
{ VertexNode data; //顶点信息 struct Enode *next;//指针域 }Vnode,Adjlist[MaxNum];//邻接表顶点 typedef struct Enode {
int adjvex;//顶点编号
ENode *firstarc;//指针域 }ENode;//边结点 typedef struct { Adjlist Vexs;
int n,e;//图中当前的顶点数和边数 } ALGraph;//邻接表
设计算法判别无向图中任意给定的两个顶点之间是否存在长度为k的简单路径。 函数原型定义：int Exit_Path_K(ALGraph G,int i,int j,int k) 参考答案：
int Exit_Path_K(ALGraph G,int i,int j,int k){
//判别无向图中任意给定的两个顶点之间是否存在长度为k的简单路径 if(i==j&&k==0) return 1; // 找到路径
else {
if(k>0)//尚未找到
visited[i]=1;//置访问标记
for(p=G.vexs[i].firstarc;p;p=p->next){//遍历邻接点
w=p->adjvex; if(!visited[w])
Exit_Path_K(G,w,j,k-1); }//for }//else
if(k==0) return 1; else return 0; }// Exit_Path_K
—３—