2010山东省数据结构分析基础

1、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=i

//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点 {LinkedList h;

h=(LinkedList)malloc(sizeof(LNode));//申请结点 h->next=h; //形成空循环链表 for(i=0;inext;

while(p!=h && p->data

{pre=p; p=p->next;} //查找A[i]的插入位置

if(p==h || p->data!=A[i]) //重复数据不再输入 {s=(LinkedList)malloc(sizeof(LNode));

s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中 }

}//for

return(h); }算法结束

2、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。

（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true （2）s,n-1 // Knap←Knap(s,n-1)

3、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能： （1）．建立有向图G的邻接表存储结构； （2）．判断有向图G是否有根，若有，则打印出所有根结点的值。

4、给出折半查找的递归算法，并给出算法时间复杂度性分析。

5、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立，现证明当n=m时结论成立。 设中序序列为S1，S2，?，Sm,后序序列是P1,P2,?，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，?，Si-1是左子树的中序序列，而Si+1,Si+2,?,Sm是右子树的中序序列。

若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，?，Sm}和{P1，P2，?，Pm-1}可以唯一确定右子树，从而也确定了二叉树。 若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，?，Sm-1}和{P1，P2，?，Pm-1}唯一确定左子树，从而也确定了二叉树。

最后，当1

6、4、 void LinkList_reverse(Linklist &L)

//链表的就地逆置;为简化算法,假设表长大于2 {

p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) {

q->next=p;p=q;

q=s;s=s->next; //把L的元素逐个插入新表表头 }

q->next=p;s->next=q;L->next=s; }//LinkList_reverse

7、本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\\n”,v); num=0;}//if p=g[v].firstarc; while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex); p=p->next;} //while

visited[v]=0; num--; //恢复顶点v }//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。 {static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

本文来源：https://www.bwwdw.com/article/vh08.html