數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)習(xí)題解答參考范本

精品精品感謝下載載感謝下載載1.3 設(shè)n是正整數(shù)。試寫(xiě)出下列程序段中用記號(hào)“ △”標(biāo)注的語(yǔ)句的頻度：(2) i=1;k=0;do{△ k+=10*i;i++;}while(i<=n-1)當(dāng)n=1 時(shí)，執(zhí)行1；當(dāng)n>=2 時(shí)，執(zhí)行n-1 次；(3) i=1;k=0;do{△ k+=10*i;i++;}while(i==n);當(dāng)n=2 時(shí)，執(zhí)行2次；當(dāng)n!=2 時(shí)，執(zhí)行1次(4) i=1;j=0;while(i+j {△ if(i<j)i++;elsej++;}執(zhí)行n次；(5) x=n;y=0;//n 是不小于1的常數(shù)while(x>=(y+1)*(y+1)){△ y++;}執(zhí)行 向下取整)(6) x=91;y=100;while(y>0)△ if(x>100){x-=10;y--;}else x++;}If語(yǔ)句執(zhí)行100次(7) for(i=0;i<n;i++)for(j=i;j<n;j++)for(k=j;k<n;k++)過(guò)程：

n1ni0ji

△ x+=2;(n j) n(n 1)(n 2)6第二章2.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫(xiě)一個(gè)算法，將元素 x到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲(chǔ)空間是否滿，若滿返回 Error；否則從后向前先移數(shù)據(jù)，找到合適的位置插入。StatusInsert_SqList(SqList&La,intx)// 把x插入遞增有序表 La 中{if(La.length==La.listsize)returnERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;returnOK;}//Insert_SqList2.5試寫(xiě)一個(gè)算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲(chǔ)空間將線性表（,a2,...,an-1,an）(an,an-1,...,a2,a1)//思路就是兩個(gè)指示變量 i，j同時(shí)分別從順序表的開(kāi)始和結(jié)尾處相向改voidreverse(SqList&A)// 順序表的就地逆置{ElemTypep;for(i=1,j=A.length;i<j;i++,j--){//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse已知線性表L采用順序存儲(chǔ)結(jié)構(gòu)存放，對(duì)兩種不同情況分別寫(xiě)出算法，刪除L中多余的元素，使得L中沒(méi)有重復(fù)元素：（1）L中數(shù)據(jù)元素?zé)o序排列；(2)L數(shù)據(jù)元素非遞減有序排列。voidDelete_SameElem(SqLink&L,intL.length){//內(nèi)層循環(huán)移動(dòng)參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個(gè)表inti=0;intj=i+1;intlength=L.length;while(i<length){for(j=i+1;j<length;j++){if(L.Elem[j]==L.Elem[i]){//for(k=j;k<length-1;k++){L.Elem[k]=L.Elem[k+1];length--;j--;// 移動(dòng)元素后，由于少了一個(gè)元素，因此要減 1}}//endifIf(L.Elem[j]>L.Elem[i])break;// 第二小問(wèn)添加此句}//endfor}//endwhile}//endfunctoion已知線性表L采用鏈?zhǔn)浇Y(jié)構(gòu)存放。對(duì)兩種不同情況分別寫(xiě)出算法，刪除L值相同的多余元素，使得L中沒(méi)有重復(fù)元素：(1)L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。（1）L中數(shù)據(jù)元素?zé)o序排列；思路：由于是無(wú)序排列，需要線性表中每個(gè)元素都要相互進(jìn)行比較。StatusListDelete （Linklist&L ）//L是帶頭結(jié)點(diǎn)的線性表{ElemType*p,*q;p==L->next;q=p->next;// 設(shè)定p變化較慢， q變化較快while(p->next){while(q){if(p->data!=q->data)q=q->next;else{q=q->next;p->next=q;}//else}//whilep=p->next;q=p->next;// 開(kāi)始后一結(jié)點(diǎn)的尋找returnOK ；}//ListDelete(2)L中數(shù)據(jù)元素非遞減有序排列。思路：由于是有序的，遍歷一次線性表就行了StatusListDelete(LinkList&L){ElemType*p,*q;p=L->next;q=p->next;while(p->next){if(p->data!=q->data){p=p->next// 和第一問(wèn)不同地方q=p->next;}//ifelse{while(p->data==q->data)q=q->next;// 多個(gè)連續(xù)的重復(fù)值}//elsep->next=q;p=q;q=p->next;// 刪除值重復(fù)的結(jié)點(diǎn)，并修改相應(yīng)的指針returnOK ；}//ListDelete設(shè)有兩個(gè)非遞減有序的單鏈表 A,B請(qǐng)寫(xiě)出算法，將A和B就地歸并成一按元素值非遞增有序的單鏈表。// 將合并逆置后的結(jié)果放在 C表中，并刪除 B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驅(qū)指針qb=pb;//保存pb的前驅(qū)指針pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->data<pb->data){qa=pa;pa=pa->next;qa->next=A->next; //將當(dāng)前最小結(jié)點(diǎn)插入 A表表頭A->next=qa;}else{qb=pb;pb=pb->next;qb->next=A->next; //將當(dāng)前最小結(jié)點(diǎn)插入 A表表頭A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb){qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}2.13 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表 L=(a1,a2,a3)。試寫(xiě)一間復(fù)雜度為O(n)的算法，將L改造為L(zhǎng)=(a1,a3,a2)。voidReform(DuLinkedList&L)// 按1,3,5,...4,2 的順序重排雙向循環(huán)鏈表 L中的所有結(jié)點(diǎn){p=L.next;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;}//p指向最后一個(gè)奇數(shù)結(jié)點(diǎn)if(p->next==L)// 結(jié)點(diǎn)個(gè)數(shù)是奇數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn) next指向最后一個(gè)偶數(shù)結(jié)點(diǎn)p->next=L->pre->pre;else//結(jié)點(diǎn)個(gè)數(shù)是偶數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn) next指向最后一個(gè)偶數(shù)結(jié)點(diǎn)p->next=L->pre;p=p->next;// 此時(shí)p 指向最后一個(gè)偶數(shù)結(jié)點(diǎn)while(p->pre->pre!=L){p->next=p->pre->pre;p=p->next;}p->next=L;// 最后一個(gè)結(jié)點(diǎn) next指向頭結(jié)點(diǎn)//調(diào)整了next 鏈的結(jié)構(gòu)此時(shí)pre 鏈仍為原狀//調(diào)整pre 鏈的結(jié)構(gòu)for(p=L;p->next!=L;p=p->next)p->next->pre=p;L->pre=p// 頭結(jié)點(diǎn)的prea2結(jié)點(diǎn)}//Reform第三章 棧和隊(duì)列試寫(xiě)一個(gè)算法，識(shí)別依次讀入的一個(gè)以 @為結(jié)束符的字符序列是否為形如“序列1&序列模式的字符序列。其中序列1和序列2中都不包含字符‘&且序列2是序列1的逆序。例如“a ”是屬于該模式的字符序列，“13&31算法：intSeqReverse()// 判斷輸入的字符串中 '&'前和'&'后部分是否為逆串 ,是則返回1,否則返回0{InitStack(s);while((e=getchar())!='&'){= @)return/ 不允許在&@’push(s,e);}//序列1輸入完畢while((e=getchar())!='@'){if(StackEmpty(s))return0;pop(s,c);if(e!=c)return0;}if(!StackEmpty(s))return0;// 1return1;}//IsReverse假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種符號(hào)：圓括號(hào)“ (”和“)、方括號(hào)“和“]、花括號(hào)“{”和“，且這三種括號(hào)可按任意次序嵌套使用。編寫(xiě)判別給定表達(dá)式中所含的括號(hào)是否正確配對(duì)的算法 （已知表達(dá)式已存入數(shù)據(jù)元素為字的順序表中。算法：StatusBracketTest(char*str)// 判別表達(dá)式中三種括號(hào)是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')if(*p=='}'&&c!='{')returnERROR;returnERROR;//必須與當(dāng)前棧頂括號(hào)匹配}//if}//forif(!StackEmpty(s))returnERROR;//進(jìn)棧的符號(hào)還有剩余， ErrorreturnOK;}//BracketTest設(shè)表達(dá)式由單字母變量、雙目運(yùn)算符和圓括號(hào)組成（如 試寫(xiě)一個(gè)算法，將一個(gè)書(shū)寫(xiě)正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。思路：遇到數(shù)字直接發(fā)送 .遇到(直接入棧 .遇到)則將棧內(nèi)元素發(fā)送直至遇到 (.棧則直接入棧 5.棧非空時(shí)若優(yōu)先級(jí)大于棧內(nèi)則入棧，否則棧內(nèi)元素出棧intRankOfOperator(charc){switch(c){case'#':return-1;case'(':return0;case'+':case'-':return1;case'*':case'/':case')':return2;}}intPrecede(charc,charch){returnRankOfOperator(c)>RankOfOperator(ch);}voidExpressionTOPolandStyle(charsuffix[],char*exp){Stacks;InitStack(s,100);inti=0;charc;while(*exp){if(isdigital(*exp))suffix[i++]=*exp;else{switch(*exp){case'(':push(s,'(');case')':while((c=pops(s))!='(')suffix[i++]=c;break;default:if(IsEmpty(s))push(s,*exp);else{suffix[i++]=pop(s);exp--;//與后面的exp++相抵消，使得棧內(nèi)優(yōu)先級(jí)大于等于棧外的都出棧}}//endswitch}//endexp++;}//endwhilewhile(!IsEmpty(s))suffix[i++]=pop(s);suffix[i]=0;}假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，只設(shè)一個(gè)尾指針指向隊(duì)尾元素，不設(shè)頭指針。試編寫(xiě)相應(yīng)的隊(duì)列初始化、 入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳隊(duì)頭元素的值）要點(diǎn)：定義好數(shù)據(jù)類型，帶頭結(jié)點(diǎn)的單循環(huán)鏈表，只有尾指針，注意刪除元素時(shí)只有一個(gè)元素的特殊性typedefintDataTypestructNode{DataTypedata;Node*next;};structCycleListQueue{Node*tail;};voidInitCycleListQueue(CycleListQueue&L){L.tail=newNode;L.tail->next=L.tail;}voidEnterQueue(CycleListQueue&L,DataTypevalue){Node*p=newNode;p->data=value;p->next=L.tail->next;L.tail->next=p;L.tail=p;}voidDeparQueue(CycleListQueue&L,DataType&d){if(L.tail->next!=L.tail->next->next){Node*p=L.tail->next->next;L.tail->next->next=p->next;d=p->data;if(p==L.tail)L.tail=p->next;deletep;returnd;}}rearlength分別指示隊(duì)尾元素和隊(duì)列長(zhǎng)度。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳遞回隊(duì)頭元素的值）此循環(huán)隊(duì)列的隊(duì)滿條件： Q.length==MAXQSIZE;入隊(duì)算法：StatusEnCyQueue(CyQueue&Q,intx)// 帶length 域的循環(huán)隊(duì)列入隊(duì)算法{if(Q.length==MAXSIZE) returnOVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.base[Q.rear]=x;//rear 指向隊(duì)尾元素Q.length++;returnOK;}//EnCyQueue出隊(duì)算法：StatusDeCyQueue(CyQueue&Q,int&x)// 帶length 域的循環(huán)隊(duì)列出隊(duì)算法，用 x返回隊(duì)元素的值{if(Q.length==0) returnError;// 空隊(duì)列，錯(cuò)誤head=(Q.rear-Q.length+1)%MAXSIZE;//head 指向隊(duì)x=Q.base[head];Q.length--;returnOK }//DeCyQueue試寫(xiě)一個(gè)算法：判別讀入的一個(gè)以‘ @’為結(jié)束符的字符序列是否是“回文所謂“回文”是指正讀和反讀都相同的字符序列，如“ xxyzyxx”是回文而“abcab”則不是回文）。StatusTest()// 判別輸入的字符串是否回文序列 是則返回1,否則返回0{InitStack(S);InitQueue(Q);while((c=getchar())!='@'){Push(S,c);EnQueue(Q,c);// 同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)}while(!StackEmpty(S)){精品Pop(S,a);DeQueue(Q,b);if(a!=b) returnERROR;}returnOK;}//Test第五章 多維數(shù)組設(shè)有一個(gè)準(zhǔn)對(duì)角矩陣a21

a12a22

a33a43

a34a44

......

......

a2m

1,2m

a2m

1,2ma2m,2m1 a2m,2m按以下方式存于一維數(shù)組 B[4m]中：0 1 2 3 4 5 6 k 4m-2 4m-1a11 a12 a21 a22 a33 a34 a43 ... aij ... a2m-1,2m a2m,2m感謝下載載精品寫(xiě)出由一對(duì)下標(biāo)(i,j)求k的轉(zhuǎn)換公式。因?yàn)?i 行前有 2(i-1) 個(gè)元素?，F(xiàn)考慮 i 行情況，當(dāng) j 是奇數(shù)，i 行有 1 個(gè)素,k=2(i-1)+1-1=2(i-1) ；否則i行有2個(gè)元素，k=2(i-1)+2-1=2i-1 。故：k=或若i為奇數(shù)，k=2(i-1)+j-i=i+j-2; 當(dāng)i為偶數(shù)時(shí)，k=2i-(i-j)-1=i+j-1k=已知稀疏矩陣A4×5如下：0101005230600000004007用三元組表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。三元組表：i j v1 2 11 5 52 1 22 2 32 4 6感謝下載載精品4 2 44 5 7十字鏈表<1 2 1

