【正文】 typedef struct node {int data。}2. 2. r[i]x) i=i+1。 if (ij) {r[i]=r[j]。void quickpass(int r[], int s, int t){ int i=s, j=t, x=r[s]。四、算法設(shè)計(jì)題1. 1. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6. 6. qrlink=prlink。 (22，40，45，48，80，78)，(40，45，48，80，22，78)2. 2. (1，3，4，2)，(1，3，2，4) O(n2)，O(nlog2n)5. 5.二、填空題1. 1.四、算法設(shè)計(jì)題(16分) 1． 1． 設(shè)有無(wú)向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。 設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為_(kāi)__________________________。7. 7. 中序遍歷二叉排序樹(shù)所得到的序列是___________序列（填有序或無(wú)序）。}}3. 3.void push(sqstack amp。 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。2. 2. (A) 9 (B) 10 (C) 11 (D) 127．設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。 (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ù)為（ ）。}}void inorder(bitree *bt){ if (bt!=0) {inorder(btlchild)。int minnum=32768,flag=1。}3. 3.}bt=(bitree*)malloc(sizeof(bitree))。 if(ch==39。void createbitree(bitree *amp。typedef char datatype。}2. 2.p!=0。p!=0。int lklistsymmetry(lklist *head){ sqstack stack。 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。 哈夫曼樹(shù)略，WPL=783. 3. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。 CBA8. 8. O(n)，O(n)3. 3. 設(shè)計(jì)判斷一棵二叉樹(shù)是否是二叉排序樹(shù)的算法。 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹(shù)的算法。 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。2．設(shè)給定一個(gè)權(quán)值集合W=(3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹(shù)并計(jì)算哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。}if (j==strlen(t))return(istrlen(t))。 jstrlen(t)) if(s[i]==t[j]){i=i+l。 下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語(yǔ)句。 設(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è)一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹(shù)的后序遍歷序列為_(kāi)_________。 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為m，則e和m有______關(guān)系。 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)和e條邊，則其對(duì)應(yīng)的鄰接表中有_________個(gè)表頭結(jié)點(diǎn)和_________個(gè)表結(jié)點(diǎn)。 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)B，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為_(kāi)_____________________________________。 設(shè)一棵二叉樹(shù)中有n個(gè)結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí)，該二叉鏈表中共有________個(gè)指針域，__________個(gè)空指針域。 設(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è)順序循環(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 =____________。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希爾排序 (A) 6 (B) 4 (C) 3 (D) 27．將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中，則數(shù)組A的長(zhǎng)度最少為（ ）。 (A) 線性結(jié)構(gòu) (B) 樹(shù)型結(jié)構(gòu) (C) 圖型結(jié)構(gòu) (D) 集合3．?dāng)?shù)組的邏輯結(jié)構(gòu)不同于下列（ ）的邏輯結(jié)構(gòu)。（五）D∧ （2）中序遍歷二叉樹(shù)，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指針的逆序單鏈表（或按二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表）。H!s1) ④s1(或s1!=NULL或s1amp。 28．該圖的圖形為： 圖1 圖2 27．?dāng)?shù)據(jù)結(jié)構(gòu)試題參考答案一、 一、amp。 （1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)； （2）說(shuō)明該算法的功能。(!T－rchild)){ s=(ListNode*)malloc(sizeof(ListNode))； s－data=T－data； s－next=Leafhead； Leafhead=s； } Inorder(T－rchild)； } } 對(duì)于如下所示的二叉樹(shù) int EnQueue (Queue2*Q,int i,DateType x) {//若第 i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0 if(i0||i1)return 0； if(Q－rear[i]==Q－front[ ① ]return0； Q－data[ ② ]=x； Q－rear[i]=[ ③ ]。amp。59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key))%m =0,1,…，m－1其中 h1(key)=key%11+1回答下列問(wèn)題：（1）對(duì)表中關(guān)鍵字35，20，33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？四、算法閱讀題（本大題共4小題，每小題5分，共20分）30．下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為： str(s1,s2)= 請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。29．已知一個(gè)散列表如下圖所示： 23．在單鏈表上難以實(shí)現(xiàn)的排序方法有 和 。21．已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有 個(gè)葉子結(jié)點(diǎn)。17．在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head= 。1．算法指的是（ ） A．計(jì)算機(jī)程序 B．解決問(wèn)題的計(jì)算方法 C．排序算法 D．解決問(wèn)題的有限運(yùn)算序列2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ） A．必須是不連續(xù)的 B．連續(xù)與否均可 C．必須是連續(xù)的 D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3．將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（ ） A．O（1） B．O（n） C．O（m） D．O（m+n）4．由兩個(gè)棧共享一個(gè)向量空間的好處是：（ ） A．減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B．節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C．減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D．節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率5．設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ ） A．front=front+1 B．front=(front+1)%(m1) C．front=(front1)%m D．front=(front+1)%m6．如下陳述中正確的是（ ） A．串是一種特殊的線性表 B．串的長(zhǎng)度必須大于零 C．串中元素只能是字母 D．空串就是空白串7．若目標(biāo)串的長(zhǎng)度為n，模式串的長(zhǎng)度為[n/3]，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3）8．一個(gè)非空廣義表的表頭（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子9．假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對(duì)應(yīng)的稀疏矩陣是（ ） 10．在一棵度為3的樹(shù)中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為( ) A．4 B．5 C．6 D．711．在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,零元素的個(gè)數(shù)為( ) A．e B．2e C．n2－e D．n2－2e12．假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序14．適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（ ）A．有序表 B．分塊有序表 C．三叉排序樹(shù) D．線性鏈表15．不定長(zhǎng)文件是指（ ）A．文件的長(zhǎng)度不固定 B．記錄的長(zhǎng)度不固定C．字段的長(zhǎng)度不固定 D．關(guān)鍵字項(xiàng)的長(zhǎng)度不固定 q→next=HL。 {Lnode *P=HL。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）1是：（low + high）/2。2336