【正文】 值集合{72，73，71，23，94，16，05，68}對(duì)應(yīng)的二叉樹進(jìn)行進(jìn)堆，并寫出具體步驟。五、判斷題(10分)1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。( )5．對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞情況下的時(shí)間復(fù)雜度是0(n2)。( )9．按中序遍歷一棵二叉排序樹所得到的中序遍歷序列是一個(gè)遞增序列10．進(jìn)棧操作push(x，s)作用于鏈接棧時(shí)，無需判滿。 (A)‘STRUCTURE’ (B)‘DATA’ (C)‘ASTRUCTURE’ (D)‘DATA STRUCTURE’5．下列哪種排序需要的附加存儲(chǔ)開(A)快速排序 (B?堆排序 (C)歸并排序 (D)插人排序6．對(duì)任何一棵樹T，設(shè)分別是度為0，1，…，m的結(jié)點(diǎn)，則（ ）。2．雙向循環(huán)鏈表的主要優(yōu)點(diǎn)是______________。6．具有128個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_______________。 bubble(Rectype R[n]) { int i，j，exchang； Rectype temp。j=______________。 ___________________。 2．線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡述各自關(guān)于運(yùn)算實(shí)現(xiàn)的優(yōu)缺點(diǎn)。(10 分)2．編寫一個(gè)算法計(jì)算一個(gè)廣義表的原子結(jié)點(diǎn)個(gè)數(shù)。( )2．先序遍歷一棵一又搜索樹所得的結(jié)點(diǎn)訪問序列不可能是鎂值遞增序列、( )3．若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。( )7．進(jìn)棧操作時(shí)，必須判斷棧是否已滿。 (A)快速排序 (B)堆排序 (c)歸并排序 (D)計(jì)數(shù)排序4．若按( )列出二叉排序樹中所存儲(chǔ)的元素，則恰好是集合中所有元素從小到大的排序。 for(i＝l。j) s=s+1。10．設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則需要修改指針的操作為( )。( )3．在堆中執(zhí)行INSERT與DELETEMIN運(yùn)算都只需O(log2n)時(shí)間。( )7．先序遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列不可能是鏈值遞增序列。(三、填空題(每空2分．共22分)1．在雙向循環(huán)表中，在p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為____________＝p。2．若字符串t＝‘a(chǎn)babcab’，前綴函數(shù)next[5]＝________________3．一個(gè)具有M個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_________________。7．設(shè)一棵二叉樹共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則它共有__________個(gè)度為2的結(jié)點(diǎn)。(5分)3．樹與二叉樹之間有何區(qū)別?(5分)4．巳知圖如下所示。（注，）(10分)3．設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉樹中所在的層次。jt。i++)for(j=0。k++) c[i][j]= c[i][j]+ a[i][k]* b[k][j]。(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)5．在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是( )。 snext=pnext。 pnextprior=s。 snext=pnext。 pnext=s。 (A)4 (B)5 (C)6 (D)710．在一個(gè)具有n個(gè)結(jié)點(diǎn)的無向完全圖中，包含有( )條邊。(A)4 (D)5 (L)6 (D)7二、填空題(22分，前4題每空2分，第5題每空1分)1．若要在一個(gè)單鏈表的*p結(jié)點(diǎn)之前插入一個(gè)*s結(jié)點(diǎn)時(shí)，可執(zhí)行下列操作snext=____________； pnext=s；t=pdata；pdata=____________；sdata=____________。 4．一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄的交換次數(shù)為__________，在整個(gè)排序過程中共需進(jìn)行_________趟才可以完成。( )3．設(shè)有兩個(gè)串p和q．其中q是p的子串，把q在p中首次出現(xiàn)的位置作為q在p中的位置的算法稱為匹配。( )7．哈希表的查找效率主要取決于哈希建表時(shí)所選取的哈希函數(shù)和處理沖突的方法。①試按表中元素的次序依次插入一棵初始為空的二叉排序樹，字符之間以字典順序比較大?。嫵鰧?duì)應(yīng)的二叉排序樹，且求出在等概率情況下查找成功的平均查找長度。4．判別以下序列是否為堆，如果不是，則把它調(diào)整為堆。2．試設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉樹中的層次。 (A)線性結(jié)構(gòu) (B)樹結(jié)構(gòu) (C)圖結(jié)構(gòu) (D)鏈表結(jié)構(gòu)2．設(shè)有二維數(shù)組A[50][60]，其元素長度為1字節(jié)，按列優(yōu)先順序存儲(chǔ)，首元素A[0][0]的地址為200，則元素A[10][20]的存儲(chǔ)地址為( )。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6.—個(gè)55的對(duì)稱矩陣采用壓縮存儲(chǔ)，需要存儲(chǔ)( )個(gè)元素。3．在求最小生成樹的兩種算法中，____________算法適合于稀疏圖。7．二叉排序樹采用____________序遍歷可以得到結(jié)點(diǎn)的有序序列。（ ）2．如果某有向圖的所有頂點(diǎn)可以構(gòu)成一個(gè)拓?fù)渑判?，則說明有向圖存在回路。( )6．設(shè)一棵二叉樹共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則共有49個(gè)度為1的結(jié)點(diǎn)7．一個(gè)有序的單鏈表采用折半查找法比順序查找效率高得多。(5分)(2)如果下圖表示的是采用孩子—兄弟法轉(zhuǎn)換后的一棵樹。(5分)(2)基于你給出的鄰接矩陣，求從頂點(diǎn)6出發(fā)的深度優(yōu)先遍歷。(4分)Typedef struct { int data[100]。stop++。完成程序。}Node。 __________________。(5分)int strc(char s[], char t[]){ int i。t[i]!=0。}六、編程題(共15分)1．編寫算法對(duì)一個(gè)整型數(shù)組中的元素進(jìn)行位置調(diào)整，將所有負(fù)數(shù)放在下標(biāo)較低的一端，將所有正數(shù)放在下標(biāo)較高的一端，所有的0在中間。 *rchild。 (A)A，B，C，D，E (B)B，C，D，E，A (C)E，A，B，C，D (D)E，D，C，B，A 3．在所有排序方法中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無關(guān)的是( (A)快速排序 (B)冒泡排序 (C)直接插入排序 (D)直接選擇排序4．設(shè)一棵二叉樹共用20個(gè)度為2的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)共有( )個(gè)。 (A)O(1) (B)O(n) (C)O(n2) (D)O(log2n)8．一棵完全二叉樹中根結(jié)點(diǎn)的編號(hào)為l，而且23號(hào)結(jié)點(diǎn)有左孩子但沒有右孩子，則完全二叉樹總共有( )個(gè)結(jié)點(diǎn)。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。4．順序存儲(chǔ)的隊(duì)列如果不采用循環(huán)方式，則會(huì)出現(xiàn)下列問題：_________________。 8．設(shè)無向圖G有100條邊，則G至少有_____________個(gè)頂點(diǎn)。(5分)3．已知5個(gè)結(jié)點(diǎn)的權(quán)值分別是4，6，1，13，7，試畫出這些結(jié)點(diǎn)構(gòu)成的Huffman樹。(5分)5．(1)根據(jù)線性表(23，49，28，10，30，5，16)畫出二叉排序樹。 int front。 *e=Qdata[Qfront]。如果找不到值為x的元素，則新元素成為順序表的最后一個(gè)元素。 int length。 for(k=0。 else for(i=alength1。 return 1。 p=pnext)。(8分)Typedef struct LinkNode{ int data。2．已知單鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法判斷一個(gè)單鏈表中各結(jié)點(diǎn)的值是否由小到大排列。}Node。 (A)直接插入排序 (B)起泡排序 (c)快速排序 (D)直接選擇排序5．一棵Huffman樹總共有11個(gè)結(jié)點(diǎn)，則葉子結(jié)點(diǎn)有( )個(gè)。 (A)13 (B)401 (C)402 (D)403二、判斷題(每題1分，共8分。( )4．進(jìn)棧操作時(shí)，必須判斷棧是否已滿。（ ）8．對(duì)于二叉排序樹，根元素肯定是值最大的元素。 4．如果某有向圖的所有頂點(diǎn)可以構(gòu)成一個(gè)拓?fù)渑判蛐蛄?，則說明該有向圖__________。8．一個(gè)具有n個(gè)結(jié)點(diǎn)的線性表采用堆排序，在建堆之后還要進(jìn)行__________次堆調(diào)整。（5分）3．已知下圖是一個(gè)有向圖。(1)從頂點(diǎn)D開始，寫出各頂點(diǎn)加人生成樹的次序。(4分)(2)畫出刪除值為46的結(jié)點(diǎn)后的二叉排序樹。for(i= ____________________ 。 j++) { if(____________________){tmp=a[j]。完成以下程序。Node *search_link(Node *head, int e){Node *p, *q。 p=pnext) if(pdata==e) ________________。 Struct LinkNode *lchild, *rchild。 return。(8分)2．已知順序表的數(shù)據(jù)結(jié)構(gòu)如下，編寫算法．刪除順序表前面的10個(gè)元素。}SQ。(A)e (B)2e (C)n2一e (D)n2—2e4．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( )。(A)3 (B)4 (C)7 （D）8 8．已知某算法的執(zhí)行時(shí)間為，n為問題規(guī)模，則該算法的時(shí)間復(fù)雜度是( )。( )3．不論是行優(yōu)先還是列優(yōu)先，二維數(shù)組的最后一個(gè)元素的存儲(chǔ)位置是—樣的。( )7．一個(gè)稀疏矩陣采用三元組法存儲(chǔ)不可能是((5,3,7),(5,4,4),(5,3,5))。2．一個(gè)55的對(duì)稱矩陣采用壓縮存儲(chǔ)，需要存儲(chǔ)____________個(gè)元素。6．快速排序法在最差的情況下的時(shí)間復(fù)雜廢是______________。(5分) (2)在上述堆的堆頂元素去掉，把堆的最后一個(gè)元素放到堆頂位置，再調(diào)整為大頂堆(用二叉樹表示)。(1)畫出該無向圖的鄰接矩陣。(5分)(2)畫出最終的最小生成樹。struct LinkNode *next。 free(p)。 ________________ = pnext。下面的函數(shù)serach的功能是采用折半查找法查找值為e的元素，并返回其下標(biāo)，如果找不到，返回1。i2=n1。 else ________________。(7分)typedef struct{ int elem[100]。 ／* c將記錄小于0的元素個(gè)數(shù) *／for(i=0,c=0。 }xlength=_________________。提示：可先將數(shù)組排序。}Node。 (A)1140 (B)1145 (C)1120 (D)l1254．若用數(shù)組S[1..n]作為兩個(gè)棧S1和S2的共用存儲(chǔ)結(jié)構(gòu)，對(duì)任何一個(gè)棧，只有當(dāng)S全滿時(shí)才不能進(jìn)行人棧操作。 (A)n—l (D)2n一1 (C)n十1 (D)2n十17．某二叉樹的中序序列和后序序列正好相反，則該二叉樹一定是( )的二叉樹。 (A)堆排序 (D)冒泡排序 (c)簡單選鋒排序 (D)快速排序二、判斷題(每小題1分，共10分。( ) 4．如果一個(gè)串中的所有字符均在另一個(gè)串中出現(xiàn)，則說明前者是后者的子串。( )8．折半查找說法的前提之一是線性表有序。 2．對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q[0…M1]，隊(duì)首、隊(duì)尾指針分別為f和r，隊(duì)列判空的條件是________________。 5．已知二叉樹中葉子數(shù)為50，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為___________________。9．直接選擇排序算法在最好情況下所做的交換元素的次數(shù)為________________。 5．己知下面二又排序樹各結(jié)點(diǎn)的值依次為1～9，請(qǐng)寫出該二叉排序樹按層次遍歷的結(jié)果。 ／* 查找區(qū)間初始化 *／int m。 ／* 將查找區(qū)間定為左半邊 *／else________________。(每空2分)void SqList_Intersect(SqList A, SqList B, SqList amp。 j=) ／* A、B表均末到表尾 */ {if([i]==[j]) ／* A表元素比B表元素小，A表下標(biāo)后移 *／______________________。 j++。 { if(w0) { print(w, )。二叉樹類型定義如下。 2．編寫函數(shù)用于刪除元素遞增排列的帶首結(jié)點(diǎn)單鏈表L中值大于mink且小于maxk的所有元素，并給出其時(shí)間復(fù)雜度。