應(yīng)本數(shù)據(jù)結(jié)構(gòu)試卷

1、2013年一、單項(xiàng)選擇題1.以下數(shù)據(jù)結(jié)構(gòu)是非線性結(jié)構(gòu)的是( D)。A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹2設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ B）。A 5，3，4，6，1，2B 3，2，5，6，4，1C 3，1，2，5，4，6D 1，5，4，6，2，33.引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是(A)。A.出隊(duì)B.入隊(duì) C.取隊(duì)頭元素D.取隊(duì)尾元素4采用散列技術(shù)實(shí)現(xiàn)表的存儲(chǔ)和查找 ，需解決的主要問題是（ D ）。A如何申請(qǐng)到足夠大的空間 B如何正確認(rèn)識(shí)元素之間的邏輯關(guān)系 C如何找到一個(gè)好的查找方法 D如何構(gòu)造一個(gè)散列地址均勻分布的散列函數(shù)5廣義表A

2、=(a,(b),(), c,( d,e)的長(zhǎng)度為( B ) A.4 B.5 C.6 D.7 6.樹結(jié)構(gòu)最適合用來表示( C )。A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)7設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到的序列為（ A ）。ABADCBBCDACCDABDCBDA8設(shè)某棵二叉樹中有1000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（ B ）。A9B10C11D129.已知森林F=T1，T2，T3，T4，T5，各棵樹Ti(i=1，2，3，4，5)中所含結(jié)點(diǎn)的個(gè)數(shù)分別為7，3，5，1，4，則與F對(duì)應(yīng)的二叉樹

3、的右子樹中結(jié)點(diǎn)個(gè)數(shù)為(D )。A.2 B.3 C.11 D.1310.除根結(jié)點(diǎn)外，樹上每個(gè)結(jié)點(diǎn)( A )A.可有任意多個(gè)孩子、一個(gè)雙親B.可有任意多個(gè)孩子、任意多個(gè)雙親C.可有一個(gè)孩子、任意多個(gè)雙親D.只有一個(gè)孩子、一個(gè)雙親11.設(shè)某散列表的長(zhǎng)度為10，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（B ）。A9B 7C 1D 312數(shù)據(jù)的基本單位是（ C ）。A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量13下面程序的時(shí)間復(fù)雜度為( )。for（i=1，s=0； i=n； i+） t=1;for(j=1；jnext=s；front=s；Bs-next=rear；rear=s；Crear-n

4、ext=s；rear=s；Ds-next=front；front=s；17如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是（C）。A.棧 B.隊(duì)列 C.樹 D.圖18下面關(guān)于線性表的敘述錯(cuò)誤的是（ D ）。A線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)19.若以S和X分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作序列是（D ）。A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX2

5、0多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲(chǔ)方式是因?yàn)椋–）。A數(shù)組的元素處在行和列兩個(gè)關(guān)系中B數(shù)組的元素必須從左到右順序排列C數(shù)組的元素之間存在次序關(guān)系D數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)21. 對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為7的元素個(gè)數(shù)為（ B ）。A1 B2 C3 D422設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（B ）。A小于等于m的最大奇數(shù)B小于等于m的最大素?cái)?shù)C大于等于m的最大奇數(shù)D大于等于m的最大素?cái)?shù)23若有序表的關(guān)鍵字序列為（b,c,d,e,f,g

6、,q,r,s,t），則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為（B）。Af,c,b Bf,d,b Cg,c,b Dg,d,b24判斷一個(gè)順序棧st（最多元素為StackSize）為棧滿的條件表達(dá)式是（D）。Ast.top!= StackSize Bst.top!=0 Cst.top=-1 Dst.top=StackSize-125以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中（n0），空鏈域的個(gè)數(shù)為（B）。A2n-1 Bn+1 Cn-1 D2n+126下列程序段的時(shí)間復(fù)雜度為（ C ）。i=0,s=0; while(in) s=s+i;i+;AO(n1/2)BO(n1

7、/3)CO(n)DO(n2)27算法指的是（ D ）。A計(jì)算機(jī)程序 B運(yùn)算方法C排序方法 D解決問題的方法或步驟28在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（D）。A插入B刪除 C排序D查找29在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素(1in)之前插入一個(gè)元素時(shí)，需要依次后移元素個(gè)數(shù)為（B）。An-i Bn-i+1 Cn-i-1 Di30設(shè)順序循環(huán)隊(duì)列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ C ）。AR-FBF-RC(R-F+M)MD(F-R+M)M31從廣義表LS（(p,q)

