【正文】 1 / 100 全國(guó) 2022 年 10 月高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu)試題 課程代碼： 02331 請(qǐng)考生按規(guī)定用筆將所有試題的答案涂、寫(xiě)在答題紙上。 選擇題部分 注意事項(xiàng)： 1. 答題前，考生務(wù)必將自己的考試課程名稱(chēng)、姓名、準(zhǔn)考證號(hào)用黑色字跡的簽字筆或鋼筆填寫(xiě)在答題紙規(guī)定的位置上。 2. 每小題選出答案后，用 2B 鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑。如需改動(dòng)，用橡皮擦干凈后，再選涂其他答案標(biāo)號(hào)。不能答在試題卷上。 一、單項(xiàng)選擇題 (本大題共 l5 小題，每小題 2 分，共 30 分 ) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求 的，請(qǐng)將其選出并將 “答題 紙 ”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無(wú)分。 1．一個(gè)算法的時(shí)間耗費(fèi)的數(shù)量級(jí)稱(chēng)為該算法的 A．效率 B．難度 C．可實(shí)現(xiàn)性 D．時(shí)間復(fù)雜度 2．順序表便于 A．插入結(jié)點(diǎn) B．刪除結(jié)點(diǎn) C．按值查找結(jié)點(diǎn) D．按序號(hào)查找結(jié)點(diǎn) 3．設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為 head，指針變量 P 指向尾結(jié)點(diǎn)的條件是 A． pnextnext==head B． pnext==head C． pnextnext==NULL D． pnext==NULL 4．設(shè)以數(shù)組 A[0..m1]存放循環(huán)隊(duì)列， front 指向隊(duì)頭元素， rear 指向隊(duì)尾元素的下一個(gè)位置，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為 A． (rearfront+m)％ m B． rearfront+1 C． (frontrear+m)％ m D． (rearfront)％ m 2 / 100 5．下列關(guān)于順序棧的敘述中，正確的是 A．入棧操作需要判斷棧滿(mǎn)，出棧操作需要判斷?？? B．入棧操作不需要判斷棧滿(mǎn)，出棧操作需要判斷?？? C．入棧操作需要判斷棧滿(mǎn)，出棧操作不 需要判斷?？? D．入棧操作不需要判斷棧滿(mǎn)，出棧操作不需要判斷?？? 6． A 是一個(gè) 1010 的對(duì)稱(chēng)矩陣，若采用行優(yōu)先的下三角壓縮存儲(chǔ)，第一個(gè)元素 a0,0的存儲(chǔ)地址為 1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則 a7,5的地址為 A． 25 B． 26 C． 33 D． 34 7．樹(shù)的后序遍歷等價(jià)于該樹(shù)對(duì)應(yīng)二叉樹(shù)的 A．層次遍歷 B．前序遍歷 C．中序遍歷 D．后序遍歷 8．使用二叉線索樹(shù)的目的是便于 A．二叉樹(shù)中結(jié)點(diǎn)的插入與刪除 B．在二叉樹(shù)中查找雙親 C． 確定二叉樹(shù)的高度 D．查找一個(gè)結(jié)點(diǎn)的前趨和后繼 9．設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為 n，則該圖邊的數(shù)目最多為 A． nl B． n(n1)／ 2 C． n(n+1)／ 2 D． n2 10．可進(jìn)行拓?fù)渑判虻膱D只能是 A．有向圖 B．無(wú)向圖 C．有向無(wú)環(huán)圖 D．無(wú)向連通圖 11．下列排序方法中穩(wěn)定的是 A．直接插入排序 B．直接選擇排序 C．堆排序 D．快速排序 12．下列序列 不為 ． ． 堆的是 A． 75,45,65,30,15,25 B． 75,65,45,30,25,15 C． 75,65,30,l5,25,45 D． 75,45,65,25,30,15 13．對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須是 A．順序存儲(chǔ) B．鏈?zhǔn)酱鎯?chǔ) 3 / 100 C．順序存儲(chǔ)且按關(guān)鍵字有序 D．鏈?zhǔn)酱鎯?chǔ)且按關(guān)鍵字有序 14．分別用以下序列生成二叉排序樹(shù)，其中三個(gè)序列生成的二叉排序樹(shù)是相同的， 不同 ． ． 的序列是 A． (4,1,2,3,5) B． (4,2,3,l,5) C． (4,5,2,1,3) D． (4,2,1,5,3) 15．下列關(guān)于 m 階 B 樹(shù)的敘述中， 錯(cuò)誤 ． ． 的是 A．每個(gè)結(jié)點(diǎn)至多有 m 個(gè)關(guān)鍵字 B．每個(gè)結(jié)點(diǎn)至多有 m 棵子樹(shù) C．插入關(guān)鍵字時(shí)，通過(guò)結(jié)點(diǎn)分裂使樹(shù)高增加 D．刪除關(guān)鍵字時(shí)通過(guò)結(jié)點(diǎn)合并使樹(shù)高降低 非選擇題部分 注意事項(xiàng)： 用黑色字跡的簽字筆或鋼筆將答案寫(xiě)在答題紙上，不能答在試題卷上。 二、填空題 (本大題共 10 小題，每小題 2 分，共 20 分 ) 16．?dāng)?shù)據(jù)元素之間的邏輯關(guān)系稱(chēng)為數(shù)據(jù)的 ______結(jié)構(gòu)。 17．在線性表中，表的長(zhǎng)度定義為 ______。 18．用 S 表示入棧操作， X 表示出棧操作，若元素入棧的順序?yàn)? 4，為了得到 2 的出棧順序，相應(yīng)的 S 和 X 的操作序列為 ______。 19．在二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最短的樹(shù)稱(chēng)為 ______。 20．已知廣義表 G， head(G)與 tail(G)的深度分別為 4 和 6，則 G 的深度是 ______。 21．一組字符 (a,b,c,d)在文中出現(xiàn)的次數(shù)分別為 (7， 6， 3， 5)，字符＇ d＇的哈夫曼編碼的長(zhǎng)度為 ______。 22．在一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要 ______條邊。 23．直接選擇排序算法的時(shí)間復(fù)雜度是 ______。 24．對(duì)于長(zhǎng) 度為 81 的表，若采用分塊查找，每塊的最佳長(zhǎng)度為 ______。 25．用二叉鏈表保存有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，則結(jié)點(diǎn)中有 ______個(gè)空指針域。 三、解答題 (本大題共 4 小題，每小題 5 分，共 20 分 ) 4 / 100 26．假設(shè) Q 是一個(gè)具有 11 個(gè)元素存儲(chǔ)空間的循環(huán)隊(duì)列 (隊(duì)尾指針指向隊(duì)尾元素的下一 個(gè)位置，隊(duì)頭指針指向隊(duì)頭元素 )，初始狀態(tài) ==0；寫(xiě)出依次執(zhí)行 下列操作后頭、尾指針的當(dāng)前值。 a,b,c,d,e,f 入隊(duì)， a,b,c,d 出隊(duì)； (1) =______； =______。 g,h,i,j,k,l 入隊(duì)， e,f,g,h 出隊(duì)； (2) =______； =______。 M,n,o,P 入隊(duì)， i,j,k,l,m 出隊(duì)； (3) =______； =______。 27．已知一個(gè)無(wú)向圖如題 27 圖所示，以 ① 為起點(diǎn)，用普里姆 (Prim)算法求其最小生成樹(shù)，畫(huà)出最小生成樹(shù)的構(gòu)造過(guò)程。 28．用歸并排序法對(duì)序列 (98,36,9,0,47,23,1,8)進(jìn)行排序，問(wèn)： (1)一 共需要幾趟歸并可完成排序。 (2)寫(xiě)出第一趟歸并后數(shù)據(jù)的排列次序。 29．一組記錄關(guān)鍵字 (55,76,44,32,64,82,20,16,43)，用散列函數(shù) H(key)=key％ 11 將記錄 散列到散列表 HT[0..12]中去，用線性探測(cè)法解決沖突。 (1)畫(huà)出存入所有記錄后的散列表。 (2)求在等概率情況下，查找成功的平均查找長(zhǎng)度。 四、算法閱讀題 (本大題共 4 小題，每小題 5 分，共 20 分 ) 30．順序表類(lèi)型定義如下： define ListSize 100 typedef struct { int data[ListSize]； int length； }SeqList； 5 / 100 閱讀下列算法，并回答問(wèn)題： void f30(SeqList *L) { int i,j； i=0； while(iLlength) if (Ldata[i]％ 2!=0) { for(j=i+1。 jLlength。 j++ } Ldata[j1]=Ldata[j]。 Llength。 } else i++ } （ 1）若 Ldata 中的數(shù)據(jù)為（ 22,4,63,0,15,29,34,42,3） ,則執(zhí)行上述算法后 Ldata 中的數(shù)據(jù)以及 Llength 的值各是什么？ （ 2）該算法的功能是什么？ ： define MVN 100 ∥ 最大頂點(diǎn)數(shù) typedef int EType。 ∥ 邊上權(quán)值類(lèi)型 typedef struct{ EType edges[MVN][MVN]。 ∥ 鄰接矩陣，即邊表 int n。 ∥ 圖的頂點(diǎn)數(shù) ｝ MGraph。 ∥ 圖類(lèi)型 例如，一個(gè)有向圖的鄰接矩陣如下所示： 0 1 0 0 01 0 0 0 10 1 0 1 01 0 0 0 00 0 0 1 1A??????????? 閱讀下列算法，并回答問(wèn)題： 6 / 100 Void f31(MGraph G) { Int i,j,k=0。 Step1: for (i=0。 i。 i++) for (j=0。 j。 j++) if ([i][j]= =1) k++。 printf(“%d n”,k)。 step2: for (j=0。 j。 j++) { k=0。 for (i=0。 i。 j++) if ([i][j]= =1) k++。 printf(“%d n”,k)。 } } (1)stepl 到 step2 之間的二重循環(huán)語(yǔ)句的功能是什么 ? (2)step2 之后的二重循環(huán)語(yǔ)句的功能是什么 ? 32．閱讀下列算法，并回答問(wèn)題： void f32(int r[]， int n) { Int i， j； for (i=2； in； i++) { r[0]=r[i]； j=il； while (r[0]r[j]) { r[j+l]=r[j]； j=j1； } 7 / 100 r[j+l]=r[0]； } } (1)這是哪一種插入排序算法 ?該算法是否穩(wěn)定 ? (2)設(shè)置 r[0]的作用是什么 ? 33．順序表類(lèi)型定義如下： typedef int SeqList[100]； 閱讀下列算法，并回答問(wèn)題： void f33(SeqList r， int n) { int a, b， i； if (r[0]r[1]) { a=r[0]； b=r[1]； else { a=r[1]； b=r[0]； } for (i=2； in； i++) if (r[i]a) a=r[i]。 else if (r[i]b) b=r[i]； printf(＂ a=％ d， b=％ d。 n＂， a， b)； } (1)給出該算法的功能； (2)給出該算法的時(shí)間復(fù)雜度。 五、算法設(shè)計(jì)題 (本題 10 分 ) 34．二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)類(lèi)型定義如下 typedef struct node{ int data； struct node *lchild， *rchild； } BinNode； typedef BinNode *BinTree； 編寫(xiě)遞歸算法，求只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)總數(shù)，并計(jì)算這些結(jié)點(diǎn)的數(shù)據(jù)值的和。 8 / 100 函數(shù)的原型為： void f34(BinTree T, int *count, int *sum) *count 和 *sum 的初值為 0。 9 / 100 10 / 100 11 / 100 2022年 1 月高等教育自學(xué)考試 全國(guó) 統(tǒng)一命題考試 數(shù)據(jù)結(jié)構(gòu) 試題 課程代碼： 02331 考生答題注意事項(xiàng)： 1. 本卷所有試卷必須在答題卡上作答。答在試卷和草稿紙上的無(wú)效。 2. 第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用 2B 鉛筆將“答題卡”的相應(yīng)代碼涂黑。 3. 第二部分為非選擇題。必須注明大、小題號(hào)，使用 毫米黑色字跡筆作答。 4. 合理安排答題空間，超出答題區(qū)域無(wú)效。 一、單項(xiàng)選擇題 (本大題共 15 小題，每小題 2 分，共 30 分 ) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選