1.設(shè)A=(a1,a2,…,an)，B=(b1,b2,…,bm)是兩個(gè)遞增有序的線(xiàn)性表（其中n、m均大于1），且所有數(shù)據(jù)元素均不相同。假設(shè)A、B均采用帶頭節(jié)點(diǎn)的單鏈表存放，設(shè)計(jì)一個(gè)盡可能高效的算法判斷B是否為A的一個(gè)子序列，并分析你設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。（15分） 1.（15分）解：采用二路歸并思路，用p、q分別掃描有序單鏈表A、B，先找到第一個(gè)兩者值相等的節(jié)點(diǎn)，然后在兩者值相等時(shí)同步后移，如果B掃描完畢返回1，否則返回0。對(duì)應(yīng)的算法如下：

int SubSeq(LinkList *A,LinkList *B){LinkList *p=A->next,*q=B->next;while (p!=NULL && q!=NULL)//找兩個(gè)單鏈表中第一個(gè)值相同的節(jié)點(diǎn){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){//當(dāng)兩者值相等時(shí)同步后移p=p->next;q=q->next;}if (q==NULL)//當(dāng)B中節(jié)點(diǎn)比較完畢返回1return 1;else//否則返回0return 0;}

本算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(1)。其中m、n分別為A、B單鏈表的長(zhǎng)度。

2.假設(shè)二叉樹(shù)b采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，輸出該二叉樹(shù)中從根節(jié)點(diǎn)出發(fā)的第一條最長(zhǎng)的路徑長(zhǎng)度，并輸出此路徑上各節(jié)點(diǎn)的值。并分析你設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。（15分） 3.2.（15分）解：由于二叉樹(shù)中最長(zhǎng)路徑一定是從根節(jié)點(diǎn)到某個(gè)葉子節(jié)點(diǎn)的路徑，可以求出所有葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的逆路徑，通過(guò)比較長(zhǎng)度得出最長(zhǎng)路徑，可以采用多種解法。算法中用形參maxpath[]數(shù)組存放最長(zhǎng)路徑，maxpathlen存放最長(zhǎng)路徑長(zhǎng)度。 解法1：對(duì)應(yīng)的算法如下：

(資料圖片僅供參考)

void MaxPath(BTNode *b,ElemType maxpath[],int &maxpathlen){//maxpathlen的初值為0struct snode{BTNode *node;//存放當(dāng)前節(jié)點(diǎn)指針int parent;//存放雙親節(jié)點(diǎn)在隊(duì)列中的位置} Qu[MaxSize];//定義非循環(huán)隊(duì)列ElemType path[MaxSize];//存放一條路徑int pathlen;//存放一條路徑長(zhǎng)度int front,rear,p,i;//定義隊(duì)頭和隊(duì)尾指針front=rear=-1;//置隊(duì)列為空隊(duì)列rear++;Qu[rear].node=b;//根節(jié)點(diǎn)指針進(jìn)進(jìn)隊(duì)Qu[rear].parent=-1;//根節(jié)點(diǎn)沒(méi)有雙親節(jié)點(diǎn)while (frontfront++;b=Qu[front].node;//隊(duì)頭出隊(duì)列if (b->lchild==NULL && b->rchild==NULL)//*b為葉子節(jié)點(diǎn){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)//通過(guò)比較求最長(zhǎng)路徑{for (i=0;ilchild!=NULL)//左孩子節(jié)點(diǎn)進(jìn)隊(duì){rear++;Qu[rear].node=b->lchild;Qu[rear].parent=front;}if (b->rchild!=NULL)//右孩子節(jié)點(diǎn)進(jìn)隊(duì){rear++;Qu[rear].node=b->rchild;Qu[rear].parent=front;}}}

本算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。

假設(shè)一個(gè)無(wú)向圖是非連通的，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，輸出圖中各連通分量的節(jié)點(diǎn)序列。（10分）（10分）解：采用深度優(yōu)先搜索遍歷非連通圖，并輸出各連通分量節(jié)點(diǎn)序列的算法如下： int visited[MAXV]={0}; DFSGraph(AGraph *G) { int i,j=1; //用j記錄連通分量的序號(hào) for (i=0;in;i++) if (visited[i]==0) { printf(“第%d個(gè)連通分量節(jié)點(diǎn)序列:”,j++); DFS(G,i); //調(diào)用前面的深度優(yōu)先遍歷算法 } } 采用廣度優(yōu)先搜索遍歷非連通圖，并輸出各連通分量節(jié)點(diǎn)序列的算法如下： int visited[MAXV]={0}; BFSGraph(AGraph *G) { int i,j=1; //用j記錄連通分量的序號(hào) for (i=0;in;i++) if (visited[i]==0) { printf(“第%d個(gè)連通分量節(jié)點(diǎn)序列:”,j++); BFS(G,i); //調(diào)用前面的廣度優(yōu)先遍歷算法 } }

題3 1.設(shè)A和B是兩個(gè)結(jié)點(diǎn)個(gè)數(shù)分別為m和n的單鏈表（帶頭結(jié)點(diǎn)），其中元素遞增有序。設(shè)計(jì)一個(gè)盡可能高效的算法求A和B的交集，要求不破壞A、B的結(jié)點(diǎn)，將交集存放在單鏈表C中。給出你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

設(shè)A和B是兩個(gè)結(jié)點(diǎn)個(gè)數(shù)分別為m和n的單鏈表（帶頭結(jié)點(diǎn)），其中元素遞增有序。設(shè)計(jì)一個(gè)盡可能高效的算法求A和B的交集，要求不破壞A、B的結(jié)點(diǎn)，將交集存放在單鏈表C中。給出你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。 解：算法如下：

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;}

算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(MIN(m,n))。 【評(píng)分說(shuō)明】算法為8分，算法的時(shí)間復(fù)雜度和空間復(fù)雜度各占1分。

假設(shè)二叉樹(shù)b采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值為x的結(jié)點(diǎn)（假設(shè)這樣的結(jié)點(diǎn)是唯一的）的雙親結(jié)點(diǎn)地址p，提示，根結(jié)點(diǎn)的雙親為NULL，若在b中未找到值為x的結(jié)點(diǎn)，p亦為NULL。假設(shè)二叉樹(shù)b采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值為x的結(jié)點(diǎn)的雙親結(jié)點(diǎn)p，提示，根結(jié)點(diǎn)的雙親為NULL，若未找到這樣的結(jié)點(diǎn)，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;}

【評(píng)分說(shuō)明】本題有多種解法，相應(yīng)給分。

題4 1.用單鏈表來(lái)存儲(chǔ)集合，并假設(shè)這樣的單鏈表中的節(jié)點(diǎn)遞增有序，設(shè)計(jì)一個(gè)盡可能高效的算法求兩個(gè)集合A和B的并集C。設(shè)A、B中分別有m和n個(gè)元素，分析你設(shè)計(jì)的算法的時(shí)間和空間復(fù)雜度。（15分）

解：由于單鏈表是遞增有序的，可以采用歸并算法提高求并集的效率，結(jié)果并集C采用尾插法建表。對(duì)應(yīng)算法如下：

void Unionset(LinkList *A,LinkList *B,LinkList *&C){LinkList *pa=A->next,*pb=B->next,*s,*r;C=(LinkList *)malloc(sizeof(LinkList));//建立C的頭節(jié)點(diǎn)r=C;//r始終指向單鏈表C的尾節(jié)點(diǎn)while (pa!=NULL && pb!=NULL){if (pa->datadata)//僅復(fù)制*pa節(jié)點(diǎn){s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;}else if (pa->data>pb->data)//僅復(fù)制*pb節(jié)點(diǎn){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)//復(fù)制A單鏈表的余下節(jié)點(diǎn){s=(LinkList *)malloc(sizeof(LinkList));s->data=pa->data;r->next=s; r=s;pa=pa->next;}while (pb!=NULL)//復(fù)制B單鏈表的余下節(jié)點(diǎn){s=(LinkList *)malloc(sizeof(LinkList));s->data=pb->data;r->next=s; r=s;pb=pb->next;}r->next=NULL;}

本算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(m+n)，其中m、n分別為A、B單鏈表中的節(jié)點(diǎn)個(gè)數(shù)。 評(píng)分：算法占11分，時(shí)間和空間復(fù)雜度各占2分。

2.假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，假設(shè)每個(gè)節(jié)點(diǎn)值為單個(gè)字符且所有節(jié)點(diǎn)值不同，設(shè)計(jì)一個(gè)算法，輸出二叉樹(shù)b中第k的所有節(jié)點(diǎn)值，并分析你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。（15分） 2. 解：采用先序序列，對(duì)應(yīng)的算法如下：

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);}}

