【正文】 指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為 和 。A、f+1==r B、r+1==f C、f==0 D、f==r由3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹 。先根： 。void AH(Heap amp。}else return 1。pLlinkRlink=q。7．廣義表的_______ 定義為廣義表中括弧的重數(shù)。例如，從集合{1..4}中選取2個元素的所有組合的輸出結(jié)果為：1 2，1 3，1 4，2 3， 2 4，3 4。6．假定一棵三叉樹的結(jié)點個數(shù)為50，則它的最小深度為 ，最大深度為 。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）從一維數(shù)組A[n]上進(jìn)行快速排序的遞歸算法。 （2分） 最小生成樹的權(quán)：55 3 1 2 5 6 四、閱讀算法，回答問題（第一題7分，第二題8分） （12，26，9，8，15，30，50） 向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。void b(int P[],int i,int k)//從集合（1..n）中選取k（k=n）個元素的所有組合{if (k==0) printf(P)。即包括1時，求出集合（2..n）中取出k1個元素的所有組合；不包括1 時，求出集合（2..n）中取出k個元素的所有組合。6．答：（1）176 （2）76和108 （3）28和116。 數(shù)據(jù)排列情況： 。2．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為 ，在表尾插入元素的時間復(fù)雜度為 ?！={0,2,1,3,1,4,2,4,2,5,3,6,3,7,4,7,4,8,5,7,6,7,7,8}。4．對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 ______個，單鏈表為_______個。qRlink=p。int Binsch( ElemType A[] , int low , int high , KeyType K ){ if ( low=high ){int mid = (low+high)/2。for ( int i=0。 1二分查找過程所對應(yīng)的判定樹既是一棵 ，又是一棵 。請構(gòu)造一棵哈曼夫樹，并計算該哈曼夫樹的帶權(quán)路徑長度wpl。A、無向圖 B、有向圖 C、稠密圖 D、稀疏圖10．若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為（ ）。 D、pnext=HLnext。元素值3456586394比較次數(shù)四、應(yīng)用題（每題10分，共50分）1．設(shè)待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。A、先進(jìn)先出 B、后進(jìn)先出 C、進(jìn)優(yōu)于出 D、出優(yōu)于進(jìn)8．假設(shè)以數(shù)組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。C、firstlink == first。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則樹中所含的結(jié)點數(shù)為 個，樹的深度為 ，樹的度為 。5．一棵有n(n0)個結(jié)點的d度樹，若用多重鏈表表示，樹中每個結(jié)點都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域? 為什么?儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是多少？數(shù)據(jù)結(jié)構(gòu)作業(yè)題（二）一、選擇題（每題2分，共20分）1．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（ ）。 jn。9．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。 棧又稱為 表，隊列又稱為 表。 對于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有 個，散列地址為3的元素有 個，散列地址為5的元素有 個。 if ( x=[j]) break。A．一定連續(xù) B．一定不連續(xù) C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù)4．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ ）。pLlink=q。請說明為什么不能或如何才能得到。A O（1） B O（1og2n）C O（n） D O（nlog2n）5．假設(shè)有兩個串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（ ）。11．以二分查找方法查找一個線性表時，此線性表必須是 存儲的 表。習(xí)題二參考答案一、選擇題（每題2分，共20分）12345678910BDACDDBBCA二、填空題（每空2分，共40分）1．n12．（15，02，21，24，26，57，43，66，81，48，73）3．O（n）4．HLnext==NULL HLnext==HL5．O(nlog2n) ；O(n2)6．6； 31； 197．2； 1； 1； 68． 6 9．集合結(jié)構(gòu)；線性結(jié)構(gòu)；樹型結(jié)構(gòu)；圖形結(jié)構(gòu)10．ni+1三、應(yīng)用題（每題10分，共60分）1．答：可以做到。 }else if (itemBSTdata) BST=BSTleft。amp。贈語； 如果我們做與不做都會有人笑，如果做不好與做得好還會有人笑，那么我們索性就做得更好，來給人笑吧！ 現(xiàn)在你不玩命的學(xué)，以后命玩你。 } return false。設(shè)ab,cd(ab和cd情況類似)，此時需2次比較，取b和d比較，若bd，則有序abd；若bd時則有序cdb，此時已進(jìn)行了3次比較。13．快速排序在平均情況下的空間復(fù)雜度為 ，在最壞情況下的空間復(fù)雜度為 。 7．在最壞的情況下，冒泡排序法的時間復(fù)雜度為（ ）。先序：中序：后序：按層：3．已知一個圖的頂點集V和邊集G分別為：V={0,1,2,3,4,5,6,7}。 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)行刪除運算時（ ）。A. pLlink=q。 i=j。四、閱讀算法（第一題7分，第二題8分） void AA(LNode * amp。 一棵深度為5的滿二叉樹中的結(jié)點數(shù)為 個，一棵深度為3的滿四叉樹中的結(jié)點數(shù)為 個。三、應(yīng)用題（每題10分，共60分）1．設(shè)有5個互不相同的元素a、b、c、d、e，能否通過7次比較就將其排好序？如果能，請列出其比較過程；如果不能，則說明原因。A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)5．?dāng)?shù)據(jù)結(jié)構(gòu)是（ ）。 pnext=HL。9．在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著 、 和 的聯(lián)系。3．在一棵樹中，（ ）沒有前驅(qū)結(jié)點。A、20 B、18 C、25 D、226．下列程序段的時間復(fù)雜度為（ ）。10的對稱矩陣A，將其下三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。C、pnext=HL。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．在任意一棵