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

數據結構作業(yè)題及參考答案數據結構作業(yè)題及參考答案數據結構作業(yè)題及參考答案數據結構作業(yè)題及參考答案編制僅供參考審核批準生效日期地址：電話：傳真:郵編:東北農業(yè)大學網絡教育學院數據結構作業(yè)題（一）一、選擇題（每題2分，共20分）1．在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（）。A、O(n) B、O(n/2) C、O(1) D、O(n2)2．帶頭結點的單鏈表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、20 B、18 C、25 D、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)于進8．假設以數組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數為（）。A、(rear-front-1)％n B、(rear-front)％nC、(front-rear+1)％n D、(rear-front+n)％n9．高度為5的完全二叉樹中含有的結點數至少為（）。A、16 B、17 C、31 D、10．如圖所示有向圖的一個拓撲序列是()A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空題（每空1分，共20分）1．n(n﹥0)個頂點的無向圖最多有條邊，最少有條邊。2．在一棵AVL樹中，每個結點的左子樹高度與右子樹高度之差的絕對值不超過。3．已知8個數據元素為（34，76，45，18，26，54，92，65），按照依次插入結點的方法生成一棵二叉排序樹，則該樹的深度為。4．在二叉樹的第i層上至多有結點。5．對于一棵具有n個結點的二叉樹，若一個結點的編號為i(1≤i≤n)，則它的左孩子結點的編號為，右孩子結點的編號為，雙親結點的編號為。6．數據的存儲結構被分為、、和四種。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則樹中所含的結點數為個，樹的深度為，樹的度為。8．在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要條邊。9．在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間分別存在著、和的聯(lián)系。10．一棵含999個結點的完全二叉樹的深度為。三、運算題（每題5分，共10分）1．設有一個1010的對稱矩陣A，將其下三角部分按行存放在一個一維數組B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。2．已知一個有序表(15,26,34,39,45,56,58,63,74,76,83,94)順序存儲于一維數組a[12]中，根據折半搜索過程填寫成功搜索下表中所給元素34,56,58,63,94時的比較次數。元素值3456586394比較次數四、應用題（每題10分，共50分）1．設待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。（1）用直接插入排序。試以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排序。（2）用直接選擇排序。試以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排序。2．判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調整為堆）。（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80，82，85，98，1003．試找出分別滿足下列條件的所有二叉樹。1）先序序列和中序序列相同2）中序序列和后序序列相同3）先序序列和后序序列相同4）中序序列與層次遍歷序列相同4．設T是一棵二叉樹，除葉子結點外，其它結點的度數皆為2，若T中有6個葉結點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結點？

