數據結構作業(yè)題及參考答案

數據結構作業(yè)題及參考答案-標準化文件發(fā)布號：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII東北農業(yè)大學網絡教育學院數據結構作業(yè)題（一）一、選擇題（每題2分，共20分）在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（）。A、O（n）B、O（n/2）C、O（1）D、O（n2）帶頭結點的單鏈表first為空的判定條件是（）。A、first==NULL;B、first->link==NULL;C、first->link==first;D、first!=NULL;3．在一棵樹中，（）沒有前驅結點。A、分支結點B、葉結點C、樹根結點D、空結點4．在有向圖中每個頂點的度等于該頂點的（）。A、入度B、出度C、入度與出度之和D、入度與出度之差5．對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（）的值除以9。A、20B、18C、25D、226．下列程序段的時間復雜度為（）。s=0；for（i=1；i<n；i++）for（j=1；j<n；j++）s+=i*j；A、O（1）B、O（n）C、O（2n）D、O（n2）7．棧是一種操作受限的線性結構，其操作的主要特征是（）。A、先進先出B、后進先出C、進優(yōu)于出D、出優(yōu)于進?假設以數組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數為（）。A、（rear-front-1）％nB、（rear-front）％nC、（front-rear+1）％nD、（rear-front+n）％n?高度為5的完全二叉樹中含有的結點數至少為（）。．答：先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹一右子樹一根"，根據以上原則，本題解答如下：（1）若先序序列與后序序列相同，則或為空樹，或為只有根結點的二叉樹（2）若中序序列與后序序列相同，則或為空樹，或為任一結點至多只有左子樹的二叉樹．（3）若先序序列與中序序列相同，則或為空樹，或為任一結點至多只有右子樹的二叉樹．（4）若中序序列與層次遍歷序列相同，則或為空樹，或為任一結點至多只有右子樹的二叉樹4．答：（1）T樹的最大深度Kmax=6（除根外，每層均是兩個結點）T樹的最小深度Kmin=4（具有6個葉子的完全二叉樹是其中的一種形態(tài)）（2）非葉子結點數是5°（n2=n0-1）（3）哈夫曼樹見下圖，其帶權路徑長度wpl=51Wpl=4*3+3*3+2*（4+5+6）=51n(n>0)個結點的d度樹共有nd個鏈域，除根結點外，每個結點均有一個指針所指,故該樹的空鏈域有nd-(n-1)=n(d-1)+1個。習題二參考答案一、選擇題(每題2分，共20分)12345678910BDACDDBBCA二、填空題(每空2分，共40分)1．n-1.(15,02,21,24,26,57,43,66,81,48,73).0(n).HL->next=NULLHL->next=HL.O(nlog2n)；O(n2)26.6：31：19.2；1；1；6._69?集合結構；線性結構；樹型結構；圖形結構10.n-i+1三、應用題(每題10分，共60分)1.答：可以做到。取a與b進行比較，c與d進行比較。設a>b,c>d(a<b和c<d情況類似)此時需2次比較，取b和d比較，若b>d，則有序a>b>d；若b<d時則有序c>d>b,此時已進行了3次比較。再把另外兩個元素按折半插入排序方法,插入到上述某個序列中共需4次比較,從而共需7次比較2．該排序方法為快速排序。3.①快速排序②冒泡排序③直接插入排序4．答：(1)T樹的最大深度Kmax=6(除根外，每層均是兩個結點)T樹的最小深度Kmin=4(具有6個葉子的完全二叉樹是其中的一種形態(tài))5．答：n(n>0)個結點的d度樹共有nd個鏈域，除根結點外，每個結點均有一個指針所指,故該樹的空鏈域有nd-(n-1)=n(d-1)+1個。6．答：(1)176(2)76和108(3)28和116。習題三參考答案一、單選題(每題2分，共10分1、A2、B3、D4、D5、D二、填空題（每空1分，共25分）1、1:11:NM:N（或者1對11對NM對N）、p->nexta[p].next、引用、后進先出先進先出、162TOC\o"1-5"\h\z、3121、6、查找成功左子樹右子樹、n2、nn-111、二叉搜索樹理想平衡樹（次序無先后）12、O（n）O（nlog2n）O（n）13、596三、運算題（每題6分，共24分）1、先根：a,b,e,c,f,h,i,j,g,d;（2分）后根：e,b,h,i,j,f,g,c,d,a;（2分）按層：a,b,c,d,e,f,g,h,i,j;（2分）2、最小生成樹的權：55、312、56四、閱讀算法，回答問題（第一題7分，第二題8分）1、（12，26，9，8，15，30，50）

2、向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。五、算法填空，在畫有橫線的地方填寫合適的內容(12分returnmidreturnBinsch(A,low,mid-1,K)returnBinsch(A,mid+1,high,K)六、編寫算法(14分)評分標準：請根據編程情況酌情給分。boolFind(BTreeNode*BST,ElemType&item){while(BST!=NULL){if(item==BT->data){item=BST->data;returntrue;}elseif(item<BST->data)BST=BST->left;elseBST=BST->right;}returnfalse;}習題四參考答案一、選擇題（每題2分，共20分）12345678910CDACCDCDBC二、填空題（每空2分，共30分）1．算法的時間復雜度和空間復雜度2．有窮性；確定性；可行性。4．424．426?非零元很少（tvvm*n）且分布沒有規(guī)律5．91748788

7．深度8．7．深度8．99．1210．64三、計算題(每題6分，共30分)1．輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素(4356)得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結果135426。2．先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a按層：a,b,d,c,e,f3．(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,(6,4)4,(5,7)204．拓撲序列：1,3,6,0,2,5,4,7,85．[40342538]46[805679]四、算法填空(10分)1．BST->left=BST->right=NULLInsert(BST->left,item)Insert(BST->right,item)五、編程(10分)2?從集合(l..n)中選出k(本題中k=2)個元素，為了避免重復和漏選，可分別求出包括1和不包括1的所有組合。即包括1時，求出集合(2..n)中取出k-1個元素的所有組合；不包括1時，求出集合(2..n)中取出k個元素的所有組合。，將這兩種情況合到一起，就是題目的解

intA[],n;//設集合已存于數組A中。voidcomb(intP[],inti,intk)//從集合(l..n)中選取k(k<=n)個元素的所有組合{if(k==0)printf(P);elseif(k<=n){P[i]=A[i];comb(P,i+1,k-1);comb(P,i+1,k);}}//算法結束習題五參考答案一、單選題（每題2分，共20分）1．B2．D3．A4．B6．D7．C8．A9．D、填空題（每空1分，共25分）1．集合結構線性結構樹形結構2．O(n)O(1)3．行號列號元素值（次序無先后）4．35．top==06．5507．168．最小值最大值9．n-110．O(n2)O（n十e)O(e)11．順序有序5．B10．A圖形結構

12．稠密稀疏13．O（1og2n）O（n1.1.(40，38.35，30，25，20)2.（0，3）2，（4，6）4，（0，2)5，(1，3.（50，42，46，38，40，56，79，84)4.[3638404046567980][256675三、運算題（每題5分，共20分）5）6，（0，1）8，（3，6）10，（5，7）2084]四、閱讀算法，回答問題（每題5分，共10分）1．(50，30，5，8，12，15)2．121553018五、算法填空，在畫有橫線的地方填寫合適的內容（10分（A[i]stn<