1 5 5<2 1 2 2 2 3 2 4 6< < <<4 2 4 4 5 7< < <第六章 數(shù)和二叉樹(shù)6.5 已知一棵度為 k的樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nk個(gè)度為k的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？設(shè)葉子結(jié)點(diǎn)有x個(gè)，則樹(shù)的結(jié)點(diǎn)總數(shù)為n1+n2+ 同時(shí)除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都指向一個(gè)結(jié)點(diǎn)，所有從這個(gè)角度考慮樹(shù)的結(jié)點(diǎn)總數(shù)為：n1+2?n2+?k?nk+1;n1+n2+ n1+2 +,可得x=

k(i 1)?ni 1i2已知一棵樹(shù)如圖6-1歷序列和后根遍歷序列。感謝下載載精品AB C DE F G HI J K圖6-1先根遍歷：ABCEIJFGKHD后根遍歷：BIJEFKGHCDA對(duì)應(yīng)的二叉樹(shù)：感謝下載載精品ABCE DIFJGK H6-2所示的森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)。I K LJ M ND E OF GH圖6-2樹(shù)對(duì)應(yīng)的二叉樹(shù)感謝下載載精品I LKJ MNDOEF 6-2H G森林對(duì)應(yīng)的二叉樹(shù)：AIBJCKDLEMFH G NO感謝下載載精品精品感謝下載載感謝下載載6.11已知某二叉樹(shù)的中序序列為 DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請(qǐng)畫(huà)出該二叉樹(shù)。AB IC G H JKE F6.14 假設(shè)某個(gè)電文由(a,b,c,d,e,f,g,h)8 個(gè)字母組成，每個(gè)字母在電文中出現(xiàn)次數(shù)分別為(7,19,2,6,32,3,21,10) ，試解答下列問(wèn)題：畫(huà)出出huffman 樹(shù)；100060284019b 21g

