學年二學期數據結構期末考試試卷(a卷)(存儲版)

　　

【正文】 次_______________ 任課教員_________ 出題教員簽名________ 任課教研室主任簽名_______日期_______ 隊別__________ 教學班次___________ 學號___________ 姓名____________ ??????????密????????????封????????????線??????????????? 2( log )o n n 評卷人 得分 三、單項選擇題（ 60小題，共 30分） 1． 若需在 的時間內完成對數組 的排序 ，且要求排序是穩定的，則可選擇的排序方法是 A、快速排序 B、 堆排序 C、 歸并排序 D、直接插入排序 3． 在采用鏈接 法 處理沖突的開散列表上，假定 裝填 因子 a 的值為 4， 則 查找任 一 元素的平均查 找 長度為 A、 3 B、 3． 5 C、 4 D、 2． 5 4． 設散 列 表的長 m=14，散列函數為 h(k)=k％ 11，表中已有 4 個 記 錄 (如圖所示 )， 如果采用二 次 探測再散列來處理沖突， 則關鍵字為 49 的記錄其存儲地址是 A、 8 B、 3 C、 5 D、 9 5． 若根據查找表建 立長度 為 m 的閉散列表 并采用 二次探測處理沖突，假定對一個 元 素第一次計算的 散列地址為 d，則第 4 次 計 算的散列地址為 A、 (d+l)％ m B、 (d1)％ m C、 (d+4)％ m D、 (d4)％ m 6． 對下列 4 個序列用快速排序方法進行排序， 以序列的第 1 個元素為基準進行劃分． 在 第 l趟劃分 過程中，元素移動次數最多的是序列 A、 70， 75， 82， 90, 23, 16， 10， 68 B、 70， 75， 68， 23， 10， 16， 90， 82 C、 82， 75， 70， 16， 10， 90， 68， 23 D、 23， 10， 16， 70， 82， 75， 68, 90 7． 已 知待排序的 n 個元素 可 分為 n／ k 個 組 ，每個組包含 k 個元素，且任一組內的各元 素 均分別大于 前組內的所有元素和小于后組內的所有元素，若采用基于比較的排序，其時間下界應為 A、 ( log )2o k k B、 2( log )o k n C、 2( log )o n k D、 ( log )2o n n 8． 若對一個元素進行直接選擇排序，則進行任 一 趟排序的過程中，為尋找 最 小值 元 素所需要的時間 復雜性 為 A、 O(l) B、 2(log )on C、 2()on D、 ()on 9． 在對一個元素進行直接選擇排序過 程 中，第 i 趟需從 （ ） 個元素 中 選擇 出 最小值 元 素。 A、 插入 B、 冒泡 C、 二路歸并 D、 堆積 23． 在含有 n 個關鍵字的小根堆（堆頂元素最小）中，關鍵字最大的記錄有可能存儲在（ ）位置上。 。 。 A、前序線索樹 B、中 序線索樹 C、 后序線索樹 40． 遍 歷 仍需要棧支持的 A、 前序線索樹 B、 中序線索樹 C、 后序線豢樹 41． 設 F 是森林， B 是由 F 變換得到的 二叉 樹。 A、 .0 （ 1 ） B、 0 （ n ） C、 0 （ nlog2n ） D、 0 （ n2 ） 49． P 和 q 兩個指針分別指向雙向循環鏈表 L 兩個元素， p 所指元素是 q 所指元素的后繼的條件是。 C、 B 樹和 B+樹都能有效地支持順序檢索。 slink=q。 4． PROC sift(VAR r： listtype。 WHILE (j=m) AND NOT finished DO [IF(jm) AND ((2)__) THEN j:=j+1。 7． 索引文件中的索引表是 一 張指示 _______之間對應關系的表：索引表 中 的每項稱作________。 IF head=NIL THEN[ head:=(1)______。 r＾ .next:= (10)___。 11． 表達式求值是 ______應用的一個典型例子。 22． 廣義表的元素可 以 是廣義表；因此，廣義表是 一 個 _______的結構。 27． 在單鏈表中設置頭結點的作用是 ___________。 34． 線索二元樹的左線索指向其 ______，右線索指向其 ______。試對這種序列討論各種簡單排序方法的時間復雜度。 40． 若對一棵二叉樹從 0 開始進行結點編號，并按此編號把它順序存儲到一維數組中，即編號為 0 的結點存儲到 a[0]中，其余類推，則 a[i]元素的左 子女結點為 ，右子女結點為 ，雙親結點 為 . 評卷人 得分 六、簡答題（ 4小題，共 8分） 1． 在多關鍵字排序時， LSD 和 MSD 兩種方法的特點是什么？ 2． 以歸并算法為例，比較內排序和外排序的不同，說明外排序如何提高操作效率。 32． 在完全二叉樹中，編號為 i 和 j 的兩個結點處于同一層的條件是 ______。i++) sum+=1。 19． 深度為 k（ 設根的層數為 1)的完全二叉樹至少有 _______個結點，至多有 ______個結點． k和結點數 n 之間的關系足 _________. 20． 已知鏈隊列的頭尾指針分別是 f 和 r，則將值 x 入隊的操作序列是 _______。 read(num) ] ENDP。 r＾ .next:= (8)____。 {在鏈首為 head 的表中按遞增序插入 x} new(r)。{sift} 5． 直接插入排序用監視哨的作用是 _______。 finished:=false。 2． 克魯斯卡爾算法的時間復雜度為 _____，它 對 ______圖較為適臺。 slink=p。 A、 (1)(2) B、 (1) C、 (2) D、(1)、 (2)都錯 56． 利用二叉鏈表存儲樹，則根結點的右指針是 A、指向最左孩子 B、指向最右孩子 C、空 D、非空 57． 下面關于 B 和 B+樹的敘述中，不正確的是 A、 B 樹和 B+樹都是平衡的多叉樹。 A、 可以順序存儲 B、數據元素是一個字符 C、可以鏈接存儲 D、 數據元素可以是多個字符 47． 下列說法正確的是。q ne x t p ne x t q pri or p p ne x t q p ne x t q? ? ? ? ? ? ? ? ? 38． 若某線性表最常用的操作是