評(píng)分：采用先序、中序、后序和層次遍歷均可，算法占13分，時(shí)間復(fù)雜度占2分。

說(shuō)明：以上兩題求算法的時(shí)間和空間復(fù)雜度只需給出結(jié)果，不必給出詳細(xì)步驟。

圖的鄰接表是一種圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，請(qǐng)給出鄰接表的完整類(lèi)型定義。采用你所設(shè)計(jì)的鄰接表作為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法，求出無(wú)向圖G的連通分量個(gè)數(shù)。（10分）

3. 解：鄰接表的類(lèi)型定義如下：typedef char ElemType;typedef int InfoType;typedef struct ANode//邊的節(jié)點(diǎn)結(jié)構(gòu)類(lèi)型{int adjvex;//該邊的終點(diǎn)位置struct ANode *nextarc;//指向下一條邊的指針I(yè)nfoType info;//該邊的相關(guān)信息，對(duì)于帶權(quán)圖可存放權(quán)值} ArcNode;typedef struct Vnode//鄰接表頭節(jié)點(diǎn)的類(lèi)型{ElemType data;//頂點(diǎn)信息ArcNode *firstarc;//指向第一條邊} VNode;typedef VNode AdjList[MAXV];//AdjList是鄰接表類(lèi)型typedef struct{AdjList adjlist;//鄰接表int n,e;//分別為圖中頂點(diǎn)數(shù)和邊數(shù)} AGraph;//聲明圖的鄰接表類(lèi)型采用遍歷方式求無(wú)向圖G中連通分量個(gè)數(shù)。基于深度優(yōu)先遍歷的算法如下：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);//對(duì)圖G從頂點(diǎn)i開(kāi)始進(jìn)行深度優(yōu)先遍歷n++;//調(diào)用DFS的次數(shù)即為連通分量數(shù)}return n;}基于廣度優(yōu)先遍歷的算法如下：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);//對(duì)圖G從頂點(diǎn)i開(kāi)始進(jìn)行廣度優(yōu)先遍歷n++;//調(diào)用BFS的次數(shù)即為連通分量數(shù)}return n;}