11G52c 3f

176d 7a

10h

32e寫(xiě)出每個(gè)字母的 huffman 編碼；a:1010b:00c:10000d:1001e:11f:10001g:01h:1011在對(duì)該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17 寫(xiě)出按層次遍歷二叉樹(shù)的算法。StatusLevelOrderTraverse(BitTreeT,Status(*Visit)(TElemTypee)// 層序遍歷二叉樹(shù){InitQueue(Q);// 初始化隊(duì)列if(!T) returnError;// 空樹(shù)，直接返EnQueue(Q,T);// 根結(jié)點(diǎn)入隊(duì)BiTNode*p;while(!QueueEmpty(Q)){DeQueue(Q,p);Visit(p->data);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) }//whilereturnOk;}//LevelOrderTraverse6.19 寫(xiě)出判斷兩棵給定二叉樹(shù)是否相似的算法。(注：兩棵二叉樹(shù) B1和B2相似是指：B1和B2皆空，或者皆不空且 B1的左右子樹(shù)和B2的左、右子樹(shù)分別相似。 )思路：采用遞歸進(jìn)行比較判斷boolBiTreeSimilar(BiTreeT1,BiTreeT2){if(T1==Null&&T2==Null)return1;elseif(T1==Null||T2==Null)return0;elsereturn(BiTreeSilimar(T1->lchild,T2->lchild)&&BiTreeSimilar(T1->rchild,T2->rchild));}6.21 寫(xiě)出統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法，樹(shù)用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結(jié)點(diǎn)的 firstchild 為Null，則為葉子結(jié)點(diǎn)；采用遞歸方法。intCountLeaves(TreeT ，int&num)//num 傳遞的初值為 0{if(T->nextsibling!=Null)num+=CountLeaves(T->nextsibling);if(T->firstchild!=Null)num+=CountLeaves(T->firstchild);elsenum+=1;//firstchild 域?yàn)榭?，則為葉子結(jié)點(diǎn)returnnum;}V1V5V1V5V6V2V4V37-1已知有向圖如圖 7-1所示請(qǐng)給出該圖的鄰接矩陣示意圖鄰接表示意圖逆鄰接表所有強(qiáng)連通分量(1) 鄰接矩陣000000100100010001001011100000110010（2）鄰接表0 v1 <1 v2 3 0 <2 v3 5 1 <v4v5v6

5 4 2 <0 <4 1 0 <（3）逆鄰接表0 v1 <v2v3v4v5v6

5 4 1 <5 2 <3 <1 <5 3 <3 2 <（4）強(qiáng)連通分量

V1 V5V6V2 V3已知圖G的鄰接矩陣如圖 7-2所示。寫(xiě)出該圖從頂點(diǎn) 1出發(fā)的深度優(yōu)先索序列和廣度優(yōu)先搜索序列，并畫(huà)出相應(yīng)的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。112345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖7-2深度優(yōu)先序列： 173456210981734 85 96 102深度優(yōu)先生成樹(shù)：廣度優(yōu)先序列： 1793105486217 93 10 54 8 62廣度優(yōu)先生成樹(shù)：9.1若對(duì)大小均為 n的有序順序表和無(wú)序順序表分別進(jìn)行順序查找， 試在下列三種情況下別討論兩者在等概率時(shí)平均查找長(zhǎng)度是否相同？（1）查找不成功，即表中沒(méi)有關(guān)鍵字等于給定的值 K的記錄；（2）查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值 K的記錄；（3）查找成功，且表中有若干個(gè)關(guān)鍵字等于給定值 K的記錄，要求找出所有這些記錄解：對(duì)有序順序表：1

n+21. n+1[1+2+...+(n+1)]= 2

（將該項(xiàng)看作一項(xiàng)混入原有序列中，問(wèn)題轉(zhuǎn)變成 n+1個(gè)元素序列的成功查找問(wèn)題）n2．1[1+2+...+n

n+123. 1

+2+...+n

(k-

n-1)]=

k+2

將此K項(xiàng)看作一項(xiàng)n-(k-1) 2對(duì)無(wú)序順序表：1. n1

n+12. n[1+2+...+= 2n3.

i=(n+k)(n-k+1)g 1

n+k=

考慮最后一個(gè)記錄的出現(xiàn)位置i=k

2 n

k2畫(huà)出對(duì)長(zhǎng)度為 17的有序表進(jìn)行折半查找的判定樹(shù)，并分別求其等概率時(shí)查找長(zhǎng)度和找失敗的ASL。1 59解：ASL=171 2?2 4 4?8 5?2) 171 76ASL18(47 ?2 47 52) 18 增加虛結(jié)點(diǎn)94 132 6 11 151 3 5 7 10 12 14 168 17已知如下所示長(zhǎng)度為 12的表Jan，F(xiàn)eb，Apr，May，Jun，July，Sept，Oct，Nov，Dec）表中，每一個(gè)元素的查找概率分別為： （0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07 ）（1）若對(duì)該表進(jìn)行順序查找，求查找成功的平均查找長(zhǎng)度；（2）畫(huà)出從初態(tài)為空開(kāi)始，依次插入結(jié)點(diǎn)，生成的二叉排序樹(shù)；（3）計(jì)算該二叉排序樹(shù)查找成功的平均查找長(zhǎng)度；（4）將二叉排序樹(shù)中的結(jié)點(diǎn) Mar 刪除，畫(huà)出經(jīng)過(guò)刪除處理后的二叉排序樹(shù)。1）

ASL=1 0.25?2 ...+0.07?12 5.43（2）與初始輸入序列有關(guān)JanJanFebMarAprJunMayAugJulySepDecOctNov（3）ASL=1 2 ...+0.07?5 3.2（4）找到Mar 的直接后繼，將Mar 的左子樹(shù)移動(dòng)到最左孩子的左孩子處，然后用直后繼取代當(dāng)前結(jié)點(diǎn)。JanFeb MayApr

Jun

SepAug

July

OctDec

Nov9.5 已知關(guān)鍵字序列 {10，25，33，19，06，49，37，76，60}，哈希地址空間為 0-10哈希函數(shù)為 H(key)=Key%11 ，求：（1）用開(kāi)放定址線性探測(cè)法處理沖突，構(gòu)造哈希表 HT1，分別計(jì)算在等概率情況下 HT1查找成功和查找失敗的 ASL；（2）用開(kāi)放定址二次探測(cè)法處理沖突，構(gòu)造哈希表 HT2，計(jì)算在等概率下 HT2 查找成的ASL；（3）用拉鏈法解決沖突，構(gòu)造哈希表 HT3，計(jì)算HT3在等概率情況查找成功的 ASL。解：這9個(gè)數(shù)的hash值為： 10,3,0,8,6,5,4,10,5沖突有2個(gè)。012345678910337625374906601910

17 3?1 3?139 9=(F

+F(1)+...+F(10))/11=3811

遇到空還沒(méi)有，則算失敗。（2）d=0,1,-1,4,-4 ??01234567891033602549061976101 5ASL

97 1 5?3(3)033123254375496060678199101076ASL

17 2?119 9精品精品感謝下載載感謝下載載1 總則1.1 為了加強(qiáng)公司的環(huán)境衛(wèi)生管理，創(chuàng)造一個(gè)整潔、文明、溫馨的購(gòu)物、辦公環(huán)境，根據(jù)《公共場(chǎng)所衛(wèi)生管理?xiàng)l例》的要求，特制定本制度。1.2 集團(tuán)公司的衛(wèi)生管理部門(mén)設(shè)在企管部，并負(fù)責(zé)將集團(tuán)公司的衛(wèi)生區(qū)域詳細(xì)劃分到各部室，各分公司所轄區(qū)域衛(wèi)生由分公司客服部負(fù)責(zé)劃分，確保無(wú)遺漏。2 衛(wèi)生標(biāo)準(zhǔn)2.1 室內(nèi)衛(wèi)生標(biāo)準(zhǔn)2.1.1 地面、墻面：無(wú)灰塵、無(wú)紙屑、無(wú)痰跡、無(wú)泡泡糖等粘合物、無(wú)積水，墻角無(wú)灰吊、無(wú)蜘蛛網(wǎng)。2.1.2 門(mén)、窗、玻璃、鏡子、柱子、電梯、樓梯、燈具等，做到明亮、無(wú)灰塵、無(wú)污跡、無(wú)粘合物，特別是玻璃，要求兩面明亮。2.1.3 柜臺(tái)、貨架：清潔干凈，貨架、柜臺(tái)底層及周?chē)鸁o(wú)亂堆亂放現(xiàn)象、無(wú)灰塵、無(wú)粘合物，貨架頂部、背部和底部干凈，不存放雜物和私人物品。2.1.4 購(gòu)物車(chē)（筐）、直接接觸食品的售貨工具（包括刀、叉等）：做到內(nèi)外潔凈，無(wú)污垢和粘合物等。購(gòu)物車(chē)（筐）要求每天營(yíng)業(yè)前簡(jiǎn)單清理，周五全面清理消毒；售貨工具要求每天消毒，并做好記錄。2.1.5 商品及包裝：商品及外包裝清潔無(wú)灰塵（外包裝破損的或破舊的不得陳列）。2.1.6 收款臺(tái)、服務(wù)臺(tái)、辦公櫥、存包柜：保持清潔、無(wú)灰塵，臺(tái)面和側(cè)面無(wú)灰塵、無(wú)灰吊和蜘蛛網(wǎng)。桌面上不得亂貼、亂畫(huà)、亂堆放物品，用具擺放有序且干凈，除當(dāng)班的購(gòu)物小票收款聯(lián)外，其它單據(jù)不得存放在桌面上。2.1.7 垃圾桶：桶內(nèi)外干凈，要求營(yíng)業(yè)時(shí)間隨時(shí)清理，不得溢出，每天下班前徹底清理，不得留有垃圾過(guò)夜。2.1.8 窗簾：定期進(jìn)行清理，要求干凈、無(wú)污漬。2.1.9 吊飾：屋頂?shù)牡躏椧鬅o(wú)灰塵、無(wú)蜘蛛網(wǎng)，短期內(nèi)不適用的吊飾及時(shí)清理徹底。2.1.10 內(nèi)、外倉(cāng)庫(kù)：半年徹底清理一次，無(wú)垃圾、無(wú)積塵、無(wú)蜘蛛網(wǎng)等。2.1.11 室內(nèi)其他附屬物及工作用具均以整潔為準(zhǔn)，要求無(wú)灰塵、無(wú)粘合物等污垢。2.2 室外衛(wèi)生標(biāo)準(zhǔn)2.2.1 門(mén)前衛(wèi)生：地面每天班前清理，平時(shí)每一小時(shí)清理一次，每周四營(yíng)業(yè)結(jié)束后有條件的用水沖洗地面（冬季可根據(jù)情況適當(dāng)清理），墻面干凈且無(wú)亂貼亂畫(huà)。2.2.2 院落衛(wèi)生：院內(nèi)地面衛(wèi)生全天保潔，果皮箱、消防器械、護(hù)欄及配電箱等設(shè)施每周清理干凈。垃圾池周邊衛(wèi)生清理徹底，不得有垃圾溢出。2.2.3 綠化區(qū)衛(wèi)生：做到無(wú)雜物、無(wú)紙屑、無(wú)塑料袋等垃圾。3 清理程序3.1 室內(nèi)和門(mén)前院落等區(qū)域衛(wèi)生：每天營(yíng)業(yè)前提前10分鐘把所管轄區(qū)域內(nèi)衛(wèi)生清理完畢，營(yíng)業(yè)期間隨時(shí)保潔。下班后5-10分鐘清理桌面及衛(wèi)生區(qū)域。3.2 綠化區(qū)衛(wèi)生：每周徹底清理一遍，隨時(shí)保持清潔無(wú)垃圾。4 管理考核4.1 實(shí)行百分制考核，每月一次（四個(gè)分公司由客服部分別考核、集團(tuán)職4.2 集團(tuán)堅(jiān)持定期檢查和不定期抽查的方式監(jiān)督各分公司、部門(mén)的衛(wèi)生工作。每周五為衛(wèi)生檢查日，集團(tuán)檢查結(jié)果考核至各分公司，各分公司客服部的檢查結(jié)果考核至各部門(mén)。4.3 集團(tuán)公司每年不定期組織衛(wèi)生大檢查活動(dòng)，活動(dòng)期間的考核以通知為準(zhǔn)。5 監(jiān)督考核部門(mén)：企管部、分公司客服部。!1.3 設(shè)n是正整數(shù)。試寫(xiě)出下列程序段中用記號(hào)“ △”標(biāo)注的語(yǔ)句的頻度：(2) i=1;k=0;do{△ k+=10*i;i++;}while(i<=n-1)當(dāng)n=1 時(shí)，執(zhí)行1；當(dāng)n>=2 時(shí)，執(zhí)行n-1 次；(3) i=1;k=0;do{△ k+=10*i;i++;}while(i==n);當(dāng)n=2 時(shí)，執(zhí)行2次；當(dāng)n!=2 時(shí)，執(zhí)行1次(4) i=1;j=0;while(i+j {△ if(i<j)i++;elsej++;}執(zhí)行n次；(5) x=n;y=0;//n 是不小于1的常數(shù)while(x>=(y+1)*(y+1)){△ y++;}執(zhí)行 向下取整)(6) x=91;y=100;while(y>0)△ if(x>100){x-=10;y--;}else x++;}If語(yǔ)句執(zhí)行100次(7) for(i=0;i<n;i++)for(j=i;j<n;j++)for(k=j;k<n;k++)過(guò)程：

n1ni0ji

△ x+=2;(n j) n(n 1)(n 2)6第二章2.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫(xiě)一個(gè)算法，將元素 x到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲(chǔ)空間是否滿，若滿返回 Error；否則從后向前先移數(shù)據(jù)，找到合適的位置插入。StatusInsert_SqList(SqList&La,intx)// 把x插入遞增有序表 La 中{if(La.length==La.listsize)returnERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;returnOK;}//Insert_SqList2.5試寫(xiě)一個(gè)算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲(chǔ)空間將線性表（,a2,...,an-1,an）(an,an-1,...,a2,a1)//思路就是兩個(gè)指示變量 i，j同時(shí)分別從順序表的開(kāi)始和結(jié)尾處相向改voidreverse(SqList&A)// 順序表的就地逆置{ElemTypep;for(i=1,j=A.length;i<j;i++,j--){//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse已知線性表L采用順序存儲(chǔ)結(jié)構(gòu)存放，對(duì)兩種不同情況分別寫(xiě)出算法，刪除L中多余的元素，使得L中沒(méi)有重復(fù)元素：（1）L中數(shù)據(jù)元素?zé)o序排列；(2)L數(shù)據(jù)元素非遞減有序排列。voidDelete_SameElem(SqLink&L,intL.length){//內(nèi)層循環(huán)移動(dòng)參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個(gè)表inti=0;intj=i+1;intlength=L.length;while(i<length){for(j=i+1;j<length;j++){if(L.Elem[j]==L.Elem[i]){//for(k=j;k<length-1;k++){L.Elem[k]=L.Elem[k+1];length--;j--;// 移動(dòng)元素后，由于少了一個(gè)元素，因此要減 1}}//endifIf(L.Elem[j]>L.Elem[i])break;// 第二小問(wèn)添加此句}//endfor}//endwhile}//endfunctoion已知線性表L采用鏈?zhǔn)浇Y(jié)構(gòu)存放。對(duì)兩種不同情況分別寫(xiě)出算法，刪除L值相同的多余元素，使得L中沒(méi)有重復(fù)元素：(1)L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。（1）L中數(shù)據(jù)元素?zé)o序排列；思路：由于是無(wú)序排列，需要線性表中每個(gè)元素都要相互進(jìn)行比較。StatusListDelete （Linklist&L ）//L是帶頭結(jié)點(diǎn)的線性表{ElemType*p,*q;p==L->next;q=p->next;// 設(shè)定p變化較慢， q變化較快while(p->next){while(q){if(p->data!=q->data)q=q->next;else{q=q->next;p->next=q;}//else}//whilep=p->next;q=p->next;// 開(kāi)始后一結(jié)點(diǎn)的尋找returnOK ；}//ListDelete(2)L中數(shù)據(jù)元素非遞減有序排列。思路：由于是有序的，遍歷一次線性表就行了StatusListDelete(LinkList&L){ElemType*p,*q;p=L->next;q=p->next;while(p->next){if(p->data!=q->data){p=p->next// 和第一問(wèn)不同地方q=p->next;}//ifelse{while(p->data==q->data)q=q->next;// 多個(gè)連續(xù)的重復(fù)值}//elsep->next=q;p=q;q=p->next;// 刪除值重復(fù)的結(jié)點(diǎn)，并修改相應(yīng)的指針returnOK ；}//ListDelete設(shè)有兩個(gè)非遞減有序的單鏈表 A,B請(qǐng)寫(xiě)出算法，將A和B就地歸并成一按元素值非遞增有序的單鏈表。// 將合并逆置后的結(jié)果放在 C表中，并刪除 B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驅(qū)指針qb=pb;//保存pb的前驅(qū)指針pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->data<pb->data){qa=pa;pa=pa->next;qa->next=A->next; //將當(dāng)前最小結(jié)點(diǎn)插入 A表表頭A->next=qa;}else{qb=pb;pb=pb->next;qb->next=A->next; //將當(dāng)前最小結(jié)點(diǎn)插入 A表表頭A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb){qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}2.13 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表 L=(a1,a2,a3)。試寫(xiě)一間復(fù)雜度為O(n)的算法，將L改造為L(zhǎng)=(a1,a3,a2)。voidReform(DuLinkedList&L)// 按1,3,5,...4,2 的順序重排雙向循環(huán)鏈表 L中的所有結(jié)點(diǎn){p=L.next;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;}//p指向最后一個(gè)奇數(shù)結(jié)點(diǎn)if(p->next==L)// 結(jié)點(diǎn)個(gè)數(shù)是奇數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn) next指向最后一個(gè)偶數(shù)結(jié)點(diǎn)p->next=L->pre->pre;else//結(jié)點(diǎn)個(gè)數(shù)是偶數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn) next指向最后一個(gè)偶數(shù)結(jié)點(diǎn)p->next=L->pre;p=p->next;// 此時(shí)p 指向最后一個(gè)偶數(shù)結(jié)點(diǎn)while(p->pre->pre!=L){p->next=p->pre->pre;p=p->next;}p->next=L;// 最后一個(gè)結(jié)點(diǎn) next指向頭結(jié)點(diǎn)//調(diào)整了next 鏈的結(jié)構(gòu)此時(shí)pre 鏈仍為原狀//調(diào)整pre 鏈的結(jié)構(gòu)for(p=L;p->next!=L;p=p->next)p->next->pre=p;L->pre=p// 頭結(jié)點(diǎn)的prea2結(jié)點(diǎn)}//Reform第三章 棧和隊(duì)列試寫(xiě)一個(gè)算法，識(shí)別依次讀入的一個(gè)以 @為結(jié)束符的字符序列是否為形如“序列1&序列模式的字符序列。其中序列1和序列2中都不包含字符‘&且序列2是序列1的逆序。例如“a ”是屬于該模式的字符序列，“13&31算法：intSeqReverse()// 判斷輸入的字符串中 '&'前和'&'后部分是否為逆串 ,是則返回1,否則返回0{InitStack(s);while((e=getchar())!='&'){= @)return/ 不允許在&@’push(s,e);}//序列1輸入完畢while((e=getchar())!='@'){if(StackEmpty(s))return0;pop(s,c);if(e!=c)return0;}if(!StackEmpty(s))return0;// 1return1;}//IsReverse假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種符號(hào)：圓括號(hào)“ (”和“)、方括號(hào)“和“]、花括號(hào)“{”和“，且這三種括號(hào)可按任意次序嵌套使用。編寫(xiě)判別給定表達(dá)式中所含的括號(hào)是否正確配對(duì)的算法 （已知表達(dá)式已存入數(shù)據(jù)元素為字的順序表中。算法：StatusBracketTest(char*str)// 判別表達(dá)式中三種括號(hào)是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')if(*p=='}'&&c!='{')returnERROR;returnERROR;//必須與當(dāng)前棧頂括號(hào)匹配}//if}//forif(!StackEmpty(s))returnERROR;//進(jìn)棧的符號(hào)還有剩余， ErrorreturnOK;}//BracketTest設(shè)表達(dá)式由單字母變量、雙目運(yùn)算符和圓括號(hào)組成（如 試寫(xiě)一個(gè)算法，將一個(gè)書(shū)寫(xiě)正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。思路：遇到數(shù)字直接發(fā)送 .遇到(直接入棧 .遇到)則將棧內(nèi)元素發(fā)送直至遇到 (.棧則直接入棧 5.棧非空時(shí)若優(yōu)先級(jí)大于棧內(nèi)則入棧，否則棧內(nèi)元素出棧intRankOfOperator(charc){switch(c){case'#':return-1;case'(':return0;case'+':case'-':return1;case'*':case'/':case')':return2;}}intPrecede(charc,charch){returnRankOfOperator(c)>RankOfOperator(ch);}voidExpressionTOPolandStyle(charsuffix[],char*exp){Stacks;InitStack(s,100);inti=0;charc;while(*exp){if(isdigital(*exp))suffix[i++]=*exp;else{switch(*exp){case'(':push(s,'(');case')':while((c=pops(s))!='(')suffix[i++]=c;break;default:if(IsEmpty(s))push(s,*exp);else{suffix[i++]=pop(s);exp--;//與后面的exp++相抵消，使得棧內(nèi)優(yōu)先級(jí)大于等于棧外的都出棧}}//endswitch}//endexp++;}//endwhilewhile(!IsEmpty(s))suffix[i++]=pop(s);suffix[i]=0;}假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，只設(shè)一個(gè)尾指針指向隊(duì)尾元素，不設(shè)頭指針。試編寫(xiě)相應(yīng)的隊(duì)列初始化、 入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳隊(duì)頭元素的值）要點(diǎn)：定義好數(shù)據(jù)類型，帶頭結(jié)點(diǎn)的單循環(huán)鏈表，只有尾指針，注意刪除元素時(shí)只有一個(gè)元素的特殊性typedefintDataTypestructNode{DataTypedata;Node*next;};structCycleListQueue{Node*tail;};voidInitCycleListQueue(CycleListQueue&L){L.tail=newNode;L.tail->next=L.tail;}voidEnterQueue(CycleListQueue&L,DataTypevalue){Node*p=newNode;p->data=value;p->next=L.tail->next;L.tail->next=p;L.tail=p;}voidDeparQueue(CycleListQueue&L,DataType&d){if(L.tail->next!=L.tail->next->next){Node*p=L.tail->next->next;L.tail->next->next=p->next;d=p->data;if(p==L.tail)L.tail=p->next;deletep;returnd;}}rearlength分別指示隊(duì)尾元素和隊(duì)列長(zhǎng)度。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳遞回隊(duì)頭元素的值）此循環(huán)隊(duì)列的隊(duì)滿條件： Q.length==MAXQSIZE;入隊(duì)算法：StatusEnCyQueue(CyQueue&Q,intx)// 帶length 域的循環(huán)隊(duì)列入隊(duì)算法{if(Q.length==MAXSIZE) returnOVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.base[Q.rear]=x;//rear 指向隊(duì)尾元素Q.length++;returnOK;}//EnCyQueue出隊(duì)算法：StatusDeCyQueue(CyQueue&Q,int&x)// 帶length 域的循環(huán)隊(duì)列出隊(duì)算法，用 x返回隊(duì)元素的值{if(Q.length==0) returnError;// 空隊(duì)列，錯(cuò)誤head=(Q.rear-Q.length+1)%MAXSIZE;//head 指向隊(duì)x=Q.base[head];Q.length--;returnOK }//DeCyQueue試寫(xiě)一個(gè)算法：判別讀入的一個(gè)以‘ @’為結(jié)束符的字符序列是否是“回文所謂“回文”是指正讀和反讀都相同的字符序列，如“ xxyzyxx”是回文而“abcab”則不是回文）。StatusTest()// 判別輸入的字符串是否回文序列 是則返回1,否則返回0{InitStack(S);InitQueue(Q);while((c=getchar())!='@'){Push(S,c);EnQueue(Q,c);// 同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)}while(!StackEmpty(S)){精品Pop(S,a);DeQueue(Q,b);if(a!=b) returnERROR;}returnOK;}//Test第五章 多維數(shù)組設(shè)有一個(gè)準(zhǔn)對(duì)角矩陣a21

a12a22

a33a43

a34a44

......

......

a2m

1,2m

a2m

1,2ma2m,2m1 a2m,2m按以下方式存于一維數(shù)組 B[4m]中：0 1 2 3 4 5 6 k 4m-2 4m-1a11 a12 a21 a22 a33 a34 a43 ... aij ... a2m-1,2m a2m,2m感謝下載載精品寫(xiě)出由一對(duì)下標(biāo)(i,j)求k的轉(zhuǎn)換公式。因?yàn)?i 行前有 2(i-1) 個(gè)元素?，F(xiàn)考慮 i 行情況，當(dāng) j 是奇數(shù)，i 行有 1 個(gè)素,k=2(i-1)+1-1=2(i-1) ；否則i行有2個(gè)元素，k=2(i-1)+2-1=2i-1 。故：k=或若i為奇數(shù)，k=2(i-1)+j-i=i+j-2; 當(dāng)i為偶數(shù)時(shí)，k=2i-(i-j)-1=i+j-1k=已知稀疏矩陣A4×5如下：0101005230600000004007用三元組表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。三元組表：i j v1 2 11 5 52 1 22 2 32 4 6感謝下載載精品4 2 44 5 7十字鏈表<1 2 1