8、,r,s）中分解出原子q的運(yùn)算是（A）。Atail(head(LS)Bhead(tail(head(LS)Chead(tail(LS)Dtail(tail(head(LS)32已知廣義表的表頭為A，表尾為(B,C)，則此廣義表為（C ）。A.(A,(B,C) B.（A）,B,C）C.(A,B,C) D.(A,B,C)33. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（ D ）。A2k-1 B.2k+1 C.2k-1 D. 2k-134. 設(shè)一棵完全二叉樹中有60個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（C ）。A8B7C6D535.某二叉樹的前序和后序序列正好相同，則該二叉樹的特點(diǎn)是（A ）。A空或者只有一個(gè)結(jié)點(diǎn) B

9、高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無左孩子 D任一結(jié)點(diǎn)無右孩子36設(shè)輸入序列是1、2、3、n，經(jīng)過棧的操作后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（ A ）。An-iBn-1-iCn+1-iD不能確定37設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有的結(jié)點(diǎn)個(gè)數(shù)為（D）。A2k-1B2kC2k-1D2k-138. 下列有關(guān)二叉樹的說法中正確的是（ B ）。A二叉樹的度一定為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為239設(shè)某三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為（ B ）。A3B4C5D640設(shè)F是由T1、T2和T3三棵樹組成的森林

10、，與F對(duì)應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的右子樹的結(jié)點(diǎn)數(shù)為（ C ）。 AN1-1BN2-1CN2+N3DN1+N341采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（ B ）。 A n B (n+1)/2 Cn/2 D (n-1)/242下列程序段的時(shí)間復(fù)雜度為（A ）。s=i=0；do i=i+1； s=s+i；while(i=n)；A. O(n)B. O(nlog2n)C. O(n2)D. O(n3/2)43在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成（B）。A內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B線性結(jié)構(gòu)和非線性結(jié)構(gòu)C緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D動(dòng)態(tài)結(jié)構(gòu)和

11、靜態(tài)結(jié)構(gòu)44根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該元素存儲(chǔ)地址的存儲(chǔ)方法是（D）。A順序存儲(chǔ)方法B鏈?zhǔn)酱鎯?chǔ)方法 C索引存儲(chǔ)方法D散列存儲(chǔ)方法45若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是（ B ）。A問題規(guī)模 B語(yǔ)句條數(shù)C循環(huán)層數(shù) D函數(shù)數(shù)量46設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作后其頭指針rear值為（ D ）。Afront=front+1 Brear=rear+1Cfront=(front+1)%m Drear =( rear +1)%m47隊(duì)列和棧的主要區(qū)別是（D ）。A.邏輯結(jié)構(gòu)不同 B.存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)

12、數(shù)不同 D.限定插入和刪除的位置不同48設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置為644，A22存放位置為676，每個(gè)元素占一個(gè)存儲(chǔ)空間，則A33存放位置為（ C）。 A688 B678 C692 D69649.對(duì)廣義表L=(a,b),(c,d),(e,f)執(zhí)行操作tail(tail(L)的結(jié)果是(B)。A.(e,f) B.(e,f) C.(f)D.()50設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（ B）。ANl+N2+NmBl+N2+2N3+3N4+(m-1)NmCN2+2N3+3N4+(m-1)NmD2Nl+3N2+(m+1)Nm51

13、. 深度為k的完全二叉樹中最少結(jié)點(diǎn)個(gè)數(shù)為（ B ）。A2k-1-1B2k-1C2k-1+1D2k-152設(shè)按照從上到下、從左到右的順序，從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。A2i+1B2iCi/2D2i-153除第一層外，滿二叉樹中每一層結(jié)點(diǎn)個(gè)數(shù)是上一層結(jié)點(diǎn)個(gè)數(shù)的（C）。A1/2倍B1倍 C2倍D3倍54.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序從前往后掃描的第一趟冒泡排序結(jié)束后的結(jié)果是（ D ）。AF，H，C，D，P，A，M，Q，R，S，Y，XBP，A，C，S，Q，D，F(xiàn)，X，R，H，M，YCA，D，C，

14、R，F(xiàn)，Q，M，S，Y，P，H，XDH，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y55.設(shè)一個(gè)順序有序表A114中有14個(gè)元素，則采用二分法查找元素A4的過程中比較元素的順序?yàn)? C )。AA1，A2，A3，A4BA1，A14，A7，A4CA7，A3，A5，A4DA7，A5 ，A3，A456線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元地址(A )。A不一定是連續(xù)的 B部分地址必須是連續(xù)的C必須是連續(xù)的D一定是不連續(xù)的57.一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為( C ) 。 A.3 B.4 C.5 D.6 58若有18個(gè)元素的有序表存放在一維數(shù)組A118中，第一個(gè)元素存放在A1中，現(xiàn)進(jìn)行二

15、分查找，則查找A3的比較序列依次為( )。A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，359能進(jìn)行二分查找的線性表,必須以（A）。A順序方式存儲(chǔ),且元素按關(guān)鍵字有序B鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字有序C順序方式存儲(chǔ),且元素按關(guān)鍵字分塊有序D鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字分塊有序60對(duì)于哈希函數(shù)H(key)=key%13，被稱為同義詞的關(guān)鍵字是( D )。A35和41 B.23和39C.15和44 D.25和5161.設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（C ）。A. O(n)B. O(nlog2n)C. O(1)D. O(n2)62算法分析

16、的目的是（B）。A辨別數(shù)據(jù)結(jié)構(gòu)的合理性 B評(píng)價(jià)算法的效率C研究算法中輸入與輸出的關(guān)系 D鑒別算法的可讀性63具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ C ）。A樹 B多維數(shù)組 C棧和隊(duì)列 D廣義表64.廣義表L= (a，()的表尾是( B)。A.() B.()C.a D.(a)65設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ D ）。A空或只有一個(gè)結(jié)點(diǎn)B高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無左孩子D任一結(jié)點(diǎn)無右孩子66 在對(duì)n個(gè)關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進(jìn)行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個(gè)數(shù)為（D）。Ai Bi+1 Cn-iDn-i+16

17、7若棧采用順序存儲(chǔ)結(jié)構(gòu)，則下列說法中正確的是（ ）。A需要判斷棧滿且需要判斷?？誃不需要判斷棧滿但需要判斷?？誄需要判斷棧滿但不需要判斷?？誅不需要判斷棧滿也不需要判斷?？?8在任意一棵二叉樹的前序序列和后序序列中，各葉子結(jié)點(diǎn)之間的相對(duì)次序關(guān)系（B）。A不一定相同 B都相同 C都不相同 D互為逆序69利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（ C）。AO(n)BO(nlog2n)CO(n2)DO(log2n)70.假定一個(gè)順序隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件為 （ D ）。Af+1=r Br+1=f Cf=0 Df=r71一個(gè)非空廣義表的表尾（ B ）。A不可

18、能是子表 B只能是子表C只能是原子 D可以是子表或原子72.二維數(shù)組A45采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且第1個(gè)元素的地址為100，則元素A23的地址為(A)。A.126B.125 C.127D.12873.設(shè)一組初始關(guān)鍵字的長(zhǎng)度為9，則插入排序可以得到有序序列的最多排序趟數(shù)為（C）。A6B7C8D974查找運(yùn)算主要是對(duì)關(guān)鍵字的（C ）。A移位B交換C比較D定位75用散列函數(shù)求元素在散列表中的存儲(chǔ)位置時(shí)，可能會(huì)出現(xiàn)不同的關(guān)鍵字得到相同散列函數(shù)值的沖突現(xiàn)象?？捎糜诮鉀Q上述問題的是( A )A.線性探測(cè)法B.除留余數(shù)法C.平方取中法D.折疊法二、填空題1所謂“就地排序”，是指排序

19、算法輔助空間的復(fù)雜度為 穩(wěn)定 的排序方法。2在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)方法、_鏈?zhǔn)酱鎯?chǔ)方法_、索引存儲(chǔ)方法和散列存儲(chǔ)方法等四種。3.當(dāng)棧空時(shí)再做退棧運(yùn)算產(chǎn)生的溢出稱為_下溢_。4.一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱是 _數(shù)據(jù)類型_。5.隊(duì)列的操作是按_先進(jìn)先出_原則進(jìn)行的。6.去除廣義表LS=(a1,a2,，an)中第1個(gè)元素，由其余元素構(gòu)成的廣義表稱為L(zhǎng)S的_表尾_。7已知廣義表C=(a，(b，c)，d)，則tail(head(tail(C)= _(c)_。8實(shí)現(xiàn)二分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)，且其中元素排列必須是_ _有序_的。9數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器

20、內(nèi)的表示，稱為數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 。10被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表是 隊(duì)列 。11若待散列的序列為(18, 24，35，12，27，18，26)，散列函數(shù)為H(key)=key%9，與18發(fā)生沖突的元素有_2_個(gè)。12.設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為13的元素需要經(jīng)過_3_次比較。13含有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，空指針域的個(gè)數(shù)為_n+1_。 14對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為_99_。15

21、對(duì)n個(gè)記錄的排序文件進(jìn)行冒泡排序時(shí)，最多的比較次數(shù)是_n-1_n(n-1)/2_。16.數(shù)據(jù)物理結(jié)構(gòu)的主要實(shí)現(xiàn)方法包括兩種情況：鏈?zhǔn)酱鎯?chǔ)方法和_ 順序存儲(chǔ)方法_。17下述程序段的的時(shí)間復(fù)雜度為_O(n)_。k=1; for(i=0;in;i+) Aij=k+; 18高度為5的完全二叉樹的結(jié)點(diǎn)數(shù)至少有 16 。19設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1，則T中的葉子數(shù)為 8 。20一種抽象數(shù)據(jù)類型封裝的兩部分是數(shù)據(jù)和 操作 。21.若允許表達(dá)式內(nèi)多種括號(hào)混合嵌套，則為檢查表達(dá)式中括號(hào)是否正確配對(duì)的算法中通常選用的輔助數(shù)據(jù)結(jié)構(gòu)是_順序棧結(jié)構(gòu)_。22.對(duì)一棵完全二叉樹按

