數(shù)據(jù)結構(C語言版)習題解答參考范本

精品精品感謝下載載感謝下載載1.3 設n是正整數(shù)。試寫出下列程序段中用記號“ △”標注的語句的頻度：(2) i=1;k=0;do{△ k+=10*i;i++;}while(i<=n-1)當n=1 時，執(zhí)行1；當n>=2 時，執(zhí)行n-1 次；(3) i=1;k=0;do{△ k+=10*i;i++;}while(i==n);當n=2 時，執(zhí)行2次；當n!=2 時，執(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語句執(zhí)行100次(7) for(i=0;i<n;i++)for(j=i;j<n;j++)for(k=j;k<n;k++)過程：

n1ni0ji

△ x+=2;(n j) n(n 1)(n 2)6第二章2.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將元素 x到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲空間是否滿，若滿返回 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àn)順序表的就地逆置，即在原表的存儲空間將線性表（,a2,...,an-1,an）(an,an-1,...,a2,a1)//思路就是兩個指示變量 i，j同時分別從順序表的開始和結尾處相向改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采用順序存儲結構存放，對兩種不同情況分別寫出算法，刪除L中多余的元素，使得L中沒有重復元素：（1）L中數(shù)據(jù)元素無序排列；(2)L數(shù)據(jù)元素非遞減有序排列。voidDelete_SameElem(SqLink&L,intL.length){//內層循環(huán)移動參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個表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--;// 移動元素后，由于少了一個元素，因此要減 1}}//endifIf(L.Elem[j]>L.Elem[i])break;// 第二小問添加此句}//endfor}//endwhile}//endfunctoion已知線性表L采用鏈式結構存放。對兩種不同情況分別寫出算法，刪除L值相同的多余元素，使得L中沒有重復元素：(1)L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。（1）L中數(shù)據(jù)元素無序排列；思路：由于是無序排列，需要線性表中每個元素都要相互進行比較。StatusListDelete （Linklist&L ）//L是帶頭結點的線性表{ElemType*p,*q;p==L->next;q=p->next;// 設定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;// 開始后一結點的尋找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// 和第一問不同地方q=p->next;}//ifelse{while(p->data==q->data)q=q->next;// 多個連續(xù)的重復值}//elsep->next=q;p=q;q=p->next;// 刪除值重復的結點，并修改相應的指針returnOK ；}//ListDelete設有兩個非遞減有序的單鏈表 A,B請寫出算法，將A和B就地歸并成一按元素值非遞增有序的單鏈表。// 將合并逆置后的結果放在 C表中，并刪除 B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驅指針qb=pb;//保存pb的前驅指針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; //將當前最小結點插入 A表表頭A->next=qa;}else{qb=pb;pb=pb->next;qb->next=A->next; //將當前最小結點插入 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 設以帶頭結點的雙向循環(huán)鏈表表示的線性表 L=(a1,a2,a3)。試寫一間復雜度為O(n)的算法，將L改造為L=(a1,a3,a2)。voidReform(DuLinkedList&L)// 按1,3,5,...4,2 的順序重排雙向循環(huán)鏈表 L中的所有結點{p=L.next;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;}//p指向最后一個奇數(shù)結點if(p->next==L)// 結點個數(shù)是奇數(shù)，使最后一個奇數(shù)結點 next指向最后一個偶數(shù)結點p->next=L->pre->pre;else//結點個數(shù)是偶數(shù)，使最后一個奇數(shù)結點 next指向最后一個偶數(shù)結點p->next=L->pre;p=p->next;// 此時p 指向最后一個偶數(shù)結點while(p->pre->pre!=L){p->next=p->pre->pre;p=p->next;}p->next=L;// 最后一個結點 next指向頭結點//調整了next 鏈的結構此時pre 鏈仍為原狀//調整pre 鏈的結構for(p=L;p->next!=L;p=p->next)p->next->pre=p;L->pre=p// 頭結點的prea2結點}//Reform第三章 棧和隊列試寫一個算法，識別依次讀入的一個以 @為結束符的字符序列是否為形如“序列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ù)據(jù)元素為字的順序表中。算法：StatusBracketTest(char*str)// 判別表達式中三種括號是否匹配{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;//必須與當前棧頂括號匹配}//if}//forif(!StackEmpty(s))returnERROR;//進棧的符號還有剩余， ErrorreturnOK;}//BracketTest設表達式由單字母變量、雙目運算符和圓括號組成（如 試寫一個算法，將一個書寫正確的表達式轉換為逆波蘭式。思路：遇到數(shù)字直接發(fā)送 .遇到(直接入棧 .遇到)則將棧內元素發(fā)送直至遇到 (.棧則直接入棧 5.棧非空時若優(yōu)先級大于棧內則入棧，否則棧內元素出棧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++相抵消，使得棧內優(yōu)先級大于等于棧外的都出棧}}//endswitch}//endexp++;}//endwhilewhile(!IsEmpty(s))suffix[i++]=pop(s);suffix[i]=0;}假設以帶頭結點的單循環(huán)鏈表表示隊列，只設一個尾指針指向隊尾元素，不設頭指針。試編寫相應的隊列初始化、 入隊和出隊算法（在出隊算法中要傳隊頭元素的值）要點：定義好數(shù)據(jù)類型，帶頭結點的單循環(huán)鏈表，只有尾指針，注意刪除元素時只有一個元素的特殊性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分別指示隊尾元素和隊列長度。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法（在出隊算法中要傳遞回隊頭元素的值）此循環(huán)隊列的隊滿條件： Q.length==MAXQSIZE;入隊算法：StatusEnCyQueue(CyQueue&Q,intx)// 帶length 域的循環(huán)隊列入隊算法{if(Q.length==MAXSIZE) returnOVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.base[Q.rear]=x;//rear 指向隊尾元素Q.length++;returnOK;}//EnCyQueue出隊算法：StatusDeCyQueue(CyQueue&Q,int&x)// 帶length 域的循環(huán)隊列出隊算法，用 x返回隊元素的值{if(Q.length==0) returnError;// 空隊列，錯誤head=(Q.rear-Q.length+1)%MAXSIZE;//head 指向隊x=Q.base[head];Q.length--;returnOK }//DeCyQueue試寫一個算法：判別讀入的一個以‘ @’為結束符的字符序列是否是“回文所謂“回文”是指正讀和反讀都相同的字符序列，如“ xxyzyxx”是回文而“abcab”則不是回文）。StatusTest()// 判別輸入的字符串是否回文序列 是則返回1,否則返回0{InitStack(S);InitQueue(Q);while((c=getchar())!='@'){Push(S,c);EnQueue(Q,c);// 同時使用棧和隊列兩種結構}while(!StackEmpty(S)){精品Pop(S,a);DeQueue(Q,b);if(a!=b) returnERROR;}returnOK;}//Test第五章 多維數(shù)組設有一個準對角矩陣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感謝下載載精品寫出由一對下標(i,j)求k的轉換公式。因為 i 行前有 2(i-1) 個元素?，F(xiàn)考慮 i 行情況，當 j 是奇數(shù)，i 行有 1 個素,k=2(i-1)+1-1=2(i-1) ；否則i行有2個元素，k=2(i-1)+2-1=2i-1 。故：k=或若i為奇數(shù)，k=2(i-1)+j-i=i+j-2; 當i為偶數(shù)時，k=2i-(i-j)-1=i+j-1k=已知稀疏矩陣A4×5如下：0101005230600000004007用三元組表作為存儲結構，繪出相應的三元組表示意圖；用十字鏈表作為存儲結構，繪出相應的十字鏈表示意圖。三元組表：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ù)和二叉樹6.5 已知一棵度為 k的樹中有n1個度為1的結點，n2個度為2的結點，nk個度為k的結點，問該樹中有多少個葉子結點？設葉子結點有x個，則樹的結點總數(shù)為n1+n2+ 同時除了根結點外，每個結點都指向一個結點，所有從這個角度考慮樹的結點總數(shù)為：n1+2?n2+?k?nk+1;n1+n2+ n1+2 +,可得x=

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

