【文章內(nèi)容簡(jiǎn)介】 ________個(gè)記錄。 ，還建有 __________。 三、解答題（本大題共 4 小題，每小題 5 分，共 20 分） （ 注： 矩陣元素的行列下標(biāo)均從 1 開(kāi)始） 0 0 0 0 00 7 1 0 08 0 5 0 00 0 0 0 00 0 6 2 9??????????? （ 1） 畫(huà)出三元 組表； 24 / 100 （ 2）畫(huà)出 三元組表的行表。 (1) (2) CBADHEGF，后序遍歷序列為 ABCDEFGH。 （ 1）畫(huà)出該森林； （ 2）畫(huà)出該森林所對(duì)應(yīng)的二叉樹(shù)。 (1) (2) （ 429， 653， 275， 897， 170， 908， 473， 256， 726）進(jìn)行基數(shù)排序，寫出每一趟的排序結(jié)果。 （ 87， 25， 310， 08， 27， 132， 68， 96， 187， 133， 70， 63， 47， 135） 構(gòu)造散列表，假設(shè)散列函數(shù)為 h（ key） =key％ 13,用拉鏈法解決沖突 。 （ 1）畫(huà)出該散列表； （ 2）求等概率情況下查找成功的平均查找長(zhǎng)度 ASL。 （ 3）寫出刪除值為 70 的關(guān)鍵字時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)。 (1) (2) (3) 四、算法閱讀題（本大題共 4 小題，每小題 5 分，共 20 分） ，并回答問(wèn)題： （ 1）假設(shè) L=（ 3， 7， 7， 11， 20， 20， 20， 51， 51），寫出執(zhí)行函數(shù) f30（ amp。L）后的 L； （ 2）簡(jiǎn)述 f30 的功能。 void f30(SeqList*L) { ∥ L 為非空的有序表 int i=1,k=0。 while(i＜ L－＞ length） ｛ if(L－＞ data[i]!=L－＞ data[k]) 25 / 100 L－＞ data[++k]=L－＞ data[i]。 i++。 } L－＞ length=k+1； } (1) (2) ，并回答問(wèn)題： （ 1）假設(shè)棧 S=（ 3， 8， 6， 2， 5），其中 5 為棧頂元素，寫出執(zhí)行函數(shù) f31（ amp。S）后的 S； （ 2）簡(jiǎn)述函數(shù) f31 的功能。 void f31(Stack *S){ Queue Q； InitQueue(amp。Q)。 while(!StackEmpty(S)) EnQueue(amp。Q,Pop(amp。S))。 while(!QueueEmpty(Q)) Push(amp。S,DeQueue(amp。Q))。 } （ 1） （ 2） n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)順序存儲(chǔ)在向量 BT[1.. n]中，閱讀下列算法，并回答問(wèn)題： （ 1）若向量 BT 為： A B C D E F G 1 2 3 4 5 6 7 畫(huà)出執(zhí)行函數(shù) f32（ BT,7,1）的返回結(jié)果 。 (2)簡(jiǎn)述函數(shù) f32 的功能。 BinTree f32(DataType BT[],int n,int i) { 26 / 100 BinTree p。 if (i＞ n) return NULL。 p=（ BinTNode*） malloc(sizeof(BinTNode))。 p－＞ data=BT[i]。 p－＞ lchild=f32(BT,n,i*2)。 p－＞ rchild=f32(BT,n,i*2+1)。 return p。 } (1) (2) ： ﹟ define MaxNum 50 ∥圖的最大頂點(diǎn)數(shù) typedef struct node { int adjvex。 ∥鄰接點(diǎn)域 struct node *next。 ∥鏈指針域 } EdgeNode。 ∥邊表結(jié)點(diǎn)結(jié)構(gòu) typedef struct{ char vertex； ∥頂點(diǎn)域 EdgeNode *firstedge。 ∥邊表頭指針 } VertexNode。 ∥頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu) typedef struct { VertexNode adjlist [MaxNum]。 ∥鄰接表 int n,e。 ∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) } ALGraph。 ∥鄰接表描述的圖 typedef struct{ char vertex[MaxNum]。 ∥頂點(diǎn)表 int adjmatrix [MaxNum][MaxNum]。 ∥鄰接矩陣 int n,e。 ∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) } AMGraph。 ∥鄰接矩陣描述的圖 27 / 100 下列算法是將鄰接 表描述的圖 G1 改為鄰接矩陣描述的圖 G2，在空白處填上適當(dāng)內(nèi)容使算法完整： void f33（ ALGraph G1,AMGraph *G2） { int i, j。 EdgeNode *p。 G2－＞ n=。 G2－＞ e= (1) 。 for (i=0。 i＜ 。 i++) { G2－＞ vertex[i]= (2) 。 p=[i].firstedge。 for (j=0。 j＜ 。 j++） G2－＞ adjmatrix[i][j]=0。 while (p) { G2－＞ adjmatrix[i][p－＞ adjvex]=1。 (3) 。 } } } (1) (2) (3) 五、算法設(shè)計(jì)題（本題 10 分） 。編寫算法，要求利用二分查找法確定插入位置，將元素ｘ插入到Ｌ中，使Ｌ保持有序。 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)。錯(cuò)選、多選或未選均無(wú)分。 （ ） n 個(gè)元素的有序表歸并成一個(gè)有序表，最少的比較次數(shù)是（ ） m，隊(duì)頭指針 front 指向隊(duì)頭元素，隊(duì)尾指針 rear 指向隊(duì)尾元素的下一個(gè)位置，則向隊(duì)列中插入新元素時(shí)，修改指針的操作是（ ） =(rear1)%m。 =(front+1)%m。 =(front1)%m。 =(rear+1)%m。 ，處理參數(shù)及返回地址，應(yīng)采用的數(shù)據(jù)結(jié)構(gòu)是（ ） p 和 q，其中 q 是 p 的子串，則求 q 在 p 中首次出現(xiàn)位置的算法稱為（ ） A，若 head(A)等于 tail(A)，則表 A 為（ ） A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) n(n0)個(gè)結(jié)點(diǎn)的二叉樹(shù)的先序序列與后序序列正好相反，則該二叉樹(shù)一定是 （ ） n 的二叉樹(shù) 2 的結(jié)點(diǎn)的二叉樹(shù) 33 / 100 l 的結(jié)點(diǎn)個(gè)數(shù)是 3，度為 2 的結(jié)點(diǎn)個(gè)數(shù)是 4，則該二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ） （ ） 次 G=(V， E)，其中 V={V1， V2， V3， V4}， E={V1， V2， V1， V3， V2，V3， V2， V4， V3， V4}，圖 G 的拓?fù)湫蛄惺牵? ） ,V2,V3,V4 ,V3,V2,V4 ,V3,V4,V2 ,V2,V4,V3 O(n log n)的穩(wěn)定排序算法是（ ） 序 (51， 22， 83， 46， 75， 18， 68， 30)，對(duì)其進(jìn)行快速排序，第一趟劃分完成后的關(guān)鍵字序列是（ ） A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68) C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83) 395 個(gè)，平均分成 5 塊。若先對(duì)索引表采用順序查找，再對(duì)塊中元素進(jìn)行順序查找，則 在等概率情況下，分塊查找成功的平均查找長(zhǎng)度是（ ） 10 個(gè)關(guān)鍵字的 3 階 B樹(shù)中進(jìn)行查找，至多訪問(wèn)的結(jié)點(diǎn)個(gè)數(shù)為（ ） 文件系統(tǒng)中采用多級(jí)索引的目的是（ ） 34 / 100 二、填空題（本大題共 10 小題，每小題 2 分，共 20 分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。 、存儲(chǔ)結(jié)構(gòu)和 數(shù)據(jù)的 ____________三部分組成。 ，需要修改 _______________個(gè)結(jié)點(diǎn)指針域的值。 S 的初始狀態(tài)為空，若元素 a、 b、 c、 d、 e、 f 依次進(jìn)棧，得到的出棧序列是 b、 d、c、 f、 e、 a，則棧 S 的容量至少是 ________________。 ________________。 G=(a,b， (c， d， (e， f))， G)的長(zhǎng)度為 ________________。 T 采用孩子兄弟鏈表存儲(chǔ)，如果樹(shù) T 中某個(gè)結(jié)點(diǎn) 為葉子結(jié)點(diǎn)，則該結(jié)點(diǎn)在二叉鏈表中所對(duì)應(yīng)的結(jié)點(diǎn)一定是 ________________。 n 個(gè)頂點(diǎn)的無(wú)向連通圖，最少有 ________________條邊。 ，快速排序、簡(jiǎn)單選擇排序和直接插入排序三種排序方法中，運(yùn)行效率最高的是 ________________。 h 的具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中，查找任一結(jié)點(diǎn)的最多比較次數(shù)是______________。 ____________大小不固定。 三、解答題（本大題共 4 小題，每小 題 5 分，共 20 分） （結(jié)點(diǎn)值大小按字母順序）的前序遍歷序列為 EBACDFHG， 請(qǐng)回答下列問(wèn)題： (1)畫(huà)出此二叉排序樹(shù)； (2)若將此二叉排序樹(shù)看作森林的二叉鏈表存儲(chǔ)，請(qǐng)畫(huà)出對(duì)應(yīng)的森林。 ，請(qǐng)回答下面問(wèn)題： (1)給出該圖的鄰接矩陣； (2)從結(jié)點(diǎn) A 出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。 {25， 96， 11， 63， 57， 78， 44}，請(qǐng)回答下列問(wèn)題： 35 / 100 (1)畫(huà)出堆排序的初始堆（大根堆）； (2)畫(huà)出第二次重建堆之后的 堆。 (56， 23， 41， 79， 38， 62， 18)，用散列函數(shù) H(key)=key%11 將其散列到散列表 HT[0..10]中，采用線性探測(cè)法處理沖突。請(qǐng)回答下列問(wèn)題： (1)畫(huà)出散列存儲(chǔ)后的散列表： (2)求在等概率情況下查找成功的平均查找長(zhǎng)度。 四、算法閱讀題（本大題共 4 小題，每小題 5 分，共 20 分） 。 void f30(int A[]， int n) { int i,j,m。 for (i=1； in； i++) for (j=0； ji； j++) { m=A[i*n+j]； A[i*n+j]=A[j*n+i]； A[j*n+i]=m； } } 回答下列問(wèn)題： (1)已知矩陣 B=??????????9 8 7 6 5 4 3 2 1 ，將其按行優(yōu)先存于一維數(shù)組 A 中，給出執(zhí)行函數(shù)調(diào) 用 f30(A， 3)后矩陣 B 的值； (2)簡(jiǎn)述函數(shù) f30 的功能。 ，其類型定義如下： typedef struct node { char data。 36 / 100 struct node*Ichild, *rchild。 ∥左右孩子指針 } *BinTree； 閱讀下列程序。 void f31(BinTree T) { InitStack(S)。 ∥ 初始化一個(gè)堆棧 S while (T || !StackEmpty(S) { while (T) { Push(S,T)。 T=Tlchild。 } if (!StackEmpty(S)) { T=Pop(S)。 printf(“ %c” ,Tdata)。 T=Trchild。 } } } 回答下列問(wèn)題： (1)已知以 T 為根指針的二叉樹(shù)如圖所示， 請(qǐng)寫出執(zhí)行 f31(T)的輸出結(jié)果： (2)簡(jiǎn)述算法 f31 的功能。