22、從1開始順序編號(hào)，則編號(hào)為25的結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為_12_。23設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中共有_129_個(gè)結(jié)點(diǎn)。24.假設(shè)用表示樹的邊（其中x是y的雙親），已知一棵樹的邊集為,，則該樹的度是_3_。25.設(shè)一組初始關(guān)鍵字序列為(76，65，13，38，97，27，10)，則第1趟從前往后掃描的冒泡排序結(jié)果為_10，76，65，13，38，97，27_ _65,13,38,76,27,10,97_。26.若序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱該排序算法是_穩(wěn)定_。27.先在所有的記錄中選出鍵值最小的記錄，將它與第一個(gè)記錄交換；然后在其

23、余的記錄中再選出最小的記錄與第二個(gè)記錄交換，依此類推，直至所有記錄排序完成。這種排序方法稱為_直接選擇排序_。28.按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有_5_種。29.解決散列表沖突的開放地址法分為線性探測(cè)法、雙重散列法和_二次探查法_。30.設(shè)有一批數(shù)據(jù)元素，為了最快地存取某元素，宜用_順序_存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。31數(shù)據(jù)類型按其值能否分解,通?？煞譃樵宇愋秃蚠結(jié)構(gòu)類型_兩種。32.數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面包括_邏輯結(jié)構(gòu)_、存儲(chǔ)結(jié)構(gòu)和運(yùn)算。33.棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端稱為_棧頂_。34假設(shè)三維數(shù)組A1098按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且第一個(gè)元素a000的存儲(chǔ)地址為100，

