【正文】 什么時候離光明最近？那就是你覺得黑暗太黑的時候。 b(P,i+1,k1)。 得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。bool Find( BTreeNode * BST , ElemType amp。3．①快速排序 ②冒泡排序 ③直接插入排序4．答：（1）T樹的最大深度Kmax=6（除根外，每層均是兩個結(jié)點）T樹的最小深度Kmin=4（具有6個葉子的完全二叉樹是其中的一種形態(tài)）456123（2）非葉子結(jié)點數(shù)是5。 int Count（BTreeNode*BT）東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)作業(yè)題參考答案習(xí)題一參考答案一、選擇題（每題2分，共20分）12345678910ABCCCDBBAB二、填空題（每題1分，共20分）1．n(n1)/2； 02． 1 3． 5 4．2i15．2i； 2i+1； i/26．順序；鏈接；索引；散列7．10； 4； 38．n19．一對一； 一對多； 多對多10． 10 三、運算題（每題5分，共10分）1．根據(jù)題意，矩陣A中當(dāng)元素下標(biāo)I與J滿足I≥J時，任意元素A[I][J]在一維數(shù)組B中的存放位置為I * (I + 1) / 2 + J，因此，A[8][5]在數(shù)組B中位置為 8 * (8 + 1) / 2 + 5 = 41。 ， ， ， ， ， ， 。8．在一個小根堆中，堆頂結(jié)點的值是所有結(jié)點中的 ，在一個大根堆中，堆頂結(jié)點的值是所有結(jié)點中的 。，也可以是不連續(xù)的10．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯結(jié)構(gòu)上，我們可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）。A指針 B引用 C值2．在一個單鏈表HL中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(zhí)行（ ）?！　_______, ________, ________, ________, ________, ________, ________。9．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有______個葉子結(jié)點。2．一個算法具有5個特性: 、 、 ，有零個或多個輸入、有一個或多個輸出。D. qLlink=pLlink。qLlink=q；B. pLlink=q。 bool Find( BTreeNode * BST , ElemType amp。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容。 ++。 InsertRear(HL,50)。按層： 。 對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為 。 A、鏈接方式存儲，元素?zé)o序 B．鏈接方式存儲，元素有序 C、順序方式存儲，元素?zé)o序 D．順序方式存儲，元素有序二、填空題（每空1分，共25分）在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著 、 和 的聯(lián)系。下面是一組由不同排序方法進(jìn)行一遍排序后的結(jié)果。6．假定對長度n=50的有序表進(jìn)行二分查找，則對應(yīng)的判定樹高度為________，判定樹中前5層的結(jié)點數(shù)為________，最后一層的結(jié)點數(shù)為________。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．在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（ ）。 for(int i=0。C、pnext=HL。 （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．試找出分別滿足下列條件的所有二叉樹。10的對稱矩陣A，將其下三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。4．在二叉樹的第i層上至多有 結(jié)點。A、20 B、18 C、25 D、226．下列程序段的時間復(fù)雜度為（ ）。A、O(n) B、O (n/2) C、O (1) D、O (n2)2．帶頭結(jié)點的單鏈表first為空的判定條件是（ ）。3．在一棵樹中，（ ）沒有前驅(qū)結(jié)點。A、16 B、17 C、31 D、3210．如圖所示有向圖的一個拓?fù)湫蛄惺? )A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空題（每空1分，共20分）1．n (n﹥0) 個頂點的無向圖最多有 條邊，最少有 條邊。9．在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著 、 和 的聯(lián)系。（2）用直接選擇排序。 pnext=HL。A、24 B、48 C、72 D、533．一個數(shù)組元素a[i]與（ ）的表示等價。A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)5．?dāng)?shù)據(jù)結(jié)構(gòu)是（ ）。3．一個算法的時間復(fù)雜度為(3n2+2nlog2n+4n7)/(5n)，其數(shù)量級表示為 。三、應(yīng)用題（每題10分，共60分）1．設(shè)有5個互不相同的元素a、b、c、d、e，能否通過7次比較就將其排好序？如果能，請列出其比較過程；如果不能，則說明原因。A、O(1) B、O(n) C、O(n2) D、O(log 2 n)假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為 。 一棵深度為5的滿二叉樹中的結(jié)點數(shù)為 個，一棵深度為3的滿四叉樹中的結(jié)點數(shù)為 個。三、運算題（每題6分，共24分） 假定一棵普通樹的廣義表表示為 a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后根、按層遍歷的結(jié)果。四、閱讀算法（第一題7分，第二題8分） void AA(LNode * amp。 } 該算法被調(diào)用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數(shù)據(jù)元素依次為： 。 i=j。 else 。A. pLlink=q。qLlink=pLlink。 A. ij1 B. ij C. ji+1 D. 不確定的7．有六個元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8．用鏈接方式存儲的隊列，在進(jìn)行刪除運算時（ ）。6．所謂稀疏矩陣指的是_______。先序：中序：后序：按層：3．已知一個圖的頂點集V和邊集G分別為：V={0,1,2,3,4,5,6,7}。四、算法填空（10分）1． 五、編程（10分）1．設(shè)計算法以求解從集合{1..n}中選取k（k=n）個元素的所有組合。 7．在最壞的情況下，冒泡排序法的時間復(fù)雜度為（ ）。5．當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top = =N表示?？?，則表示棧滿的條件為 。13．快速排序在平均情況下的空間復(fù)雜度為 ，在最壞情況下的空間復(fù)雜度為 。2．void AF（Queue＆Q）{ InitQueue（Q）： int a [4]={5，8，12，15} for（int i一0；i＜4；i斗＋＝ Qln