11G52c 3f

176d 7a

10h

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

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

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

（將該項看作一項混入原有序列中，問題轉變成 n+1個元素序列的成功查找問題）n2．1[1+2+...+n

n+123. 1

+2+...+n

(k-

n-1)]=

k+2

將此K項看作一項n-(k-1) 2對無序順序表：1. n1

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

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

n+k=

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

2 n

k2畫出對長度為 17的有序表進行折半查找的判定樹，并分別求其等概率時查找長度和找失敗的ASL。1 59解：ASL=171 2?2 4 4?8 5?2) 171 76ASL18(47 ?2 47 52) 18 增加虛結點94 132 6 11 151 3 5 7 10 12 14 168 17已知如下所示長度為 12的表Jan，F(xiàn)eb，Apr，May，Jun，July，Sept，Oct，Nov，Dec）表中，每一個元素的查找概率分別為： （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）若對該表進行順序查找，求查找成功的平均查找長度；（2）畫出從初態(tài)為空開始，依次插入結點，生成的二叉排序樹；（3）計算該二叉排序樹查找成功的平均查找長度；（4）將二叉排序樹中的結點 Mar 刪除，畫出經(jīng)過刪除處理后的二叉排序樹。1）

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

Jun

SepAug

July

OctDec

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

17 3?1 3?139 9=(F

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

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

97 1 5?3(3)033123254375496060678199101076ASL

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

n1ni0ji

△ x+=2;(n j) n(n 1)(n 2)6第二章2.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將元素 x到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲空間是否滿，若滿返回 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àn)順序表的就地逆置，即在原表的存儲空間將線性表（,a2,...,an-1,an）(an,an-1,...,a2,a1)//思路就是兩個指示變量 i，j同時分別從順序表的開始和結尾處相向改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采用順序存儲結構存放，對兩種不同情況分別寫出算法，刪除L中多余的元素，使得L中沒有重復元素：（1）L中數(shù)據(jù)元素無序排列；(2)L數(shù)據(jù)元素非遞減有序排列。voidDelete_SameElem(SqLink&L,intL.length){//內層循環(huán)移動參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個表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--;// 移動元素后，由于少了一個元素，因此要減 1}}//endifIf(L.Elem[j]>L.Elem[i])break;// 第二小問添加此句}//endfor}//endwhile}//endfunctoion已知線性表L采用鏈式結構存放。對兩種不同情況分別寫出算法，刪除L值相同的多余元素，使得L中沒有重復元素：(1)L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。（1）L中數(shù)據(jù)元素無序排列；思路：由于是無序排列，需要線性表中每個元素都要相互進行比較。StatusListDelete （Linklist&L ）//L是帶頭結點的線性表{ElemType*p,*q;p==L->next;q=p->next;// 設定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;// 開始后一結點的尋找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// 和第一問不同地方q=p->next;}//ifelse{while(p->data==q->data)q=q->next;// 多個連續(xù)的重復值}//elsep->next=q;p=q;q=p->next;// 刪除值重復的結點，并修改相應的指針returnOK ；}//ListDelete設有兩個非遞減有序的單鏈表 A,B請寫出算法，將A和B就地歸并成一按元素值非遞增有序的單鏈表。// 將合并逆置后的結果放在 C表中，并刪除 B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驅指針qb=pb;//保存pb的前驅指針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; //將當前最小結點插入 A表表頭A->next=qa;}else{qb=pb;pb=pb->next;qb->next=A->next; //將當前最小結點插入 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 設以帶頭結點的雙向循環(huán)鏈表表示的線性表 L=(a1,a2,a3)。試寫一間復雜度為O(n)的算法，將L改造為L=(a1,a3,a2)。voidReform(DuLinkedList&L)// 按1,3,5,...4,2 的順序重排雙向循環(huán)鏈表 L中的所有結點{p=L.next;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;}//p指向最后一個奇數(shù)結點if(p->next==L)// 結點個數(shù)是奇數(shù)，使最后一個奇數(shù)結點 next指向最后一個偶數(shù)結點p->next=L->pre->pre;else//結點個數(shù)是偶數(shù)，使最后一個奇數(shù)結點 next指向最后一個偶數(shù)結點p->next=L->pre;p=p->next;// 此時p 指向最后一個偶數(shù)結點while(p->pre->pre!=L){p->next=p->pre->pre;p=p->next;}p->next=L;// 最后一個結點 next指向頭結點//調整了next 鏈的結構此時pre 鏈仍為原狀//調整pre 鏈的結構for(p=L;p->next!=L;p=p->next)p->next->pre=p;L->pre=p// 頭結點的prea2結點}//Reform第三章 棧和隊列試寫一個算法，識別依次讀入的一個以 @為結束符的字符序列是否為形如“序列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ù)據(jù)元素為字的順序表中。算法：StatusBracketTest(char*str)// 判別表達式中三種括號是否匹配{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;//必須與當前棧頂括號匹配}//if}//forif(!StackEmpty(s))returnERROR;//進棧的符號還有剩余， ErrorreturnOK;}//BracketTest設表達式由單字母變量、雙目運算符和圓括號組成（如 試寫一個算法，將一個書寫正確的表達式轉換為逆波蘭式。思路：遇到數(shù)字直接發(fā)送 .遇到(直接入棧 .遇到)則將棧內元素發(fā)送直至遇到 (.棧則直接入棧 5.棧非空時若優(yōu)先級大于棧內則入棧，否則棧內元素出棧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++相抵消，使得棧內優(yōu)先級大于等于棧外的都出棧}}//endswitch}//endexp++;}//endwhilewhile(!IsEmpty(s))suffix[i++]=pop(s);suffix[i]=0;}假設以帶頭結點的單循環(huán)鏈表表示隊列，只設一個尾指針指向隊尾元素，不設頭指針。試編寫相應的隊列初始化、 入隊和出隊算法（在出隊算法中要傳隊頭元素的值）要點：定義好數(shù)據(jù)類型，帶頭結點的單循環(huán)鏈表，只有尾指針，注意刪除元素時只有一個元素的特殊性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分別指示隊尾元素和隊列長度。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊和出隊算法（在出隊算法中要傳遞回隊頭元素的值）此循環(huán)隊列的隊滿條件： Q.length==MAXQSIZE;入隊算法：StatusEnCyQueue(CyQueue&Q,intx)// 帶length 域的循環(huán)隊列入隊算法{if(Q.length==MAXSIZE) returnOVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.base[Q.rear]=x;//rear 指向隊尾元素Q.length++;returnOK;}//EnCyQueue出隊算法：StatusDeCyQueue(CyQueue&Q,int&x)// 帶length 域的循環(huán)隊列出隊算法，用 x返回隊元素的值{if(Q.length==0) returnError;// 空隊列，錯誤head=(Q.rear-Q.length+1)%MAXSIZE;//head 指向隊x=Q.base[head];Q.length--;returnOK }//DeCyQueue試寫一個算法：判別讀入的一個以‘ @’為結束符的字符序列是否是“回文所謂“回文”是指正讀和反讀都相同的字符序列，如“ xxyzyxx”是回文而“abcab”則不是回文）。StatusTest()// 判別輸入的字符串是否回文序列 是則返回1,否則返回0{InitStack(S);InitQueue(Q);while((c=getchar())!='@'){Push(S,c);EnQueue(Q,c);// 同時使用棧和隊列兩種結構}while(!StackEmpty(S)){精品Pop(S,a);DeQueue(Q,b);if(a!=b) returnERROR;}returnOK;}//Test第五章 多維數(shù)組設有一個準對角矩陣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感謝下載載精品寫出由一對下標(i,j)求k的轉換公式。因為 i 行前有 2(i-1) 個元素?，F(xiàn)考慮 i 行情況，當 j 是奇數(shù)，i 行有 1 個素,k=2(i-1)+1-1=2(i-1) ；否則i行有2個元素，k=2(i-1)+2-1=2i-1 。故：k=或若i為奇數(shù)，k=2(i-1)+j-i=i+j-2; 當i為偶數(shù)時，k=2i-(i-j)-1=i+j-1k=已知稀疏矩陣A4×5如下：0101005230600000004007用三元組表作為存儲結構，繪出相應的三元組表示意圖；用十字鏈表作為存儲結構，繪出相應的十字鏈表示意圖。三元組表：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ù)和二叉樹6.5 已知一棵度為 k的樹中有n1個度為1的結點，n2個度為2的結點，nk個度為k的結點，問該樹中有多少個葉子結點？設葉子結點有x個，則樹的結點總數(shù)為n1+n2+ 同時除了根結點外，每個結點都指向一個結點，所有從這個角度考慮樹的結點總數(shù)為：n1+2?n2+?k?nk+1;n1+n2+ n1+2 +,可得x=

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

11G52c 3f

176d 7a

10h

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