【正文】 }}17。!find) {q=qrchild。} if (top0amp。find=1。itop。}if (top0) {q=stack[top1]。 tag[top++]=0。amp。q=T。{Bintree stack[max],q。j=n。}} while (flag)。a[i+1]=a[i]。 i+=2) //偶數(shù)掃描if (a[i]a[i+1]){flag=1。}for (i=2。a[i+1]=a[i]。i+=2) //奇數(shù)掃描if (a[i]a[i+1]){ flag=1 。for (i=1。}}}數(shù)據(jù)結(jié)構(gòu)模擬試題四參考答案一、( 共30分，每題2分)單項(xiàng)選擇題1A 2C 3A 4C 5D 6D 7B 8C 9C 10D 11D 12D 13C 14C 15 D二、（共40分，每空2分）填空題log2n snext=p 中序 300 一對(duì)一的，一對(duì)多或多對(duì)多的 最小 4 235129 2m1 1中序，M 12，4 1鄰接矩陣 1插入排序，選擇排序 1n+1,線索三、（10分）解：設(shè)N為總結(jié)點(diǎn)數(shù)，N0為葉子結(jié)點(diǎn)數(shù)則：N=N0+N1+N2+……+Nm又有：N1=度的總數(shù)，則：N1=N1*1+N2*2+……Nm*m則有：N0=1+N2+2N3+……+(m1)Nm四、（15分）cc(00)d(01)a(100)b(101)e(11)c d e a b五、（15分）線性探測(cè)再散列的散列表：0 1 2 3 4 5 6 7 8 9 10 11 1214168275519208479231110121431139113查找成功的平均長(zhǎng)度為ASL=1/12（1*6+2*1+3*3+4*1+9）=查找不成功的平均長(zhǎng)度為ASL=1/13（1+2+3+4…….+13）=7六（15分）（1）void oesort ( int a[n]){int i,flag。qnext=Bnext。}else {q=p。qnext=Anext。while (p!=L){if (pdata%2==1){q=p。B=(ListNode *)malloc(sizeof(ListNode ))。A=(ListNode *)malloc(sizeof(ListNode ))。A, ListNode *amp。//算右子樹的葉結(jié)點(diǎn)數(shù) } return leaf。 //如果該結(jié)點(diǎn)無左右孩子，則葉子數(shù)加1 GetLeaves(rootlchild)。}}八、（15分）解：int GetLeaves( BinTree root){ //求葉結(jié)點(diǎn)總數(shù) static int leaf=0。while (s!=NULL){printf(“%d”,sdata)。num=num/r。snext=head。s=(link *)malloc(sizeof(link))。int n。}link。（i，j）=LOC（0，0）＋（i*n＋j）*d－LOC（0，0）－（j*n＋i）*d =（i－j）*n*d＋（j－i）*d或： =（i－j）*（n－1）*d六、（10分）cc(00)d(01)a(100)b(101)e(11)c d e a b七、（15分）解：typedef struct node{int data。}數(shù)據(jù)結(jié)構(gòu)模擬試題五參考答案一、( 共34分，每題2分)單項(xiàng)選擇題C A D A B D B D C D 1A 1D 1D 1C 1D 1C 1C二、（共30分，每空2分）填空題答：有 、無答：N、2E答：結(jié)點(diǎn)的有窮集合、K上關(guān)系的有窮集合答：順序答：棧答：中答：4 答：2, 4 答：O(nlog2n) 答：n+1, 線索三：（共11分，每題1分）判斷題√ √ √ √1四、（10分）各趟結(jié)果如下：　　　　　 [68　05　71　23　16]　72　[94　73]　　　　　 [16　05　23] 68 [71]　72　[94　73]　　　　　 [05] 16 [23] 68 [71]　72　[94　73] 　　　　　　05　16 [23] 68 [71]　72　[94　73] 　　　　　　05　16　23　68　71　 72　[94　73] 　　　　　　05　16　23　68　71　 72　[73] 94 05　16　23　68　71　 72 　73　94五、（10分）按行存儲(chǔ)時(shí)與按列存儲(chǔ)時(shí)，計(jì)算A[i][j]地址的公式分別為 LOC（i，j）=LOC（0，0）+（I*n＋j）*d及 LOC39。 } cout”A平臺(tái)的最大值是：”na。amp。 case ‘B’: count(‘B’,nb)。 while (s!=’’){ switch(s) { case ‘A’: count(‘A’,na)。if (in) n=i 。cins。 i=0。 void count(char t, int amp。}}數(shù)據(jù)結(jié)構(gòu)模擬題三參考答案 √ √ √ . √ √二．填空題隊(duì)列為空 隊(duì)列中有2個(gè)或2個(gè)以上元素 非零元素個(gè)數(shù)的一半 66 3 12 根據(jù)記錄指針從數(shù)據(jù)區(qū)中讀記錄 繼續(xù)沿指針向下一直查到該關(guān)鍵字所在樹葉 1． 0 1 2 3 4 5 6HT2715104517202． 1 2 3 4 5 6 7 8llinkrlink2305241774264180（1，17，4，16，15，9，8，14，6，16，11，12，17，2，17，17）1..char s。(countmaxtimes)){ add(A,B)。 if((result==0)amp。A, list amp。 } count++。 if(x0){ 。 i++。 [j]=x%10。for (j=maxlength。i=。A, list amp。 i++) cout[i]。 if (result==1) for(i=。 } if (ij) result=0。([i]==[j])){ i++。 while((ij)amp。 i=。void test(list amp。 int s。} maxlength=40,maxtimes=30。 pnext=head。 r=rnext。 p=r。 r=p。 p=qnext。 void del(){ pointer p,q,r,s。 } typedef node* pointer。 node{ int data。 k=j。 c++。 (3)while (a=k) {S[c]=R[a]。 (2)S[c]=R[b]。 b=k+1。(G[u][v]==c0)) paint(u,v,c)。(v=n)amp。(v=1)amp。(u=m)amp。 if ((u=1)amp。 i++){ u=x+d[i][0]。 for (i=0。 void paint(int x, int y, int c){ int i , u, v。 int G[m+1][n+1]。 }n=j1。 i++) if (R[i]!=x){ R[j]=R[i]+x。 for (i=1。void add(){ int i, j。int R[n0+1]。(4) M[i]=1。amp。 i=1。九、（15分）設(shè)計(jì)一個(gè)算法將單循環(huán)鏈表L分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表A、B，其中，A表中結(jié)點(diǎn)是L表中值為奇數(shù)的結(jié)點(diǎn)，而B表中結(jié)點(diǎn)是L表中值為偶數(shù)的結(jié)點(diǎn)（要求利用原表結(jié)點(diǎn)）。要求算法中用到的棧采用線性鏈表存儲(chǔ)結(jié)構(gòu)（1r10）。設(shè)計(jì)以該權(quán)值為基礎(chǔ)的赫夫曼樹，并給出赫夫曼編碼。五、（10分）對(duì)于一個(gè)nn的矩陣A的任一元素A[i][j]，按行存儲(chǔ)時(shí)和按列存儲(chǔ)時(shí)的地址之差是多少。( ) 1無向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣則一定是非對(duì)稱矩陣。( ) 對(duì)具有n個(gè)頂點(diǎn)的連通圖進(jìn)行深度優(yōu)先遍歷，所得定點(diǎn)序列是唯一的。（ ）在散列法中采取開散列（鏈地址）法來解決沖突時(shí)，其裝載因子的取值一定在（0，1）之間。 （ ）當(dāng)向一個(gè)小根堆（最小堆）中插入一個(gè)具有最小值的元素時(shí)，該元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。（ 　　　）二叉排序樹或者是一顆空二叉樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值；若它的右子樹非空，則根結(jié)點(diǎn)的值小于其左孩子的值。三：（共11分,每題1分）判斷題(下列各題，你認(rèn)為正確的，請(qǐng)打“ √”，錯(cuò)的打“”)線性表采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。快速排序的平均時(shí)間復(fù)雜度是（ ）。前序?yàn)閍bc且后序?yàn)閏ba的二叉樹共有（ ）棵。通常