1 5 5<2 1 2 2 2 3 2 4 6< < <<4 2 4 4 5 7< < <第六章 數(shù)和二叉樹(shù)6.5 已知一棵度為 k的樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nk個(gè)度為k的結(jié)點(diǎn)，問(wèn)該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？設(shè)葉子結(jié)點(diǎn)有x個(gè)，則樹(shù)的結(jié)點(diǎn)總數(shù)為n1+n2+ 同時(shí)除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都指向一個(gè)結(jié)點(diǎn)，所有從這個(gè)角度考慮樹(shù)的結(jié)點(diǎn)總數(shù)為：n1+2?n2+?k?nk+1;n1+n2+ n1+2 +,可得x=

k(i 1)?ni 1i2已知一棵樹(shù)如圖6-1歷序列和后根遍歷序列。感謝下載載精品AB C DE F G HI J K圖6-1先根遍歷：ABCEIJFGKHD后根遍歷：BIJEFKGHCDA對(duì)應(yīng)的二叉樹(shù)：感謝下載載精品ABCE DIFJGK H6-2所示的森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)。I K LJ M ND E OF GH圖6-2樹(shù)對(duì)應(yīng)的二叉樹(shù)感謝下載載精品I LKJ MNDOEF 6-2H G森林對(duì)應(yīng)的二叉樹(shù)：AIBJCKDLEMFH G NO感謝下載載精品精品感謝下載載感謝下載載6.11已知某二叉樹(shù)的中序序列為 DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請(qǐng)畫(huà)出該二叉樹(shù)。AB IC G H JKE F6.14 假設(shè)某個(gè)電文由(a,b,c,d,e,f,g,h)8 個(gè)字母組成，每個(gè)字母在電文中出現(xiàn)次數(shù)分別為(7,19,2,6,32,3,21,10) ，試解答下列問(wèn)題：畫(huà)出出huffman 樹(shù)；100060284019b 21g

