【正文】 錯(cuò)選、多選或未選均無分。 rh=f34(trchild)。函數(shù)原型為： int f34（ Bitptr t）； 答： int f34(Bitptr t){ if(!t) return 0。 }*Bitptr。 五、算法設(shè)計(jì)題（本題 10分） ： typedef struct node{ int data。 } (1)已知鏈表 h如下圖所示，給出執(zhí)行 f33(h， 5， 8)之后的 輸出結(jié)果； (2)簡述算法 f33的功能。 head=headnext。amp。 閱讀下列算法 ， 并回答問題 ： void f33(LinkList head, int A, int B){ LinkList p=NULL。 struct node *next。 } } 在空白處填寫適當(dāng)?shù)膬?nèi)容 ， 使該程序功能完整。j++) (3)。 for (j=0。 } if(mi=lo) k=imi。 if (R[mi].key) hi=mil。 while(lo=hi){ mi=(lo+hi)/2。 lo=1。i=n。 int i,j,k,lo,hi,mi。 }SeqList。 typedef struct{ int key。 (2)將字符串 s中的字符倒置。gnirtS39。 答： (1) 39。,f31(str))。%s\n39。 printf(39。String39。 } main( ){ char str[100]= 39。 f31(s)。 substr(t,s,1,1)。 } char *f31(char*s){ char t[100]。 } *t=39。s++。*s){ *t=*(s+posl)。 56 / 100 } } } 答 ： (1)0 (2)m+1 (3)k+1 (4)temp (5)m+1 31．閱讀下列程序，并回答問題： include substr(char*t,char*s,int pos,int len){ while(len0amp。 a[m]= (4)。 if(kn){ temp=a[k]。amp。 k=m。amp。 f30(int a[],int n){ int k,m,temp； m= (1)。例如，有 7個(gè)整數(shù)的原始序列為(x,x,x,x,x,x,x)，變換后數(shù)組中保存的序列是 (x,x,x,x,x,x,x)。 答：ab c defghjk 29．請回答下列問題： (1)英文縮寫 DAG的中文含義是什么？ (2)請給出下面 DAG圖的全部拓?fù)渑判颉? (2)請畫 出廣義表 A對應(yīng)的圖形表示。 (2)top1=1， top2=n， top11=top2 27． 已知廣義表如下 ： A=(B,y),B=(x,L),L=(a,b),要求 ： (1)寫出下列操作的結(jié)果 ： tail(A)=（ (y)） 。 棧 stackl和棧 stack2滿的條件是：（）。 三、解答題（本大題共 4小題，每小題 5分，共 20分） 26．要在［ 0..nl］ 的向量空間中建立兩個(gè)棧 stackl和 stack2，請回答： (1)應(yīng)該如何設(shè)計(jì)這兩個(gè)棧才能充分利用整個(gè)向量空間？ (2)若 stackl的棧頂指針為 topl,stack2的棧頂指針為 top2， 如果需要充分利用整個(gè)向量空間，則： 棧 stackl空的條件是：（） 。 24．若兩個(gè)關(guān)鍵字通過散列函數(shù)映射到同一個(gè)散列地址，這種現(xiàn)象稱為（ 沖突 ）。 22．影響排序效率的兩個(gè)因素是關(guān)鍵字的（ 比 較 ）次數(shù)和記錄的移動次數(shù)。 20．用 5個(gè)權(quán)值 {3, 2， 4， 5， 1}構(gòu)造的哈夫曼 (Huffman)樹的帶權(quán)路徑長度是（ 33）。若為 front=8， rear=7，則隊(duì)列中的元素個(gè)數(shù)為（ 99）。 如果每個(gè)字符占 1個(gè)字節(jié) ， 指針占 4個(gè)字節(jié) ， 則該鏈表的存儲密度是 （ ） 。 struct node *next。sumn。函數(shù)原型為： int f34（ Bitptr t）； 2022年 10月全國自考 數(shù)據(jù)結(jié)構(gòu) 試題 課程代碼： 02331 一、單項(xiàng)選擇題（本大題共 15小題，每小題 2分，共 30分） 1．?dāng)?shù)據(jù)的四種存儲結(jié)構(gòu)是 (A) 、鏈接存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu) 、非線性存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)和圖型存儲結(jié)構(gòu) 、一對一存儲結(jié)構(gòu)、一對多存儲結(jié)構(gòu)和多對多存儲結(jié)構(gòu) 、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu) 2．若對某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè) 新結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，要使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲結(jié)構(gòu)是 (C) 3．若帶頭結(jié)點(diǎn)的單鏈表的頭指針為 head，則判斷鏈表是否為空的條件是 (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階的對稱矩陣 A，采用行優(yōu)先壓縮存儲方式， a11為第一個(gè)元素，其存儲地址為 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ān)鍵字相同元素的相對位置，則認(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)）。 struct node *lchild, *rchild。 } (1)已知鏈表 h如下圖所示，給出執(zhí)行 f33(h， 5， 8)之后的輸出結(jié)果； 51 / 100 (2)簡述算法 f33的功能。 head=headnext。amp。 閱讀下列算法 ， 并回答問題 ： void f33(LinkList head, int A, int B) { LinkList p=NULL。 struct node *next。 for (j=0； jk； j++) (3) ； R［ ij］ =x； } } 在空白處填寫適當(dāng)?shù)膬?nèi)容，使該程序功能完整。 } if (mi=lo) k=i mi。 if (R［ mi］ .key) hi=mil。 while (lo=hi) { mi=(lo+hi)/2。 void InsertSort(SeqList R［］ ,int n) {/* 待排序列保存在 R［ 1..n］ 中 */ SeqList x； int i， j， k， lo,hi,mi。 Info otherinfo。 。,f31(str))。%s\n39。 printf(39。String39。 49 / 100 } main( ) { char str[100]= 39。 f31(s)。 substr(t,s,1,1)。 } char *f31(char*s) { char t[100]。 } *t=39。s++。*s） { *t=*(s+posl)。kn) k= (3) ； if(kn) 48 / 100 { temp=a［ k］； a［ k］ =a［ m］； a［ m］ = (4) ； m= (5) ； } } } (1) (2) (3) (4) (5) ，并回答問題： include substr(char*t,char*s,int pos,int len) { while（ len0amp。 while (kn) { while(a［ k］ =0amp。amp。請?jiān)诔绦蛱幪钊牒线m的內(nèi)容，使其成為完整的算法。 四、算法閱讀題（本大題共 4小題，每小題 5分，共 20分） (a1,a2,a3...， an)按順序存放在數(shù)組 a中，每個(gè)元素均為整數(shù)，下列程序的功能是將所有小于 0的元素移到全部大于等于 0的元素之前。 ： 47 / 100 請畫出該二叉樹對應(yīng)的森林。 ： A=(B,y) B=(x， L) L=(a， b) 要求： (1)寫出下列操作的結(jié)果 tail(A)=_______________. head(B)=______________。 ，則這樣建立的索引表稱為 ___________。 m階的 B樹，每個(gè)結(jié)點(diǎn)中最多包含 ___________個(gè)關(guān)鍵字。 G中有 n個(gè)頂點(diǎn) m條邊，采用鄰接矩陣存儲，則該矩陣中非 0元素的個(gè)數(shù)為___________。 46 / 100 ___________種不同樹型的二叉樹。 100個(gè)元素的數(shù)組存儲循環(huán)隊(duì)列，如果采取少用一個(gè)元素空間的方法來區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，約定隊(duì)頭指針 front等于隊(duì)尾指針 rear時(shí)表示隊(duì)空。i++） sum+=1； ： typedef struct node{ char data［ 16］； struct node *next。 ___________。 ( ) 、鏈接存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu) 、非線性存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)和圖型存儲結(jié)構(gòu) 、一對一存儲結(jié)構(gòu)、一對多存儲結(jié)構(gòu)和多對多存儲結(jié)構(gòu) 、樹 型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu) ，要使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲結(jié)構(gòu)是 ( ) head，則判斷鏈表是否為空的條件是 ( ) =NULL next=NULL !=NULL next!=head 棧順序?yàn)?1， 2， 3....， n，如果第 2個(gè)出棧的元素是 n，則輸出的第 i(1=i=n)個(gè)元素是 ( ) +l +2 ( ) 10階的對稱矩陣 A，采用行優(yōu)先壓縮存儲方式， a11為第一個(gè)元素，其存儲地址為1，每個(gè)元素占一個(gè)字節(jié)空間，則 a85的地址為 ( ) 44 / 100 ，則該二叉 樹可能的形狀是 ( ) 2的結(jié)點(diǎn) 1，則具有 n個(gè)結(jié)點(diǎn)的二叉樹的最大高度是 ( ) B. C. +1 G中求兩個(gè)結(jié)點(diǎn)之間的最短路徑可以采用的算法是 ( ) （ Dijkstra）算法 （ Kruskal）算法 (Prim)算法 (BFS)算法 G=(V,E)是一個(gè) 帶權(quán)連通圖， G的最小生成樹的權(quán)為 ( ) ，從頂點(diǎn) 1出發(fā)進(jìn)行深度優(yōu)先遍歷可得到的序列是 ( ) 2 3 4 5 6 7 4 2 6 3 7 5 4 2 5 3 6 7 2 4 6 5 3 7 ，則認(rèn)為該排序方法是 ( ) (19, 14, 23, 1， 6， 20, 4， 27, 5， 11, 10, 9)，用散列函數(shù) H(key)=key%13