【正文】 三、解答題（本大題共4小題，每小題5分，共20分）26．畫出下列廣義表的共享結(jié)構(gòu)圖形表示 P=（（（z）,(x,y)）,((x,y),x),(z)）27．請(qǐng)畫出與下列二叉樹(shù)對(duì)應(yīng)的森林。2033int str(LinkString s1,LinkString s2) {//s1和s2為兩個(gè)鏈串的頭指針 while(s1amp。s2){ if(s1－dates2－date)return－1； if(s1－dates2－date)return1； ① ； ② ； } if( ③ )return－1； if( ④ )return1； ⑤ ； }①②③④⑤31．閱讀下面的算法 LinkList mynote(LinkList L) {//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(Lamp。Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 請(qǐng)回答下列問(wèn)題： （1）說(shuō)明語(yǔ)句S1的功能； （2）說(shuō)明語(yǔ)句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。 return1； } ① ② ③33．已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。amp。五、算法設(shè)計(jì)題（本題共10分）34．閱讀下列函數(shù)arrange() int arrange(int a[],int 1,int h,int x) {//1和h分別為數(shù)據(jù)區(qū)的下界和上界 int i,j,t； i=1；j=h； while(ij){ while(ij amp。 a[j]=x)j； while(ij amp。 a[j]=x)i++； if(ij) { t=a[j]；a[j]=a[i]；a[i]=t；} } if(a[i]x) return i； else return i－1； } （1）寫出該函數(shù)的功能； （2）寫一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組b[n]中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè)數(shù)。 單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分） 1．D ２．Ｂ ３．Ｃ ４．Ｂ ５．Ｄ ６．Ａ ７．Ｃ ８，Ｄ ９，Ａ 10．Ｃ 11．Ｄ 12．Ｃ 13．Ｄ 14．Ｃ 15．Ｂ二、填空題（本大題共10小題，每小題2分，共20分） 16．存儲(chǔ)（或存儲(chǔ)結(jié)構(gòu)） －＞next－＞next 18．進(jìn)棧和退棧 19．12 20．a(chǎn)4,8 21．384 22．a(chǎn)befcdg 23．快速排序、堆排序、希爾排序 24．２ 三、解答題（本大題共4小題，每小題5分，共20分） 26．a(chǎn)mp。amp。 （2）int f(int b[],int n) 或 int f(int b[],int n) { { int p,q； int p,q； p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； } }一、選擇題（20分）1．組成數(shù)據(jù)的基本單位是（ ）。 (A) 線性結(jié)構(gòu) (B) 樹(shù)型結(jié)構(gòu) (C) 圖型結(jié)構(gòu) (D) 集合3．?dāng)?shù)組的邏輯結(jié)構(gòu)不同于下列（ ）的邏輯結(jié)構(gòu)。 (A) 2i (B) 2i (C) 2i1 (D) 2i15．設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（ ）。 (A) 6 (B) 4 (C) 3 (D) 27．將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中，則數(shù)組A的長(zhǎng)度最少為（ ）。 (A) 3 (B) 4 (C) 5 (D) 19．根據(jù)二叉樹(shù)的定義可知二叉樹(shù)共有（ ）種不同的形態(tài)。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希爾排序 設(shè)順序循環(huán)隊(duì)列Q[0：m1]的隊(duì)頭指針和隊(duì)尾指針?lè)謩e為F和R，其中隊(duì)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向當(dāng)前隊(duì)尾元素所在的位置，則出隊(duì)列的語(yǔ)句為F =____________。 設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為_(kāi)__________，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為_(kāi)__________。 設(shè)一棵二叉樹(shù)中有n個(gè)結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí)，該二叉鏈表中共有________個(gè)指針域，__________個(gè)空指針域。 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)B，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為_(kāi)_____________________________________。 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)和e條邊，則其對(duì)應(yīng)的鄰接表中有_________個(gè)表頭結(jié)點(diǎn)和_________個(gè)表結(jié)點(diǎn)。 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為m，則e和m有______關(guān)系。 設(shè)一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹(shù)的后序遍歷序列為_(kāi)_________。 設(shè)一棵完全二叉樹(shù)中有21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開(kāi)始順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是___________，編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是_____________。 下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語(yǔ)句。while(istrlen(s) amp。 jstrlen(t)) if(s[i]==t[j]){i=i+l。}else{i=_______。}if (j==strlen(t))return(istrlen(t))。}10. 10.2．設(shè)給定一個(gè)權(quán)值集合W=(3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹(shù)并計(jì)算哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。4．設(shè)一組初始記錄關(guān)鍵字集合為(25，10，8，27，32，68)，散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k mod 7，要求分別用線性探測(cè)和鏈地址法作為解決沖突的方法設(shè)計(jì)哈希表。 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹(shù)的算法。 設(shè)計(jì)判斷一棵二叉樹(shù)是否是二叉排序樹(shù)的算法。一、選擇題 二、填空題1. 1. O(n)，O(n)3. 3. snext=pnext。 n, 2e6. 6. CBA8. 8. ij+1，010. 10. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。 哈夫曼樹(shù)略，WPL=783. 3. 線性探測(cè)： 鏈地址法：5. 5. 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。 int top。int lklistsymmetry(lklist *head){ sqstack stack。 lklist *p。p!=0。 []=pdata。p!=0。 else return(0)。}2. 2.typedef char datatype。 struct node *lchild,*rchild。void createbitree(bitree *amp。 scanf(%c,amp。 if(ch==39。) {bt=0。}bt=(bitree*)malloc(sizeof(bitree))。createbitree(btlchild)。}3. 3.int minnum=32768,flag=1。 struct node *lchild,*rchild。void inorder(bitree *bt){ if (bt!=0) {inorder(btlchild)。 minnum=btkey。}}一、選擇題(24分)1．下面關(guān)于線性表的敘述錯(cuò)誤的是（ ）。 (A) 2m1 (B) 2m (C) 2m+1 (D) 4m3．設(shè)順序循環(huán)隊(duì)列Q[0：M1]的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA5．設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（ ）條邊。 (A) 9 (B) 10 (C) 11 (D) 127．設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，82. 2. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。 int top。void push(sqstack amp。else {____________________。}}3. 3. 中序遍歷二叉排序樹(shù)所得到的序列是___________序列（填有序或無(wú)序）。5. 5. 設(shè)某棵二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為_(kāi)________；若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有_______個(gè)空指針域。7. 7. 設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為_(kāi)__________________________。 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink）。 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。 設(shè)一棵樹(shù)T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹(shù)的存儲(chǔ)結(jié)構(gòu)并將該樹(shù)轉(zhuǎn)化成對(duì)應(yīng)的二叉樹(shù)。 設(shè)有無(wú)向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。四、算法設(shè)計(jì)題(16分) 1． 1． 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案二、填空題1. 1. ++，[]=x3. 3. O(n2)，O(nlog2n)5. 5. d/27. 7. (1，3，4，2)，(1，3，2，4) (22，40，45，48，80，78)，(40，45，48，80，22，78)2. 2. qrlink=prlink。 prlink=q。 2,ASL=91*1+2*2+3*4+4*2)=25/94. 4. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6. 6.四、算法設(shè)計(jì)題1. 1.void quickpass(int r[], int s, int t){ int i=s