11G52c 3f

176d 7a

10h

32e寫(xiě)出每個(gè)字母的 huffman 編碼；a:1010b:00c:10000d:1001e:11f:10001g:01h:1011在對(duì)該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17 寫(xiě)出按層次遍歷二叉樹(shù)的算法。StatusLevelOrderTraverse(BitTreeT,Status(*Visit)(TElemTypee)// 層序遍歷二叉樹(shù){InitQueue(Q);// 初始化隊(duì)列if(!T) returnError;// 空樹(shù)，直接返EnQueue(Q,T);// 根結(jié)點(diǎn)入隊(duì)BiTNode*p;while(!QueueEmpty(Q)){DeQueue(Q,p);Visit(p->data);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) }//whilereturnOk;}//LevelOrderTraverse6.19 寫(xiě)出判斷兩棵給定二叉樹(shù)是否相似的算法。(注：兩棵二叉樹(shù) B1和B2相似是指：B1和B2皆空，或者皆不空且 B1的左右子樹(shù)和B2的左、右子樹(shù)分別相似。 )思路：采用遞歸進(jìn)行比較判斷boolBiTreeSimilar(BiTreeT1,BiTreeT2){if(T1==Null&&T2==Null)return1;elseif(T1==Null||T2==Null)return0;elsereturn(BiTreeSilimar(T1->lchild,T2->lchild)&&BiTreeSimilar(T1->rchild,T2->rchild));}6.21 寫(xiě)出統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法，樹(shù)用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結(jié)點(diǎn)的 firstchild 為Null，則為葉子結(jié)點(diǎn)；采用遞歸方法。intCountLeaves(TreeT ，int&num)//num 傳遞的初值為 0{if(T->nextsibling!=Null)num+=CountLeaves(T->nextsibling);if(T->firstchild!=Null)num+=CountLeaves(T->firstchild);elsenum+=1;//firstchild 域?yàn)榭?，則為葉子結(jié)點(diǎn)returnnum;}V1V5V1V5V6V2V4V37-1已知有向圖如圖 7-1所示請(qǐng)給出該圖的鄰接矩陣示意圖鄰接表示意圖逆鄰接表所有強(qiáng)連通分量(1) 鄰接矩陣000000100100010001001011100000110010（2）鄰接表0 v1 <1 v2 3 0 <2 v3 5 1