學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷(a卷)(更新版)

　　

【正文】 易讀性 C、 健壯 D、 高效率 53． 某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序?yàn)椋? ABDGCDFH 中序遍歷結(jié)點(diǎn)訪問順序?yàn)镈GBAECHE，則其后續(xù)遍歷結(jié)點(diǎn)訪問順序?yàn)椤?) 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． 設(shè)有一個(gè) 10 階的對稱矩陣 A，采用壓縮破除計(jì)方式，以行序?yàn)?主存儲(chǔ)， a1,1 為第一個(gè)元素，其存儲(chǔ)地址為 1，每個(gè)元素占 1 個(gè)地址空間，則 a8,5 的地址為。 。 。 A、 O(2n) B、 O(n) C、 O(n2) D、 O( 2logn ) 33． 以下那一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？ A、棧 B、 哈希表 C、線索樹 D、 雙向鏈表 34． 一個(gè)算法應(yīng)該是 A、程序 B、問題求解步驟的描述 C、要滿足五個(gè)基本特性 D、 A 和 C 35． 線性表（ a1,a2,? ,an）以鏈接方式存儲(chǔ)時(shí)，訪問第 i 位置元素的時(shí)間復(fù)雜性為 A、 O（ i） B、 O（ 1） C、 O（ n） D、 O（ i1） 36． 線性表的表元存儲(chǔ)方式有 (（ 1） )和鏈接兩種。 A、最大概率 B、最小概率 C、同等概率 D、平均概率 14． 對稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是 A、便于進(jìn)行矩陣運(yùn)算 B、便于輸入和輸出 C、節(jié)省存儲(chǔ)空間 D、降低運(yùn)算的時(shí)間復(fù)雜度 15． 對文件進(jìn)行直接存取的依據(jù)是 A、按邏輯記錄 號去存取 某個(gè)記錄 B、拄邏輯記錄的關(guān)鍵字去存取某個(gè)記錄 C、 按邏輯記錄的結(jié)構(gòu)去存取某個(gè)記錄 D、按邏輯已錄的具體內(nèi)容 去 存取某個(gè)記錄 16． 對散列文件，以下說法錯(cuò)誤的是 A、 散列文件插入、刪除方便，不需要 索 引 區(qū) 且節(jié)省存儲(chǔ)空 間 B、散列文件只能按關(guān)鍵字隨機(jī)存取且存取速度快 C、經(jīng)過多次插入、刪除后，可能 出 現(xiàn)溢出桶滿而基 桶 內(nèi)多數(shù)記錄已被刪除的情況 D、散列文件順序存取方便 18． 在排序算法中每一項(xiàng)都與其它各項(xiàng)進(jìn)行比較，計(jì)算出小于該項(xiàng)的項(xiàng)的個(gè)數(shù)，以確定該項(xiàng)的位置叫 A、插入排序 B、枚舉排序 C、選擇排序 D、交換排序 19． 對一組數(shù)據(jù)（ 84， 47， 25， 15， 21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為 （ 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、 插石家莊學(xué)院 20222022 學(xué)年第 二 學(xué)期《 數(shù)據(jù)結(jié)構(gòu) 》 期末考試 試卷 試卷 第 3 頁 （共 7 頁） 考核人數(shù)______ 考核班次_______________ 任課教員_________ 出題教員簽名________ 任課教研室主任簽名_______日期_______ 隊(duì)別__________ 教學(xué)班次___________ 學(xué)號___________ 姓名____________ ??????????密????????????封????????????線??????????????? 入 20． 有一組數(shù)據(jù)（ 15， 9， 7， 8， 20， 1， 7， 4） 用 快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)的排序?yàn)? ( )（按遞增序）。（ T ） 17． 一個(gè)樹的葉結(jié)點(diǎn)，在前序遍歷和后序遍歷下，皆以相同的相對位置出現(xiàn)。（ F ） 9． 循環(huán)隊(duì)列通常用指針來實(shí)現(xiàn) 隊(duì)列的頭尾相接。 評卷人 得分 二、判斷正誤（ 20小題，共 10分） 1． 散列表的結(jié)點(diǎn)中包含數(shù)據(jù)元素自身的信息，不包 含 任何指針。 4． 用三元數(shù)組表示稀疏矩陣的轉(zhuǎn)置矩陣 ,并簡要寫出解題步驟。 ( T ) 8． 堆排序是穩(wěn)定的排序方法。（ F ） 16． 完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。 A 、 PRIM B、 KRUSKAL 12． 用 DFS 遍歷 一 個(gè)無環(huán)有向圖 ， 并載 DFS 算法退棧返回時(shí)打印出相應(yīng)得頂點(diǎn)，則輸出的頂點(diǎn)序列是 A、 逆拓?fù)溆行虻? B、 拓?fù)溆行虻? C、 無序的 13． 散列函數(shù)有有一 個(gè)共同性質(zhì)，即函數(shù)值應(yīng)按 _____取其值域的每一個(gè)值 。 A、 遞歸調(diào)用 B、 子程序調(diào)用 C、 表達(dá)式求值 D、 A，Ｂ，Ｃ 30． 設(shè)有三個(gè)元素 X， Y， Z 順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是 A、XYZ B、 YZX C、 ZXY D、 ZYX 31． 若一個(gè)棧的輸入序列為 1,2,3,? ,n，輸出序列的第一個(gè)元素是 i，則第 j 個(gè)輸出元素是 A、 ij1 B、 ij C、 ji+1 D、 不確定的 32． 在下面的程序段中，對 x 的賦值語句的頻度為 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1。 。 。如 [a,b])表示由 a,b 構(gòu)成的廣義表，而 Head()表示取廣義表的頭部。 A、 top==0 B、 top==1 C、 top==1 D、 top==m 52． 算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為。 plink=s。 評卷人 得分 五、填空題（ 40小題，共 20分） 1． 設(shè)有兩個(gè)散列函數(shù) H1(K)=K%13 和 H2(K)=K％ 11+1，散列表為 T[0.. 12]，用 雙 重散列解決沖突。 } i:=k。 j:= (5)____] ]。數(shù)據(jù)域 data，指針域 next，鏈?zhǔn)?head，下面算法用 read(num)讀入數(shù)據(jù)，當(dāng) num 小于 0 時(shí)，輸入結(jié)束。 WHILE (4)___ AND (p＾ .next≠ NIL ) DO[q:=p。 head:= (11)______。 17． 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 _______。 25． 下面程序段的時(shí)間復(fù)雜度為 ________。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過 ________表示元素之間的關(guān)系的。 37． 如果關(guān)鍵碼按值排序，而后用二分法依次檢索這些關(guān)鍵碼，并把檢索中遇到的在二叉樹中沒有出現(xiàn)的關(guān)鍵碼依次插入到二叉排序樹中，則對這樣的二叉排序樹檢索時(shí)，平均比較次數(shù)為 _______