學年二學期數據結構期末考試試卷(a卷)(文件)

　

【正文】 ． 在單鏈表中設置頭結點的作用 是 ________。 19． 深度為 k（ 設根的層數為 1)的完全二叉樹至少有 _______個結點，至多有 ______個結點． k和結點數 n 之間的關系足 _________. 20． 已知鏈隊列的頭尾指針分別是 f 和 r，則將值 x 入隊的操作序列是 _______。 24． 空串與空格串的醫別在于 ________。i++) sum+=1。 29． 順序存儲結構是通過 ________表示元素之間的關系的 。 32． 在完全二叉樹中，編號為 i 和 j 的兩個結點處于同一層的條件是 ______。 36． 在一棵存儲結構為三叉鏈表的二叉樹中，若有一個結點是它的雙親的左子女，且它的雙親有右子女，則這個結點在后 序遍歷中的后繼結點是 ______。 40． 若對一棵二叉樹從 0 開始進行結點編號，并按此編號把它順序存儲到一維數組中，即編號為 0 的結點存儲到 a[0]中，其余類推，則 a[i]元素的左 子女結點為 ，右子女結點為 ，雙親結點 為 . 評卷人 得分 六、簡答題（ 4小題，共 8分） 1． 在多關鍵字排序時， LSD 和 MSD 兩種方法的特點是什么？ 2． 以歸并算法為例，比較內排序和外排序的不同，說明外排序如何提高操作效率。 3． 伙伴空間 4． 串 5． 文件 。試對這種序列討論各種簡單排序方法的時間復雜度。 38． 可以唯一的標識一個記錄的關鍵字稱為 __________。 34． 線索二元樹的左線索指向其 ______，右線索指向其 ______。 30． 高度為 h 的 23 樹中葉子結點的數目至多為 ______。 27． 在單鏈表中設置頭結點的作用是 ___________。 (n1) sum=1； for (i=0。 22． 廣義表的元素可 以 是廣義表；因此，廣義表是 一 個 _______的結構。 18． 順序存儲結構使線性表中邏輯上相鄰的數據元素在物理位胃上也相鄰。 11． 表達式求值是 ______應用的一個典型例子。 read(num)。 r＾ .next:= (10)___。 (5)___ ]。 IF head=NIL THEN[ head:=(1)______。建立一個數據以遞增序組成的鏈表。 7． 索引文件中的索引表是 一 張指示 _______之間對應關系的表：索引表 中 的每項稱作________。 r[i]:=t。 WHILE (j=m) AND NOT finished DO [IF(jm) AND ((2)__) THEN j:=j+1。 j:= (1)__。 4． PROC sift(VAR r： listtype。 函數 Hl 用來計算散 列 地址， 當 發生沖突時， H2 作為 計算下 一個探測地址增 量 ， 假 定在某時刻表 T 的狀 態如圖 所 示 。 slink=q。 B、 qlink=s。 C、 B 樹和 B+樹都能有效地支持順序檢索。 A、 正確性 B、 易讀性 C、 健壯 D、 高效率 53． 某二叉樹的前序遍歷結點訪問順序為， ABDGCDFH 中序遍歷結點訪問順序為DGBAECHE，則其后續遍歷結點訪問順序為。 A、 .0 （ 1 ） B、 0 （ n ） C、 0 （ nlog2n ） D、 0 （ n2 ） 49． P 和 q 兩個指針分別指向雙向循環鏈表 L 兩個元素， p 所指元素是 q 所指元素的后繼的條件是。 ) A、 [[a,b],b,a] B、 [[b,a],[a],[b]] C、 [[a],[a,b],[b]] D、 [b,[a],[a,b]] E、 [[a],[b],[b,a]] F 、 [[b],[b,a],[a]] 45． 設有一個 10 階的對稱矩陣 A，采用壓縮破除計方式，以行序為 主存儲， a1,1 為第一個元素，其存儲地址為 1，每個元素占 1 個地址空間，則 a8,5 的地址為。 A、前序線索樹 B、中 序線索樹 C、 后序線索樹 40． 遍 歷 仍需要棧支持的 A、 前序線索樹 B、 中序線索樹 C、 后序線豢樹 41． 設 F 是森林， B 是由 F 變換得到的 二叉 樹。 。 。 。 。 A、 O(2n) B、 O(n) C、 O(n2) D、 O( 2logn ) 33． 以下那一個術語與數據的存儲結構無關？ A、棧 B、 哈希表 C、線索樹 D、 雙向鏈表 34． 一個算法應該是 A、程序 B、問題求解步驟的描述 C、要滿足五個基本特性 D、 A 和 C 35． 線性表（ a1,a2,? ,an）以鏈接方式存儲時，訪問第 i 位置元素的時間復雜性為 A、 O（ i） B、 O（ 1） C、 O（ n） D、 O（ i1） 36． 線性表的表元存儲方式有 (（ 1） )和鏈接兩種。 A、 插入 B、 冒泡 C、 二路歸并 D、 堆積 23． 在含有 n 個關鍵字的小根堆（堆頂元素最小）中，關鍵字最大的記錄有可能存儲在（ ）位置上。 A、最大概率 B、最小概率 C、同等概率 D、平均概率 14． 對稀疏矩陣進行壓縮存儲目的是 A、便于進行矩陣運算 B、便于輸入和輸出 C、節省存儲空間 D、降低運算的時間復雜度 15． 對文件進行直接存取的依據是 A、按邏輯記錄 號去存取 某個記錄 B、拄邏輯記錄的關鍵字去存取某個記錄 C、 按邏輯記錄的結構去存取某個記錄 D、按邏輯已錄的具體內容 去 存取某個記錄 16． 對散列文件，以下說法錯誤的是 A、 散列文件插入、刪除方便，不需要 索 引 區 且節省存儲空 間 B、散列文件只能按關鍵字隨機存取且存取速度快 C、經過多次插入、刪除后，可能 出 現溢出桶滿而基 桶 內多數記錄已被刪除的情況 D、散列文件順序存取方便 18． 在排序算法中每一項都與其它各項進行比較，計算出小于該項的項的個數，以確定該項的位置叫 A、插入排序 B、枚舉排序 C、選擇排序 D、交換排序 19． 對一組數據（ 84， 47， 25， 15， 21）排序，數據的排列次序在排序的過程中的變化為 （ 1） 84 47 25 15 21 （ 2） 15 47 25 84 21 （ 3） 15 21 25 84 47 （ 4） 15 21 25 47 84 則采用的排序是 A. 選擇 B、 冒泡 C、 快速 D、 插石家莊學院 20222022 學年第 二 學期《 數據結構 》 期末考試 試