2010江苏省C语言版高级

1、约瑟夫环问题（Josephus问题）是指编号为1、2、 ，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列， ，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。

2、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.

typedef struct node

{int data; struct node *lchild,*rchild;}node;

int N2,NL,NR,N0;

void count(node *t)

{if (t->lchild!=NULL) if (1)___ N2++; else NL++;

else if (2)___ NR++; else (3)__ ;

if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;

}

26.树的先序非递归算法。

void example(b)

btree *b;

{ btree *stack[20], *p；

int top;

if (b!=null)

{ top=1; stack[top]=b;

while (top>0)

{ p=stack[top]; top--;

printf(“%d”,p->data);

if (p->rchild!=null)

{(1)___; (2)___;

}

if (p->lchild!=null)

(3)___; (4)__;

}}}}

3、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。

#include <stdio.h>

typedef char datatype;

typedef struct node{

datatype data;

struct node * next;

} listnode;

typedef listnode* linklist;

/*--------------------------------------------*/

/* 删除单链表中重复的结点 */

/*--------------------------------------------*/

linklist deletelist(linklist head)

{ listnode *p,*s,*q;

p=head->next;

while(p)

{s=p;

q=p->next;

while(q)

if(q->data==p->data)

{s->next=q->next;free(q);

q=s->next;}

else

{ s=q; /*找与P结点值相同的结点*/

q=q->next;

}

p=p->next;

}

return head;

}

4、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100

typedef struct Node

{char info; struct Node *llink, *rlink; }TNODE;

char pred[MAX],inod[MAX];

main(int argc,int **argv)

{ TNODE *root;

if(argc<3) exit 0;

strcpy(pred,argv[1]); strcpy(inod,argv[2]);

root=restore(pred,inod,strlen(pred));

postorder(root);

}

TNODE *restore(char *ppos,char *ipos,int n)

{ TNODE *ptr； char *rpos; int k;

if(n<=0) return NULL;

ptr->info=(1)_______;

for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;

k=(3)_______;

ptr->llink=restore(ppos+1, (4)_______,k );

ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);

return ptr;

}

postorder(TNODE*ptr)

{ if(ptr=NULL) return;

postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }

5、假设K1， ，Kn是n个关键词，试解答：

试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2， ，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

6、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度

{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点

int i，top=0,tag[],longest=0;

while(p || top>0)

{ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下

if(tag[top]==1) //当前结点的右分枝已遍历

{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度

if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈，记住最高栈顶指针，退栈

}

else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下

}//while(p!=null||top>0)

}//结束LongestPath

7、编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。

8、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）

9、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100

typedef struct Node

{char info; struct Node *llink …… 此处隐藏：3409字，全部文档内容请下载后查看。喜欢就下载吧 ……