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