1.设A=(a1,a2,…,an)，B=(b1,b2,…,bm)是两个递增有序的线性表（其中n、m均大于1），且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放，设计一个尽可能高效的算法判断B是否为A的一个子序列，并分析你设计的算法的时间复杂度和空间复杂度。（15分） 1.（15分）解：采用二路归并思路，用p、q分别扫描有序单链表A、B，先找到第一个两者值相等的节点，然后在两者值相等时同步后移，如果B扫描完毕返回1，否则返回0。对应的算法如下：

int SubSeq(LinkList *A,LinkList *B){LinkList *p=A->next,*q=B->next;while (p!=NULL && q!=NULL)//找两个单链表中第一个值相同的节点{if (p->datadata)p=p->next;else if (p->data>q->data)q=q->next;elsebreak;}while (p!=NULL && q!=NULL && p->data==q->data){//当两者值相等时同步后移p=p->next;q=q->next;}if (q==NULL)//当B中节点比较完毕返回1return 1;else//否则返回0return 0;}

本算法的时间复杂度为O(m+n)，空间复杂度为O(1)。其中m、n分别为A、B单链表的长度。

(资料图片)

2.假设二叉树b采用二叉链存储结构存储，试设计一个算法，输出该二叉树中从根节点出发的第一条最长的路径长度，并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。（15分） 3.2.（15分）解：由于二叉树中最长路径一定是从根节点到某个叶子节点的路径，可以求出所有叶子节点到根节点的逆路径，通过比较长度得出最长路径，可以采用多种解法。算法中用形参maxpath[]数组存放最长路径，maxpathlen存放最长路径长度。 解法1：对应的算法如下：

void MaxPath(BTNode *b,ElemType maxpath[],int &maxpathlen){//maxpathlen的初值为0struct snode{BTNode *node;//存放当前节点指针int parent;//存放双亲节点在队列中的位置} Qu[MaxSize];//定义非循环队列ElemType path[MaxSize];//存放一条路径int pathlen;//存放一条路径长度int front,rear,p,i;//定义队头和队尾指针front=rear=-1;//置队列为空队列rear++;Qu[rear].node=b;//根节点指针进进队Qu[rear].parent=-1;//根节点没有双亲节点while (frontfront++;b=Qu[front].node;//队头出队列if (b->lchild==NULL && b->rchild==NULL)//*b为叶子节点{p=front;pathlen=0;while (Qu[p].parent!=-1){path[pathlen]=Qu[p].node->data;pathlen++;p=Qu[p].parent;}path[pathlen]=Qu[p].node->data;pathlen++;if (pathlen>maxpathlen)//通过比较求最长路径{for (i=0;ilchild!=NULL)//左孩子节点进队{rear++;Qu[rear].node=b->lchild;Qu[rear].parent=front;}if (b->rchild!=NULL)//右孩子节点进队{rear++;Qu[rear].node=b->rchild;Qu[rear].parent=front;}}}

本算法的时间复杂度为O(n)，空间复杂度为O(n)。

假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。（10分）（10分）解：采用深度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下： int visited[MAXV]={0}; DFSGraph(AGraph *G) { int i,j=1; //用j记录连通分量的序号 for (i=0;in;i++) if (visited[i]==0) { printf(“第%d个连通分量节点序列:”,j++); DFS(G,i); //调用前面的深度优先遍历算法 } } 采用广度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下： int visited[MAXV]={0}; BFSGraph(AGraph *G) { int i,j=1; //用j记录连通分量的序号 for (i=0;in;i++) if (visited[i]==0) { printf(“第%d个连通分量节点序列:”,j++); BFS(G,i); //调用前面的广度优先遍历算法 } }

题3 1.设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。给出你所设计的算法的时间复杂度和空间复杂度。

设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。给出你所设计的算法的时间复杂度和空间复杂度。 解：算法如下：

void insertion(LinkList *A,LinkList *B,LinkList *&C){LinkList *p=A->next,*q=B->next,*s,*t;C=(LinkList *)malloc(sizeof(LinkList));t=C;while (p!=NULL && q!=NULL){if (p->data==q->data){s=(LinkList *)malloc(sizeof(LinkList));s->data=p->data;t->next=s;t=s;p=p->next;q=q->next;}else if (p->datadata)p=p->next;elseq=q->next;}t->next=NULL;}

算法的时间复杂度为O(m+n)，空间复杂度为O(MIN(m,n))。 【评分说明】算法为8分，算法的时间复杂度和空间复杂度各占1分。

假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点（假设这样的结点是唯一的）的双亲结点地址p，提示，根结点的双亲为NULL，若在b中未找到值为x的结点，p亦为NULL。假设二叉树b采用二叉链存储结构，设计一个算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为x的结点的双亲结点p，提示，根结点的双亲为NULL，若未找到这样的结点，p亦为NULL。 解：算法如下：

void findparent(BTNode *b,ElemType x,BTNode *&p){if (b!=NULL){if (b->data==x) p=NULL;else if (b->lchild!=NULL && b->lchild->data==x)p=b;else if (b->rchild!=NULL && b->rchild->data==x)p=b;else{findparent(b->lchild,x,p);if (p==NULL)findparent(b->rchild,x,p);}}else p=NULL;}

【评分说明】本题有多种解法，相应给分。

题4 1.用单链表来存储集合，并假设这样的单链表中的节点递增有序，设计一个尽可能高效的算法求两个集合A和B的并集C。设A、B中分别有m和n个元素，分析你设计的算法的时间和空间复杂度。（15分）

解：由于单链表是递增有序的，可以采用归并算法提高求并集的效率，结果并集C采用尾插法建表。对应算法如下：

void Unionset(LinkList *A,LinkList *B,LinkList *&C){LinkList *pa=A->next,*pb=B->next,*s,*r;C=(LinkList *)malloc(sizeof(LinkList));//建立C的头节点r=C;//r始终指向单链表C的尾节点while (pa!=NULL && pb!=NULL){if (pa->datadata)//仅复制*pa节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;}else if (pa->data>pb->data)//仅复制*pb节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pb->data;r->next=s; r=s;pb=pb->next;}else{s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;pb=pb->next;}}while (pa!=NULL)//复制A单链表的余下节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;}while (pb!=NULL)//复制B单链表的余下节点{s=(LinkList *)malloc(sizeof(LinkList));s->data=pb->data;r->next=s; r=s;pb=pb->next;}r->next=NULL;}

本算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)，其中m、n分别为A、B单链表中的节点个数。 评分：算法占11分，时间和空间复杂度各占2分。

2.假设二叉树采用二叉链存储结构进行存储，假设每个节点值为单个字符且所有节点值不同，设计一个算法，输出二叉树b中第k的所有节点值，并分析你所设计算法的时间复杂度。（15分） 2. 解：采用先序序列，对应的算法如下：

void Dispk(BTNode *b,int k){Dispk1(b,k,1);}void Dispk1(BTNode *b,int k,int h){if (b!=NULL){if (h==k) printf(“%c “,b->data);Dispk1(b->lchild,k,h+1);Dispk1(b->rchild,k,h+1);}}

评分：采用先序、中序、后序和层次遍历均可，算法占13分，时间复杂度占2分。

说明：以上两题求算法的时间和空间复杂度只需给出结果，不必给出详细步骤。

图的邻接表是一种图的链式存储结构，请给出邻接表的完整类型定义。采用你所设计的邻接表作为存储结构，设计一个算法，求出无向图G的连通分量个数。（10分）

3. 解：邻接表的类型定义如下：typedef char ElemType;typedef int InfoType;typedef struct ANode//边的节点结构类型{int adjvex;//该边的终点位置struct ANode *nextarc;//指向下一条边的指针InfoType info;//该边的相关信息，对于带权图可存放权值} ArcNode;typedef struct Vnode//邻接表头节点的类型{ElemType data;//顶点信息ArcNode *firstarc;//指向第一条边} VNode;typedef VNode AdjList[MAXV];//AdjList是邻接表类型typedef struct{AdjList adjlist;//邻接表int n,e;//分别为图中顶点数和边数} AGraph;//声明图的邻接表类型采用遍历方式求无向图G中连通分量个数。基于深度优先遍历的算法如下：int visited[MAXV]={0};int Getnum(AGraph *G)//求图G的连通分量{int i,n=0,visited[MAXVEX];for (i=0;in;i++)if (visited[i]==0){DFS(G,i);//对图G从顶点i开始进行深度优先遍历n++;//调用DFS的次数即为连通分量数}return n;}基于广度优先遍历的算法如下：int visited[MAXV]={0};int Getnum1(AGraph *G)//求图G的连通分量{int i,n=0,visited[MAXVEX];for (i=0;in;i++)if (visited[i]==0){BFS(G,i);//对图G从顶点i开始进行广度优先遍历n++;//调用BFS的次数即为连通分量数}return n;}

评分：邻接表的类型定义占5分，求无向图G的连通分量个数的算法占5分。

第五套题

（10分）某带头结点的非空单链表L中所有元素为整数，结点类型定义如下：

typedef struct node{int data;struct node *next;} LinkNode;

设计一个尽可能高效的算法，将所有小于零的结点移到所有大于等于零的结点的前面。

（10分）答案：

void Move(LinkNode *&L){LinkNode *p=L->next,*pre=L;     while (p!=NULL && p->data<0)//跳过小于0的结点     {pre=p;p=pre->next;     }while (p!=NULL){if (p->data<0)//若*p结点值小于0{pre->next=p->next;//从链表中删除*p结点p->next=L->next;//将*p结点插入到头结点之后L->next=p;p=pre->next;//p指向*pre之后结点，pre不变}else//若*p结点值不小于0{pre=p;//pre、p同步后移一个结点p=p->next;}}}

（15分）假设二叉树中有n个结点，每个结点值为单个字符，而且所有结点值均不相同，采用二叉链存储结构存储，其结点类型定义如下：

typedef struct node{char data;     struct node *lchild,*rchild;} BTNode;

请完成以下任务： （1）设计一个算法，在二叉树b中查找x结点（指结点值为x的结点），若找到该结点，返回其地址，否则返回NULL。给出你设计的算法的时间复杂度。（8分） （2）设计一个算法，利用（1）小题设计的算法输出二叉树b中x结点的所有子孙结点值。（7分） 2. （15分）答案： （1）（7分）

BTNode *Findx(BTNode *b,char x)//在二叉树b中查找x结点{BTNode *p;if (b==NULL) return NULL;else{if (b->data==x)return b;p=Findx(b->lchild,x);if (p!=NULL)return p;return Findx(b->rchild,x);}}

算法的时间复杂度为O(n)（1分）。 （2）（7分）

void Sons(BTNode *b,char x)//输出x结点的子孙，初始时b指向x结点{if (b!=NULL){if (b->data!=x)printf("%c ",b->data);Sons(b->lchild,x);Sons(b->rchild,x);}}void OutSons(BTNode *b,char x)//输出二叉树b中x结点的所有子孙结点值{BNode *p= Findx(b,x);if (p!=NULL)Sons(p,x);}

题6

1.设计一个算法delminnode(LinkList *&L)，在带头结点的单链表L中删除所有结点值最小的结点（可能有多个结点值最小的结点）。

解：用p从头至尾扫描单链表，pre指向p结点的前驱，用minp保存值最小的结点指针，minpre指向minp结点的前驱。一面扫描，一面比较，将最小值的结点放到*minp中。算法如下：

void delminnode(LinkList *&L){LinkList *pre=L,*p=pre->next,*minp=p,*minpre=pre;ElemType mindata=p->data;while (p!=NULL && p->datamindata=p->data;p=p->next;}p=pre->next;while (p!=NULL){if (p->data==mindata){pre->next=p->next;free(p);}pre=pre->next;p=pre->next;}}

评分标准：根据算法的正确性评分，不考虑算法的时间复杂度。

2.假设二叉树采用二叉链存储结构存储，设计一个算法copy(BTNode *b,BTNode *&t)，由二叉树b复制成另一棵二叉树t。 2．解：递归算法如下：

void copy(BTNode *b,BTNode *&t){BTNode *l,*r;if (b==NULL) t=NULL;else{t=(BTNode *)malloc(sizeof(BTNode));copy(b->lchild,l);copy(b->rchild,r);t->lchild=l;t->rchild=r;}}

评分标准：根据算法的正确性评分，不考虑算法的时间复杂度。

假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。解：采用深度优先搜索遍历非连通图，并输出各连通分量节点序列的算法如下：

DFSGraph(AGraph *G){int i,j=1;//用j记录连通分量的序号for (i=0;in;i++)if (visited[i]==0){printf("第%d个连通分量节点序列:",j++);DFS(G,i);//调用深度优先遍历算法}}

题9

（15分）有两个递增有序表，所有元素为整数，均采用带头结点的单链表存储，结点类型定义如下：

typedef struct node{int data;struct node *next;} LinkNode;

设计一个尽可能高效的算法，将两个递增有序单链表ha、hb合并为一个递减有序单链表hc，要求算法空间复杂度为O(1)。

（15分）参考算法如下：

void merge(LinkNode *ha， LinkNode *hb， LinkNode *&hc){LinkNode *pa=ha->next，*pb=hb->next，*q;free(hb);hc=ha; hc->next=NULL;//hc利用ha的头结点，并设置为空while (pa!=NULL && pb!=NULL)//扫描ha、hb的数据结点{if (pa->datadata)//将较小结点采用头插法插入到hc中{q=pa->next;pa->next=hc->next;hc->next=pa;pa=q;}else{q=pb->next;pb->next=hc->next;hc->next=pb;pb=q;}}if (pb!=NULL) pa=pb;while (pa!=NULL)//将没有扫描完的结点采用头插法插入到hc中{q=pa->next;pa->next=hc->next;hc->next=pa;pa=q;}}

评分说明：上述算法的时间复杂度为O(m+n)。若设计的算法时间复杂度为O(m*n)，至少扣3分，若设计的算法空间复杂度不为O(1)，扣2分。

2、（10分）设二叉树中每个结点存放单个字符，其结点类型如下：

typedef struct node{char  data;    struct node *lchild，*rchild;} BTNode;

设计一个算法求其中单分支的结点个数。 2、（10分）参考算法如下：

int singleodes(BTNode *b){if (b==NULL) return 0;     if ((b->lchild==NULL && b->rchild!=NULL) ||//单分支的结点(b->lchild!=NULL && b->rchild==NULL)return singleodes(b->lchild)+ singleodes(b->rchild)+1;elsereturn singleodes(b->lchild)+ singleodes(b->rchild);）

评分说明：可以采用任意一种遍历方法。判断单分支的结点为3分。