(3)若葉結點的權值分別為1,2,3,4,5,6。請構造一棵哈曼夫樹，并計算該哈曼夫樹的帶權路徑長度wpl。5．一棵有n(n>0)個結點的d度樹，若用多重鏈表表示，樹中每個結點都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域為什么儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是多少數據結構作業(yè)題（二）一、選擇題（每題2分，共20分）1．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執(zhí)行（）。A、HL=p;p->next=HL; B、p->next=HL;HL=p;C、p->next=HL;p=HL; D、p->next=HL->next;HL->next=p;2．由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）。A、24 B、48 C、72 D、533．一個數組元素a[i]與（）的表示等價。A、*(a+i) B、a+i C、*a+i D、&a+i4．下面程序段的時間復雜度為（）。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)5．數據結構是（）。A、一種數據類型B、數據的存儲結構C、一組性質相同的數據元素的集合D、相互之間存在一種或多種特定關系的數據元素的集合6．在線性表的下列運算中，不改變數據元素之間結構關系的運算是（）。A、插入 B、刪除 C、排序 D、定位7．若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則可能出現(xiàn)的出棧序列為（）。A、3，2，6，1，4，5 B、3，4，2，1，6，5C、1，2，5，3，4，6 D、5，6，4，2，3，18．在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系（）。A、不一定相同 B、都相同 C、都不相同 D、互為逆序9．圖的鄰接矩陣表示法適用于表示（）。A、無向圖 B、有向圖 C、稠密圖 D、稀疏圖10．若有序表的關鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關鍵字b的過程中，先后進行比較的關鍵字依次為（）。A、f,c,b B、f,d,b C、g,c,b D、g,d,b二、填空題（每空2分，共40分）1．含n個頂點的無向連通圖中至少含有條邊。2．若對關鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進行一趟增量為3的希爾排序，則得到的結果為。3．一個算法的時間復雜度為(3n2+2nlog2n+4n-7)/(5n)，其數量級表示為。4．在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為和。5．快速排序在平均情況下的時間復雜度為，在最壞情況下的時間復雜度為。6．假定對長度n=50的有序表進行二分查找，則對應的判定樹高度為________，判定樹中前5層的結點數為________，最后一層的結點數為________。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則度為3、2、1、0的結點數分別為、、和個。8．在一棵二叉樹中，假定雙分支結點數為5個，單分支結點數為6個，則葉子結點數為個。9．數據的邏輯結構被分為、、和四種。10．在一個長度為n的順序存儲線性表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移個元素。三、應用題（每題10分，共60分）1．設有5個互不相同的元素a、b、c、d、e，能否通過7次比較就將其排好序？如果能，請列出其比較過程；如果不能，則說明原因。2．有一隨機數組(25,84,21,46,13,27,68,35,20),現(xiàn)采用某種方法對它們進行排序,其每趟排序結果如下,則該排序方法是什么初始:25,84,21,46,13,27,68,35,20第一趟:20,13,21,25,46,27,68,35,84第二趟:13,20,21,25,35,27,46,68,84第三趟:13,20,21,25,27,35,46,68,843．請在（）內填入正確的排序方法。設一數組中原有數據如下：15，13，20，18，12，60。下面是一組由不同排序方法進行一遍排序后的結果。（）排序的結果為：12，13，15，18，20，60（）排序的結果為：13，15，18，12，20，60（）排序的結果為：13，15，20，18，12，604．設T是一棵二叉樹，除葉子結點外，其它結點的度數皆為2，若T中有6個葉結點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結點？

