【正文】 。 void f32(int A[],int n) { int i,j,m=l,t； for (i=0。 inlamp。amp。m。 i++) { for (j=0； jn； j++) 37 / 100 printf(“ %d ” ,A[j])； printf(“＼ n” )。 m=0： for (j=1。 jni。 j++) if (A[j1]A[j]) { t=A[jl]。 A[j1]=A[j]； A[j]=t； m=1； } } } 回答問題： 已 知整型數(shù)組 A[ ]={34,26,15,89,42}，寫出執(zhí)行函數(shù)調(diào)用 f32(A,5)后的輸出結(jié)果。 ： define MAXLEN 100 typedef int KeyType。 typedef struct { KeyType key。 InfoType otherinfo。 } NodeType； typedef NodeType SqList[MAXLEN]。 閱讀下列程序。 Int f33(SqList R， NodeType X, int p, int q) { int m。 if (pq) return 1。 m=(p+q)／ 2； if (R[m].key==) return m。 38 / 100 if (R[m].key) return f33(R,X,p,ml)。 else return f33(R,X,m+l,q)。 } 請回答下列問題： (1)若有序的順序表 R 的關(guān)鍵字序列為 (2,5， 13,26,55,80,105)，分別寫出 =18 和 =26時(shí)，執(zhí)行函數(shù)調(diào)用 f33(R,X,0,6)的函數(shù)返 回值。 (2)簡述算法 f33 的功能。 五、算法設(shè)計(jì)題（本題 10 分） ，單鏈表的類型定義如下： typedef struct node { int data。 struct node*next。 }LinkNode， *LinkList。 編寫程序，求頭指針為 head 的單循環(huán)鏈表中 data 域值為正整數(shù)的結(jié)點(diǎn)個(gè)數(shù)占結(jié)點(diǎn)總數(shù)的比例，若為空表輸出 0，并給出所寫算法的時(shí)間復(fù)雜度。函數(shù)原型為： float f34(LinkList head): 39 / 100 40 / 100 41 / 100 42 / 100 43 / 100 全國 2022 年 10月高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu) 試題 課程代碼： 02331 一、單項(xiàng)選擇題（本大題共 15小題，每小題 2分，共 30分） 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。 ( ) 、鏈接存儲(chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu) 、非線性存儲(chǔ)結(jié)構(gòu)、樹型存儲(chǔ)結(jié)構(gòu)和圖型存儲(chǔ)結(jié)構(gòu) 、一對一存儲(chǔ)結(jié)構(gòu)、一對多存儲(chǔ)結(jié)構(gòu)和多對多存儲(chǔ)結(jié)構(gòu) 、樹 型存儲(chǔ)結(jié)構(gòu)、圖型存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu) ，要使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲(chǔ)結(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)先壓縮存儲(chǔ)方式， a11為第一個(gè)元素，其存儲(chǔ)地址為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構(gòu)造散列表，用拉鏈法解決沖突，散列地址為 1的鏈中記錄個(gè)數(shù)為 ( ) 45 / 100 ，下列二叉樹中符合二叉排序樹性質(zhì)的是 ( ) ，可以采用的文件組織方式為 ( ) 二、填空題（本大題共 10小題，每小題 2分，共 20分） 請每小題的空格中填上正確答案。錯(cuò)填、不填均無 分。 ___________。 sum=1； for（ i=0； sumn。i++） sum+=1； ： typedef struct node{ char data［ 16］； struct node *next。 } LinkStrNode； 如果每個(gè)字符占 1個(gè)字節(jié) ， 指針占 4個(gè)字節(jié) ， 則該鏈表的存儲(chǔ)密度是 ___________。 100個(gè)元素的數(shù)組存儲(chǔ)循環(huán)隊(duì)列，如果采取少用一個(gè)元素空間的方法來區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，約定隊(duì)頭指針 front等于隊(duì)尾指針 rear時(shí)表示隊(duì)空。若為 front=8， rear=7，則隊(duì)列中的元素個(gè)數(shù)為 ___________。 46 / 100 ___________種不同樹型的二叉樹。 5個(gè)權(quán)值 {3, 2， 4， 5， 1}構(gòu)造的哈夫曼 (Huffman)樹的帶權(quán)路徑長度是 ___________。 G中有 n個(gè)頂點(diǎn) m條邊，采用鄰接矩陣存儲(chǔ)，則該矩陣中非 0元素的個(gè)數(shù)為___________。 ___________次數(shù)和記錄的移動(dòng)次數(shù)。 m階的 B樹，每個(gè)結(jié)點(diǎn)中最多包含 ___________個(gè)關(guān)鍵字。 ，這種現(xiàn)象稱為 ___________。 ，則這樣建立的索引表稱為 ___________。 三、解答題（本大題共 4小題，每小題 5分，共 20分） ［ 0..nl］ 的向量空間中建立兩個(gè)棧 stackl和 stack2，請回答： (1)應(yīng)該如何設(shè)計(jì)這兩個(gè)棧才能充分利用整個(gè)向量空間？ (2)若 stackl的棧頂指針為 topl,stack2的棧頂指針為 top2， 如果 需要充分利用整個(gè)向量空間，則： 棧 stackl空的條件是： ___________； 棧 stack2空的條件是： ___________； 棧 stackl和棧 stack2滿的條件是： ___________。 ： A=(B,y) B=(x， L) L=(a， b) 要求： (1)寫出下列操作的結(jié)果 tail(A)=_______________. head(B)=______________。 (2)請畫出廣義表 A對應(yīng)的圖形表示。 ： 47 / 100 請畫出該二叉樹對應(yīng)的森林。 答下列問題： (1)英文縮寫 DAG的中文含義是什么？ (2)請給出下面 DAG圖的全部拓?fù)渑判颉? 四、算法閱讀題（本大題共 4小題，每小題 5分，共 20分） (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)。請?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) 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。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)。 49 / 100 } main( ) { char str[100]= 39。39。String39。39。 printf(39。39。%s\n39。39。,f31(str))。 } (1)請寫出執(zhí)行該程序后的輸出結(jié)果； (2)簡述函數(shù) f31的功能。 。 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。 else lo=mi+l。 } if (mi=lo) k=i mi。 50 / 100 else k=i mi1。 for (j=0； jk； j++) (3) ； R［ ij］ =x； } } 在空白處填寫適當(dāng)?shù)膬?nèi)容，使該程序功能完整。 (1) (2) (3) ： typedef struct node { int data。 struct node *next。 } *LinkList。 閱讀下列算法 ， 并回答問題 ： 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é)果； 51 / 100 (2)簡述算法 f33的功能。 五、算法設(shè)計(jì)題（本題 10分） ： typedef struct node{ int data。 struct node *lchild, *rchild。 }*Bitptr； 編寫遞歸算法求二叉樹的高度 。函數(shù)原型為： int f34（ Bitptr t）； 2022年 10月全國自考 數(shù)據(jù)結(jié)構(gòu) 試題 課程代碼： 02331 一、單項(xiàng)選擇題（本大題共 15小題，每小題 2分，共 30分） 1．?dāng)?shù)據(jù)的四種存儲(chǔ)結(jié)構(gòu)是 (A) 、鏈接存儲(chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu) 、非線性存儲(chǔ)結(jié)構(gòu)、樹型存儲(chǔ)結(jié)構(gòu)和圖型存儲(chǔ)結(jié)構(gòu) 、一對一存儲(chǔ)結(jié)構(gòu)、一對多存儲(chǔ)結(jié)構(gòu)和多對多存儲(chǔ)結(jié)構(gòu) 、樹型存儲(chǔ)結(jié)構(gòu)、圖型存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu) 2．若對某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè) 新結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，要使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲(chǔ)結(jié)構(gòu)是 (C) 3．若帶頭結(jié)點(diǎn)的單鏈表的頭指針為 head，則判斷鏈表是否