數據結構試題有哪些？數據結構試題及評分解析

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分。