24、則元素a987的存儲(chǔ)地址是 _1801_2257_。 35用廣義表的取表頭head和取表尾tail的運(yùn)算，從廣義表LS=(b,c,(f),(d)中分解出原子c的操作為_head(tail(LS)_。36.廣義表L=(a，(b，( )的長(zhǎng)度為_2_。37.任意一棵完全二叉樹中，度為1的結(jié)點(diǎn)數(shù)最多為_1_。38.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第2趟遞增的直接選擇排序后的結(jié)果為_10,13,97,76,65,27,38_。39.設(shè)有序查找表中有100個(gè)元素，如果用二分法查找數(shù)據(jù)元素X，則最少需要比較_7_次就可以斷定數(shù)據(jù)元素X是否在查找表中。40循環(huán)隊(duì)列用數(shù)組

25、Am存放元素值，已知其頭、尾指針分別是front和rear，則當(dāng)前隊(duì)列中元素的個(gè)數(shù)是_(rear-front+m) % m_。41若進(jìn)棧序列為a,b,c則通過入出棧操作可能得到的a,b,c的不同排列個(gè)數(shù)為_5_。42已知一棵完全二叉樹中共有768個(gè)結(jié)點(diǎn)，則該樹中葉子結(jié)點(diǎn)的個(gè)數(shù)是 384 。43有一個(gè)長(zhǎng)度為30的有序表采用二分查找方法進(jìn)行查找，則查找長(zhǎng)度為3的元素個(gè)數(shù)為 4 。44.設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_2k-1_。45.具有n個(gè)結(jié)點(diǎn)的二叉樹，擁有指向孩子結(jié)點(diǎn)的分支數(shù)目是_n-1_。46設(shè)順序表中有n個(gè)數(shù)據(jù)元素，則在第i個(gè)位置上插入一個(gè)

26、數(shù)據(jù)元素需要移動(dòng)表中_n-i n-i+1_個(gè)數(shù)據(jù)元素。47在初始為空的隊(duì)列中插入元素A,B,C,D以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)頭元素是_C_。48假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為 bceda 。49n個(gè)結(jié)點(diǎn)的滿二叉樹的高度為 log(n+1) 。50.對(duì)一組初始關(guān)鍵字序列（40，50， 20，15，70，95，60，45，10）進(jìn)行自前向后掃描的冒泡排序，則第一趟需要移動(dòng)的記錄的次數(shù)為_8_5_。51.在一般情況下用直接插入排序、直接選擇排序和冒泡排序的過程中，所需記錄交換次數(shù)最少的是_n-1

27、_。52.如果一個(gè)算法總的運(yùn)行次數(shù)是常數(shù)，則該算法的時(shí)間復(fù)雜度為_O(1)_。53.若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用_鏈?zhǔn)絖存儲(chǔ)結(jié)構(gòu)。54.設(shè)順序棧存放在S.datamaxsize中，棧底位置是maxsize-1，變量top指示棧頂元素的位置，則?？諚l件是_s.top=maxsize-1 s.top=maxsize_。55.冒泡排序是一種穩(wěn)定排序方法。該排序方法的時(shí)間復(fù)雜度為_ O(n2)_。56.對(duì)n個(gè)記錄采用直接選擇排序方法，第一趟排序所執(zhí)行的記錄交換次數(shù)最少為_n-1_0_。57.對(duì)一個(gè)表長(zhǎng)為n的線性表采用順序查找，在等概率情況下，查找成功的平均查找長(zhǎng)度是_（n+1）/

28、2_。58.圖中樹T的度為_3_。59.在各種查找算法中，平均查找長(zhǎng)度和結(jié)點(diǎn)的個(gè)數(shù)n無關(guān)的查找方法是_哈希表_。60.已知二叉樹有7個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為5，則總結(jié)點(diǎn)數(shù)為_18_。61. 數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借助 指針 表示數(shù)據(jù)元素之間的邏輯關(guān)系。62數(shù)據(jù)結(jié)構(gòu)算法中，通常用空間復(fù)雜度和 時(shí)間復(fù)雜度 兩種方法衡量其效率。63. 設(shè)輸入序列為1、2、3，則經(jīng)過入棧和出棧操作后可以得到 5 種不同的輸出序列。64.棧下溢是指在?？諘r(shí)進(jìn)行 退棧 操作。65. 設(shè)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCD，則該二叉樹的中序遍歷序列為 DBAC 。66二分查找排序的時(shí)間復(fù)雜度

29、是 O(log2n) 。67.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的_物理結(jié)構(gòu)_。68在有序表（12，24，36，48，60，72，84）中利用順序查找關(guān)鍵字72時(shí)，所需進(jìn)行的關(guān)鍵字比較次數(shù)為 6 。 69.產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的 同義詞 。70.設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有 512 個(gè)。71.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)，且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉樹中共有 2n-1 個(gè)結(jié)點(diǎn)。72.若一個(gè)算法中的語(yǔ)句頻度之和為T(n)=3720n+4log2n，則算法的時(shí)間復(fù)雜度為 O(n) 。73.線性表L=（a1,a2,an）采用順

30、序存儲(chǔ)，假定在不同的n+1個(gè)位置上插入的概率相同，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)是 0 n/2 。74.已知完全二叉樹的第5層有4個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)目是 10 。75.描述客觀事物的數(shù)、字符以及能輸入計(jì)算機(jī)中并被計(jì)算機(jī)處理的符號(hào)的集合被稱為 數(shù)據(jù) 。三、應(yīng)用綜合題1、已知有6個(gè)元素A,B,C,D,E,F依次進(jìn)棧，若得到的出棧序列為ADCFEB，請(qǐng)寫出棧操作的過程。用PUSH(i)表示i進(jìn)棧，POP( )表示出棧。 PUSH(i)POP(i) PUSH(i) PUSH(i) PUSH(i)POP(i)POP(i) PUSH(i) PUSH(i) POP(i) POP(i) POP(i

31、)2、已知循環(huán)隊(duì)列Q的順序存儲(chǔ)類型定義如下：#define QueueSize 100typedef char DataType;typedef struct DataType dataQueueSize; int front,rear;CirQueue;CirQueue *Q;請(qǐng)分別寫出判斷隊(duì)空和隊(duì)滿的條件。 隊(duì)空的條件：Q-front=Q-rear; 隊(duì)滿的條件: (Q-rear + 1)% QueueSize = Q-front;3、設(shè)二維數(shù)組A56的每個(gè)元素占3個(gè)字節(jié)，已知Loc(a00)=100，請(qǐng)回答：按行優(yōu)先存儲(chǔ)時(shí)，計(jì)算a25的存儲(chǔ)地址； a25的存儲(chǔ)地址=100+(2*6+5)

