2011年内蒙古自治区基础数据入门
- 格式：rtf
- 大小：49.24 KB
- 文档页数：1
1、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A 的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
2、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
3、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
4、二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。
（1）．请各举一个结点个数为5的二部图和非二部图的例子。
（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。
设G用二维数组A来表示，大小为n*n（n为结点个数）。
请在程序中加必要的注释。
若有必要可直接利用堆栈或队列操作。
【
5、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
