【正文】 (C)歸并排序 (D)插人排序6．對(duì)任何一棵樹T，設(shè)分別是度為0，1，…，m的結(jié)點(diǎn)，則（ ）。 (A)1 (B)2 (C)3 (D)48．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( )。2．雙向循環(huán)鏈表的主要優(yōu)點(diǎn)是______________。4．設(shè)有一個(gè)空棧，現(xiàn)輸入序列為l，2，3，4，5，經(jīng)過Push，Push，Pop，Push，Pop，Push，Pop，Push后，輸出序列為__________________ 。6．具有128個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_______________。8．設(shè)鍵值序列為{k1，k2，…，kn}，建堆和排序全過程共需進(jìn)行____________次堆調(diào)整。 bubble(Rectype R[n]) { int i，j，exchang； Rectype temp。 do{ exchang = False。j=______________。 R[j1]=R[j]。 ___________________。 }while(________________)。 2．線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)述各自關(guān)于運(yùn)算實(shí)現(xiàn)的優(yōu)缺點(diǎn)。 4．快速排序?yàn)槭裁词遣环€(wěn)定的排序?試舉例說明。(10 分)2．編寫一個(gè)算法計(jì)算一個(gè)廣義表的原子結(jié)點(diǎn)個(gè)數(shù)。(8分)五、判斷題(每題1分，共8分。( )2．先序遍歷一棵一又搜索樹所得的結(jié)點(diǎn)訪問序列不可能是鎂值遞增序列、( )3．若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。（ ）5．二叉排序樹中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。( )7．進(jìn)棧操作時(shí)，必須判斷棧是否已滿。( )模擬試題4一、選擇題(20分)1．n個(gè)頂點(diǎn)的無向圖的鄰接表中結(jié)點(diǎn)總數(shù)最多有( )個(gè)。 (A)快速排序 (B)堆排序 (c)歸并排序 (D)計(jì)數(shù)排序4．若按( )列出二叉排序樹中所存儲(chǔ)的元素，則恰好是集合中所有元素從小到大的排序。6．下面程序段的時(shí)間復(fù)雜度為( )。 for(i＝l。j++) for(j=n。j) s=s+1。(A)必須是連續(xù)的 (B)連續(xù)不連續(xù)都可以(c)部分地址必須是連續(xù)的 (D)必須是不連續(xù)的8．具有2000個(gè)結(jié)點(diǎn)的二叉樹，其高度至少為( )。10．設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則需要修改指針的操作為( )。 (B)p＝p一＞next (C)p＝p一＞next一＞next (D)P一＞next＝p二、判斷題(10分)1．具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個(gè)元素，則必有ab的關(guān)系。( )3．在堆中執(zhí)行INSERT與DELETEMIN運(yùn)算都只需O(log2n)時(shí)間。( )5．即使某排序算法是不穩(wěn)定的，但該方法仍有實(shí)際應(yīng)用價(jià)值。( )7．先序遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列不可能是鏈值遞增序列。 ( )9．表中的每一個(gè)元京都有前驅(qū)和后繼元素。(三、填空題(每空2分．共22分)1．在雙向循環(huán)表中，在p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為____________＝p。______________＝f。2．若字符串t＝‘a(chǎn)babcab’，前綴函數(shù)next[5]＝________________3．一個(gè)具有M個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_________________。5．設(shè)鏈值序列為{K1,K2,…,Kn}，用篩選法建堆必須從第__________個(gè)元素開始篩選。7．設(shè)一棵二叉樹共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則它共有__________個(gè)度為2的結(jié)點(diǎn)。四、應(yīng)用題(20分)1．依次輸入集合{20，13，22，5，16，3，48，24}中的鍵值，得到一棵二叉排序樹，試畫出該二叉排序樹并求出在等概率下成功查找的平均查找長(zhǎng)度。(5分)3．樹與二叉樹之間有何區(qū)別?(5分)4．巳知圖如下所示。五、算法設(shè)計(jì)(28分)1．編寫一個(gè)程序，輸出二叉排序樹BT中最小的鍵值。（注，）(10分)3．設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉樹中所在的層次。im。jt。for(i=0。i++)for(j=0。j++)for(k=0。k++) c[i][j]= c[i][j]+ a[i][k]* b[k][j]。 (A) ni (B) ni+1 (C) ni1 (D) i3．在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)．在查找成功的情況下需平均比較( )個(gè)元素結(jié)點(diǎn)。(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)，其操作是( )。 sprior=p。 snext=pnext。 snext=pnext。 pnextprior=s。 pnextprior=s。 snext=pnext。 snext=pnext。 pnext=s。 (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)4 (B)5 (C)6 (D)710．在一個(gè)具有n個(gè)結(jié)點(diǎn)的無向完全圖中，包含有( )條邊。 (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ù)與記錄的初始排列無關(guā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=____________。 3．假定對(duì)線性表R[059]進(jìn)行分塊查找，共分10塊，每塊長(zhǎng)度等于6。 4．一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄的交換次數(shù)為__________，在整個(gè)排序過程中共需進(jìn)行_________趟才可以完成。三、判斷題(10分)1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單元。( )3．設(shè)有兩個(gè)串p和q．其中q是p的子串，把q在p中首次出現(xiàn)的位置作為q在p中的位置的算法稱為匹配。( )5．對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞情況下的時(shí)間復(fù)雜度是0(n2)。( )7．哈希表的查找效率主要取決于哈希建表時(shí)所選取的哈希函數(shù)和處理沖突的方法。( )9．按中序遍歷一棵二叉排序樹所得到的中序遍歷序列是一個(gè)遞增序列10．進(jìn)棧操作push(x，s)作用子鏈接棧時(shí)，無需判滿。①試按表中元素的次序依次插入一棵初始為空的二叉排序樹，字符之間以字典順序比較大?。嫵鰧?duì)應(yīng)的二叉排序樹，且求出在等概率情況下查找成功的平均查找長(zhǎng)度。2．已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。4．判別以下序列是否為堆，如果不是，則把它調(diào)整為堆。五、算法設(shè)計(jì)(18分)1．已知線性表的元素按遞增順序排列，并以帶首結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。2．試設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉樹中的層次。4．試設(shè)計(jì)將數(shù)組A[0…N—1]中所有奇數(shù)移到所有偶數(shù)之前的算法，要求不另外增加存儲(chǔ)空間，且時(shí)間復(fù)雜度為O(n)。 (A)線性結(jié)構(gòu) (B)樹結(jié)構(gòu) (C)圖結(jié)構(gòu) (D)鏈表結(jié)構(gòu)2．設(shè)有二維數(shù)組A[50][60]，其元素長(zhǎng)度為1字節(jié)，按列優(yōu)先順序存儲(chǔ)，首元素A[0][0]的地址為200，則元素A[10][20]的存儲(chǔ)地址為( )。 (A)5 (B)6 (C)7 (D)8 4．具有20個(gè)結(jié)點(diǎn)的二叉樹，其深度最大為( )。 (A) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6.—個(gè)55的對(duì)稱矩陣采用壓縮存儲(chǔ)，需要存儲(chǔ)( )個(gè)元素。 (A)3 (B)4 (C)5 (D)68．設(shè)一棵二叉樹共有50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則共有( )個(gè)度為2的結(jié)點(diǎn) (A)25 (B)49 (C)50 (D)51二、填空題(每題2分，共16分)1．一個(gè)算法，如果不論問題規(guī)模大小，運(yùn)行所需時(shí)間都一樣，則該算法的時(shí)間復(fù)雜度是_____________。3．在求最小生成樹的兩種算法中，____________算法適合于稀疏圖。5．設(shè)循環(huán)隊(duì)列Q[1..N]的首尾指針為F，R，當(dāng)插入元素時(shí)尾指針只加1，首指針F總是指向隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素的個(gè)數(shù)為____________。7．二叉排序樹采用____________序遍歷可以得到結(jié)點(diǎn)的有序序列。三、判斷題(每題1分，共8分。（ ）2．如果某有向圖的所有頂點(diǎn)可以構(gòu)成一個(gè)拓?fù)渑判?，則說明有向圖存在回路。4．Huffman樹沒有度為1的結(jié)點(diǎn)。( )6．設(shè)一棵二叉樹共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則共有49個(gè)度為1的結(jié)點(diǎn)7．一個(gè)有序的單鏈表采用折半查找法比順序查找效率高得多。( )四、簡(jiǎn)答題(共38分)1．排序(1)寫出線性表(26，45，12，z0，30，5，15，29，16，2，18)采用基數(shù)排序后，第一趟結(jié)束時(shí)的結(jié)果。(5分)(2)如果下圖表示的是采用孩子—兄弟法轉(zhuǎn)換后的一棵樹。(5分)3．已知下圖是一個(gè)有向圖。(5分)(2)基于你給出的鄰接矩陣，求從頂點(diǎn)6出發(fā)的深度優(yōu)先遍歷。(1)各元素的平均查找長(zhǎng)度是多少？(4分)(2)查找值為10的元素，查找時(shí)與哪些元素進(jìn)行了比較?(4分)五、程序填空題(共15分)1．己知STACK表示棧的數(shù)據(jù)結(jié)構(gòu)，push為將一個(gè)值為e的元素進(jìn)棧，若成功返回1，否則返回0。(4分)Typedef struct { int data[100]。 /* 棧頂元素的下標(biāo) */}STACK。stop++。return 1。完成程序。 Struct LinkNode *lchild。}Node。 if (__________________) return NULL。 __________________。 return 。(5分)int strc(char s[], char t[]){ int i。 s[i]!=0amp。t[i]!=0。 return(s[i]t[i])。}六、編程題(共15分)1．編寫算法對(duì)一個(gè)整型數(shù)組中的元素進(jìn)行位置調(diào)整，將所有負(fù)數(shù)放在下標(biāo)較低的一端，將所有正數(shù)放在下標(biāo)較高的一端，所有的0在中間。(7分)Typedef struct LinkNode{ int data。 *rchild。模擬試題7一、選擇題(每小題1分，共8分)1．如果樹的結(jié)點(diǎn)A有4個(gè)兄弟，而且B為A的雙親，則B的度為( )。 (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) front==rear (B) (rear+1)%MAXSIZE==front (C) frontrear==1 (D) rear%MAXSIZE==front6．設(shè)有1000個(gè)元素，用折半查找時(shí)，最小比較次數(shù)為( )。 (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)。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，則元素必為線性表。( )4．有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。( )6．圖的生成樹的邊數(shù)應(yīng)小于頂點(diǎn)數(shù)。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。2．已知某算法的執(zhí)行時(shí)間為(n+n2)/2+log2 (2n+1)，n 為問題