數(shù)據(jù)結構課程課后習題的答案

...wd......wd......wd...?數(shù)據(jù)構造簡明教程?練習題及參考答案練習題11.單項選擇題〔1〕線性構造中數(shù)據(jù)元素之間是〔〕關系。A.一對多B.多對多C.多對一D.一對一答：D〔2〕數(shù)據(jù)構造中與所使用的計算機無關的是數(shù)據(jù)的〔〕構造。A.存儲B.物理C.邏輯D.物理和存儲答：C〔3〕算法分析的目的是〔〕。A.找出數(shù)據(jù)構造的合理性B.研究算法中的輸入和輸出的關系C.分析算法的效率以求改進D.分析算法的易懂性和文檔性答：C〔4〕算法分析的兩個主要方面是〔〕。A.空間復雜性和時間復雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性答：A〔5〕計算機算法指的是〔〕。A.計算方法B.排序方法C.求解問題的有限運算序列D.調(diào)度方法答：C〔6〕計算機算法必須具備輸入、輸出和〔〕等5個特性。A.可行性、可移植性和可擴大性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性答：B2.填空題〔1〕數(shù)據(jù)構造包括數(shù)據(jù)的①、數(shù)據(jù)的②和數(shù)據(jù)的③這三個方面的內(nèi)容。答：①邏輯構造②存儲構造③運算〔2〕數(shù)據(jù)構造按邏輯構造可分為兩大類，它們分別是①和②。答：①線性構造②非線性構造〔3〕數(shù)據(jù)構造被形式地定義為〔D,R〕，其中D是①的有限集合，R是D上的②有限集合。答：①數(shù)據(jù)元素②關系〔4〕在線性構造中，第一個結點①前驅(qū)結點，其余每個結點有且只有1個前驅(qū)結點；最后一個結點②后繼結點，其余每個結點有且只有1個后繼結點。答：①沒有②沒有〔5〕在樹形構造中，樹根結點沒有①結點，其余每個結點有且只有②個前驅(qū)結點；葉子結點沒有③結點，其余每個結點的后繼結點數(shù)可以是④。答：①前驅(qū)②1③后繼④任意多個〔6〕在圖形構造中，每個結點的前驅(qū)結點數(shù)和后繼結點數(shù)可以是〔〕。答：任意多個〔7〕數(shù)據(jù)的存儲構造主要有四種，它們分別是①、②、③和④存儲構造。答：①順序②鏈式③索引④哈?！?〕一個算法的效率可分為①效率和②效率。答：①時間②空間3.簡答題〔1〕數(shù)據(jù)構造和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎答：簡單地說，數(shù)據(jù)構造定義了一組按某些關系結合在一起的數(shù)組元素的集合。數(shù)據(jù)類型不僅定義了一組數(shù)據(jù)元素，而且還在其上定義了一組操作?！?〕簡述線性構造、樹形構造和圖形構造的不同點。答：線性構造反映結點間的邏輯關系是一對一的，樹形線性構造反映結點間的邏輯關系是一對多的，圖在構造反映結點間的邏輯關系是多對多的?！?〕設有采用二元組表示的數(shù)據(jù)邏輯構造S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，問相對于關系R，哪些結點是開場結點，哪些結點是終端結點答：該邏輯構造為樹形構造，其中a結點沒有前驅(qū)結點，稱為根結點，b、e、g、i結點沒有后繼結點，是終端結點，也稱為葉子結點?！?〕以下各函數(shù)是算法中語句的執(zhí)行頻度，n為問題規(guī)模，給出對應的時間復雜度：T1(n)=nlog2n-1000log2nT2(n)=-1000log2nT3(n)=n2-1000log2nT4(n)=2nlog2n-1000log2n答：T1(n)=O(nlog2n)，T2(n)=O()，T3(n)=O(n2)，T4(n)=O(nlog2n)?！?〕分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。intj=0,s=0,n=100;do{ j=j+1; s=s+10*j;}while(j<n&&s<n);答：j=0，第1次循環(huán)：j=1，s=10。第2次循環(huán)：j=2，s=30。第3次循環(huán)：j=3，s=60。第4次循環(huán)：j=4，s=100。while條件不再滿足。所以，其中循環(huán)語句的執(zhí)行次數(shù)為4?！?〕執(zhí)行下面的語句時，語句s++的執(zhí)行次數(shù)為多少ints=0;for(i=1;i<n-1;i++) for(j=n;j>=i;j--)s++;答：語句s的執(zhí)行次數(shù)?！?〕設n為問題規(guī)模，求以下算法的時間復雜度。voidfun1(intn){ intx=0,i; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++)x++;}答：其中x++語句屬基本運算語句，=O(n2)。〔8〕設n為問題規(guī)模，是一個正偶數(shù)，試計算以下算法完畢時m的值，并給出該算法的時間復雜度。voidfun2(intn){ intm=0;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;}答：由，該程序段的時間復雜度為O(n2)。上機實驗題1有一個整型數(shù)組a，其中含有n個元素，設計盡可能好的算法求其中的最大元素和次大元素，并采用相關數(shù)據(jù)測試。解：maxs算法用于返回數(shù)組a[0..n-1]中的最大元素值max1和次大元素值max2，max1和max2設計為引用類型。對應的程序如下：#include<stdio.h>voidmaxs(inta[],intn,int&max1,int&max2){ inti; max1=max2=a[0]; for(i=1;i<n;i++) if(a[i]>max1) { max2=max1; max1=a[i]; } elseif(a[i]>max2) max2=a[i];}voidmain(){ inta[]={1,4,10,6,8,3,5,7,9,2}; intn=10; intmax1,max2;maxs(a,n,max1,max2); printf("最大元素值=%d,次大元素值=%d\n",max1,max2);}練習題21.單項選擇題〔1〕數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相對順序一樣并且是連續(xù)的，稱之為〔〕。A.存儲構造B.邏輯構造C.順序存儲構造D.鏈式存儲構造答：C〔2〕在n個結點的順序表中，算法的時間復雜度是O〔1〕的操作是〔〕。A.訪問第i個結點〔1≤i≤n〕和求第i〔2≤i≤n〕個結點的前驅(qū)結點B.在第i〔1≤i≤n〕個結點后插入一個新結點C.刪除第i個結點〔1≤i≤n〕D.將n個結點從小到大排序答：A〔3〕向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動〔〕個元素。A.8B.63.5C.63D.7答：B〔4〕鏈式存儲構造所占存儲空間〔〕。A.分兩局部，一局部存放結點值，另一局部存放表示結點間關系的指針B.只有一局部，存放結點值C.只有一局部，存儲表示結點間關系的指針D.分兩局部，一局部存放結點值，另一局部存放結點所占單元數(shù)答：A〔5〕線性表假設采用鏈式存儲構造時，要求內(nèi)存中可用存儲單元的地址〔〕。A.必須是連續(xù)的B.局部地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答：D〔6〕一個線性表在〔〕情況下適用于采用鏈式存儲構造。A.需經(jīng)常修改其中的結點值B.需不斷對其進展刪除插入C.其中含有大量的結點D.其中結點構造復雜答：B〔7〕單鏈表的存儲密度〔〕A.大于1B.等于1C.小于1D.不能確定答：C2.填空題〔1〕在順序表中插入或刪除一個元素時，需要平均移動〔①〕元素，具體移動的元素個數(shù)與〔②〕有關。答：①表中一半②表長和該元素在表中的位置〔2〕向一個長度為n的順序表的第i個元素〔1≤i≤n+1〕之前插入一個元素時，需向后移動〔〕個元素。答：n-i+1〔3〕向一個長度為n的順序表中刪除第i個元素〔1≤i≤n〕時，需向前移動〔〕個元素。答：n-i〔4〕在順序表中訪問任意一個元素的時間復雜度均為〔①〕，因此順序表也稱為〔②〕的數(shù)據(jù)構造。答：①O(1)②隨機存取〔5〕順序表中邏輯上相鄰的元素的物理位置〔①〕相鄰。單鏈表中邏輯上相鄰的元素的物理位置〔②〕相鄰。答：①一定②不一定〔6〕在帶頭結點的單鏈表中，除頭結點外，任一結點的存儲位置由〔〕指示。答：其前驅(qū)結點的鏈域的值〔7〕在含有n個數(shù)據(jù)結點的單鏈表中要刪除結點*p，需找到它的〔①〕，其時間復雜度為〔②〕。答：①前驅(qū)結點的地址②O(n)〔8〕含有n〔n>1〕個結點的循環(huán)雙向鏈表中，為空的指針域數(shù)為〔〕。答：03.簡答題〔1〕試比較順序存儲構造和鏈式存儲構造的優(yōu)缺點。在什么情況下用順序表比鏈表好答：順序存儲構造中，相鄰數(shù)據(jù)元素的存放地址也相鄰，并要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。其優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈式存儲構造中，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩局部，一局部存放結點值，另一局部存放表示結點間關系的指針。其優(yōu)點是插入或刪除元素時很方便，使用靈活；缺點是存儲密度小，存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。假設線性表的長度變化不大，且其主要操作是查找，那么采用順序表；假設線性表的長度變化較大，且其主要操作是插入、刪除操作，那么采用鏈表?！?〕對于表長為n的順序表，在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需要移動的元素的平均個數(shù)為多少刪除一個元素所需要移動的平均個數(shù)為多少答：插入一個元素所需要移動的元素的平均個數(shù)為(n-1)/2，刪除一個元素所需要移動的平均個數(shù)為n/2?！?〕在鏈表中設置頭結點的作用是什么答：在鏈表中設置頭結點后，不管鏈表是否為空表，頭結點指針均不空，并使得對鏈表的操作〔如插入和刪除〕在各種情況下統(tǒng)一，從而簡化了算法的實現(xiàn)過程?！?〕對于雙鏈表和單鏈表，在兩個結點之間插入一個新結點時需修改的指針各為多少個答：對于雙鏈表，在兩個結點之間插入一個新結點時，需修改前驅(qū)結點的next域、后繼結點的prior域和新插入結點的next、prior域。所以共修改4個指針。對于單鏈表，在兩個結點之間插入一個新結點時，需修改前一結點的next域，新插入結點的next域。所以共修改兩個指針?！?〕某含有n〔n>1〕結點的線性表中，最常用的操作是在尾結點之后插入一個結點和刪除第一個結點，那么采用以下哪種存儲方式最節(jié)省運算時間。①單鏈表；②僅有頭指針不帶頭結點的循環(huán)單鏈表；③雙鏈表；④僅有尾指針的循環(huán)單鏈表。答：在單鏈表中，刪除第一個結點的時間復雜度為O(1)。插入結點需找到前驅(qū)結點，所以在尾結點之后插入一個結點，需找到尾結點，對應的時間復雜度為O(n)。在僅有頭指針不帶頭結點的循環(huán)單鏈表中，刪除第一個結點的時間復雜度O(n)，因為刪除第一個結點后還要將其改為循環(huán)單鏈表；在尾結點之后插入一個結點的時間復雜度也為O(n)。在雙鏈表中，刪除第一個結點的時間復雜度為O(1)；在尾結點之后插入一個結點，也需找到尾結點，對應的時間復雜度為O(n)。在僅有尾指針的循環(huán)單鏈表中，通過該尾指針可以直接找到第一個結點，所以刪除第一個結點的時間復雜度為O(1)；在尾結點之后插入一個結點也就是在尾指針所指結點之后插入一個結點，時間復雜度也為O(1)。因此④最節(jié)省運算時間。4.算法設計題〔1〕設計一個高效算法，將順序表的所有元素逆置，要求算法空間復雜度為O(1)。解：遍歷順序表L的前半局部元素，對于元素L.data[i]〔0≤i＜L.length/2〕，將其與后半局部對應元素L.data[L.length-i-1]進展交換。對應的算法如下：voidreverse(SqList&L){ inti; ElemTypex; for(i=0;i<L.length/2;i++) { x=L.data[i]; //L.data[i]與L.data[L.length-i-1]交換L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=x;}}本算法的時間復雜度為O(n)?！?〕設計一個算法從順序表中刪除重復的元素，并使剩余元素間的相對次序保持不變。解：對于順序表L，用i從1開場遍歷其元素，設L.data[0..j]〔j的初值為0〕中沒有重復的元素。檢測L.data[i]〔j<i<L.length〕，假設L.data[i]和L.data[0..j]中任何一個元素都不一樣，那么將L.data[i]存入L.data[j+1]中。對應的算法如下：voiddelsame(SqList&L)//L為引用型參數(shù){ inti,j=0,k; for(i=1;i<L.length;i++){ k=0; while(k<=j&&L.data[k]!=L.data[i]) k++; if(k>j) //表示L.data[i]和L.data[0..j]中所有元素都不一樣{ j++; L.data[j]=L.data[i]; }}L.length=j+1;//順序表長度置新值}本算法的時間復雜度為O(n2)，空間復雜度為O(1)。〔3〕設計一個算法從有序順序表中刪除重復的元素，并使剩余元素間的相對次序保持不變。解：在有序順序表L中，所有重復的元素應是相鄰存放的，用k保存不重復出現(xiàn)的元素個數(shù)，先將不重復的有序區(qū)看成是L.data[0..0]，置e=L.data[0]，用i從1開場遍歷L的所有元素：當L.data[i]≠e時，將它放在L.data[k]中，k增1，置e=L.data[i]，最后將L的length置為k。對應的算法如下：voiddelsame1(SqList&L) //L為引用型參數(shù){ inti,k=1; //k保存不重復的元素個數(shù) ElemTypee;e=L.data[0]; for(i=1;i<L.length;i++){ if(L.data[i]!=e) //只保存不重復的元素{ L.data[k]=L.data[i];k++; e=L.data[i]; } } L.length=k; //順序表長度置新值}本算法是一個高效算法，其時間復雜度為O(n)，空間復雜度為O(1)。如果每次遇到重復的元素，都通過移動其后所有元素來刪除它，這樣的時間復雜度會變成O(n2)?！?〕設計一個算法刪除單鏈表L中第一個值為x的結點。解：用p、q遍歷整個單鏈表，p指向*q的前驅(qū)結點，q用于查找第一個值為x的結點，當找到后將*q結點刪除，返回1；否那么返回0。對應的算法如下：intdelx(SLink*&L,ElemTypex){ SLink*p=L,*q=p->next; //p指向*q的前驅(qū)結點 while(q!=NULL&&q->data!=x) { p=q; q=q->next; } if(q!=NULL) //找到值為x的結點 { p->next=q->next; free(q); return1; } elsereturn0; //未找到值為x的結點}〔5〕設計一個算法判定單鏈表L是否是遞增的。解：判定鏈表L從第2個結點開場的每個結點的值是否比其前驅(qū)的值大。假設有一個不成立，那么整個鏈表便不是遞增的；否那么是遞增的。對應的算法如下：intincrease(SLink*L){ SLink*pre=L->next,*p; //pre指向第一個數(shù)據(jù)結點 p=pre->next; //p指向*pre結點的后繼結點 while(p!=NULL) { if(p->data>=pre->data) //假設正序那么繼續(xù)判斷下一個結點 { pre=p; //pre、p同步后移 p=p->next; } elsereturn0; } return1;}〔6〕有一個整數(shù)元素建設的單鏈表A，設計一個算法，將其拆分成兩個單鏈表A和B，使得A單鏈表中含有所有的偶數(shù)結點，B單鏈表中所有的奇數(shù)結點，且保持原來的相對次序。解：采用重新單鏈表的方法，由于要保持相對次序，所以采用尾插法建設新表A、B。用p遍歷原單鏈表A的所有數(shù)據(jù)結點，假設為偶數(shù)結點，將其鏈到A中，假設為奇數(shù)結點，將其鏈到B中。對應的算法如下：voidSplit(SLink*&A,SLink*&B){SLink*p=A->next,*ra,*rb; ra=A; B=(SLink*)malloc(sizeof(SLink)); //建設頭結點 rb=B; //r總是指向B鏈表的尾結點 while(p!=NULL) { if(p->data%2==0) //偶數(shù)結點 { ra->next=p; //將*p結點鏈到A中 ra=p; p=p->next; } else //奇數(shù)結點 { rb->next=p; //將*p結點鏈到B中 rb=p; p=p->next; } } ra->next=rb->next=NULL;}本算法的時間復雜度為O(n)，空間復雜度為O(1)?！?〕有一個有序單鏈表〔從小到大排列〕，表頭指針為L，設計一個算法向該單鏈表中插入一個元素為x的結點，使插入后該鏈表仍然有序。解：先建設一個待插入的結點，然后依次與鏈表中的各結點的數(shù)據(jù)域比較大小，找到插入該結點的位置，最后插入該結點。對應的算法如下：voidinorderList(SLink*&L,ElemTypex){ SLink*s,*p,*q; s=(SLink*)malloc(sizeof(SLink));//建設一個待插入的結點 s->data=x;s->next=NULL; if(L==NULL||x<L->data) //假設單鏈表為空或x小于第1個結點date域 { s->next=L; //把*s結點插入到頭結點之后L=s; } else { q=L; //尋找插入位置,p指向待比較的結點,q指向p的前驅(qū)結點 p=q->next; while(p!=NULL&&x>p->data) //假設x小于p所指結點的data域值 if(x>p->data) { q=p; p=p->next; } s->next=p; //將s結點插入到*q和*p之間 q->next=s;}}〔8〕有一個單鏈表L，其中可能出現(xiàn)值域重復的結點，設計一個算法刪除值域重復的結點。并分析算法的時間復雜度。解：用p遍歷單鏈表，用r遍歷*p結點之后的結點，q始終指向*r結點的直接前驅(qū)結點，假設r->data==p->data，那么刪除*r結點，否那么q、r同步后移一個結點。對應的算法如下：voiddels1(SLink*&L){ SLink*p=L->next,*q,*r,*t; while(p!=NULL) { q=p; r=q->next; while(r!=NULL) { if(r->data==p->data) //r指向被刪結點 { t=r->next; q->next=t;free(r); r=t; } else { q=r;r=r->next; } } p=p->next; }}本算法的時間復雜度為O(n2)?！?〕有一個遞增有序單鏈表〔允許出現(xiàn)值域重復的結點〕，設計一個算法刪除值域重復的結點。并分析算法的時間復雜度。解：由于是有序表，所以一樣值域的結點都是相鄰的。用p遍歷遞增單鏈表，假設*p結點的值域等于其后結點的值域，那么刪除后者。對應的算法如下：voiddels(SLink*&L){ SLink*p=L->next,*q; while(p->next!=NULL) { if(p->data==p->next->data) //找到重復值的結點 { q=p->next; //q指向這個重復值的結點 p->next=q->next; //刪除*q結點 free(q); } elsep=p->next; }}本算法的時間復雜度為O(n)?！?0〕有一個雙鏈表L，設計一個算法查找第一個元素值為x的結點，將其與后繼結點進展交換。解：先找到第一個元素值為x的結點*p，q指向其后繼結點，此題是將*p結點移到*q結點之后，實現(xiàn)過程是：刪除*p結點，再將其插入到*q結點之后。對應的算法如下：intswap(DLink*L,ElemTypex){ DLink*p=L->next,*q; while(p!=NULL&&p->data!=x) p=p->next; if(p==NULL) //未找到值為x的結點 return0; else //找到值為x的結點*p { q=p->next; //q指向*p的后繼結點 if(q!=NULL) //*p結點不是尾結點 { p->prior->next=q; //先刪除*p結點 q->prior=p->prior; p->next=q->next; //將*p結點插入到*q結點之后 if(q->next!=NULL) q->next->prior=p; q->next=p; p->prior=q; return1; } else //*p結點是尾結點 return0; //無法與后繼結點交換，返回0 }}〔11〕對于有n〔n≥1〕個數(shù)據(jù)結點的循環(huán)單鏈表L，設計一個算法將所有結點逆置。解：采用頭插法重建循環(huán)單鏈表L的思路，先建設一個空的循環(huán)單鏈表，用p遍歷所有數(shù)據(jù)結點，每次將*p結點插入到前端。對應的算法如下：voidReverse(SLink*&L){ SLink*p=L->next,*q; L->next=L; //建設一個空循環(huán)單鏈表 while(p!=L) { q=p->next; p->next=L->next; //將*p結點插入到前端 L->next=p; p=q; }}上機實驗題2有兩個整數(shù)集合采用有序單鏈表存儲，設計盡可能高效的算法求兩個集合的并集、交集和差集。并用相關數(shù)據(jù)進展測試。#include<stdio.h>#include"SLink.h"voidUnion(SLink*L1,SLink*L2,SLink*&L3) //求并集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } elseif(p->data>q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next; } else { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; q=q->next; } } while(p!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } while(q!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next; } tc->next=NULL;}voidInterSection(SLink*L1,SLink*L2,SLink*&L3) //求交集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) p=p->next; elseif(p->data>q->data) q=q->next; else //p->data=q->data { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; q=q->next; } } tc->next=NULL;}voidSubs(SLink*L1,SLink*L2,SLink*&L3) //求差集{ SLink*p,*q,*s,*tc; L3=(SLink*)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next; while(p!=NULL&&q!=NULL) { if(p->data<q->data) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } elseif(p->data>q->data) q=q->next; else //p->data=q->data { p=p->next; q=q->next; } } while(p!=NULL) { s=(SLink*)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; } tc->next=NULL;}voidmain(){ SLink*A,*B,*C,*D,*E; ElemTypea[]={1,3,6,8,10,20}; CreateListR(A,a,6); //尾插法建表 printf("集合A:");DispList(A); ElemTypeb[]={2,5,6,10,16,20,30}; CreateListR(B,b,7); //尾插法建表 printf("集合B:");DispList(B); printf("求A、B并集C\n"); Union(A,B,C); //求A、B并集C printf("集合C:");DispList(C); printf("求A、B交集C\n"); InterSection(A,B,D); //求A、B并集D printf("集合D:");DispList(D); printf("求A、B差集E\n"); Subs(A,B,E); //求A、B差集E printf("集合E:");DispList(E); DestroyList(A); DestroyList(B); DestroyList(C); DestroyList(D); DestroyList(E);}練習題31.單項選擇題〔1〕棧中元素的進出原那么是〔〕。A.先進先出 B.后進先出C.棧空那么進D.棧滿那么出答：B〔2〕設一個棧的進棧序列是A、B、C、D〔即元素A～D依次通過該棧〕，那么借助該棧所得到的輸出序列不可能是〔〕。A.A,B,C,D B.D,C,B,AC.A,C,D,B D.D,A,B,C答：D〔3〕一個棧的進棧序列是a、b、c、d、e，那么棧的不可能的輸出序列是〔〕。A.edcba B.decba C.dceab D.abcde答：C〔4〕一個棧的進棧序列是1，2，3，…，n，其輸出序列的第一個元素是i〔1≤i≤n〕那么第j〔1≤j≤n〕個出棧元素是〔〕。A.i B.n-iC.j-i+1D.不確定答：D〔5〕設順序棧st的棧頂指針top的初始時為-1，?？臻g大小為MaxSize，那么判定st棧為?？盏臈l件為〔〕。A.st.top==-1 B.st.top!=-1C.st.top!=MaxSize D.st.top==MaxSize答：A〔6〕設順序棧st的棧頂指針top的初始時為-1，?？臻g大小為MaxSize，那么判定st棧為棧滿的條件是。A.st.top!=-1B.st.top==-1C.st.top!=MaxSize-1 D.st.top==MaxSize-1答：D〔7〕隊列中元素的進出原那么是〔〕。A.先進先出B.后進先出C.棧空那么進D.棧滿那么出答：A〔8〕元素A、B、C、D順序連續(xù)進入隊列qu后，隊頭元素是〔①〕，隊尾元素是〔②〕。A.A B.BC.C D.D答：①A②D?！?〕一個隊列的入列序列為1234，那么隊列可能的輸出序列是〔〕。A.4321 B.1234C.1432 D.3241答：B〔10〕循環(huán)隊列qu〔隊頭指針front指向隊首元素的前一位置，隊尾指針rear指向隊尾元素的位置〕的隊滿條件是〔〕。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontA.qu.rear==qu.front答：C〔11〕循環(huán)隊列qu〔隊頭指針front指向隊首元素的前一位置，隊尾指針rear指向隊尾元素的位置〕的隊空條件是〔〕。A.(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D〔12〕設循環(huán)隊列中數(shù)組的下標是0～N-1，其頭尾指針分別為f和r〔隊頭指針f指向隊首元素的前一位置，隊尾指針r指向隊尾元素的位置〕，那么其元素個數(shù)為〔〕。A.r-f B.r-f-1C.(r-f)％N+1 D.(r-f+N)％N答：D〔13〕設有4個數(shù)據(jù)元素a、b、c和d，對其分別進展棧操作或隊操作。在進棧或進隊操作時，按a、b、c、d次序每次進入一個元素。假設?；蜿牭某跏紶顟B(tài)都是空?，F(xiàn)要進展的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是〔①〕，第二次出棧得到的元素是〔②〕；類似地，考慮對這4個數(shù)據(jù)元素進展的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是〔③〕，第二次出隊得到的元素是〔④〕。經(jīng)操作后，最后在棧中或隊中的元素還有〔⑤〕個。①～④：A.a B.b C.c D.d⑤： A.1 B.2 C.3 D.0答：①B②D③A④B⑤B〔14〕設棧S和隊列Q的初始狀態(tài)為空，元素e1～e6依次通過棧S，一個元素出后即進隊列Q，假設6個元素出隊的序列是e2、e4、e3、e6、e5、e1，那么棧S的容量至少應該是〔〕。A.5 B.4 C.3 D.2答：C2.填空題〔1〕棧是一種特殊的線性表，允許插入和刪除運算的一端稱為〔①〕。不允許插入和刪除運算的一端稱為〔②〕。答：①棧頂②棧底〔2〕一個棧的輸入序列是12345，的輸出序列為12345，其進棧出棧的操作為〔〕。答：1進棧，1出棧，2進棧，2出棧，3進棧，3出棧，4進棧，4出棧，5進棧，5出棧。〔3〕有5個元素，其進棧次序為A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出?！布碈第一個且D第二個出?！车拇涡蛴小病?。答：CDBAE、CDEBA、CDBEA?！?〕順序棧用data[0..n-1]存儲數(shù)據(jù)，棧頂指針為top，其初始值為0，那么元素x進棧的操作是〔〕。答：data[top]=x;top++;〔5〕順序棧用data[0..n-1]存儲數(shù)據(jù)，棧頂指針為top，其初始值為0，那么出棧元素x的操作是〔〕。答：top--;x=data[top];〔6〕〔〕是被限定為只能在表的一端進展插入運算，在表的另一端進展刪除運算的線性表。答：隊列〔7〕設有數(shù)組A[0..m]作為循環(huán)隊列的存儲空間，front為隊頭指針〔它指向隊首元素的前一位置〕，rear為隊尾指針〔它指向隊尾元素的位置〕，那么元素x執(zhí)行入隊的操作是〔〕。答：rear=(rear+1)%(m+1);A[rear]=x;〔8〕設有數(shù)組A[0..m]作為循環(huán)隊列的存儲空間，front為隊頭指針〔它指向隊首元素的前一位置〕，rear為隊尾指針〔它指向隊尾元素的位置〕，那么元素出隊并保存到x中的操作是〔〕。答：front=(front+1)%(m+1);x=A[rear];3.簡答題〔1〕簡要說明線性表、棧與隊的異同點。答：一樣點：都屬地線性構造，都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：①運算規(guī)那么不同，線性表為隨機存取，而棧是只允許在一端進展插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進展插入、另一端進展刪除運算，因而是先進先出表FIFO。②用途不同，棧用于子程調(diào)用和保護現(xiàn)場等，隊列用于多道作業(yè)處理、指令存放及其他運算等等。〔2〕順序隊的“假溢出〞是怎樣產(chǎn)生的如何知道循環(huán)隊列是空還是滿答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有進隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出〞。采用循環(huán)隊列是解決假溢出的途徑。另外，解決循環(huán)隊列是空還是滿的方法如下：①設置一個布爾變量以區(qū)別隊滿還是隊空；②浪費一個元素的空間，用于區(qū)別隊滿還是隊空。③使用一個計數(shù)器記錄隊列中元素個數(shù)〔即隊列長度〕。通常采用法②，讓隊頭指針front指向隊首元素的前一位置，隊尾指針rear指向隊尾元素的位置，這樣判斷循環(huán)隊列隊空標志是：front=rear，隊滿標志是：(rear+1)%MaxSize=front。4.算法設計題〔1〕假設采用順序棧存儲構造，設計一個算法，利用棧的基本運算返回指定棧中棧底元素，要求仍保持棧中元素不變。這里只能使用棧st的基本運算來完成，不能直接用st.data[0]來得到棧底元素。解：假定采用順序棧構造。先退棧st中所有元素，利用一個臨時棧tmpst存放從st棧中退棧的元素，最后的一個元素即為所求，然后將臨時棧tmpst中的元素逐一出棧并進棧到st中，這樣恢復st棧中原來的元素。對應算法如下：intGetBottom(SqStackst,ElemType&x){ ElemTypee;SqStacktmpst; //定義臨時棧 InitStack(tmpst); //初始化臨時棧 if(StackEmpty(st)) //空棧返回0 return0; while(!StackEmpty(st)) //臨時棧tmpst中包含st棧中逆轉(zhuǎn)元素 { Pop(st,x); Push(tmpst,x); } while(!StackEmpty(tmpst)) //恢復st棧中原來的內(nèi)容 { Pop(tmpst,e); Push(st,e); } return1; //返回1表示成功}〔2〕設計一個算法，采用一個順序棧逆向輸出單鏈表L中所有元素。解：此題并不需要改變單鏈表L的構造。設置一個順序棧st，先遍歷單鏈表并將所有元素進棧，然后棧不空循環(huán)并輸出棧中所有元素。對應算法如下：voidReverseDisp(SLink*L){ ElemTypex; structnode { ElemTypedata[MaxSize]; inttop; }st; //定義一個順序棧 st.top=-1;SLink*p=L->next; while(p!=NULL) //遍歷單鏈表，將所有元素進棧 { st.top++; st.data[st.top]=p->data; p=p->next; } while(st.top!=-1) //棧不空循環(huán)，輸出棧中所有元素 { x=st.data[st.top]; st.top--; printf("%d",x); } printf("\n");}〔3〕設計一個循環(huán)隊列，用front和rear分別作為隊頭和隊尾指針，另外用一個標志tag標識隊列可能空〔0〕或可能滿〔1〕，這樣加上front==rear可以作為隊空或隊滿的條件。要求設計隊列的相關基本運算算法。解：設計的隊列的類型如下：typedefstruct{ ElemTypedata[MaxSize]; intfront,rear; //隊頭和隊尾指針 inttag; //為0表示隊空,為1時表示不空}QueueType;初始時tag=0，進展成功的插入操作后tag=1，進展成功的刪除操作后tag=0；因為只有在插入操作后隊列才有可能滿，只有在刪除操作后隊列才有可能空，因此，這樣的隊列的基本要素如下：初始時：tag=0，front=rear隊空條件：qu.front==qu.rear&&qu.tag==0隊滿條件：qu.front==qu.rear&&qu.tag==1對應的算法如下：//-----初始化隊列算法-----voidInitQueue1(QueueType&qu){ qu.front=qu.rear=0; qu.tag=0; //為0表示隊空可能為空}//-----判隊空算法-----intQueueEmpty1(QueueTypequ){ return(qu.front==qu.rear&&qu.tag==0);}//-----判隊滿算法-----intQueueFull1(QueueTypequ){ return(qu.tag==1&&qu.front==qu.rear);}//-----進隊算法-----intenQueue1(QueueType&qu,ElemTypex){ if(QueueFull1(qu)==1) //隊滿 return0; qu.rear=(qu.rear+1)%MaxSize;qu.data[qu.rear]=x;qu.tag=1; //至少有一個元素,可能滿 return1;}//-----出隊算法-----intdeQueue1(QueueType&qu,ElemType&x)//出隊{ if(QueueEmpty1(qu)==1) //隊空 return0; qu.front=(qu.front+1)%MaxSize;x=qu.data[qu.front];qu.tag=0; //出隊一個元素,可能空 return1;}〔4〕假設用一個循環(huán)單鏈表表示隊列，并且只設一個指針rear指向隊尾結點，但不設頭指針，設計出相應的隊初始化、進隊、出隊和判隊空的算法。解：假設鏈隊是不帶頭結點的循環(huán)單鏈表，其示意圖如圖3.1所示。隊空條件：rear==NULL；進隊操作：在*rear結點之后插入結點并讓rear指向該結點；出隊操作：刪除*rear結點之后的一個結點。對應的算法如下：圖3.1不帶頭結點的循環(huán)單鏈表表示隊列typedefstructnode{ ElemTypedata; structnode*next;}QNode; //鏈隊結點類型//-----初始化隊列-----voidInitQueue(QNode*&rear){ rear=NULL;}//-----進隊算法-----voidEnQueue(QNode*&rear,ElemTypex){ QNode*s; s=(QNode*)malloc(sizeof(QNode));//創(chuàng)立新結點 s->data=x; if(rear==NULL) //原鏈隊為空 { s->next=s; //構成循環(huán)鏈表 rear=s; } else { s->next=rear->next; //將*s結點插入到*rear結點之后 rear->next=s; rear=s; //讓rear指向這個新插入的結點 }}//-----出隊算法-----intDeQueue(QNode*&rear,ElemType&x){ QNode*q; if(rear==NULL) //隊空 return0; elseif(rear->next==rear) //原隊中只有一個結點 { x=rear->data; free(rear); rear=NULL; } else //原隊中有兩個或以上的結點 { q=rear->next; x=q->data; rear->next=q->next; free(q); } return1;}//-----判隊空算法-----intQueueEmpty(QNode*rear){ return(rear==NULL);}上機實驗題3假設以I和O字符分別表示進棧和出棧操作，棧的初態(tài)和終棧均為空，進棧和出棧的操作序列可表示為僅由I和O組成的序列。如IOIIOIOO序列是合法的，而IOOIOIIO序列是不合法的。設計一個算法判定所給的操作序列是否合法。假設合法返回1；否那么返回0。〔假設被判定的操作序列已存入一維數(shù)組中〕。并用相關數(shù)據(jù)進展測試。解：采用一個鏈棧來判斷操作序列是否合法，其中str為存放操作序列的字符數(shù)組，n為該數(shù)組的元素個數(shù)〔這里的ElemType類型設定為char〕。對應的算法如下：#include<stdio.h>#include<malloc.h>typedefstructnode{ chardata; structnode*next;}LStack; //鏈棧結點類型voidInitStack(LStack*&ls) //初始化棧運算算法{ ls=NULL;}voidDestroyStack(LStack*&ls) //銷毀棧運算算法{ LStack*pre=ls,*p; if(pre==NULL)return; //考慮空棧的情況 p=pre->next; while(p!=NULL) { free(pre); //釋放*pre結點 pre=p;p=p->next; //pre、p同步后移 } free(pre); //釋放尾結點}voidPush(LStack*&ls,charx) //進棧運算算法{ LStack*p; p=(LStack*)malloc(sizeof(LStack)); p->data=x; //創(chuàng)立結點*p用于存放x p->next=ls; //插入*p結點作為棧頂結點 ls=p;}intPop(LStack*&ls,char&x) //出棧運算算法{ LStack*p; if(ls==NULL) //?？?下溢出返回0 return0; else //棧不空時出棧元素x并返回1 { p=ls; //p指向棧頂結點 x=p->data; //取棧頂元素x ls=p->next; //刪除結點*p free(p); //釋放*p結點 return1; }}intStackEmpty(LStack*ls) //判斷?？者\算算法{ if(ls==NULL)return1; elsereturn0;}intjudge(charstr[],intn) //判斷str序列的合法性{ inti,tag;charx;LStack*ls; InitStack(ls); //鏈棧ls初始化 for(i=0;i<n;i++) { if(str[i]=='I') //為I時進棧 Push(ls,str[i]); elseif(str[i]=='O') //為O時出棧 { if(StackEmpty(ls)) { DestroyStack(ls); return0; //棧空時返回0 } elsePop(ls,x); } else { DestroyStack(ls); return0; //其他值無效退出 } } tag=StackEmpty(ls); DestroyStack(ls); returntag; //棧為空時返回1,否那么返回0}voidmain(){ charstr1[]="IOIIOIOO"; charstr2[]="IOOIOIIO"; charstr3[]="IIIOIOIO"; charstr4[]="IIIOOIOO"; printf("各序列判斷結果如下:\n"); printf("%s序列%s合法的\n",str1,judge(str1,8)?"是":"不是"); printf("%s序列%s合法的\n",str2,judge(str2,8)?"是":"不是"); printf("%s序列%s合法的\n",str3,judge(str3,8)?"是":"不是"); printf("%s序列%s合法的\n",str4,judge(str4,8)?"是":"不是");}練習題41.單項選擇題〔1〕串是一種特殊的線性表，其特殊性表達在〔〕。A.可以順序存儲 B.數(shù)據(jù)元素是一個字符C.可以鏈式存儲D.數(shù)據(jù)元素可以是多個字符答：B〔2〕以下〔〕是"abcd321ABCD"串的子串。A.abcd B.321AB C."abcABC" D."21AB"答：D〔3〕兩個串相等必有串長度相等且〔〕。A.串的各位置字符任意 B.串中各對應位置字符均相等C.兩個串含有一樣的字符 D.兩個所含字符任意答：B2.填空題〔1〕空串是指〔①〕，空白串是指〔②〕。答：①不包含任何字符〔長度為0〕的串②由一個或多個空格〔僅由空格符〕組成的串〔2〕對于帶頭結點的鏈串s，串為空的條件是〔〕。答：s->next==NULL。〔3〕對于一個含有n個字符的鏈串s，查找第i個元素的算法的時間復雜度為〔〕。答：O(n)3.簡答題〔1〕設s為一個長度為n的串，其中的字符各不一樣，那么s中的互異的非平凡子串〔非空且不同于s本身〕的個數(shù)是多少答：由串s的特性可知，1個字符的子串有n個，2個字符的子串有n-1個，3個字符的子串有n-2個，…，n-2個字符的子串有3個，n-1個字符的子串有2個。所以，非平凡子串的個數(shù)=n+(n-1)+(n-2)+…+2=?！?〕假設s1和s2為串，給出使s1//s2=s2//s1成立的所有可能的條件〔其中，“//〞表示兩個串連接運算符〕。答：所有可能的條件為：〔1〕s1和s2為空串〔2〕s1或s2其中之一為空串〔3〕s1和s2為一樣的串〔4〕假設兩串長度不等，那么長串由整數(shù)個短串組成。4.算法設計題〔1〕設計一個算法RepChar(s,x,y)，將順序串s中所有字符x替換成字符y。要求空間復雜度為O(1)。解：因要求算法空間復雜度為O(1)，所以只能對串s直接替換。從頭開場遍歷串s，一旦找到字符x便將其替換成y。對應算法如下：voidRepStr(SqString&s,charx,chary){ inti; for(i=0;i<s.length;i++) if(s.data[i]==x) s.data[i]=y;}〔2〕設計一個算法，判斷鏈串s中所有元素是否為遞增排列的。解：用p和q指向鏈串s的兩個連續(xù)結點，p先指向開場結點，當q->data≥p->data時，p和q同步后移一個結點；否那么返回0。當所有元素是遞增排列時返回1。對應算法如下：intincrease(LinkString*s){ LinkString*p=s->next,*q; if(p!=NULL) { while(p->next!=NULL) { q=p->next; //q指向*p的后續(xù)結點 if(q->data>=p->data) p=q; else //逆序時返回0 return0; } } return1;}〔3〕假設以鏈式構造存儲一個串s，設計一個算法求串s中最長等值子串。解：假設串用帶頭結點的單鏈表存儲串s。用max存放最大平臺長度，掃描串s，計算一個平臺的長度n，假設n大于max，那么置max為n。對應的算法如下：intmaxlength(LinkString*s){ intn,max=0;LinkString*p=s->next,*q; while(p!=NULL) { n=1; q=p;p=p->next; while(p!=NULL&&p->data==q->data) { n++; p=p->next; } if(n>max)max=n; } returnmax;}上機實驗題4兩個非空串s和t采用順序存儲構造存儲，設計一個算法求這兩個串最大公共子串，并用相關數(shù)據(jù)進展測試。解：采用Index算法思路設計由順序串s、t產(chǎn)生最大公共子串str。對應的程序如下：#include<stdio.h>#include"SqString.h" //包含順序串的基本運算函數(shù)SqStringmaxcomstr(SqStrings,SqStringt){ SqStringstr; intmidx=0,mlen=0,tlen,i=0,j,k; //用(midx,mlen)保存最大公共子串 while(i<s.length) //用i掃描串s { j=0; //用j掃描串t while(j<t.length) { if(s.data[i]==t.data[j]) //找一子串,在s中下標為i,長度為tlen { tlen=1; for(k=1;i+k<s.length&&j+k<t.length &&s.data[i+k]==t.data[j+k];k++) tlen++; if(tlen>mlen) //將較大長度者賦給midx與mlen { midx=i; mlen=tlen; } j+=tlen; //繼續(xù)掃描t中第j+tlen字符之后的字符 } elsej++; } i++; //繼續(xù)掃描s中第i字符之后的字符 } for(i=0;i<mlen;i++) //將最大公共子串復制到str中 str.data[i]=s.data[midx+i]; str.length=mlen; returnstr; //返回最大公共子串}voidmain(){ SqStrings,t,str; Assign(s,"aababcabcdabcde"); Assign(t,"aabcd"); printf("s:");DispStr(s); printf("t:");DispStr(t); printf("求s、t的最大公共子串str\n"); str=maxcomstr(s,t); printf("str:");DispStr(str);}練習題51.單項選擇題〔1〕假設有60行70列的二維數(shù)組a[1..60,1..70]〔數(shù)組下標從1開場〕以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為〔〕。A.16902 B.16904 C.14454D.以上都不對答：A〔2〕對特殊矩陣采用壓縮存儲的目的主要是為了〔〕。A.表達變得簡單 B.對矩陣元素的存取變得簡單C.去掉矩陣中的多余元素 D.減少不必要的存儲空間答：D〔3〕一個n×n的對稱矩陣，如果采用壓縮存儲以行或列為主序放入內(nèi)存，那么壓縮存儲的容量是〔〕。A.n2 B.n2/2 C.n(n+1)/2 D.(n+1)2/2答：C〔4〕設矩陣a是一個對稱矩陣，為了節(jié)省存儲，將其下三角局部按行序存放在一維數(shù)組b[1..n(n-1)/2]中〔數(shù)組下標均從1開場〕，對下三角局部中任一元素ai,j〔i≤j〕在一維數(shù)組b中下標k的值是〔〕。A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j答：B〔5〕有一個二維數(shù)組A，行下標的范圍是0～8，列下標的范圍是1～5，每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是〔①〕。假設按行存儲，那么A[3,5]和A[5,3]的第一個字節(jié)的地址分別是〔②〕和〔③〕。假設按列存儲，那么A[7,1]和A[2,4]的第一個字節(jié)的地址分別是〔④〕和〔⑤〕。A.28B.44C.76D.92E.108F.116G.132H.176I.184J.188答：①H②C③E④A⑤F〔6〕有一個二維數(shù)組A，行下標的范圍是1～6，列下標的范圍是0～7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是〔①〕個字節(jié)。假設存儲數(shù)組元素A[1,0]的第一個字節(jié)的地址是0，那么存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是〔②〕。假設按行存儲，那么A[2,4]的第一個字節(jié)的地址是〔③〕。假設按列存儲，那么A[5,7]的第一個字節(jié)的地址是〔④〕。A.12 B.66 C.72 D.96 E.114 F.120G.156 H.234I.276J.282K.283L.288答：①L②J③C④I〔7〕稀疏矩陣一般的壓縮存儲方法有兩種，即〔〕。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表答：C2.填空題〔1〕三維數(shù)組A[c1..d1,c2..d2,c3..d3]〔c1≤d1，c2≤d2，c3≤d3〕共含有〔〕個元素。答：(d1-c1+1)×(d2-c2+1)×(d3-c3+1)?！?〕二維數(shù)組A[m][n]采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A[0][0])，那么A[i][j]的地址是〔〕。答：LOC(A[0][0])+(n×i+j)×k?！?〕二維數(shù)組A[10][20]采用列序為主方式存儲，每個元素占一個存儲單元，并且A[0][0]的存儲地址是200，那么A[6][12]的地址是〔〕。答：326〔4〕二維數(shù)組A[10..20][5..10]采用行序為主方式存儲，每個元素占4個存儲單元，并且A[10][5]的存儲地址是1000，那么A[18][9]的地址是〔〕。答：1208〔5〕有一個10階對稱矩陣A，采用壓縮存儲方式〔以行序為主存儲下三角局部，且A[0][0]存放在B[1]中〕，那么A[8][5]在B中的地址是〔〕。答：42〔6〕設n階下三角矩陣A[1..n][1..n]已壓縮到一維數(shù)組S[1..n(n+1)/2]中，假設按行序為主存儲，那么A[i][j]對應的S中的存儲位置是〔〕。答：i(i-1)/2+j?！?〕稀疏矩陣的三元組表示中，每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的〔〕。答：行下標、列下標和元素值3.算法設計題〔1〕假定數(shù)組A[0..n-1]的n個元素中有多個零元素，設計一個算法將A中所有的非零元素依次移到A的前端。解：從前向后找為零的元素A[i]，從后向前找非零的元素A[j]，將A[i]和A[j]進展交換。對應的算法如下：voidmove(ElemTypeA[],intn){ inti=0,j=n-1; ElemTypetmp;while(i<j) { while(A[i]!=0)i++; while(A[j]==0)j--; if(i<j) { tmp=A[i]; A[i]=A[j]; A[j]=tmp; } }}〔2〕一個n×n矩陣B按行優(yōu)先存于一個一維數(shù)組A[0..n(n-1)]中，試給出一個就地算法將原矩陣轉(zhuǎn)置后仍存于數(shù)組A中。解：矩陣轉(zhuǎn)置是將矩陣中第i行第j列的元素與第j行第i列的元素互換位置。因此先應確定矩陣與一維數(shù)組的映射關系：bi,j在一維數(shù)組A中的下標為i～n+j，bj,i在一維數(shù)組A中的下標為j×n+i。對應的算法如下：voidtrans(ElemTypeA[],intn){ inti,j; ElemTypetmp; for(i=0;i<n;i++) for(j=0;j<i;j++) { tmp=A[i*n+j];A[i*n+j]=A[j*n+i]; A[j*n+i]=tmp;}}〔3〕如果矩陣A中存在這樣的一個元素A[i][j]滿足條件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，那么稱之為該矩陣的一個馬鞍點。設計一個算法求出m×n的矩陣A的所有馬鞍點。解：先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，假設某元素既在min[i]中，又在max[j]中，那么該元素A[i][j]便是馬鞍點，找出所有這樣的元素，即找到了所有馬鞍點。實現(xiàn)程序如下：#include<stdio.h>#definem3#definen4voidminmax(intA[m][n]){ inti,j,have=0;intmin[m],max[n]; for(i=0;i<m;i++) //計算出每行的最小值元素，放入min[m]之中 { min[i]=A[i][0]; for(j=1;j<n;j++) if(A[i][j]<min[i]) min[i]=A[i][j]; } for(j=0;j<n;j++) //計算出每列的最大值元素，放入max[1..n]之中{ max[j]=A[0][j]; for(i=1;i<m;i++) if(A[i][j]>max[j]) max[j]=A[i][j]; } for(i=0;i<m;i++) //判定是否為馬鞍點 for(j=0;j<n;j++) if(min[i]==max[j]) { printf("(%d,%d):%d\n",i,j,A[i][j]);//顯示馬鞍點 have=1; } if(!have) printf("沒有鞍點\n");}voidmain(){ inta[m][n]; inti,j; for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); minmax(a); //調(diào)用minmax()找馬鞍點}〔4〕設有二維數(shù)組A[m][n]，其元素為整數(shù)，每行每列都按從小到大有序，試給出一個算法求數(shù)組中值為x的元素的行號i和列號j。設值x在A中存在，要求比較次數(shù)不多于m+n次。解：由于算法要求比較次數(shù)不多于m+n次，因此不能按行掃描數(shù)組的每一元素，否那么比較次數(shù)在最壞情況下可達m×n次。根據(jù)該數(shù)組的特點可從矩陣右上角按副對角線方向向左下角查找，算法如下：intfind(inta[M][N],intx,intm,intn){ inti=0,j=n-1,flag=0;while(i<m&&j>=0) if(a[i][j]!=x) if(a[i][j]>x)j--; //修改列號 elsei++; //修改行號 else //a[i][j]==x { flag=1; break; } returnflag;}上機實驗題5采用一維動態(tài)數(shù)組模擬二維數(shù)組的操作，即將一個二維數(shù)組的元素存放在一個一維數(shù)組中，一維數(shù)組的空間根據(jù)二維數(shù)組的大小動態(tài)分配。設計一個算法實現(xiàn)兩個二維數(shù)組的相加運算。并用相關數(shù)據(jù)進展測試。解：對應的程序如下：#include<stdio.h>#include<malloc.h>typedefintElemType;typedefstruct{ ElemType*p; //存放二維數(shù)組元素 intm,n; //存放二維數(shù)組的行數(shù)和列數(shù)}Mat2;voidInitMat(Mat2&M,intx,inty) //初始化二維數(shù)組M{ M.m=x;M.n=y; M.p=(ElemType*)malloc(x*y*sizeof(ElemType));}intSetij(Mat2&M,inti,intj,ElemTypex) //置二維數(shù)組(i,j)位置值為x{ intk; if(i>=0&&i<M.m&&j>=0&&j<M.n) { k=i*M.n+j; M.p[k]=x; return1; //成功賦值返回1 } elsereturn0; //參數(shù)錯誤返回0}intGetij(Mat2M,inti,intj,ElemType&x) //取二維數(shù)組(i,j)位置值并賦給x{ intk; if(i>=0&&i<M.m&&j>=0&&j<M.n) { k=i*M.n+j;x=M.p[k]; return1; //成功取值返回1 } elsereturn0; //參數(shù)錯誤返回0}voidDispMat(Mat2M) //輸出二維數(shù)組{ inti,j,k; for(i=0;i<M.m;i++){ for(j=0;j<M.n;j++) { k=i*M.n+j; printf("%3d",M.p[k]); } printf("\n"); }}intAddMat(Mat2A,Mat2B,Mat2&C) //兩個二維數(shù)組相加運算{ inti,j;ElemTypex,y; if(A.m!=B.m||A.n!=B.n) return0; //兩數(shù)組行列數(shù)不同返回0 for(i=0;i<A.m;i++) for(j=0;j<A.n;j++) { Getij(A,i,j,x);Getij(B,i,j,y); Setij(C,i,j,x+y);} return1;}voidDestroyMat(Mat2M) //銷毀二維數(shù)組M{ free(M.p);}voidmain(){ Mat2A,B,C; InitMat(A,2,3); Setij(A,0,0,1);Setij(A,0,1,1);Setij(A,0,2,1); Setij(A,1,0,1);Setij(A,1,1,1);Setij(A,1,2,1);printf("A:\n");DispMat(A);InitMat(B,2,3); Setij(B,0,0,2);Setij(B,0,1,2);Setij(B,0,2,2); Setij(B,1,0,2);Setij(B,1,1,2);Setij(B,1,2,2);printf("B:\n");DispMat(B); InitMat(C,2,3);printf("C=A+B\n");AddMat(A,B,C); printf("C:\n");DispMat(C); DestroyMat(A); DestroyMat(B); DestroyMat(C);}練習題61.單項選擇題〔1〕樹最適合用來表示〔〕。A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C.元素之間具有層次關系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)答：C〔2〕樹是結點的有限集合，它〔①〕根結點，記為T。其余的結點分成為m〔m≥0〕個〔②〕的集合T1、T2、…、Tm，每個集合又都是樹，此時結點T稱為Ti的雙親結點，Ti稱為T的子樹〔1≤i≤m〕。一個結點的子