(3)若葉結點的權值分別為1,2,3,4,5,6。請構造一棵哈曼夫樹，并計算該哈曼夫樹的帶權路徑長度wpl。5．一棵有n(n>0)個結點的d度樹，若用多重鏈表表示，樹中每個結點都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域為什么6．有一個二維數組A[0:8,1:5]，每個數組元素用相鄰的4個字節(jié)存儲,存儲器按字節(jié)編址，假設存儲數組元素A[0,1]的第一個字節(jié)的地址是0，那么存儲數組的最后一個元素的第一個字節(jié)的地址是多少若按行存儲,則A[3,5]和A[5,3]的第一個字節(jié)的地址是多少若按列存儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是多少數據結構作業(yè)題（三）一、單選題（每題2分，共10分）1、在長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，需要從前向后依次前移個元素。A、n-iB、n-i+1C、n-i-1D、i2、設一個廣義表中結點的個數為n，則求廣義表深度算法的時間復雜度為。A、O(1)B、O(n)C、O(n2)D、O(log2n)3、假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為。A、f+1==rB、r+1==fC、f==0D、f==r4、由3個結點可以構造出多少種不同的二叉樹。A、2B、3C、4D、5 5、適用于折半查找的表的存儲方式及元素排列要求為。 A、鏈接方式存儲，元素無序B．鏈接方式存儲，元素有序 C、順序方式存儲，元素無序D．順序方式存儲，元素有序二、填空題（每空1分，共25分）1、在線性結構、樹結構和圖結構中，前驅和后繼結點之間分別存在著、和的聯(lián)系。2、在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為，若假定p為一個數組a中的下標，則其后繼結點的下標為。3、在初始化一個稀疏矩陣的函數定義中，矩陣形參應說明為參數。4、棧又稱為表，隊列又稱為表。5、后綴表達式“45+3*24+*”的值為。6、一棵深度為5的滿二叉樹中的結點數為個，一棵深度為3的滿四叉樹中的結點數為個。7、對于一棵含有40個結點的理想平衡樹，它的高度為。8、從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結點的值，則表明，若元素的值小于根結點的值，則繼續(xù)向查找，若元素的值大于根結點的值，則繼續(xù)向查找。9、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為。10、對于一個具有n個頂點和e條邊的連通圖，其生成樹中頂點數和邊數分別為和。11、二分查找過程所對應的判定樹既是一棵，又是一棵。12、在歸并排序中，進行每趟歸并的時間復雜度為，整個排序過程的時間復雜度為，空間復雜度為。 13、給定一組數據{6，2，7，10，3，12}以它構造一棵哈夫曼樹，則樹高為__________，帶權路徑長度WPL的值為__________。三、運算題（每題6分，共24分）1、假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后根、按層遍歷的結果。先根：。后根：。按層：。2、已知一個帶權圖的頂點集V和邊集G分別為：V={0，1，2，3，4，5，6，7}；E={（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；則求出該圖的最小生成樹的權。最小生成樹的權：。3、對于線性表（18,25,63,50,42,32,90,66）進行散列存儲時，若選用H(K)=K%9作為散列函數，則散列地址為0的元素有個，散列地址為3的元素有個，散列地址為5的元素有個。4、假定一組記錄的排序碼為（46，79，56，38，40，80，25，34），在對其進行快速排序的過程中，對應二叉搜索樹的深度為，分支結點數為。四、閱讀算法（第一題7分，第二題8分）1、voidAA(LNode*&HL){InitList(HL);InsertRear(HL,30);InsertRear(HL,50);inta[5]={15,8,9,26,12};for(inti=0;i<5;i++)InsertFront(HL,a[i]);}該算法被調用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數據元素依次為：。2、voidAH(Heap&HBT,constElemTypeitem)ey);elseif(K<A[mid].key);else;}elsereturn-1;}六、編寫算法（14分）編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結點的非遞歸算法，若查找成功則由item帶回整個結點的值并返回true，否則返回false。boolFind(BTreeNode*BST,ElemType&item)數據結構作業(yè)題（四）一、選擇題（每題2分，共20分）1．從邏輯上可以把數據結構分為（）兩大類。A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構2．以下數據結構中，哪一個是線性結構（）A．廣義表B.二叉樹C.稀疏矩陣D.串3．連續(xù)存儲設計時，存儲單元的地址（）。A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)4．若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（）。A.O(0)B.O(1)C.O(n)D.O(n2)5．在雙向鏈表指針p的結點前插入一個指針q的結點操作是（）。A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;6．若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（）。A.i-j-1B.i-jC.j-i+1D.不確定的7．有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列（）A.543612B.453126C.346521D.2341568．用鏈接方式存儲的隊列，在進行刪除運算時（）。A.僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改9．若用一個大小為6的數組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少(

)A.1和5B.2和4C.4和2D.5和110．棧和隊列的共同點是（）。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點二、填空題（每空2分，共30分）1．數據結構中評價算法的兩個重要指標是和。2．一個算法具有5個特性:、、，有零個或多個輸入、有一個或多個輸出。3．在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動________個元素。4．對于雙向鏈表,在兩個結點之間插入一個新結點需修改的指針共______個，單鏈表為_______個。5．設數組a[1..50,1..80]的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a[45,68]的存儲地址為__;若以列序為主序順序存儲，則元素a[45,68]的存儲地址為__。6．所謂稀疏矩陣指的是_______。7．廣義表的_______定義為廣義表中括弧的重數。8．具有256個結點的完全二叉樹的深度為______。9．已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹有______個葉子結點。10．高度為8的完全二叉樹至少有______個葉子結點。三、計算題（每題6分，共30分）1．如果輸入序列為123456,試問能否通過棧結構得到以下兩個序列:435612和135426;請說明為什么不能或如何才能得到。2．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結果。先序：中序：后序：按層：3．已知一個圖的頂點集V和邊集G分別為：V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20,(6,7)30};按照普里姆算法從頂點0出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊。________,________,________,________,________,________,________。4.已知一個圖的頂點集V和邊集G分別為：V={0,1,2,3,4,5,6,7,8};E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>};若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，則按主教材中介紹的進行拓撲排序的算法，寫出得到的拓撲序列（提示：先畫出對應的圖形，然后再運算）。拓撲序列：5．假定一組記錄的排序碼為(46,79,56,38,40,80,25,34)，則對其進行快速排序的第一次劃分后的結果為________________。四、算法填空（10分）1．五、編程（10分）1．設計算法以求解從集合{1..n}中選取k（k<=n）個元素的所有組合。例如，從集合{1..4}中選取2個元素的所有組合的輸出結果為：12，13，14，23，24，34。數據結構作業(yè)題（五）一、選擇題（每題2分，共20分）1．若需要利用形參直接訪問實參，則應把形參變量說明為（）參數。A指針B引用C值2．在一個單鏈表HL中，若要在指針q所指結點的后面插入一個由指針p所指向的結點，則執(zhí)行（）。Aq一>next=p一>next；p一>next=q；Bp一>next=q一>next；q=p；C9一>next=p一>next；p一>next=q；Dp一>next=q一>next；q一>next=p；3．在一個順序隊列中，隊首指針指向隊首元素的（）位置。A前一個B后一個C當前4．向二叉搜索樹中插入一個元素時，其時間復雜度大致為（）。AO（1）BO（1og2n）CO（n）DO（nlog2n）5．假設有兩個串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（）。A.連接 B.模式匹配 C.求子串 D.求串長6．我們對記錄進行排序的目的是（）。A.分類 B.合并 C.存儲 D.查找7．在最壞的情況下，冒泡排序法的時間復雜度為（）。(lgn) (nlgn) (n2) (n)8．廣義表(A,B,E,F,G)的表尾是（）。A.(B,E,F,G) B.() C.（A，B，E，F(xiàn)，G) D.（G）9．線性表如果采用鏈式存儲結構，要求內存中的存儲單元的地址（）。A.必須是連續(xù)的B.部分要求是連續(xù)的C.一定不是連續(xù)的D.可以是連續(xù)的，也可以是不連續(xù)的10．在數據結構中，從邏輯結構上，我們可以把數據結構分為（）。A.線性結構和非線性結構B.內部結構和外部結構C.順序結構和鏈式結構D.動態(tài)結構和靜態(tài)結構二、填空題（每空1分，共25分）1．數據的邏輯結構被分為、、和四種。2．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為，在表尾插入元素的時間復雜度為。3．在一個稀疏矩陣中，每個非零元素所對應的三元組包括該元素的、和三項。4．在廣義表的存儲結構中，每個結點均包含有個域。5．當用長度為N的數組順序存儲一個棧時，假定用top==N表示?？?，則表示棧滿的條件為。6．假定一棵三叉樹的結點個數為50，則它的最小深度為，最大深度為。7．在一棵二叉樹中，第5層上的結點數最多為。8．在一個小根堆中，堆頂結點的值是所有結點中的，在一個大根堆中，堆頂結點的值是所有結點中的。9．在一個具有n個頂點的無向圄中，要連通所有頂點則至少需要條邊。10．假定一個圖具有n個頂點和e條邊，貝采用鄰接矩陣、鄰接表和邊集數組表示時，其相應的空間復雜度分別為、和。11．以二分查找方法查找一個線性表時，此線性表必須是存儲的表。12．在索引表中，若一個索引項對應主表中的一條記錄，則稱此索引為表。13．快速排序在平均情況下的空間復雜度為，在最壞情況下的空間復雜度為。三、運算題（每題5分，共20分）1．假定一個大堆為（56，38，42，30，25，40，35，20），則依次從中刪除兩個元素后得到的堆為。2．已知一個圖的頂點集V和邊集6分別為：V={0，1，2，3，4，5，6，7}；E={（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；按照克魯斯卡爾算法得到最小生成材，拭寫出在最小生成樹中依次得到的各條邊。，，，，，，。3．假定一組數據的初始堆為（84，79，56，42，40，46，50，38），請寫出在堆排序階段進行前三次對換和篩運算后數據的排列情況。數據排列情況：。4．假定一組記錄的徘序碼為（46，79，56，38，40，80，36，40，75，66，84，24），對其進行歸并排序的過程中，第三趟歸并后的結果為：。四、閱讀算法，回答問題（每題5分，共10分）1．voidAA（List＆L）{InitList（L）；InsertRear（L，30）；InsertFront（L，50）；inta[4]={5，8，12，15}for（inti=0；1＜4；i＋＋＝InsertRear（L，a[i]）；}該算法被調用執(zhí)行后，得到的線性表L為：。2．voidAF（Queue＆Q）{InitQueue（Q）：inta[4]={5，8，12，15}for（inti一0；i＜4；i斗＋＝Qlnsert（Q，遷6）；QInsert（Q，QDelete（Q））；QInsert（Q，30）；QInsert（Q，QDelete（Q）＋10）；whi1e（！QueueEmpty（Q））cout＜＜QDeleie（Q）＜＜”；}該算法被調用后得到的輸出結果為：。五、算法填空，在畫有橫線的地方填寫合適的內容（10分）從一維數組A[n]上進行快速排序的遞歸算法。voidQuickSort（ElemTypeA[]，ints，intt）{inti=sj=t十1；ElemTypex=A[s]；d0｛doi++；while；／／填寫一個循環(huán)條件doj--；while（A[j]．stn＞x．stn）；if（I<j）{ElemTypetemp=A［i］；A［i］=A［j］；A［j］＝temp；}}while（i＜j）；A[s]=A[j]；A[j]=x；if（s＜i一1）；if（j十1＜t）；}六、編寫算法（15分）編寫一個遞歸算法，統(tǒng)計并返回以BT為樹根指針的二叉樹中的葉子結點的個數。intCount（BTreeNode*BT）東北農業(yè)大學網絡教育學院數據結構作業(yè)題參考答案習題一參考答案一、選擇題（每題2分，共20分）12345678910ABCCCDBBAB二、填空題（每題1分，共20分）1．n(n-1)/2；02．13． 54．2i-15．2i；2i+1；i/26．順序；鏈接；索引；散列7．10；4；38．n-19．一對一；一對多；多對多10．10三、運算題（每題5分，共10分）1．根據題意，矩陣A中當元素下標I與J滿足I≥J時，任意元素A[I][J]在一維數組B中的存放位置為I*(I+1)/2+J，因此，A[8][5]在數組B中位置為 8*(8+1)/2+5=41。2．判斷結果元素值3456586394比較次數21344四、應用題（每題10分，共50分）1．答： (1)直接插入排序第一趟 (3)[8,3],2,5,9,1,6第二趟 (2)[8,3,2],5,9,1,6第三趟 (5)[8,5,3,2],9,1,6第四趟 (9)[9,8,5,3,2],1,6第五趟 (1)[9,8,5,3,2,1],6第六趟 (6)[9,8,6,5,3,2,1](2)直接選擇排序（第六趟后僅剩一個元素，是最小的，直接選擇排序結束）第一趟 (9)[9],3,2,5,8,1,6第二趟 (8)[9,8],2,5,3,1,6第三趟 (6)[9,8,6],5,3,1,2第四趟 (5)[9,8,6,5],3,1,2第五趟 (3)[9,8,6,5,3],1,2第六趟 (2)[9,8,6,5,3,2],12．(1)是大堆；(2)是大堆；（4）是小堆；(3)不是堆，調成大堆100，98，66，85，80，60，40，77，82，10，203．答：先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據以上原則，本題解答如下：（1）若先序序列與后序序列相同，則或為空樹，或為只有根結點的二叉樹（2）若中序序列與后序序列相同，則或為空樹，或為任一結點至多只有左子樹的二叉樹．（3）若先序序列與中序序列相同，則或為空樹，或為任一結點至多只有右子樹的二叉樹．（4）若中序序列與層次遍歷序列相同，則或為空樹，或為任一結點至多只有右子樹的二叉樹4．答：（1）T樹的最大深度Kmax=6（除根外，每層均是兩個結點）T樹的最小深度Kmin=4（具有6個葉子的完全二叉樹是其中的一種形態(tài)）（2）非葉子結點數是5。（n2=n0-1）（3）哈夫曼樹見下圖，其帶權路徑長度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=5144561235．答：n（n>0）個結點的d度樹共有nd個鏈域，除根結點外，每個結點均有一個指針所指，故該樹的空鏈域有nd-(n-1)=n(d-1)+1個。習題二參考答案一、選擇題（每題2分，共20分）12345678910BDACDDBBCA二、填空題（每空2分，共40分）1．n-12．（15，02，21，24，26，57，43，66，81，48，73）3．O（n）4．HL->next==NULLHL->next==HL5．O(nlog2n)；O(n2)6．6；31；197．2；1；1；68．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)）456123（2）非葉子結點數是456123（3）哈夫曼樹見下圖，其帶權路徑長度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=515．答：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、D 4、D 5、D二、填空題（每空1分，共25分）1、1:11:NM:N（或者1對11對NM對N）2、p->nexta[p].next3、引用4、后進先出先進先出5、1626、31217、68、查找成功左子樹右子樹9、n210、nn-111、二叉搜索樹理想平衡樹（次序無先后）12、O(n)O(nlog2n)O(n) 13、5 96三、運算題（每題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、最小生成樹的權：553、3124、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;