【正文】 為空的條件是 (B) =NULL next=NULL !=NULL next!=head 4． 若元素的入棧順序?yàn)?1， 2， 3....， n， 如果第 2個(gè)出棧的元素是 n， 則輸出的第 i(1=i=n)個(gè)元素是 (D) +l +2 52 / 100 5． 串匹配算法的本質(zhì)是 (C) 6．設(shè)有一個(gè) 10階的對(duì)稱矩陣 A，采用行優(yōu)先壓縮存儲(chǔ)方式， a11為第一個(gè)元素，其存儲(chǔ)地址為 1，每個(gè)元素占一個(gè)字節(jié)空間，則 a85的地址為 (C) 7．若一棵二叉樹的前序遍歷 序列與后序遍歷序列相同，則該二叉樹可能的形狀是 (B) 2的結(jié)點(diǎn) 8．若根結(jié)點(diǎn)的層數(shù)為 1，則具有 n個(gè)結(jié)點(diǎn)的二叉樹的最大高度是 (A) B. 2log n???? C. 2log n????+1 9．在圖 G中求兩個(gè)結(jié)點(diǎn)之間的最短路徑可以采用的算法是 (A) 拉（ Dijkstra）算法 （ Kruskal）算法 (Prim)算法 (BFS)算法 10．下圖 G=(V,E)是一個(gè)帶權(quán)連通圖， G的最小生成樹的權(quán)為 (D) 11．在下圖中，從頂點(diǎn) 1出發(fā)進(jìn)行深度優(yōu)先遍歷可得到的序列是 (B) 2 3 4 5 6 7 4 2 6 3 7 5 4 2 5 3 6 7 2 4 6 5 3 7 12．如果在排序過(guò)程中不改變關(guān)鍵字相同元素的相對(duì)位置，則認(rèn)為該排序方法是 (B) 13．設(shè)有一組關(guān)鍵字 (19, 14, 23, 1， 6， 20, 4， 27, 5， 11, 10, 9)，用散列函數(shù) H(key)=key%13 53 / 100 構(gòu)造散列表，用拉鏈法解決沖突，散列地址為 1的鏈中記錄個(gè)數(shù)為 (C) 14．已知二叉樹結(jié)點(diǎn)關(guān)鍵字類型為字符，下列二叉樹中符合二叉排序樹性質(zhì)的是 (D) 15．若需高效地查詢多關(guān)鍵字文件，可以采用的文件組織方式為 (D) 二、填空題（本大題共 10小題，每小題 2分，共 20分） 16．下面程序段的時(shí)間復(fù)雜度為（ O(n)）。 sum=1； for(i=0。sumn。i++) sum+=1； 17．已知鏈表結(jié)點(diǎn)定義如下： typedef struct node{ char data[16]。 struct node *next。 } LinkStrNode。 如果每個(gè)字符占 1個(gè)字節(jié) ， 指針占 4個(gè)字節(jié) ， 則該鏈表的存儲(chǔ)密度是 （ ） 。 18．使用一個(gè) 100個(gè)元素的數(shù)組存儲(chǔ)循環(huán)隊(duì)列，如果采取少用一個(gè)元素空間的方法來(lái)區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，約定隊(duì)頭指針 front等于隊(duì)尾指針 rear時(shí)表示隊(duì)空。若為 front=8， rear=7，則隊(duì)列中的元素個(gè)數(shù)為（ 99）。 54 / 100 19． 3個(gè)結(jié)點(diǎn)可以組成（ 5）種不同樹型的二叉樹。 20．用 5個(gè)權(quán)值 {3, 2， 4， 5， 1}構(gòu)造的哈夫曼 (Huffman)樹的帶權(quán)路徑長(zhǎng)度是（ 33）。 21．若無(wú)向圖 G中有 n個(gè)頂點(diǎn) m條邊，采用鄰接矩陣存儲(chǔ)，則該矩陣中非 0元素的個(gè)數(shù)為（ 2m）。 22．影響排序效率的兩個(gè)因素是關(guān)鍵字的（ 比 較 ）次數(shù)和記錄的移動(dòng)次數(shù)。 23．對(duì)任 m階的 B樹，每個(gè)結(jié)點(diǎn)中最多包含（ m1）個(gè)關(guān)鍵字。 24．若兩個(gè)關(guān)鍵字通過(guò)散列函數(shù)映射到同一個(gè)散列地址，這種現(xiàn)象稱為（ 沖突 ）。 25．如果要為文件中的每個(gè)記錄建立一個(gè)索引項(xiàng)，則這樣建立的索引表稱為（ 稠密索引 ）。 三、解答題（本大題共 4小題，每小題 5分，共 20分） 26．要在［ 0..nl］ 的向量空間中建立兩個(gè)棧 stackl和 stack2，請(qǐng)回答： (1)應(yīng)該如何設(shè)計(jì)這兩個(gè)棧才能充分利用整個(gè)向量空間？ (2)若 stackl的棧頂指針為 topl,stack2的棧頂指針為 top2， 如果需要充分利用整個(gè)向量空間，則： 棧 stackl空的條件是：（） 。 棧 stack2空的條件是：（） 。 棧 stackl和棧 stack2滿的條件是：（）。 答： (1)采用雙向棧的形式， stack1的棧底設(shè)置在下標(biāo)為 0的元素上， stack2的棧底設(shè)置在下標(biāo)為 n1的元素上。 (2)top1=1， top2=n， top11=top2 27． 已知廣義表如下 ： A=(B,y),B=(x,L),L=(a,b),要求 ： (1)寫出下列操作的結(jié)果 ： tail(A)=（ (y)） 。 head(B)=（ x） 。 (2)請(qǐng)畫 出廣義表 A對(duì)應(yīng)的圖形表示。 答：AB yx La b 28．已知二叉樹如下： 55 / 100 請(qǐng)畫出該二叉樹對(duì)應(yīng)的森林。 答：ab c defghjk 29．請(qǐng)回答下列問(wèn)題： (1)英文縮寫 DAG的中文含義是什么？ (2)請(qǐng)給出下面 DAG圖的全部拓?fù)渑判颉? 答： (1)有向無(wú)環(huán)圖 (2)abdcefg， abdcfeg， adbcefg， adbcfeg 四、算法閱讀題（本大題共 4小題，每小題 5分，共 20分） 30．已知線性表 (a1,a2,a3...， an)按順序存放在數(shù)組 a中，每個(gè)元素均為整數(shù)，下列程序的功能是將所有小于 0的元素移到全部大于等于 0的元素之前。例如，有 7個(gè)整數(shù)的原始序列為(x,x,x,x,x,x,x)，變換后數(shù)組中保存的序列是 (x,x,x,x,x,x,x)。請(qǐng)?jiān)诔绦蛱幪钊牒线m的內(nèi)容，使其成為完整的算法。 f30(int a[],int n){ int k,m,temp； m= (1)。 while (a[m]0 amp。amp。mn) m= (2)。 k=m。 while (kn){ while(a[k]=0amp。amp。kn) k= (3)。 if(kn){ temp=a[k]。 a[k]=a[m]。 a[m]= (4)。 m= (5)。 56 / 100 } } } 答 ： (1)0 (2)m+1 (3)k+1 (4)temp (5)m+1 31．閱讀下列程序，并回答問(wèn)題： include substr(char*t,char*s,int pos,int len){ while(len0amp。amp。*s){ *t=*(s+posl)。 t++。s++。len。 } *t=39。\039。 } char *f31(char*s){ char t[100]。 if (strlen(s)=1) return s。 substr(t,s,1,1)。 substr(s,s,2,strlen(s)1)。 f31(s)。 return strcat(s,t)。 } main( ){ char str[100]= 39。39。String39。39。 printf(39。39。%s\n39。39。,f31(str))。 } (1)請(qǐng)寫出執(zhí)行該程序后的輸出結(jié)果； (2)簡(jiǎn)述函數(shù) f31的功能。 答： (1) 39。39。gnirtS39。39。 (2)將字符串 s中的字符倒置。 32．下面程序?qū)崿F(xiàn)插入排序算法。 typedef struct{ int key。 Info otherinfo。 }SeqList。 void InsertSort(SeqList R[],int n){ /*待排序列保存在 R［ 1..n］ 中 */ SeqList x。 int i,j,k,lo,hi,mi。 for (i=2。i=n。i++){ (1)。 lo=1。 hi=il。 while(lo=hi){ mi=(lo+hi)/2。 if ( (2)) break。 if (R[mi].key) hi=mil。 57 / 100 else lo=mi+l。 } if(mi=lo) k=imi。 else k=imi1。 for (j=0。jk。j++) (3)。 R[ij]=x。 } } 在空白處填寫適當(dāng)?shù)膬?nèi)容 ， 使該程序功能完整。 答 ： (1)x=R[i] (2) R[mi].key== (3) R[ij]=R[ij1] 58 / 100 33．設(shè)有單鏈表類型定義如下： typedef struct node { int data。 struct node *next。 } *LinkList。 閱讀下列算法 ， 并回答問(wèn)題 ： void f33(LinkList head, int A, int B){ LinkList p=NULL。 while (head !=NULL){ if (headdataAamp。amp。headdataB) p=head。 head=headnext。 } if (p !=NULL) printf(%d\n,pdata)。 } (1)已知鏈表 h如下圖所示，給出執(zhí)行 f33(h， 5， 8)之后的 輸出結(jié)果； (2)簡(jiǎn)述算法 f33的功能。 答： (1)7 (2)輸出鏈表 h中（若存在）最后一個(gè)大于 A到小于 B的值。 五、算法設(shè)計(jì)題（本題 10分） ： typedef struct node{ int data。 struct node *lchild, *rchild。 }*Bitptr。 編寫遞歸算法求二叉樹的高度。函數(shù)原型為： int f34（ Bitptr t）； 答： int f34(Bitptr t){ if(!t) return 0。 lh=f34(tlchild)。 rh=f34(trchild)。 return lhrh?lh+1:rh+1 59 / 100 全國(guó) 2022 年 1 月高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu)試題 課程代碼： 02331 一、單項(xiàng)選擇題 (本大題共 15 小題，每小題 2 分，共 30 分 ) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。 1．若一個(gè)算法的時(shí)間復(fù)雜度用 T(n)表示，其中 n的含義是（ ） A．問(wèn)題規(guī)模 B．語(yǔ)句條數(shù) C．循環(huán)層數(shù) D．函數(shù)數(shù)量 2．具有線性結(jié)構(gòu)的數(shù)據(jù) 結(jié)構(gòu)是（ ） A．樹 B．圖 C．棧和隊(duì)列 D．廣義表 3．將長(zhǎng)度為 n的單鏈表連接在長(zhǎng)度為 m 的單鏈表之后，其算法的時(shí)間復(fù)雜度為（ ） A． O(1) B． O(m) C． O(n) D． O(m+n) 4．在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是（ ） A． 2個(gè) B． 3個(gè) C． 4個(gè) D． 6個(gè) 5．假設(shè)以數(shù)組 A[60]存放循環(huán)隊(duì)列的元素，其頭指針是 front=47，當(dāng)前隊(duì)列有 50個(gè)元素，則隊(duì)列的尾指針值為（ ） A． 3 B． 37 C． 50 D． 97 6．若棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則下列說(shuō)法中正確的是（ ） A．需要判斷棧滿且需要判斷?？? B．不需要判斷棧滿但需要判斷棧空 C．需要判斷棧滿但不需要判斷?？? D．不需要判斷棧滿也不需要判斷?？? 7．若串 str=” Software”，其子串的數(shù)目是（ ） A． 8 B． 9 C． 36 D． 37 8．設(shè)有一個(gè) 10 階的下三角矩陣 A，采用行優(yōu)先壓縮存儲(chǔ)方式， all為第一個(gè)元素，其存儲(chǔ)地址為 1000，每個(gè)元素占一個(gè)地址單元，則 a85的 地址為 （ ） 60 / 100 A． 1012 B． 1017 C． 1032 D． 1039 9．允許結(jié)點(diǎn)共享的廣義表稱為（ ） A．純表 B．線性表 C．遞歸表 D．再入表 10．下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（ ） A． B樹 B． AVL樹 C．二叉排序樹 D．哈夫曼樹 11．對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄校渲?錯(cuò)誤 ． ． 的是（ ） A． 1， 5， 2， 6， 3， 4 B． 1， 5， 6， 2， 3， 4 C． 5， 1， 6， 3， 4， 2 D． 5， 1， 2， 6， 4， 3 12．以 v1為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（ ） A． v1， v2，