32、*3=151按列優(yōu)先存儲(chǔ)時(shí)，寫出數(shù)組A的第12個(gè)元素下標(biāo)，并說明原因。 數(shù)組A的第12個(gè)元素下標(biāo)=2,1 因?yàn)樵摂?shù)組按列存儲(chǔ)的。每列為5個(gè)元素。4、已知三維數(shù)組Amnp按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占d個(gè)存儲(chǔ)單元，第一個(gè)元素的存儲(chǔ)地址為L(zhǎng)oc(a000)，請(qǐng)寫出：數(shù)組A共占的字節(jié)數(shù)=m*n*p*d數(shù)組A的任一個(gè)元素aijk的存儲(chǔ)地址計(jì)算公式。 公式= Loc(a000)+(i*n*p+j*p+k)*d;5、請(qǐng)計(jì)算以下廣義表的表頭和表尾。(a),(b),c),(d),(e) 表頭和表尾：(a)和(b),c),(d),(e) 表尾應(yīng)為(b),c),(d),(e)(a,b),(c,(d,e)

33、 表頭和表尾：(a,b)和(c,(d,e) 表尾應(yīng)為：(c,(d,e)6、請(qǐng)計(jì)算以下廣義表的長(zhǎng)度和深度。(a,b,c,(d) 長(zhǎng)度和深度:4和4 深度為2(a),(b,c,d) 長(zhǎng)度和深度:2和2 看長(zhǎng)度與深度的定義7、設(shè)用函數(shù)head( )、tail( )分別表示取廣義表的表頭和表尾操作，請(qǐng)寫出：取出廣義表A=(x,y,z),(a,b,c,d)中(y,z)的函數(shù)； 函數(shù)= tail(head(A)取出廣義表A=(x,(a,b)c,d)中原子x的函數(shù)。 函數(shù)=head(A);8、設(shè)二叉樹后序遍歷為ABC，請(qǐng)畫出所有可能的二叉樹。 9、請(qǐng)畫出具有3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。 10、樹T如下圖

34、所示，請(qǐng)回答： 樹T的度；3此處有問題吧，4樹T的度為3。結(jié)點(diǎn)I的層次和雙親結(jié)點(diǎn)；2層和雙親是H。從結(jié)點(diǎn)K到結(jié)點(diǎn)N是否有路徑。如果有，請(qǐng)計(jì)算該路徑長(zhǎng)度。有，路徑長(zhǎng)度是：3 路徑長(zhǎng)度指的是線段長(zhǎng)度嗎11、有一棵完全二叉樹按層次順序存放在一維數(shù)組中，如下所示： 請(qǐng)回答問題：指出結(jié)點(diǎn)K的雙親結(jié)點(diǎn)；H 雙親為i/2下取整指出結(jié)點(diǎn)D的左孩子結(jié)點(diǎn)； B 左孩子為2i，右孩子為2i+1（3）計(jì)算該二叉樹的度:4 12個(gè)結(jié)點(diǎn)log212下取整+1=412、設(shè)二叉樹bt的存儲(chǔ)結(jié)構(gòu)如下：不會(huì)下標(biāo)12345678910left00237580101datajhfdbacegiright0009400000其中bt為

35、樹根結(jié)點(diǎn)指針，left、right分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。左、右孩子指針域均為0的是葉子結(jié)點(diǎn)。請(qǐng)完成下列各題：畫出二叉樹bt； 寫出按前序遍歷二叉樹bt得到的結(jié)點(diǎn)序列。前序遍歷二叉樹bt序列：a b c e d f h g i j13、設(shè)一棵樹T中邊的集合為(A，B)，(A，C)，(B，D)，(C，E)，(C，F(xiàn))，(C，G)，其中邊（X，Y）表示X是Y的雙親。要求將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。 14、將下圖所示的二叉樹轉(zhuǎn)換成森林。 森林是： 15、將下圖所示的森林轉(zhuǎn)換成二叉樹。二叉樹是： 16、將下圖所示的樹轉(zhuǎn)換成二叉樹。 二叉樹是： 此圖中C改為L(zhǎng)17、對(duì)下圖所示

36、二叉樹分別按前序、中序和后序遍歷，給出相應(yīng)的結(jié)點(diǎn)序列。 前序遍歷是：ABDEGHCF 中序遍歷是：DBGEHAFC后序遍歷是：DGHEBFCA已知一棵二叉樹的中序遍歷結(jié)點(diǎn)排列為DGEHBFCA，后序遍歷結(jié)點(diǎn)排列為DGHEBFCA，畫出此二叉樹，并寫出該二叉樹的前序遍歷序列。 二叉樹是： 二叉樹的前序遍歷序列是：ACFBEGDH:已知一棵二叉樹的前序序列為ABDFCEGH，中序序列為BFDAGEHC，畫出此二叉樹，并寫出該二叉樹的后序遍歷序列。 二叉樹是： 二叉樹的后序遍歷序列是：FDBGHECA20、二叉樹bt的結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)，如圖所示：下標(biāo)01234567891011121314151

37、6171819btEAFDGCJHIB請(qǐng)完成下列各題：畫出二叉樹bt； 寫出按后序遍歷二叉樹bt得到的結(jié)點(diǎn)序列。 后序遍歷二叉樹bt得到的結(jié)點(diǎn)序列是：B C J D A H I G F E21、對(duì)下圖所示的樹T，畫出其孩子兄弟鏈表存儲(chǔ)結(jié)構(gòu)。22、對(duì)關(guān)鍵字序列（49,38,27,13,97,76,50,65）進(jìn)行直接插入排序和直接選擇排序，使關(guān)鍵字遞增有序，請(qǐng)寫出每個(gè)排序方法的前三趟結(jié)果。1.直接插入排序： 一趟排序的結(jié)果：38， 49 , 27, 13, 97, 76, 50, 65 二趟排序的結(jié)果： 27，38，49，13，97，76，50，56 三趟排序的結(jié)果： 13，27，38，49，9

38、7，76，50，652. 直接選擇排序： 一趟排序的結(jié)果：13, 38, 27, 49 , 97, 76, 50, 65 二趟排序的結(jié)果：13, 27, 38, 49 , 97, 76, 50, 65三趟排序的結(jié)果：13, 27, 38, 49 , 97, 76, 50, 6523、若對(duì)序列(87，72，69，23，94，16，5，58)采從后往前掃描的冒泡排序法進(jìn)行遞增排序，請(qǐng)寫出前三趟排序的結(jié)果。 一趟排序的結(jié)果： 5，87，72，69，23，94，16，58二趟排序的結(jié)果： 5，16，87，72，69，23，94，58,三趟排序的結(jié)果： 5，16，23，87，72，69，94，58,第三

39、趟應(yīng)改為： 5，16，23，87，72，69，58，94，24、已知待散列的線性表為（22，41，53，33，46，30），散列用的一維地址空間為0.6，假定選用的散列函數(shù)是H（K）= K%7，若發(fā)生沖突采用線性探測(cè)法處理，請(qǐng)完成下列各題：（1）畫出該散列表，并在散列表中標(biāo)出查找每個(gè)關(guān)鍵字所需的比較次數(shù)；（2）計(jì)算在查找每一個(gè)元素概率相等情況下，查找成功時(shí)的平均查找長(zhǎng)度ASL。 ASL=(1*5 +4*1)/6=1.525、已知散列函數(shù)為H(k)=k mod 11, 關(guān)鍵字序列為35，67，42，21，29，86，95，47，50，36，91，處理沖突的方法為拉鏈法，請(qǐng)完成下列各題：（1）畫出

40、該散列表； （2）計(jì)算在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度ASL。 ASL=(7*1+3*2+1*3)/11=1.45四、程序綜合題1、 閱讀下列算法，并回答問題：(1)假設(shè)數(shù)組L= 7,9,5,4,2，寫出調(diào)用函數(shù)f (L,5)后L的內(nèi)容； 2,4,5,7,9(2)寫出上述函數(shù)調(diào)用過程中進(jìn)行元素交換操作的總次數(shù)。void f (int R,int n) int i,t; for (i=0;in-1;i+) while (Ri!=i) t=RRi; RRi= Ri; Ri=t; 總次數(shù)是： 4 次2、已知線性表的存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)結(jié)構(gòu)，閱讀下列算法，并回答問題：（1）設(shè)線性表L=（21，-

41、7，-8，19，0，-11，34，30，-10），寫出執(zhí)行f（&L）后L的內(nèi)容；（2）簡(jiǎn)述算法的功能。void f（SeqList *L） int i,j;for （i=j=0;ilength; i+）if（L-datai=0）if（i!=j）L-dataj=L-datai;j+；L-length=j; 算法的功能：將線性表L中的非負(fù)整數(shù)取出并按順序形成新線性表3、 閱讀下列算法，并回答問題：(1)設(shè)線性表L=（3，7，11，14，20，51），寫出執(zhí)行f(&L,28)之后L的內(nèi)容； 內(nèi)容； 3，7，11，14，20，28，51(2)簡(jiǎn)述算法的功能。void f(SeqList*L, Data

42、Type x) int i =0, j; while (ilength & xL-datai) i+; if(ilength & x=L-datai) for(j=i+1;jlength;j+) L-dataj-1=L-dataj; L-length-; else for(j=L-length;ji;j-) L-dataj=L-dataj-1; L-datai=x; L-length+; 功能：如果給定x的值與線性表L中的值相等，則刪除，否則按元素大小的順序插入線性表L的對(duì)應(yīng)位置。4、已知線性表的存儲(chǔ)結(jié)構(gòu)為順序表，閱讀下列算法，并回答問題：(1)簡(jiǎn)述算法f的功能；將線性表L中大于零的數(shù)取出并按

43、順序形成新線性表L。 (2)設(shè)線性表L=（-4，6，0，-27，11，-51，-30），寫出執(zhí)行f（&L）之后的L狀態(tài)。void f(SeqList *L) int i,j; for( i=j=0;ilength;i +) if(L-datai) 0) if(i!=j) L-dataj=L-datai; j+; L-length=j;L的內(nèi)容是：6,115、閱讀下列算法，并回答問題：（1）設(shè)線性表L=（1，2，3，4，5，6），寫出執(zhí)行f（&L）之后的L的內(nèi)容。 135246（2）寫出上述函數(shù)調(diào)用過程中進(jìn)行元素交換操作的總次數(shù)。void f(SeqList *L) int i,j=0,t;fo

44、r(i=0;ilength;i+) if(L- datai%2) if(i!=j) t=L- datai; L- datai=L- dataj;L- dataj=t;j+;總次數(shù)：26、閱讀下列算法，并回答問題：(1)簡(jiǎn)述算法的功能； 是通過一個(gè)中間棧T，達(dá)到刪除棧S中所有與變量相同的元素。 (2)假定棧S=1,3,7,9,11，寫出執(zhí)行算法f(S,3)后棧S中的元素內(nèi)容。void f(SeqStack *S,int c)/ 設(shè)DataType 為int 型SeqStack T;int d;InitStack(&T);while(!StackEmpty(S)d=Pop(S);if(d!=c)

45、Push(T,d);while(!StackEmpty(T)d=Pop(T);Push(S,d);S中的元素內(nèi)容：1,7,9,117、閱讀下列算法，并回答問題：(1)簡(jiǎn)述算法的功能； 借助棧實(shí)現(xiàn)判斷給定的字符串是否是回文，是返回1，否則返回0 (2)如果有字符串str=”abcdcba”，寫出執(zhí)行算法f(str)后的返回值。int f (char str)SeqStack S;int j,k,i=0;InitStack(&S);while(stri!=0) i+;for(j=0;ji/2;j+)Push(&S,strj);k=(i+1)/2;for(j=k;ji;j+)if(strj!=Pop

46、(&S) return 0;return 1; 返回值為18、閱讀下列算法，并回答問題：（1）Q、Q1和Q2都是隊(duì)列結(jié)構(gòu)，設(shè)隊(duì)列Q=（1，0，-5，2，-4，-6，9），其中1為隊(duì)頭元素，寫出執(zhí)行f（&Q,&Q1,&Q2）之后隊(duì)列Q、Q1和Q2的狀態(tài)；Q為空 Q1=-5，-4，-6 Q2=1，0，2，9（2）簡(jiǎn)述算法的功能。（注：InitQueue、EnQueue、DeQueue和QueueEmpty分別是隊(duì)列初始化、入隊(duì)、出隊(duì)和判隊(duì)空的操作）void f (Queue*Q, Queue*Q1, Queue*Q2) int e;InitQueue (Q1);InitQueue (Q2);whi

47、le (!QueueEmpty(Q) e=DeQueue(Q);if (edata);if(T-rchild)Push(&S,T-rchild);if(T-lchild) T=T-lchild;elseT=Pop(&S);輸出結(jié)果：ABDCEGF10、已知具有n個(gè)結(jié)點(diǎn)的完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)在向量BT1.n中，結(jié)點(diǎn)的數(shù)據(jù)元素為字符類型，請(qǐng)閱讀下列算法，并回答問題：(1)假設(shè)向量BT中的內(nèi)容如下，請(qǐng)寫出執(zhí)行f(BT,6)后的輸出結(jié)果；輸出結(jié)果：ABDECFBTABCDEF下標(biāo)123456 (2) 簡(jiǎn)述算法的功能。void f(char BT,int n) int i=1; while(i

48、0) if(i0) i+; 算法的功能: 前序遍歷11、已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，其類型定義如下：typedef struct NodeTypeDataType data;struct NodeType *left,*right; BTreeNode;閱讀下列算法，并回答問題：簡(jiǎn)述算法的功能； 算法的功能；中序遍歷 (2)對(duì)于如圖所示的二叉樹BT，寫出執(zhí)行算法f(BT,a,8)后數(shù)組a的內(nèi)容。void f (BTreeNode * BT, DataType a ,int n) static int i=0; if(BT!=NULL)f(BT-left,a,n);ai+=BT-data;f

49、(BT-right,a,n);數(shù)組A內(nèi)容：DBGEHACF12、已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下列算法，并回答問題：（1）對(duì)下圖所示的二叉樹T，畫出執(zhí)行算法f(T)后所建立的結(jié)構(gòu)；建立的單鏈表如下：D- F-H-G（2）簡(jiǎn)述算法的功能。typedef struct node DateType data；Struct node * next；ListNode；typedef ListNode * LinkList ；LinkList Leafhead=NULL；void f (BinTree T)LinkList s；if(T)f(T-lchild)； if (!T-lchild)&(!T

50、-rchild) s=(ListNode*)malloc(sizeof(ListNode)； s-data=T-data； s-next=Leafhead； Leafhead=s； f(T-rchild)；功能：中序遍歷，按葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表。13、假設(shè)以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，其類型定義如下：typedef struct node char data; struct node *lchild, *rchild; /左右孩子指針 BinTNode,*BinTree；閱讀下列算法，并回答問題：簡(jiǎn)述算法的功能；功能；如果該結(jié)點(diǎn)有右孩子且無左孩子，把右孩子作為左孩子。(2) 已

51、知如圖所示的二叉樹以T為指向根結(jié)點(diǎn)的指針，畫出執(zhí)行f 38(T)后的二叉樹。void f38(BinTree T) if (T) f 38 (T - lchild) ; f 38(T - rchild) ; if ( ( !T - rchild) & T-lchild) T - lchild=T-rchild; T - rchild=NULL;二叉樹是：14、已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，其類型定義如下：typedef struct NodeTypeDataType data;struct NodeType *left,*right; BTreeNode，*BTree;閱讀下列算法，并回答問

52、題：簡(jiǎn)述算法的功能； 功能； 前序遍歷二叉樹。(2)對(duì)于如圖所示的二叉樹BT，畫出執(zhí)行算法f后指針pt所指的二叉樹形態(tài)。BTree f(BTree BT) BTree pt;if(BT=NULL) return NULL;ECFABD else pt=( BTreeNode*)malloc( sizeof(BTreeNode);pt-data=BT-data;pt-right=f(BT-left);pt-left=f(BT-right);return pt; pt所指的二叉樹形態(tài)： 15、閱讀下列算法，并回答問題：說明算法f采用的排序方法：排序方法：直接插入排序法。簡(jiǎn)述算法f中R0的作用。R0

53、的作用：當(dāng)中間變量用。Typedef struct KeyType key; InfoType otherinfo;RecType;typedef RecType SqListMAXSIZE;void f(SqList R,int n)/n小于MAXSIZE -1，為順序表的長(zhǎng)度int i,j;for(i=2;i=n;i+) if(Ri.keyRi-1.key) R0=Ri;for(j=i-1;R0.keyRj.key;j-)Rj+1=Rj;Rj+1=R0;16、下列算法的功能是將x插入到遞增有序的數(shù)組A中，并保持插入后的數(shù)組元素依然有序。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。vo

54、id f(DataType A,int num,DataType x) /向量A目前有num個(gè)元素 int i=0,j; while (Ai=x & i=i;j-) _ Aj+1=Aj_;/ 向后移動(dòng)元素 Ai=x; ; / 插入元素 Ai=x;17、下列算法的功能是實(shí)現(xiàn)順序表就地逆置的操作。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。#define ListSize 200typedef struct Datatype dataListSize; int length;Seqlist;void Seq_Reverse(Seqlist *L) int i; Datatype temp;f

55、or(i=0; ilength ; i+) temp= L-datai;L-datai= L-dataL-length-1-i; ; L-dataL-length-1-i =temp;18、下列算法利用二分查找方法在有序表R中插入元素x，并保持表R的有序性，其中l(wèi)ength為表R的長(zhǎng)度。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。void BinInsert(SeqList R,int length,DataType x) int low=1,high=length,mid,i;while(low=high) mid=(low+high)/2;if (x.key=mid ;i-)Ri+1

56、=Ri; Rmid=x ;length+;19、下列算法的功能是將一個(gè)非負(fù)的十進(jìn)制數(shù)N轉(zhuǎn)換成二進(jìn)制數(shù)。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。void f(int N)SeqStack S;InitStack(&S);while( N )Push(&S, N%2); N=N/2; ; while(!StackEmpty(&S) i= Pop(&S) ; printf(%d,i);20、下列算法f2 的功能是清空帶頭結(jié)點(diǎn)的鏈隊(duì)列Q。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。typedef struct nodeDataType data;struct node *next;QueueNode;typedef struct QueueNode *front;/隊(duì)頭指針QueueNode *rear;/隊(duì)尾指針LinkQueue;void f2(LinkQueue *Q)QueueNode *p,*s;p= Q-front;while(p!=NULL) s=p; p=p-next; free(s); Q-front =NULL;Q-rear= NULL ;21、下列算法的功能是建立二叉樹。請(qǐng)?jiān)诳杖碧幪钊牒?/p>