【正文】 UCTURE’ (B)‘DATA’ (C)‘ASTRUCTURE’ (D)‘DATA STRUCTURE’5．下列哪種排序需要的附加存儲(chǔ)開(kāi)(A)快速排序 (B?堆排序 (C)歸并排序 (D)插人排序6．對(duì)任何一棵樹(shù)T，設(shè)分別是度為0，1，…，m的結(jié)點(diǎn)，則（ ）。 （A） （B） （C） （D）7．對(duì)下圖v4的度為( )。 (A)1 (B)2 (C)3 (D)48．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( )。 (A)快速排序 (B)冒泡排序 (c)歸并排序 (D)直接插入排序9．設(shè)有1000個(gè)元素，用折半查找時(shí)，最大比較次數(shù)為( )，最小比較次數(shù)為( ) (A)25 (B)10 (C)7 (D)1二、填空題(26分)1．對(duì)于一個(gè)以順序?qū)崿F(xiàn)的共享?xiàng)1…n]，棧頂指針?lè)謩e為top1和top2，top1由小到大，top2由大到小，其判斷下溢的條件是_______________；判斷上溢的條件是_____________。2．雙向循環(huán)鏈表的主要優(yōu)點(diǎn)是______________。3．上三角矩陣壓縮存儲(chǔ)的下標(biāo)對(duì)應(yīng)關(guān)系k＝________________。4．設(shè)有一個(gè)空棧，現(xiàn)輸入序列為l，2，3，4，5，經(jīng)過(guò)Push，Push，Pop，Push，Pop，Push，Pop，Push后，輸出序列為_(kāi)_________________ 。5．后序序列和中序序列相同的二叉樹(shù)為_(kāi)________________。6．具有128個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)______________。7．有向圖G用鄰接矩陣A[1…m，1…m ]存儲(chǔ)，其第i行的所有元素值之和等于頂點(diǎn)vi的__________________。8．設(shè)鍵值序列為{k1，k2，…，kn}，建堆和排序全過(guò)程共需進(jìn)行____________次堆調(diào)整。9．在下面冒泡排序算法中填入適當(dāng)內(nèi)容，使該算法在發(fā)現(xiàn)有序時(shí)能及時(shí)停止。 bubble(Rectype R[n]) { int i，j，exchang； Rectype temp。 i＝1。 do{ exchang = False。 for(j=n。j=______________。j) if(R[j]R[j1]){ temp=R[j1]。 R[j1]=R[j]。 R[j]=temp。 ___________________。 } _________________。 }while(________________)。 }三、應(yīng)用題(24分) 1．已知一棵二叉樹(shù)的中序遍歷結(jié)果為DBHEAFICG，先序遍歷結(jié)果為ABDEFHCFIG，試畫出該二叉樹(shù)。 2．線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)述各自關(guān)于運(yùn)算實(shí)現(xiàn)的優(yōu)缺點(diǎn)。 3．給定有序表D＝{15，17，18，22，35，60，88，93}，用折半查找法在D中查找18，試用圖示法表示查找過(guò)程。 4．快速排序?yàn)槭裁词遣环€(wěn)定的排序?試舉例說(shuō)明。四、算法設(shè)計(jì)(30分)1．有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，編寫在值為x的結(jié)點(diǎn)之后插入m個(gè)結(jié)點(diǎn)的算法。(10 分)2．編寫一個(gè)算法計(jì)算一個(gè)廣義表的原子結(jié)點(diǎn)個(gè)數(shù)。(12分)3．設(shè)計(jì)一個(gè)算法，用于查找中序線索二叉樹(shù)中結(jié)點(diǎn)*p的中序前驅(qū)結(jié)點(diǎn)。(8分)五、判斷題(每題1分，共8分。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，則元素必為線性表。( )2．先序遍歷一棵一又搜索樹(shù)所得的結(jié)點(diǎn)訪問(wèn)序列不可能是鎂值遞增序列、( )3．若有一個(gè)葉子結(jié)點(diǎn)是某子樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹(shù)的先序遍歷的最后一個(gè)結(jié)點(diǎn)。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。（ ）5．二叉排序樹(shù)中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。( )6．圖的生成樹(shù)的邊數(shù)應(yīng)小于頂點(diǎn)數(shù)。( )7．進(jìn)棧操作時(shí)，必須判斷棧是否已滿。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。( )模擬試題4一、選擇題(20分)1．n個(gè)頂點(diǎn)的無(wú)向圖的鄰接表中結(jié)點(diǎn)總數(shù)最多有( )個(gè)。 (A)2n 〔B)n (C)n/2 (D)n(n1)2．設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹(shù)的邊數(shù)為( ) (A)n (B)n一1 (C)2n (D) 2n13．下列哪種排序需要的附加存儲(chǔ)開(kāi)銷最小( )。 (A)快速排序 (B)堆排序 (c)歸并排序 (D)計(jì)數(shù)排序4．若按( )列出二叉排序樹(shù)中所存儲(chǔ)的元素，則恰好是集合中所有元素從小到大的排序。 (A)先序 (B)中序 (C)后序 (D)按層次5．在下列4棵樹(shù)中，哪一棵是完全二叉樹(shù)( )。6．下面程序段的時(shí)間復(fù)雜度為( )。s=s0。 for(i＝l。i=n。j++) for(j=n。j=n1。j) s=s+1。 (A)O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7．采用鏈結(jié)構(gòu)存儲(chǔ)線性表時(shí)，其地址( )。(A)必須是連續(xù)的 (B)連續(xù)不連續(xù)都可以(c)部分地址必須是連續(xù)的 (D)必須是不連續(xù)的8．具有2000個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度至少為( )。 〔A)9 (B)10 (C)11 (D)129．按字母順序，下圖中的二叉排序樹(shù)是( )。10．設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則需要修改指針的操作為( )。 (A)p一＞next＝p一＞next一＞next。 (B)p＝p一＞next (C)p＝p一＞next一＞next (D)P一＞next＝p二、判斷題(10分)1．具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個(gè)元素，則必有ab的關(guān)系。( )2．二叉排序樹(shù)的左、右子樹(shù)都是二叉排序樹(shù)。( )3．在堆中執(zhí)行INSERT與DELETEMIN運(yùn)算都只需O(log2n)時(shí)間。( )4．一棵滿二叉樹(shù)同時(shí)又是一棵平衡樹(shù)。( )5．即使某排序算法是不穩(wěn)定的，但該方法仍有實(shí)際應(yīng)用價(jià)值。( )6．連通分量是無(wú)向圖中的極小連通子圖。( )7．先序遍歷一棵二叉排序樹(shù)所得的結(jié)點(diǎn)訪問(wèn)序列不可能是鏈值遞增序列。( )8．不論adt棧是用數(shù)組實(shí)現(xiàn)，還是用指針實(shí)現(xiàn)，Pop(s)與Push(x’s)的時(shí)間復(fù)雜度均)(M)。 ( )9．表中的每一個(gè)元京都有前驅(qū)和后繼元素。( )10．作為解決一類特定問(wèn)題的算法，不能沒(méi)有輸入運(yùn)算項(xiàng)。(三、填空題(每空2分．共22分)1．在雙向循環(huán)表中，在p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為_(kāi)___________＝p。f一＞next＝p一＞next。______________＝f。p一＞next＝f。2．若字符串t＝‘a(chǎn)babcab’，前綴函數(shù)next[5]＝________________3．一個(gè)具有M個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_(kāi)________________。4．有序字典是以______________為基礎(chǔ)的抽象數(shù)據(jù)類型。5．設(shè)鏈值序列為{K1,K2,…,Kn}，用篩選法建堆必須從第__________個(gè)元素開(kāi)始篩選。6．哈希表的兩種形式是：__________和__________。7．設(shè)一棵二叉樹(shù)共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則它共有__________個(gè)度為2的結(jié)點(diǎn)。8．高度為h(≥0)的二叉樹(shù)，至少有__________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。四、應(yīng)用題(20分)1．依次輸入集合{20，13，22，5，16，3，48，24}中的鍵值，得到一棵二叉排序樹(shù)，試畫出該二叉排序樹(shù)并求出在等概率下成功查找的平均查找長(zhǎng)度。(5分)2．設(shè)下圖所示的二叉樹(shù)是由森林轉(zhuǎn)換而成的，試將它還原為森林。(5分)3．樹(shù)與二叉樹(shù)之間有何區(qū)別?(5分)4．巳知圖如下所示。(5分)(1)要求用Kruskal算法求出最小生成樹(shù)(2)指出生成樹(shù)的第一條邊。五、算法設(shè)計(jì)(28分)1．編寫一個(gè)程序，輸出二叉排序樹(shù)BT中最小的鍵值。(8分)2．我們用鏈表來(lái)存儲(chǔ)多項(xiàng)式, 其中, ,試編寫求微商的算法。（注，）(10分)3．設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉樹(shù)中所在的層次。(10分)模擬試題5一、選擇題(30分)1．下列程序的時(shí)間復(fù)雜度為( )for(i=0。im。i++)for(j=0。jt。j++) c[i][j]=0。for(i=0。im。i++)for(j=0。jt。j++)for(k=0。kn。k++) c[i][j]= c[i][j]+ a[i][k]* b[k][j]。 (A) O(mnt) (B) O(m+n+t) (C) O(m+n) (D) O(mt+n)2．從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)真值表歸約（1≤i≤n），需向前移動(dòng)（ ）個(gè)元素。 (A) ni (B) ni+1 (C) ni1 (D) i3．在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)．在查找成功的情況下需平均比較( )個(gè)元素結(jié)點(diǎn)。(A) n/2 (B) n (C) (n+1)/2 (D) (n1)/24．對(duì)一個(gè)具有n個(gè)元素的線性表，建立其有序單鏈表的時(shí)間復(fù)雜度為( )。(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)，其操作是( )。 (A) pnext=s。 sprior=p。 pnextprior=s。 snext=pnext。 (B) sprior=p。 snext=pnext。 pnext=s。 pnextprior=s。 (C) pnext=s。 pnextprior=s。 sprior=p。 snext=pnext。 (D) sprior=p。 snext=pnext。 pnextprior=s。 pnext=s。 6．串的長(zhǎng)度是( )。 (A)串中不同字符的個(gè)數(shù) (B)串中不同字母的個(gè)數(shù) (C)串中所含字符的個(gè)數(shù)n(n＞0) (D)串中所含字符的個(gè)數(shù)n(n≥0)7．若有一個(gè)棧的輸入序列是l，2，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是( )。 (A) ni (B) ni1 (C) ni+1 (D) 不確定8．設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，B，C，D，E，下列( )是不可能的出棧序列 (A)A，B，C，D，E (B)B，C，D，E，A (C)E，A，B，C，D (D)E，D，C，B，A 9．在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)有2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為l的結(jié)點(diǎn)數(shù)有2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有( )個(gè)。 (A)4 (B)5 (C)6 (D)710．在一個(gè)具有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖中，包含有( )條邊。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) nn11．采用順序查找法查找長(zhǎng)度為n的線性表．則查找每個(gè)元素的平均比較次數(shù)為( ) (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/212．已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)二分查找值為90的元素時(shí)，需( )次比較可查找成功。 (A)1 (B)2 (C)3 (D)413．在順序存儲(chǔ)的線性表R[029]上進(jìn)行順序查找的平均查找長(zhǎng)度為(①)，進(jìn)行二分查找的平均查找長(zhǎng)度為(②)，講行分塊查找（設(shè)分為5塊)的平均查找長(zhǎng)度為(③) ①(A)15 (B)15．5 (C)16 (D)20 ②(A)4 (B)62／15 (C)64／15 (D)25／6 ③(A)6 (B)11 (C)5 (D)6．514．在所有排序方法中，關(guān)健碼的比較次數(shù)與記錄的初始排列無(wú)關(guān)的是( )。 (A)Shell排序 (c)直接插入排序15．已知8個(gè)元素(34，76，45，18，26，54，92，65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)，該樹(shù)的深度為( )。(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=____________；