【正文】 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)。 編寫遞歸算法求二叉樹的高度。 答： (1)7 (2)輸出鏈表 h中（若存在）最后一個(gè)大于 A到小于 B的值。headdataB) p=head。 } *LinkList。 R[ij]=x。 else k=imi1。 if ( (2)) break。i++){ (1)。 void InsertSort(SeqList R[],int n){ /*待排序列保存在 R［ 1..n］ 中 */ SeqList x。 32．下面程序?qū)崿F(xiàn)插入排序算法。39。39。39。 return strcat(s,t)。 if (strlen(s)=1) return s。len。amp。 a[k]=a[m]。 while (kn){ while(a[k]=0amp。 while (a[m]0 amp。 答： (1)有向無(wú)環(huán)圖 (2)abdcefg， abdcfeg， adbcefg， adbcfeg 四、算法閱讀題（本大題共 4小題，每小題 5分，共 20分） 30．已知線性表 (a1,a2,a3...， an)按順序存放在數(shù)組 a中，每個(gè)元素均為整數(shù)，下列程序的功能是將所有小于 0的元素移到全部大于等于 0的元素之前。 head(B)=（ x） 。 棧 stack2空的條件是：（） 。 23．對(duì)任 m階的 B樹，每個(gè)結(jié)點(diǎn)中最多包含（ m1）個(gè)關(guān)鍵字。 54 / 100 19． 3個(gè)結(jié)點(diǎn)可以組成（ 5）種不同樹型的二叉樹。 } LinkStrNode。 sum=1； for(i=0。 五、算法設(shè)計(jì)題（本題 10分） ： typedef struct node{ int data。headdataB) p=head。 } *LinkList。 50 / 100 else k=i mi1。 if ( (2) ) break。 }SeqList。 } (1)請(qǐng)寫出執(zhí)行該程序后的輸出結(jié)果； (2)簡(jiǎn)述函數(shù) f31的功能。39。39。 substr(s,s,2,strlen(s)1)。\039。 t++。amp。 f30(int a［］， int n) { int k， m,temp； m= (1) ； while (a［ m］ 0 amp。 答下列問(wèn)題： (1)英文縮寫 DAG的中文含義是什么？ (2)請(qǐng)給出下面 DAG圖的全部拓?fù)渑判颉? 三、解答題（本大題共 4小題，每小題 5分，共 20分） ［ 0..nl］ 的向量空間中建立兩個(gè)棧 stackl和 stack2，請(qǐng)回答： (1)應(yīng)該如何設(shè)計(jì)這兩個(gè)棧才能充分利用整個(gè)向量空間？ (2)若 stackl的棧頂指針為 topl,stack2的棧頂指針為 top2， 如果 需要充分利用整個(gè)向量空間，則： 棧 stackl空的條件是： ___________； 棧 stack2空的條件是： ___________； 棧 stackl和棧 stack2滿的條件是： ___________。 ___________次數(shù)和記錄的移動(dòng)次數(shù)。若為 front=8， rear=7，則隊(duì)列中的元素個(gè)數(shù)為 ___________。 sum=1； for（ i=0； sumn。錯(cuò)選、多選或未選均無(wú)分。 struct node*next。 else return f33(R,X,m+l,q)。 Int f33(SqList R， NodeType X, int p, int q) { int m。 typedef struct { KeyType key。 jni。amp。 } } } 回答下列問(wèn)題： (1)已知以 T 為根指針的二叉樹如圖所示， 請(qǐng)寫出執(zhí)行 f31(T)的輸出結(jié)果： (2)簡(jiǎn)述算法 f31 的功能。 T=Tlchild。 36 / 100 struct node*Ichild, *rchild。 四、算法閱讀題（本大題共 4 小題，每小題 5 分，共 20 分） 。 ，請(qǐng)回答下面問(wèn)題： (1)給出該圖的鄰接矩陣； (2)從結(jié)點(diǎn) A 出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。 ，快速排序、簡(jiǎn)單選擇排序和直接插入排序三種排序方法中，運(yùn)行效率最高的是 ________________。 ________________。錯(cuò)填、不填均無(wú)分。 =(front1)%m。 28 / 100 29 / 100 30 / 100 31 / 100 32 / 100 全國(guó) 2022 年 1 月自考 數(shù)據(jù)結(jié)構(gòu)試題及答案 課程代碼： 02331 一、單項(xiàng)選擇題（本大題共 15 小題，每小題 2 分，共 30 分） 在每小 題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。 while (p) { G2－＞ adjmatrix[i][p－＞ adjvex]=1。 p=[i].firstedge。 G2－＞ e= (1) 。 ∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) } AMGraph。 ∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) } ALGraph。 ∥邊表結(jié)點(diǎn)結(jié)構(gòu) typedef struct{ char vertex； ∥頂點(diǎn)域 EdgeNode *firstedge。 return p。 p=（ BinTNode*） malloc(sizeof(BinTNode))。 } （ 1） （ 2） n 個(gè)結(jié)點(diǎn)的完全二叉樹順序存儲(chǔ)在向量 BT[1.. n]中，閱讀下列算法，并回答問(wèn)題： （ 1）若向量 BT 為： A B C D E F G 1 2 3 4 5 6 7 畫出執(zhí)行函數(shù) f32（ BT,7,1）的返回結(jié)果 。S))。 void f31(Stack *S){ Queue Q； InitQueue(amp。 while(i＜ L－＞ length） ｛ if(L－＞ data[i]!=L－＞ data[k]) 25 / 100 L－＞ data[++k]=L－＞ data[i]。 （ 3）寫出刪除值為 70 的關(guān)鍵字時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)。 （ 1）畫出該森林； （ 2）畫出該森林所對(duì)應(yīng)的二叉樹。 ｛ 19， 14， 23， 1， 68， 12， 10， 78， 25｝，用鏈地址法構(gòu)造散列表，散列函數(shù)為 h（ key） =key％ 11,散列地址為 1 的鏈中有 __________個(gè)記錄。 10 階的上三角矩陣 A 按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組 B 中，若矩陣中的第一個(gè)元素 a11 在 B 中的存儲(chǔ)位置 k=0，則元素 a55 在 B 中的存儲(chǔ)位置 k=__________。錯(cuò)填、不填均無(wú)分。 ，入棧序列為 1， 2， 3， 4， 5， 6，若出棧序列為 2， 4， 3， 6， 5， 1，則操作過(guò)程中棧中元素個(gè)數(shù)最多時(shí)為（ ） 個(gè) 個(gè) 個(gè) 個(gè) （ ） 在表的兩端進(jìn)行插入和刪除 ，在另一端進(jìn)行刪除 ﹟ define NodeSize 6 22 / 100 typedef struct node{ char data[NodeSize]。 p1－＞ next=p。p2－＞ next=p1－＞ next。 R[il]=R[n+1]； } 18 / 100 } (1) (2) 五、算法設(shè)計(jì)題 (本題 10 分 ) ，單鏈表的類型定義如下： typedef struct node { DataType data； Struct node *next； } LinkNode， * LinkList； 編寫算法，在一個(gè)頭指針為 head 且?guī)ь^結(jié)點(diǎn)的單鏈表中，刪除所有結(jié)點(diǎn)數(shù)據(jù)域值為 x 的結(jié)點(diǎn)。ch)； 17 / 100 sdata=ch； pnext=s； p=s； } pnext=q； } return head； } (1) (2) ，并回答下列問(wèn)題： (1)該算法采用的是何種排序方法 ? (2)算法中的 R[n+1]的作用是什么 ? typedef struct { KeyType key； InfoType otherinfo； }RecType； typedef RecType SeqList[MaxLen]； void sort(SeqList R， int n) { //nMaxLen1 int k， i； for (k=n1。 int i。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)?shù)膬?nèi)容，使其成為一個(gè)完整的算法。s,str[j])； if (i％ 2!=0) k=i/2+1； else k=i／ 2； for (j=k。s)； gets (str)； while (str[i]!= 39。 ： ABCDEFG 和 CBDAEGF，請(qǐng)畫出此二叉樹，并給出后序遍歷序列。 初始堆： 第一趟： 第二趟： H (key)=key ％ 11，散列地址空間為 0 14 / 100 (46， 79， 56， 38， 40， 84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為 ______。 T 和 P 是兩個(gè)給定的串，在 T 中尋找等于 P 的子串的過(guò)程稱為 ______。錯(cuò)填、不填均無(wú)分。 4. 合理安排答題空間，超出答題區(qū)域無(wú)效。 2. 第一部分為選擇題。 五、算法設(shè)計(jì)題 (本題 10 分 ) 34．二叉樹的存儲(chǔ)結(jié)構(gòu)類型定義如下 typedef struct node{ int data； struct node *lchild， *rchild； } BinNode； typedef BinNode *BinTree； 編寫遞歸算法，求只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)總數(shù)，并計(jì)算這些結(jié)點(diǎn)的數(shù)據(jù)值的和。 printf(“%d n”,k)。 j++) { k=0。 j++) if ([i][j]= =1) k++。 Step1: for (i=0。 ∥ 邊上權(quán)值類型 typedef struct{ EType edges[MVN][MVN]。 jLlength。 29．一組記錄關(guān)鍵字 (55,76,44,32,64,82,20,16,43)，用散列函數(shù) H(key)=key％ 11 將記錄 散列到散列表 HT[0..12]中去，用線性探測(cè)法解決沖突。 M,n,o,P 入隊(duì)， i,j,k,l,m 出隊(duì)； (3) =______； =______。 25．用二叉鏈表保存有 n 個(gè)結(jié)點(diǎn)的二叉樹，則結(jié)點(diǎn)中有 ______個(gè)空指針域。 21．一組字符 (a,b,c,d)在文中出現(xiàn)的次數(shù)分別為 (7， 6， 3， 5)，字符＇ d＇的哈夫曼編碼的長(zhǎng)度為 ______。 17．在線性表中，表的長(zhǎng)度定義為 ______。 一、單項(xiàng)選擇題 (本大題共 l5 小題，每小題 2 分，共 30 分 ) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求 的，請(qǐng)將其選出并將 “答題 紙 ”的相應(yīng)代碼涂黑。 選擇題部分 注意事項(xiàng)： 1. 答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。 2. 每小題選出答案后，用 2B 鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。錯(cuò)涂、多涂或未涂均無(wú)分。 18．用 S 表示入棧操作， X 表示出棧操作，若元素入棧的順序?yàn)? 4，為了得到 2 的出棧順序，相應(yīng)的 S 和 X 的操作序列為 ______。 22．在一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要 ______條邊。 三、解答題 (本大題共 4 小題，每小題 5 分，共 20 分 ) 4 / 100 26．假設(shè) Q 是一個(gè)具有 11 個(gè)元素存儲(chǔ)空間的循環(huán)隊(duì)列 (隊(duì)尾指針指向隊(duì)尾元素的下一 個(gè)位置，隊(duì)頭指針指向隊(duì)頭元素 )，初始狀態(tài) ==0；寫出依次執(zhí)行 下列操作后頭、尾指針的當(dāng)前值。 27．已知一