?PAGE294?數據結構(C語言)微課版?PAGE293?附錄習題參考答案附錄習題參考答案第1章習題參考答案一、選擇題1.C2.C3.B4.A5.D6.D7.C8.C9.B10.C二、填空題1.線性結構非線性結構 2.順序存儲結構鏈式存儲結構3.聯系圖（或圖結構） 4.集合、圖5.一對一一對多 6.數據元素關系7.后繼任意多個 8.操作對象關系9.沒有沒有 10.邏輯結構存儲結構11.前驅1 12.順序索引三、判斷題1.×2.√3.×4.×四、簡答題1.因為x++共執行了n-1+n-2+……＋1=n(n-1)/2，所以執行時間為O（n2）2.O（log3n） 3.O（n2） 4.O（m*n）第2章習題參考答案一、選擇題1.D2.B3.B4.B5.B6.B7.D8.B9.C10.B11.C12.C13.B14.D15.C16.B17.B18.C19.A20.C21.D22.A23.A24.C二、填空題1.首元素其直接前驅結點的鏈域的值 2.HL→next==NULL；HL==HL→next3.有限、一對一 4.O(1)隨機存取5.表中一半表長和該元素在表中的位置 6.必定不一定7.O（1）O（n） 8.前驅結點的地址O（n）9.n-i+1n-i 10.s->left=pp->right三、判斷題1.×2.×3.×4.×5.×6.×7.√8.×9.×10.×11.×四、簡答題1.線性表為：（78，50，40，60，34，90）2.(36,12,8,50,25,5,15)3.解答：尾指針是指向終端結點的指針，用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環鏈表，其尾指針為rear，則開始結點和終端結點的位置分別是rear->next->next和rear,查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結點的時間為O(n)。五、編程題1.解答：由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數單鏈表中的結點個數了。算法如下：intListLength(LinkListL){intlen=0;ListNode*p;p=L;//設該表有頭結點while(p->next){p=p->next;len++;}returnlen;}2.intsearchmin(linklistl){intmin;int*p;p=l;min=p->data;p=p->next;while(p->next!=NULL){if(min>p->data)min=p->data;p=p->next;}returnmin;}3.intsearchmax(linklistl){intmax;int*p;p=l;max=p->data;p=p->next;while(p->next!=NULL){if(max<p->data)max=p->data;p=p->next;}returnmax;}4.順序表：要將該表逆置，可以將表中的開始結點與終端結點互換，第二個結點與倒數第二個結點互換，如此反復，就可將整個表逆置了。算法如下：voidReverseList(Seqlist*L){DataTypetemp;//設置臨時空間用于存放datainti;for(i=0;i<=L->length/2;i++)//L->length/2為整除運算{temp=L->data[i];//交換數據L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=temp;}}5.intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計數器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環時i中的值即為x結點個數returni;}//CountX6.解答：因已知順序表L是遞增有序表，所以只要從順序表終端結點（設為i位置元素）開始向前尋找到第一個小于或等于x的元素位置i后插入該位置即可。在尋找過程中，由于大于x的元素都應放在x之后，所以可邊尋找，邊后移元素，當找到第一個小于或等于x的元素位置i時，該位置也空出來了。算法如下：voidInsertIncreaseList(Seqlist*L,Datatypex){inti;if(L->length>=ListSize)Error("overflow");for(i=L->length-1;i>0&&L->data[i-1]>x;i--)L->data[i+1]=L->data[i];//比較并移動元素L->data[i]=x;L->length++;}第3章習題參考答案一、選擇題1.A2.C3.B4.B5.A6.B7.C8.C9.B10.D11.B12.D13.B14.D15.A16.B17.D18.C19.C20.B21.B二、填空題1.隊列 2.FILOFIFO3.棧頂棧底 4.前一個位置/當前位置；n-15.尾首 6.隊尾隊頭7.線性表后進先出表 8.s->next=h->nexth-next=s;9.q->front->next=NULL q->rear=q->front; 10.stack三、判斷題1.×2.√3.√4.×5.√6.√7.√8.√9.×10.×四、簡答題1.順序隊列的結構:typedefstruct{datatypedata[maxsize]intfront,rear;}sequeue;sequeue*sq;2.解答：鏈棧不需要在頭部附加頭結點，因為棧都是在頭部進行操作的，如果加了頭結點，等于要對頭結點之后的結點進行操作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。3.(1)出棧序列為：1324(2)不能得到1423序列。因為要得到14的出棧序列，則應做Push(1)，Pop()，Push(2)，Push(3)，Push(4)，Pop()。這樣，3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：Push(1)，Pop()，Push(2)，Push(3)，Push(4)，Pop()，Pop()，Pop()。4.用隊列長度計算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=325.答：該算法的功能是：利用堆棧做輔助，將隊列中的數據元素進行逆置。6.棧是僅允許在一端進行插入和刪除的線性表，又稱為后進先出表。隊列是允許在一端插入，在另一端刪除的線性表，允許插入的一端的稱為隊尾，允許刪除的一端稱為隊頭，又稱為先進先出表。7.順序棧的結構:typedefintdatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop}seqstack;seqstack*s;8.解答：循環隊列的優點是：它可以克服順序隊列的"假上溢"現象，能夠使存儲隊列的向量空間得到充分的利用。判別循環隊列的"空"以頭尾指針是否相等來確定；判別循環隊列的"滿"通過少用一個元素的空間，每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。9.隊滿條件:(q->rear+1)%m==q->front隊空條件:q->front==q=>rear10.解答：算法如下voidClearStack(SeqStack*S){//刪除棧中所有結點S->top=-1;//其實只是將棧置空}

因為要置空的是棧S，如果不用指針來做參數傳遞，那么函數進行的操作不能對原來的棧產生影響，系統將會在內存中開辟另外的單元來對形參進行函數操作。結果等于什么也沒有做。所以想要把函數操作的結果返回給實參的話，就只能用指針來做參數傳遞了。五、編程題1.linkstack*POPSTACK(linkstack*HS,datatype*data){linkstack*pif(HS==NULL){printf("underflow");returnNULL;)}else{*data=HS->data;p=HS;HS=HS->next;free(p);returnHS;}}2.intENQUEUE(sequeue*sq,datatypex){if(sq->front==(sq->rear+1)%maxsize){printf("queueisfull");returnNULL;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;returnTRUE;}}3.datatypeDEQUEUE(sequeue*sq){if(sq->front==sq->rear){printf("queueisempty");}else{sq->front=(sq->front+1)%maxsize;return(sq->data[sq->front];}}4.解答：根據題意，可定義該循環隊列的存儲結構：#defineQueueSize100

typedefcharDatatype;//設元素的類型為char型typedefstruct{intquelen;intrear;DatatypeData[QueueSize];}CirQueue;CirQueue*Q;循環隊列的隊滿條件是：Q->quelen==QueueSize知道了尾指針和元素個數，當然就能計算出隊頭元素的位置。算法如下：(1)判斷隊滿intFullQueue(CirQueue*Q){//判隊滿,隊中元素個數等于空間大小returnQ->quelen==QueueSize;}(2)入隊voidEnQueue(CirQueue*Q,Datatypex){if(FullQueue(Q))Error("隊已滿，無法入隊");Q->Data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;//在循環意義上的加1Q->quelen++;}(3)出隊DatatypeDeQueue(CirQueue*Q){inttmpfront;//設一個臨時隊頭指針if(Q->quelen==0)Error("隊已空，無元素可出隊");tmpfront=(QueueSize+Q->rear-Q->quelen+1)%QueueSize;//計算頭指針位置Q->quelen--;returnQ->Data[tmpfront];}第4章習題參考答案一、填空題1.元素值 2.333.p;(k,p,h); 4.(a,b)(b,c)5.x((x,y)) 6.((c,d))(b)7.(a,b)(c,d) 8.b（d）二、選擇題1.A2.D3.D4.B第5章習題參考答案一、選擇題1.C2.C3.B4.C5.C6.D7.A8.D9.A10.A11.C12.B13.B14.B15.D16.D17.C18.A19.D20.D21.C22.B23.C24.C二、填空題1.前趨（雙親）根 2.左右不能3.子樹個數5 4.有序N-15.2h-12h-1 6.501007.416 8.后繼任意多個9.6332 10.A[2*i+1]A[(i-1)/2]11.2nn-1 12.二叉樹13.500、499 14.O(n)35015.n、logkn+1 16.i/22i+117.133 18.9519.（3h－1）/2 20.LRD、FEGHDCB21.n1+n2=0+n2=n0-1=3126-1=32三、判斷題1.×2.×3.√4.√5.×6.√7.√8.×9.×10.√11.√12.√13.×14.×15.√16.×17.×18.×19.√20.√21.√22.√23.×24.×25.×26.√四、簡答題1.此二叉樹的后序遍歷結果是：EDCBIHJGFA2.先序遍歷序列為：ABCDFEGHIJKLM中序遍歷序列為：CFDEBGJILMKHA后序遍歷序列為：FEDCJMLKIHGBA3.后序：16,24,42,57,53,35,88,84,92,604.高度為h的完全二叉樹至少有2h-1個結點，至多有2h-1個結點(也就是滿二叉樹)。5.有五種。6.（1）3;2 （2）4;E,F,I,J,H （3）A,C （4）C,D;E,F7.度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結點只有一個孩子，就無需區分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。8.解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應前序遍歷序列中的元素集合，可繼續確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。9.答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA10.三個結點的樹有：三個結點的二叉樹有：11.注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結點一律歸入左子樹，新添連線結點一律歸入右子樹。12.13.注意根右邊的子樹肯定是森林，而孩子結點的右子樹均為兄弟。14.（1）有無左子樹 （2）有只有根節點 （3）有無右子樹15.16.這是“先根再左再根再右”，比前序遍歷多打印各結點一次，輸出結果為：ABCCEEBADFFDGG特點：①每個結點肯定都會被打印兩次；②但出現的順序不同，其規律是：凡是有左子樹的結點，必間隔左子樹的全部結點后再重復出現；如A，B，D等結點。反之馬上就會重復出現。如C，E，F，G等結點。時間復雜度以訪問結點的次數為主，精確值為2*n，時間漸近度為O(n)。17.18.解：要遵循中序遍歷的軌跡來畫出每個前驅和后繼。中序遍歷序列：554025602808335419.解：先將概率放大100倍，以方便構造哈夫曼樹。w={7,19,2,6,32,3,21,10}，按哈夫曼規則：[(19,21),[[[(2,3)，6],(7,10)],32]]字母編號對應編碼出現頻率110100.072000.193100000.02410010.065110.326100010.037010.21810110.1020.五、編程題1.INORDER(bitree*t){if(t){INORDER(t->lchild);printf("%c",t->data);INORDER(t->rchild);}}2.BtreeDepth(BT->left)BtreeDepth(BT->right)dep1+1dep2+13.求二叉樹高度算法intHIGH(bintree*tree){intm=0;k=0;l=0if(tree==NULL)m=0elsem=1if(tree->lchild!=NULL)k=HIGH(tree->lchild);if(tree->rchild!=NULL)l=HIGH(tree->rchild);if(k>l)m=k+1;elsem=l+1return(m);}4.typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==NULL&&bt2==NULL)return(1);elseif(bt1==NULL||bt2==NULL||bt1->data!=bt2->data)retu