數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

習(xí)題參考答案習(xí)題1名稱解釋（1）數(shù)據(jù)是信息載體，是對客觀事物符號表示。通俗說，凡是能被計算機識別、存取和加工處理符號、字符、圖形、圖象、聲音、視頻信號等一切信息都能夠稱為數(shù)據(jù)。（2）數(shù)據(jù)結(jié)構(gòu)是相互之間存在一個或多個特定關(guān)系數(shù)據(jù)元素集合。簡言之，數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間關(guān)系，即數(shù)據(jù)組織形式。（3）數(shù)據(jù)元素之間邏輯關(guān)系，稱為數(shù)據(jù)邏輯結(jié)構(gòu)。（4）數(shù)據(jù)元素及其關(guān)系在計算機存放器內(nèi)表示，稱為數(shù)據(jù)存放結(jié)構(gòu)。（5）線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在“一對一”關(guān)系邏輯結(jié)構(gòu)。（6）非線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在“一對一”或“一對多”關(guān)系邏輯結(jié)構(gòu)。（除了線性結(jié)構(gòu)以外樹形結(jié)構(gòu)和圖形結(jié)構(gòu)等統(tǒng)稱為非線性結(jié)構(gòu)）。判斷題（正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）√ （2）ㄨ（3）√（4）ㄨ（5）√ （6）√填空題（1）集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu) 非線性結(jié)構(gòu)（2）次序存放 鏈式存放 索引存放 散列存放（3）一對一 一對多 多對多（4）沒有 一 沒有 多個（5）任意多個 任意多個（6）有窮性 確定性 可行性 輸入 輸出（7）操作對象 關(guān)系（8）數(shù)據(jù)元素 關(guān)系（9）邏輯結(jié)構(gòu) 存放結(jié)構(gòu) 算法（10）有窮指令 事先估算法 事后統(tǒng)計法選擇題（1）A（2）C（3）C（4）D（5）D（6）B（7）A（8）B五．試分析以下程序段時間復(fù)雜度（1）O(n*m) （2）O(n) （3）O(n2)（4）O(sqrt(n)) （5）O(n)（6）O(n2)六．二元關(guān)系表示數(shù)據(jù)結(jié)構(gòu)以下，分別畫出對應(yīng)邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。集合abcde線性結(jié)構(gòu)AABCEFD（3）圖結(jié)構(gòu)126126345（4）樹結(jié)構(gòu)25402540705782366864以后，凡不會對根結(jié)點引發(fā)誤解情況下，樹形結(jié)構(gòu)結(jié)點之間關(guān)系通常不用帶箭頭線，而直接用直線畫。習(xí)題2名詞解釋（1）線性表——線性表是具備相同數(shù)據(jù)類型n（n>=0）個數(shù)據(jù)元素有限序列。其邏輯特征反應(yīng)了結(jié)點間一對一關(guān)系，是一個線性結(jié)構(gòu)。（2）次序表——用一組地址連續(xù)存放單元依次次序存放線性表數(shù)據(jù)元素（相鄰結(jié)點存放在相鄰物理位置），稱為次序表。它是一個隨機存取結(jié)構(gòu)，能夠經(jīng)過公式來計算結(jié)點存取地址。（3）單鏈表——單鏈表每個結(jié)點都有兩個域，一個數(shù)據(jù)域和一個指針域，稱之為單鏈表。（4）雙鏈表——以鏈表形式存放線性表，其結(jié)點包含一個數(shù)據(jù)域和兩個指針域，稱之為雙鏈表。（5）循環(huán)鏈表——若線性鏈表最終一個結(jié)點指針指向頭結(jié)點，使得鏈表頭尾結(jié)點相連，就組成了循環(huán)鏈表。（6）存放密度——存放密度定義為結(jié)點數(shù)據(jù)本身所占存放量與結(jié)點結(jié)構(gòu)實際分配存放量比值。次序表存放密度等于1；鏈表結(jié)構(gòu)存放密度小于1。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）ㄨ （2）ㄨ （3）√ （4）ㄨ （5）ㄨ（6）√ （7）ㄨ （8）ㄨ （9）√ （10）√三．填空題1．一定2．無須3．有限 一對一關(guān)系4．節(jié)約存放 隨機存取5．插入 刪除 小6．n/2 表長n和插入位置7．（n-1）/2 表長n和刪除位置8．O(1)9．直接前驅(qū)10．直接前趨結(jié)點地址 O(n)11．O(1)12．*P直接前驅(qū)結(jié)點地址 O(n) O(1)13．頭指針選擇題(1)B (2)A (3)B (4)C (5)A (6)A (7)B (8)B (9)D (10)B五．簡答題1．次序存放結(jié)構(gòu)優(yōu)點是節(jié)約存放空間，能夠隨機存取。（缺點是插入、刪除要作大量移動，不易擴充）；鏈表存放結(jié)構(gòu)優(yōu)點是插入、刪除操作輕易，表擴充方便。（缺點是存放密度低）。2．頭指針——指向鏈表中第一個結(jié)點（頭結(jié)點或無頭結(jié)點時開始結(jié)點）指針。頭結(jié)點——在開始結(jié)點之前附加一個結(jié)點。開始結(jié)點——在鏈表中，存放第一個數(shù)據(jù)元素結(jié)點。3．主要是簡化操作。因為表操作常在表兩端進行，所以對單循環(huán)鏈表，當(dāng)知道其尾指針rear后，其另一端頭指針是rear->next->next（表中代頭結(jié)點），僅改變兩個指針值即可，運算時間為O(1)。六．（1）返回結(jié)點*p直接前趨結(jié)點地址。（2）交換結(jié)點*p和結(jié)點*q（p和q值不變）。七．程序設(shè)計題1．解：voidShow(ListNode*P){ ListNode*t=P; do { printf("%c",t->data); t=t->rear; } while(t!=P);}2．解：voiddelete(ListNode*L){ ListNode*p=L,*q; if(L->next->data==X) { printf(“值為x結(jié)點是第一個結(jié)點，沒有直接前趨結(jié)點能夠刪除”); return; } for(;p->next->data!=X;q=p,p=p->next); //刪除指針p所指向結(jié)點 q->next=p->next; deletep;}3．解voidDel(SeqList*L,inti,intk){ intj=i-1+k; for(j=0;j<k;j++) { L->data[i-1+j]=L->data[i+k-2+j]; if(i+k-2+j>L->last) break; }}4．解：本題是遍歷該鏈表每個結(jié)點，每碰到一個結(jié)點，結(jié)點個數(shù)加1，結(jié)點個數(shù)存放在變量n中。實現(xiàn)本題功效函數(shù)以下：intcounter(head)node*head；{node*p;intn＝0;p=head；while(p!=NULL){if(p->data==x)n++；p=p->next;}return(n);}5．解：本題算法思想是：先找到兩鏈表尾指針，將第一個鏈表尾指針與第二個鏈表頭結(jié)點鏈接起來，使之成為循環(huán)。函數(shù)以下：node*link(head1,head2)node*head1,*head2;{node*p,*q;p=head1;while(p->next!=head1)p=p->next;q=head2;while(q->next!=head2)q=q->next;p->next=head2;q->next=head1;return(head1);}6．解：假設(shè)輸入一組多項式系數(shù)和指數(shù)，以輸入系數(shù)為標志結(jié)束，在建立多項式鏈表時，總是按照指數(shù)從大到小次序排列。兩個多項式鏈表A和B，其頭指針分別是heada和headb，這兩個多項多項式鏈表為C，其頭指針為headc。實現(xiàn)本題功效函數(shù)以下：structpnode*padd(heada，headb)structpnode*heada,*headb；{structpnode*headc,*p,*q,*s;intx;p=heada;q=headb;headc＝(structpnode*)malloc(sizeof(structpndoe));r=headc;while(p!=NULL&&q!=NULL){if(p->exp==q->exp)//兩結(jié)點指數(shù)相等時，將兩系數(shù)相加生成新結(jié)點插入C中{x=p->coef+q->coef;if(x!=0){s＝(structpnode*)malloc(sizeof(structpnode));s->coef＝s;s->exp=p->exp;r->link＝s;r=s;}p=p->link;q=q->link;}else//兩結(jié)點指數(shù)不相等時，將其中較小系數(shù)結(jié)點復(fù)制成一新結(jié)點插入C中if(p->exp<q->exp){s=(structpnode*)malloc(sizeof(structpnode));s->coef=q->coef;s->exp=q->exp;r->link=s;r=s;q=q->link;}else{s＝(structpnode*)malloc(sizeof(structpnode));s->coef=p->coef;s->exp=p->exp;r->link=s;r=s;p=p->link;}}while(p!=NULL)//復(fù)制A余下部分{s=(structpnode*)malloc(sizeof(structpnode));//復(fù)制一個結(jié)點ss->coef=p->coef;s->exp=p->exp;r->link=s;//把s鏈接到C中r=s;p=p->link;}while(q!=NULL)//復(fù)制B余下部分{s=(structpnode*)malloc(sizeof(structpnode));//復(fù)制一個結(jié)點ss->coef=q->coef;s->exp=q->exp;r->link=s;//把s鏈接到C中r=s;q=q->link;}r->link=NULL;//最終結(jié)點link域置空s=headc;//刪除C頭結(jié)點headc=headc->link;free(s);return(headc);}習(xí)題3一.名詞解釋（1）棧只允許在一端進行插入或刪除操作線性表稱為棧。其最大特點是“后進先出”。（2）次序棧采取次序存放結(jié)構(gòu)棧稱為次序棧。（3）鏈棧采取鏈式存放結(jié)構(gòu)棧稱為鏈棧。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）√ （2）√ （3）ㄨ （4）ㄨ （5）ㄨ （6）ㄨ三.填空題（1）后進先出（2）棧頂 棧底（3）棧空 棧滿（4）O（1） O（1）（5）必須一致（6）棧（7）?？眨?）p->next=top top=p（9）-- ++（10）LS->next 首四.單項選擇題（1）B （2）C （3）A （4）D （5）B（6）C （7）D （8）B （9）A （10）A五.求以下表示式后綴表示式（要求寫出過程）（1）AB^C^D/（2）0A–BC*+DE/+（3）ABC+*D*E-（4）AB+C*EFGH/+/-D-（5）852+/6-六．算法設(shè)計題1．解：用一整型變量top表示棧頂指針，top為0時表示棧為空。棧中元素從S[1]開始存放元素。（1）入棧算法：voidpush(charx){if((top+M)>MAXLEN-1)printf(“堆棧溢出！”);else{if(top==0){top++;S[top]=x;}else{top=top+M;S[top]=x;}}}（2）出棧算法：voidpop(charx){if(top==0)printf(“堆棧為空棧！”);else{if(top==1){x=S[top];top––;}else{x=S[top];top=top–M;}}}2．解：設(shè)表示式在字符數(shù)組a[]中，使用一堆棧S來幫助判斷。intcorrect(chara[]){stacks;InitStack(s); //調(diào)用初始化棧函數(shù)for(i=0;i<strlen(a);i++)if(a[i]==’(’)Push(s,’(’);elseif(a[i]==’)’){ifStackEmpty(s) //調(diào)用判?？蘸瘮?shù)return0; //若棧為空返回0；不然出棧elsePop(s);}if(StackEmpty(s)) //調(diào)用判棧空函數(shù)printf(“配對正確！”); //若棧空，說明配對正確，并返回1elseprintf(“配對錯誤！”); //配對錯誤返回0}

習(xí)題4一.名詞解釋（1）隊列只允許在一端進行插入，另一端進行刪除操作線性表稱為隊列。其最大特點是“先進先出”。（2）次序隊列采取次序存放結(jié)構(gòu)隊列稱為次序隊列。（3）鏈隊列采取鏈式存放結(jié)構(gòu)稱隊列為鏈隊列。（4）循環(huán)隊列為了處理次序隊列中“假溢出”現(xiàn)象，將隊列存放空間想象為一個首尾相鏈環(huán)（即把隊頭元素與對尾元素鏈結(jié)起來），存放在其中隊列稱為循環(huán)隊列。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）√ （2）√ （3）ㄨ （4）√ （5）ㄨ （6）ㄨ三．填空題1．先進先出2．隊尾 隊頭3．隊列是否為空 隊列是否為滿4．可變5．-1 NULL6．O(n) O(1) O(1) O(1)7．front==rear front==(rear+1)%MAXLEN MAXLEN-front8．空 只含有一個結(jié)點9．front==rear&&front<>NULL10．隊尾指針 寫入四、單項選擇題（1）A （2）C （3）A （4）D （5）A（6）A （7）B （8）A （9）C （10）A五．簡答題答：n個（同類）數(shù)據(jù)元素有限序列稱為線性表。線性表特點是數(shù)據(jù)元素之間存在“一對一”關(guān)系。棧和隊列都是操作受限制線性表，它們和線性表一樣，數(shù)據(jù)元素之間都存在“一對一”關(guān)系。不一樣之處是：棧是只允許在一端進行插入或刪除操作線性表，其最大特點是“后進先出”；隊列是只允許在一端進行插入，另一端進行刪除操作線性表，其最大特點是“先進先出”。六．算法設(shè)計題解：用一個循環(huán)數(shù)組Queue[0，n-1]表示該循環(huán)隊列，頭指針為front，計數(shù)器count用來統(tǒng)計隊列中結(jié)點個數(shù)。（1）入隊算法：voidinqueqe(intx){inttemp;if(count==n)printf(“隊列上溢出\n”);else{count++temp=(front+count)%n;Queue[temp]=x}}（2）出隊算法：intoutqueue(){inttemp;if(count==0)printf(“隊列下溢出\n”);else{temp=Queue[front];front=(front+1)%n;count--;returntemp;}}2．解：隊列為空：count==0,front==1隊列為滿：count=MAXLEN隊列尾第一個元素位置==(front+count)%MAXLEN隊列首第一個元素位置==(front+1)%MAXLENconstMAXLEN=100;intqueue[MAXLEN];intfront,count; //定義隊頭和計算器voidinit() //初始化隊列{front=1;count=0;}intempty() //判定隊列是否為空{(diào)if(count==0)return(1);elsereturn(0);}voidoutqueue(intqueue[],x) //取隊列頭元素給x{if(count==0)printf(“下溢出\n”);else{front=(front+1)%MAXLEN;x=queue[front];}}voidinqueue(intqueue[],intx) //x入隊列{intplace;if(count==MAXLEN)printf(“上溢出\n”);else{count++;place=(front+count)%MAXLEN;queue[MAXLEN]=x;}}voidoutqueue(intqueue[]) //刪除隊列頭元素{if(count==0)printf(“隊列下溢出\n”);else{front=(front+1)%MAXLEN;count--;}}（1）解：定義本題隊列結(jié)點類型以下：typedefstructlinknode{intdata;structlinknode*next;}qu;qu*rear;inqueue(intx) //向隊列插入結(jié)點x{qu*head,*s;s=(qu*)malloc(size(qu));//創(chuàng)建一個新結(jié)點s->data=x;if(rear＝＝NUlL)//循環(huán)隊列為空，則建立一個結(jié)點循環(huán)隊列{rear＝s;rear->next＝s;}else //循環(huán)隊列不為空，則將s插到后面{head=rear->next；rear->next＝s;rear=s;//rear一直指向最終一個結(jié)點rear->next＝head;}}(2)解：voiddelqueue(rear){if(rear==NULL)printf(“下溢出!\n”);else{head=rear->next; //head指向隊首結(jié)點if(head==rear)rear=NULL //只有—個結(jié)點，則直接刪除該結(jié)點elserear->next=head->next //不然刪除第一個結(jié)點free(head)； //釋放隊首結(jié)點}}

習(xí)題5一．名詞解釋串：串（string）是由零個或多個字符組成有限序列。通常記為S＝“a1a2...an”（n≥其中，S是串名，用雙引號或單引號括起來字符序列是串值，ai（1≤i≤n）稱為串元素，它能夠是字母、數(shù)字、空格或其余字符。串中字符個數(shù)n稱為串長度。廣義表：廣義表（GeneralizedLists）是n（n≥0）個數(shù)據(jù)元素a1,a2,…，ai…，an有序序列，通常記作：ls=（a1，a2,…，ai,…，an）其中：ls是廣義表名稱，n是它長度。每個ai（1≤i≤n）是ls組員，它能夠是單個元素，稱為廣義表ls原子，也能夠是一個廣義表，稱為廣義表子表。當(dāng)廣義表ls非空時，稱第一個元素a1為ls表頭（head），稱其余元素組成表（a2,…,ai,…，an）為ls表尾(tail)。廣義表定義是遞歸。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）ㄨ（2）√（3）ㄨ（4）ㄨ（5）√（6）√（7）ㄨ（8）√（9）ㄨ（10）√三．填空題(10個)1．長度2．空串零3．次序存放4．?dāng)?shù)據(jù)指針數(shù)據(jù)指針5．模式匹配6．次序存放和鏈式存放7．（a）(((b),c),(((d))))8．廣義表四．選擇題1．B2．D3．B4．C5．C6．A7．B8．A五．簡答題1．簡述串存放結(jié)構(gòu)及各自特點。串存放方式有主要有次序存放、堆分配存放和鏈式存放。次序結(jié)構(gòu)：用一組地址連續(xù)存放單元存放串字符序列，組成串次序存放，簡稱為次序串。特點：這種結(jié)構(gòu)是按照預(yù)設(shè)大小，為每個定義串變量分配一個固定長度存放區(qū)。所以存在存放空間越界或浪費問題。對于操作如查找不過操作簡單方便。堆分配存放結(jié)構(gòu)：在內(nèi)存中開辟地址連續(xù)存放空間作為串可利用存放空間，稱為堆空間，依照每個串長度，動態(tài)地為每個串在堆空間里申請對應(yīng)大小存放區(qū)域一個存放結(jié)構(gòu)。特點：以一組地址連續(xù)存放單元存放串字符序列，但其存放空間是在算法執(zhí)行過程中動態(tài)分配得到，串也是次序存放在所申請存放區(qū)域中。因為堆分配存放結(jié)構(gòu)串現(xiàn)有次序存放結(jié)構(gòu)特點，又沒有造成對存放空間浪費和對串長加以限制，使用非常靈活。鏈式存放結(jié)構(gòu)：是將存放區(qū)域分成一系列大小相同結(jié)點，每個結(jié)點有兩個域即數(shù)據(jù)域data和指針域next。其中數(shù)據(jù)域用于存放字符串元素，指針域用于存放下一個結(jié)點地址。特點：在串中使用鏈式存放結(jié)構(gòu)一樣是在插入、刪除等操作中沒有移動元素所帶來時間花費，存放空間擴展輕易；但結(jié)點容量會帶來存放空間利用率降低。2．廣義表具備哪些性質(zhì)？(1)廣義表是一個多層次數(shù)據(jù)結(jié)構(gòu)。廣義表元素能夠是原子，也能夠是子表，而子表元素還能夠是子表。(2)廣義表能夠是遞歸表。廣義表定義并沒有限制元素遞歸，即廣義表也能夠是其本身子表。比如表E就是一個遞歸表。(3)廣義表能夠為其余表所共享。比如D=（A,B,C）時，表A、B、C是表D共享子表。在D中能夠無須列出子表值，而用子表名稱來引用。六．下述算法功效是什么（1）實現(xiàn)串S和串T連接運算。（2）返回串S中從第n1個字符開始取n2個字符組成子串。七．程序設(shè)計題1．寫一個遞歸算法來實現(xiàn)字符逆序存放，要求不另設(shè)存放空間。#include"stdio.h"#includeMAXSIZE80charnext[MAXSIZE80];/*串最大長度*/voidreverse(intn)/*遞歸函數(shù)實現(xiàn)逆置*/{if(n<=1){next[n]=getchar();putchar(next[n]);}else{next[n]=getchar();reverse(n-1);putchar(next[n]);}}main(){inti;printf("請輸入字符串長度值!\n");scanf("%d",&i);getchar();palin(i);/*調(diào)用逆置函數(shù)*/printf("\n");}2．編寫算法實現(xiàn)將串S中第i個字符到第j個字符之間字符（不包含第i個字符和第j個字符）用串T替換。#include<stdio.h>#defineMAXSIZE80typedefstruct{charch[MAXSIZE];intlen;}SEQSTRING;SEQSTRINGS,T,S1;voidreplace(SEQSTRINGS,inti,intj,SEQSTRINGT)/*替換操作函數(shù)*/{SEQSTRINGS1;inth,k;if(i<S.len&&j<S.len)/*把i前字符存入結(jié)果串中*/{for(h=0;h<i;h++)S1.ch[h]=S.ch[h];S1.len=i;h=0;while(h<T.len)/*把替換串聯(lián)接入結(jié)果串*/{S1.ch[S1.len+h]=T.ch[h];h++;}S1.len=S1.len+T.len;h=j;for(k=S1.len;h<=S.len;k++,h++)/*把j后串接入結(jié)果串中*/S1.ch[k]=S.ch[h-1];S1.len=k;/*修改字符串總長度*/S1.ch[S1.len]='\0';puts(S.ch);puts(T.ch);puts(S1.ch);}elseprintf("error\n");return;}main(){inti,j;S.len=0;T.len=0;S1.len=0;printf("請輸入串S和T！\n");gets(S.ch);gets(T.ch);for(i=0;S.ch[i]!='\0';i++)/*計量串S長度*/S.len++;for(i=0;T.ch[i]!='\0';i++)/*計量串T長度*/T.len++;printf("請輸入替換字符位置序號i和j:");scanf("%d,%d",&i,&j);getchar();replace(S,i,j,T);/*調(diào)用替換函數(shù)*/}3．一個僅由字母組成字符串S，長度為n，其結(jié)構(gòu)為單鏈表，每個結(jié)點數(shù)據(jù)域只存放一個字母。設(shè)計一個算法，去掉字符串中全部值為x字母。#include<stdio.h>#include<malloc.h>#defineNULL0typedefstructCHUNK{chardata;structCHUNK*next;}LinkList;voiddelx(LinkList*s,charx)/*從串s中刪除全部取值為x函數(shù)*/{LinkList*p,*q,*r;intw;p=s;w=1;/*是否第一個節(jié)點標志位*/while(p->next!=NULL){if(w==1)/*處理第一個節(jié)點*/if(p->data==x)/*假如第一個節(jié)點取值為x*/{s=p->next;free(p);p=s;}else/*假如第一個節(jié)點取值不是x*/{q=p;p=p->next;w=0;}else/*處理其它節(jié)點*/{if(p->data==x)/*刪除值為x節(jié)點*/{q->next=p->next;free(p);p=q->next;}else{q=p;p=p->next;}}}p=s;printf("\n處理結(jié)果為:\n");/*輸出結(jié)果方便觀察*/while(p->next!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}main()/*主函數(shù)*/{inti,j;charch,x;LinkList*s,*p,*r;p=malloc(sizeof(LinkList));/*申請鏈頭結(jié)點*/p->data='';p->next=NULL;s=p;/*存放結(jié)果指針變量指向它*/ch='';j=0;printf("請輸入字符串中元素值,以’#’號結(jié)束輸入!\n");while(ch!='#'){scanf("%c",&ch);getchar();r=malloc(sizeof(LinkList));/*為輸入字符申請存放空間并由r指向它*/r->data=ch;/*在新空間中存入信息*/r->next=NULL;p->next=r;p=r;j++;/*字符串長度是否為空標志，j不為0表示非空串*/}p=s;while(p->next!=NULL)/*輸出原串結(jié)果方便觀察*/{printf("%c",p->data);p=p->next;}if(j>1)/*假如串值不為空，調(diào)用刪除字符處理函數(shù)*/{printf("inputx");scanf("%c",&x);printf("\n");delx(s,x);/*以串s和字符x值調(diào)用刪除字符處理函數(shù)*/}}4．編寫算法，求串S中所含不一樣字符總數(shù)和每種字符個數(shù)。#include<stdio.h>#defineMAXSIZE80typedefstruct{charch[MAXSIZE];intlen;}SEQSTRING;SEQSTRINGS,T;SEQSTRINGInputStr()/*輸入字符串函數(shù)*/{inti;T.len=0;printf("請輸入字符串:\n");gets(T.ch);for(i=0;T.ch[i]!='\0';i++)T.len++;returnT;}main(){charz[10];inti=0,j=0,m=0,l;intn=0;intr[10]={0};/*存放重復(fù)字符個數(shù)*/intlog[10]={0};/*存放重復(fù)字符標志*/S.len=0;S=InputStr();/*輸入字符*/l=S.len;while(i<l){if(!log[i])/*假如不是重復(fù)字符*/{r[m]=1;/*計算賦值*/z[m]=S.ch[i];/*在工作數(shù)組中統(tǒng)計第一次出現(xiàn)字符*/j=i+1;while(j<l)/*檢測之后重復(fù)字符個數(shù),并置位標志數(shù)組*/{if(z[m]==S.ch[j]) {r[m]++;/*重復(fù)計數(shù)*/ log[j]=1;/*置標志位*/ } j++;}i++;m++;}else{i++;}}for(i=0;i<m;i++)/*輸出全部字符種類*/printf("%c",z[i]);printf("\n");for(i=0;i<m;i++)/*輸出每種字符個數(shù)*/printf("%d",r[i]);printf("\n");printf("字符總數(shù)為:%d",l)}5．有兩個串S1和S2，設(shè)計一個算法，求一個串T，使其中字符是S1和S2中公共字符。#include<stdio.h>#include<string.h>#defineMAXSIZE80typedefstruct{charch[MAXSIZE];intlen;}SEQSTRING;voidpubstr(SEQSTRINGstr1,SEQSTRINGstr2){inti,j,k,p;SEQSTRINGt;//合并后字符串t.len=0;//以下雙層for循環(huán)功效：查找s1,s2中公共字符，并將公共字符依次放入串t中for(i=0;i<str1.len;i++)for(j=0;j<str2.len;j++){if(str1.ch[i]==str2.ch[j]) {t.len++; t.ch[t.len-1]=str1.ch[i]; }}//因合并串t中可能有重復(fù)出現(xiàn)字符值，將重復(fù)字符刪除，同一字符只留一個for(i=0;i<t.len;i++){//k=i+1;for(k=i+1;k<t.len;k++) {if(t.ch[i]==t.ch[k]) {for(j=k;j<t.len;j++) t.ch[j]=t.ch[j+1]; p=t.len-1; t.ch[p]='\0'; } }}printf("Thepubstringtis:%s!\n",t.ch);//輸出最終合并串t值}voidmain(){SEQSTRINGs1,s2;printf("Pleaseenters1:");scanf("%s",s1.ch);printf("Pleaseenters2:");scanf("%s",s2.ch);s1.len=strlen(s1.ch);//strlen直接使用了求字符數(shù)組長度函數(shù)s2.len=strlen(s2.ch);//strlen直接使用了求字符數(shù)組長度函數(shù)pubstr(s1,s2);}習(xí)題6名詞解釋（1）結(jié)點——樹結(jié)點包含一個數(shù)據(jù)及若干指向其子樹分支。（2）結(jié)點度——結(jié)點所擁有子樹數(shù)稱為該結(jié)點度。（3）樹度——樹中各結(jié)點度最大值稱為該樹度。（4）二叉樹——一棵非空二叉樹，每個結(jié)點至多只有兩棵子樹，分別稱為左子樹和右子樹，左、右子樹次序不能任意交換，且左右子樹又分別是一棵二叉樹。（5）哈夫曼樹——帶權(quán)路徑長度最小二叉樹，即最優(yōu)二叉樹，也稱為哈夫曼樹。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）√ （2）ㄨ （3）√ （4）ㄨ （5）√ （6）√ （7）ㄨ （8）ㄨ （9）ㄨ （10）√三．填空題1．結(jié)點擁有子樹數(shù)2．度為零3.樹內(nèi)各結(jié)點度最大值4．深度（或高度）5．2i-16．2h-17.n-18．69．中序10．511．2012.13．次序存放結(jié)構(gòu)和鏈式存放結(jié)構(gòu)14．最小15．EBCAD16．ABEFHCG17．EBHFACG18．EHFBGCA19．空二叉樹20．4四．選擇題（1）B （2）C （3）C （4）C （5）D（6）B （7）B （8）A （9）B （10）D（11）D （12）B （13）A （14）C （15）A五．簡答題1．答：通常樹（非空）除了根結(jié)點之外，每個結(jié)點有且僅有一個前驅(qū)結(jié)點，但每個結(jié)點都能夠有多個互不相交子集（后繼結(jié)點）。二叉樹（若非空）除了根結(jié)點之外，每個結(jié)點有且僅有一個前驅(qū)結(jié)點，但每個結(jié)點至多只有兩個后繼結(jié)點，稱為左子樹和右子樹，左、右子樹次序不能交換，且左右子樹又分別都是二叉樹。通常樹和二叉樹主要有以下區(qū)分：二叉樹結(jié)點度最大為2，而通常樹結(jié)點最大度數(shù)無限制；通常樹結(jié)點無左、右之分，而二叉樹結(jié)點有左、右之分。2．答：一棵度為2樹與一棵二叉樹區(qū)分在于：對于度為1結(jié)點，度為2樹無須區(qū)分左右；對于二叉樹必須有左右之分，且不能任意交換。3．答：（1）A是根結(jié)點。（2）葉結(jié)點：M，N，D，J，K，F(xiàn)，I。（3）G雙親：C。（4）G祖先：A，C。（5）G孩子：J，K。（6）E子孫：L，M，N。（7）E弟兄：D；F弟兄：G，H。（8）結(jié)點B層次為2；結(jié)點N層次是5。（9）樹深度是5。（10）以結(jié)點C為根子樹深度是3。（11）樹度數(shù)是3。ABABCHDDFGELMIJNK六.應(yīng)用題1．ABCAABCAADCBBABCACCB2.三個結(jié)點樹三個結(jié)點二叉樹樹3．BCHDDBCHDDFGEIA其前序遍歷序列為：EBADCFHGIGHAGHABDCEFI答：恢復(fù)二叉樹為：其后序遍歷序列為：GHDBEIFCAA5．A答：CBCBFEDDFEDDIHGIHGJJ6．124688D5124688D537AABCHDDFGEIJKAKABCHDDFGEIJ解：8．解：還原后二叉樹為：AABCHDDFGEI9.ABC+DDFABC+DDFGE/+*ˉ*+ˉ+ˉBDCAD0后綴表示式：0A–B+C–D+后綴表示式：ABC/+D–EFG+**10．解：4567812189131725356035351325D12660181798D457WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15911．解236914151617529331120498249491733D1698229201514D56113D2WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229七．算法設(shè)計題求二叉樹中度數(shù)為2結(jié)點。voidcount(BTt){if(t){if(t->lchild&&t->rchild)k++;count(t->lchild);count(t->rchild);}}求二叉樹中值為最大元素。intmaxnode(BTt,intmax){if(t){if(t->data>max)max=t->data;max=maxnode(t->lchild,max);max=maxnode(t->rchild,max);}}3．將二叉樹各結(jié)點存放到一維數(shù)組中。voidcreate(BTt,inta[],inti){if(t){a[i]=t->data;create(t->lchild,a,2*i);create(t->rchild,a,2*i+1);}}4．前序輸出二叉樹中各結(jié)點及其結(jié)點所在層號。voidpreorderlevel(BTt,inth)//t層數(shù)為h{if(t!=NULL){printf(“%d,%d”,t->data,h);preorderlevel(t->lchild,h+1);preorderlevel(t->rchild,h+1);}}求二叉樹寬度思想：按層遍歷二叉樹，采取一個隊列q，讓根結(jié)點入隊列，最終出隊列，若有左右子樹，則左右子樹根結(jié)點入隊列，如此重復(fù)，直到隊列為空。intWidth(BT*T){intfront=-1,rear=-1;//隊列初始化intflag=0,count=0,p;//p用于指向樹中層最右邊結(jié)點，標志flag統(tǒng)計層中結(jié)點數(shù)最大值if(T!=Null){rear++;q[rear]=T;flag=1;p=rear;}while(front<p){front++;T=q[front];if(T->lchild!=Null){rear++;q[rear]=T->lchild;count++;}if(T->rchild!=Null){rear++;q[rear]=T->rchild;count++;}if(front==p) //當(dāng)前層已遍歷完成{if(flag<count)flag=count;count=0;p=rear; //p指向下一層最右邊結(jié)點}} //endwhilereturn(flag);}6．解：思想：借助棧來進行對換。Swap(BinTree*T){BinTree*stack[100],*temp;inttop=-1;root=T;if(T!=Null)}top++;stack[top]=T;while(top>-1){T=stack[top];top--;if(T->child!=Null||T->rchild!=Null){//交換結(jié)點左右指針temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;}if(T->lchild!=Null){top++;stack[top]=T->lchild;}if(T->rchild!=Null){top++;stack[top]=T->rchild;}}}}main(){intI,j,k,l;printf(“\n”);root=CreateBinTree();Inorder(root);i=CountNode(root);j=CountLeafs(root);k=Depth(root);l=Width(root);printf(“\nTheNode’sNumber:%d”,i);printf(“\nTheLeafs’sNumber:%d”,j);printf(“\nTheDepthis:%d”,k);printf(“\nThewidthis:%d”,l);Swap(root);Printf(“\nTheswapTreeis:”);Inorder(root);}7．解：inth=-1,lh=1,count=0;charx=’c’; //賦初值Level(BinTreeT,inth,intlh) //求X結(jié)點在樹只層樹{if(T==Null)h=0;elseif(T->data==x){h=lh;count=h;}else{h++;Level(T->lchild,h,lh);If(h==-1)Level(T->rchild,h,lh);}}main(){BinTree*(*newroot);Printf(“\n”);Root=CreateBinTree();Inorder(root);Printf(“\n”);Level(root,h,lh);Printf(“%d”,count);}習(xí)題7一．名稱解釋（1）有向圖——在一個圖中，假如每條邊都有方向，則稱該圖有向圖。（2）無向圖——在一個圖中，假如每條邊都沒有方向，則稱該圖為無向圖。（3）完全有向圖——在一個有向圖中，假如任意兩頂點之間都有方向互為相反兩條弧相連接，則稱該圖為有向完全圖。（在一個含有n個頂點有向完全圖中，有n(n-1)條弧。）（4）最小生成樹——若無向連通圖是一個網(wǎng)，則它全部生成樹中必有一棵邊權(quán)值之和為最小生成樹，簡稱為最小生成樹。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）√（2）√（3）ㄨ（4）√（5）ㄨ（6）ㄨ（7）√（8）ㄨ三．填空題（1）鄰接矩陣 鄰接表 深度優(yōu)先遍歷 廣度優(yōu)先遍歷（2）沒有 2n（3）有 ?。?）頂點（5）出度（6）O(n2)（7）鄰接表 鄰接矩陣（8）有向（9）不是（10）O(n2)（11）n（n-1）/2（12）全部四．選擇題（1）C （2）B （3）B （4）C （5）C （6）B（7）A （8）A （9）D （10）A （11）B （12）D五．簡答題1．解（1）鄰接矩陣12345（2）鄰接表1235∧24∧35∧41∧54∧02．解：054215421D33從頂點0出發(fā)深度優(yōu)先搜索遍歷結(jié)點序列：012345（不惟一）。從頂點0出發(fā)廣度優(yōu)先搜索遍歷結(jié)點序列：012453（不惟一）。a3．解a（1）（2）深度優(yōu)先搜索：beDcabdce（或abdec）beDcd廣度優(yōu)先搜索：dabedc25432543125431811最小生成樹：10834137347六．編程題本題思想：逐一掃描鄰接矩陣各個元素，若第i行第j列元素為1，則對應(yīng)鄰接表第i個單鏈表上增加嚴格j結(jié)點。voidtrans(intedges[n][n],Adjlistadj){ inti,j; edgenode*p; for(i=0;i<n;i++) { adj[i].data=i; adj[i].link=NULL; } for(i=0;i<n;i++) for(j=0;j<n;j++) {if(edges[i][j]==1) { p=(edgenode*)malloc(sizeof(edgenode)); p->adjvex=j; p->next=adj[i].link; adj[i].link=p; } }}2．（1）求出度思想：計算出鄰接表中第i個單鏈表結(jié)點數(shù)即可。intoutdegree(adjlistadj,intv){ intdegree=0; edgenode*p; p=adj[v].link; while(p!=NULL) { degree++; p=p->next; } returndegree;}voidprintout(adjlistadj,intn){ inti,degree; printf("TheOutdegreeare:\n"); for(i=0;i<n;i++) { degree=outdegree(adj,i); printf("(%d,%d)",i,degree); }}求入度思想：計算出鄰接表中結(jié)點i結(jié)點數(shù)即可。intindegree(adjlistadj,intn,intv){ inti,j,degree=0; edgenode*p; for(i=0;i<n;i++) { p=adj[i].link; while(p!=NULL) { if(p->adjvex==v) degree++; p=p->next; } } returndegree;}voidprintin(adjlistadj,intn){ inti,degree; printf("TheIndegreeare:\n"); for(i=0;i<n;i++) { degree=Indegree(adj,n,i); printf("(%d,%d)",i,degree); }}（2）求最大度算法voidmaxoutdegree(adjlistadj,intn){ intmaxdegree=0,maxv=0,degree,i; for(i=0;i<n;i++) { degree=outdegree(adj,i); if(degree>maxdegree) { maxdegree=degree; maxv=i; } } printf("maxoutdegree%d,maxvertex=%d",maxdegree,maxv);}（3）求度為0頂點數(shù)算法intoutzero(adjlistadj,intn){ intnum=0,i; for(i=0;i<n;i++) {if(outdegree(adj,i)==0) num++; } returnnum;}習(xí)題8一．名詞解釋（1）查找——查找有稱為檢索，是在一批統(tǒng)計中按某個域鎮(zhèn)靜域值，找出對應(yīng)統(tǒng)計操作。（2）散列函數(shù)——依照關(guān)鍵字值求存放地址函數(shù)稱為散列函數(shù)（也稱為哈希函數(shù)）（3）沖突——兩個不一樣關(guān)鍵字，其散列函數(shù)值相同，因而得到同一個表相同地址現(xiàn)象稱為沖突。（即經(jīng)過Hash函數(shù)換算后，每個存放地址出現(xiàn)了存放兩個以上標識符現(xiàn)象，因而造成數(shù)據(jù)丟失稱為沖突）（4）平衡因子——二叉排序樹中每個結(jié)點左子樹高度減去右子樹高度稱為該結(jié)點平衡因子。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）√ （2）√ （3）ㄨ （4）ㄨ （5）√（6）√ （7）√ （8）ㄨ三．填空題1．任意 (n+1)/22．關(guān)鍵字有序3．次序存放結(jié)構(gòu) 有序4．索引 塊5．任意存放 關(guān)鍵字有序6．質(zhì)數(shù)7．散列8．查找9．散列函數(shù)10．多11．O（1）12．開放定址法 鏈地址法13．靜態(tài)14．動態(tài)查找15．動態(tài)16．關(guān)鍵字17．大 小18．1四．選擇題（1）A （2）B （3）D （4）C （5）D（6）C （7）D （8）B （9）A （10）C（11）C （12）B五．簡答和應(yīng)用題74374312596108D（1）結(jié)構(gòu)二叉排序樹：（2）ASL=(1*1+2*2+3*4+4*3)/10=2.91853D1853D2410191579（1）結(jié)構(gòu)二叉排序樹：（2）ASL=(1*1+2*2+3*4+4*2+5*1)/10=33．解：1385D31385D37129110（2）按中序遍歷二叉排序樹能夠得到一個有序序列：135789101213。（3）在二叉樹排序BT中刪除“12”后樹結(jié)構(gòu)：885D37139110131385D371019或4．解：（1）線性探測再散列處理沖突時所結(jié)構(gòu)散列表：012345678910111214168275519208429231110（2）鏈地址法處理沖突時所結(jié)構(gòu)散列表。0∧11412779∧2∧36855∧4∧5∧61984∧720∧8∧9∧102310∧1111∧12∧6213819110000732580D901505．解：6213819110000732580D90150325325六．算法設(shè)計題1．解：實現(xiàn)本題功效算法以下，假如查找成功，則返回指向關(guān)鍵字為x結(jié)點指針，不然返回NULL。node*sqsearch(node*head，intx){node*p=head;while(p!=NULL)if(x>p->key)p=p->link;elseif(x==p->key)returnp;else{p=NULL;returnp;}}2．解：算法思想是：首先計算要刪除關(guān)鍵字為k統(tǒng)計所在位置，將其置為空(即刪除)，然后利用線性探測法查找是否有與k發(fā)生沖突而存放到下一地址統(tǒng)計，假如有則將統(tǒng)計移到原來k所在位置，直至表中沒有與k沖突統(tǒng)計為止。實現(xiàn)本題功效算法以下：voiddelete(sqlistr，intn，intk){inth,h0,h1;h=k%n;while(r[h].key!=k)h=(h+1)％n;r[h]=NULL;h0=h;hl=(h+1)％n;while(hl!=h){while(r[h1].key％n!=h)hl=(hl+1)％n;r[h0]=r[h1];r[h1]=NULL;h0=h1;h1=(hl+1)％n;}}3．解：本題算法思想：先計算地址H(R.key)，假如沒有沖突，則直接填入;不然利用線性探測法求出下一地址，直到找到一個為零地址，然后填入。實現(xiàn)本題功效函數(shù)以下：voidinsert(recordH,intm,recordR){inti;I=H(R.key);if(H[i]==NULL)H[i]=R;else{while(H[i]!=NULL){i=(i+1)%(m+1);}H[i]=R;}}習(xí)題9一.名詞解釋（1）排序——將數(shù)據(jù)元素任意序列，重新排列成一個按關(guān)鍵字有序序列，稱為排序。（2）內(nèi)排序——排序全部過程都在內(nèi)存進行排序稱為內(nèi)排序。（3）外排序——待排序數(shù)據(jù)元素量大，以致內(nèi)存一次不能容納全部統(tǒng)計，在排序過程中不得不訪問外存放器排序過程稱為外排序。（4）穩(wěn)定排序——若對任意數(shù)據(jù)元素序列，使用某個排序方法，對它按關(guān)鍵字進行排序，若相同關(guān)鍵字元素間位置關(guān)系，排序前與排序后保持一致，稱此排序方法是穩(wěn)定。（5）堆——堆是一個完全二叉樹，它每個結(jié)點對應(yīng)于原始數(shù)據(jù)一個元素，且要求假如一個結(jié)點有子結(jié)點，則此結(jié)點數(shù)據(jù)必須大于或等于其全部子結(jié)點數(shù)據(jù)。二．判斷題（以下各題，正確請在前面括號內(nèi)打√；錯誤打ㄨ）（1）√（2）ㄨ（3）√（4）ㄨ（5）√（6）ㄨ（7）ㄨ（8）√（9）√（10）√三．填空題時間復(fù)雜度 算法所需輔助空間內(nèi)排序 外排序3希爾排序 選擇排序 快速排序5．快速排序6．插入排序7．O(n2) n-18．快速排序9．L210．冒泡選擇題D(2)A(3)A(4)C(5)D(6)C(7)D(8)C(9)B(10)C(11)D(12)A(13)D(14)B(15)D五．排序過程分析1.解：