評(píng)分：鄰接表的類(lèi)型定義占5分，求無(wú)向圖G的連通分量個(gè)數(shù)的算法占5分。

第五套題

（10分）某帶頭結(jié)點(diǎn)的非空單鏈表L中所有元素為整數(shù)，結(jié)點(diǎn)類(lèi)型定義如下：

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

設(shè)計(jì)一個(gè)盡可能高效的算法，將所有小于零的結(jié)點(diǎn)移到所有大于等于零的結(jié)點(diǎn)的前面。

（10分）答案：

void Move(LinkNode *&L){LinkNode *p=L->next,*pre=L;     while (p!=NULL && p->data<0)//跳過(guò)小于0的結(jié)點(diǎn)     {pre=p;p=pre->next;     }while (p!=NULL){if (p->data<0)//若*p結(jié)點(diǎn)值小于0{pre->next=p->next;//從鏈表中刪除*p結(jié)點(diǎn)p->next=L->next;//將*p結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后L->next=p;p=pre->next;//p指向*pre之后結(jié)點(diǎn)，pre不變}else//若*p結(jié)點(diǎn)值不小于0{pre=p;//pre、p同步后移一個(gè)結(jié)點(diǎn)p=p->next;}}}

（15分）假設(shè)二叉樹(shù)中有n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)值為單個(gè)字符，而且所有結(jié)點(diǎn)值均不相同，采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，其結(jié)點(diǎn)類(lèi)型定義如下：

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

請(qǐng)完成以下任務(wù)： （1）設(shè)計(jì)一個(gè)算法，在二叉樹(shù)b中查找x結(jié)點(diǎn)（指結(jié)點(diǎn)值為x的結(jié)點(diǎn)），若找到該結(jié)點(diǎn)，返回其地址，否則返回NULL。給出你設(shè)計(jì)的算法的時(shí)間復(fù)雜度。（8分） （2）設(shè)計(jì)一個(gè)算法，利用（1）小題設(shè)計(jì)的算法輸出二叉樹(shù)b中x結(jié)點(diǎn)的所有子孫結(jié)點(diǎn)值。（7分） 2. （15分）答案： （1）（7分）

