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