BTNode *Findx(BTNode *b,char x)//在二叉樹(shù)b中查找x結(jié)點(diǎn){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);}}

算法的時(shí)間復(fù)雜度為O(n)（1分）。 （2）（7分）

void Sons(BTNode *b,char x)//輸出x結(jié)點(diǎn)的子孫，初始時(shí)b指向x結(jié)點(diǎn){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)//輸出二叉樹(shù)b中x結(jié)點(diǎn)的所有子孫結(jié)點(diǎn)值{BNode *p= Findx(b,x);if (p!=NULL)Sons(p,x);}

題6

1.設(shè)計(jì)一個(gè)算法delminnode(LinkList *&L)，在帶頭結(jié)點(diǎn)的單鏈表L中刪除所有結(jié)點(diǎn)值最小的結(jié)點(diǎn)（可能有多個(gè)結(jié)點(diǎn)值最小的結(jié)點(diǎn)）。

解：用p從頭至尾掃描單鏈表，pre指向p結(jié)點(diǎn)的前驅(qū)，用minp保存值最小的結(jié)點(diǎn)指針，minpre指向minp結(jié)點(diǎn)的前驅(qū)。一面掃描，一面比較，將最小值的結(jié)點(diǎn)放到*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;}}

評(píng)分標(biāo)準(zhǔn)：根據(jù)算法的正確性評(píng)分，不考慮算法的時(shí)間復(fù)雜度。

2.假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，設(shè)計(jì)一個(gè)算法copy(BTNode *b,BTNode *&t)，由二叉樹(shù)b復(fù)制成另一棵二叉樹(shù)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;}}

評(píng)分標(biāo)準(zhǔn)：根據(jù)算法的正確性評(píng)分，不考慮算法的時(shí)間復(fù)雜度。

假設(shè)一個(gè)無(wú)向圖是非連通的，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，輸出圖中各連通分量的節(jié)點(diǎn)序列。解：采用深度優(yōu)先搜索遍歷非連通圖，并輸出各連通分量節(jié)點(diǎn)序列的算法如下：

DFSGraph(AGraph *G){int i,j=1;//用j記錄連通分量的序號(hào)for (i=0;in;i++)if (visited[i]==0){printf("第%d個(gè)連通分量節(jié)點(diǎn)序列:",j++);DFS(G,i);//調(diào)用深度優(yōu)先遍歷算法}}

題9

（15分）有兩個(gè)遞增有序表，所有元素為整數(shù)，均采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，結(jié)點(diǎn)類(lèi)型定義如下：

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

設(shè)計(jì)一個(gè)盡可能高效的算法，將兩個(gè)遞增有序單鏈表ha、hb合并為一個(gè)遞減有序單鏈表hc，要求算法空間復(fù)雜度為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的頭結(jié)點(diǎn)，并設(shè)置為空while (pa!=NULL && pb!=NULL)//掃描ha、hb的數(shù)據(jù)結(jié)點(diǎn){if (pa->datadata)//將較小結(jié)點(diǎn)采用頭插法插入到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)//將沒(méi)有掃描完的結(jié)點(diǎn)采用頭插法插入到hc中{q=pa->next;pa->next=hc->next;hc->next=pa;pa=q;}}

評(píng)分說(shuō)明：上述算法的時(shí)間復(fù)雜度為O(m+n)。若設(shè)計(jì)的算法時(shí)間復(fù)雜度為O(m*n)，至少扣3分，若設(shè)計(jì)的算法空間復(fù)雜度不為O(1)，扣2分。

2、（10分）設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)存放單個(gè)字符，其結(jié)點(diǎn)類(lèi)型如下：

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

設(shè)計(jì)一個(gè)算法求其中單分支的結(jié)點(diǎn)個(gè)數(shù)。 2、（10分）參考算法如下：

int singleodes(BTNode *b){if (b==NULL) return 0;     if ((b->lchild==NULL && b->rchild!=NULL) ||//單分支的結(jié)點(diǎn)(b->lchild!=NULL && b->rchild==NULL)return singleodes(b->lchild)+ singleodes(b->rchild)+1;elsereturn singleodes(b->lchild)+ singleodes(b->rchild);）

評(píng)分說(shuō)明：可以采用任意一種遍歷方法。判斷單分支的結(jié)點(diǎn)為3分。