學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷(a卷)-資料下載頁
2025-01-09 16:52本頁面
【正文】 一 張指示 _______之間對應(yīng)關(guān)系的表：索引表 中 的每項(xiàng)稱作________。 8． 對于散列文件中的每個(gè)散列地址，其對應(yīng)單鏈表中的第 一 個(gè)結(jié)點(diǎn)稱為 _______，其余結(jié)點(diǎn)稱為 __________。 9． 一個(gè)無頭結(jié)點(diǎn)的線性鏈表 (不循環(huán) )有兩個(gè)域。數(shù)據(jù)域 data，指針域 next，鏈?zhǔn)?head，下面算法用 read(num)讀入數(shù)據(jù)，當(dāng) num 小于 0 時(shí)，輸入結(jié)束。建立一個(gè)數(shù)據(jù)以遞增序組成的鏈表。 PROC insert( head, x)。 {在鏈?zhǔn)诪?head 的表中按遞增序插入 x} new(r)。r＾ .data:=x。 IF head=NIL THEN[ head:=(1)______。 r＾ .next:= (2)________ ] ELSE IF (3)___ THEN [r＾ .next:=head。 head:=r] ELSE [p:=head。 WHILE (4)___ AND (p＾ .next≠ NIL ) DO[q:=p。 (5)___ ]。 IF (6)___ THEN [ q＾ .next:=(7)___。 r＾ .next:= (8)____。 ] ELSE [p＾ .next:=(9)____。 r＾ .next:= (10)___。 ] ] ENDP。 PROC creat(head)。 head:= (11)______。 read(num)。 WHILE num0 DO [ insert(head,num)。 read(num) ] ENDP。 10． 隊(duì)列是特殊的線性表，其特殊性在于 ___________。 11． 表達(dá)式求值是 ______應(yīng)用的一個(gè)典型例子。 12． 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 L 中只有一個(gè)元素結(jié)點(diǎn)的條件是： ________ 13． 已知指針 p 指向單鏈表 L 中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是： ________ 14． 對于雙向鏈表 ,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 ______個(gè)，單鏈表為_______個(gè)。 15． 在雙向鏈表結(jié)構(gòu)中，若要求在 p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為 s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語句： s^ .next:=p； s^ .prior:= ________； p^ .prior:=s； ________:=s； 16． 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用 是 ________。 17． 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 _______。 18． 順序存儲(chǔ)結(jié)構(gòu)使線性表中邏輯上相鄰的數(shù)據(jù)元素在物理位胃上也相鄰。因此，這種表便于 ______訪問，是一種 ______結(jié)構(gòu)。 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ì)的操作序列是 _______。 21． 設(shè)循環(huán)隊(duì)列存放在向量 [0:M]中，則隊(duì)頭指針 在循 環(huán)意義下的出隊(duì)操作可表示為 _______，若用犧牲一個(gè)單元的辦法來區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針 ） ,則隊(duì)滿的條件為 _______。 22． 廣義表的元素可 以 是廣義表；因此，廣義表是 一 個(gè) _______的結(jié)構(gòu)。 23． 設(shè)有 一 個(gè) 10 階對稱矩陣 A 采用壓縮存儲(chǔ)方式 (以行為主序存儲(chǔ)： 11 1a? 1)．則 85a 的 地址為 ________。 24． 空串與空格串的醫(yī)別在于 ________。 25． 下面程序段的時(shí)間復(fù)雜度為 ________。 (n1) sum=1； for (i=0。sumn。i++) sum+=1。 26． 對矩陣壓縮是為了 _______。 27． 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 ___________。 28． 順序查找長度 n 的順序表，查找成功的平均查找長度為 _________。 29． 順序存儲(chǔ)結(jié)構(gòu)是通過 ________表示元素之間的關(guān)系的 。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過 ________表示元素之間的關(guān)系的。 30． 高度為 h 的 23 樹中葉子結(jié)點(diǎn)的數(shù)目至多為 ______。 石家莊學(xué)院 20222022 學(xué)年第 二 學(xué)期《 數(shù)據(jù)結(jié)構(gòu) 》 期末考試 試卷 試卷 第 7 頁 （共 7 頁） 考核人數(shù)______ 考核班次_______________ 任課教員_________ 出題教員簽名________ 任課教研室主任簽名_______日期_______ 隊(duì)別__________ 教學(xué)班次___________ 學(xué)號(hào)___________ 姓名____________ ??????????密????????????封????????????線??????????????? 31． 如果結(jié)點(diǎn) A 有 3 個(gè)兄弟 ，而且 B 是 A 的雙親，則 B 的度是 ______。 32． 在完全二叉樹中，編號(hào)為 i 和 j 的兩個(gè)結(jié)點(diǎn)處于同一層的條件是 ______。 33． 在順序存儲(chǔ)的二叉樹中，編號(hào)為 i 和 j 的兩個(gè)結(jié)點(diǎn)處在同一層的條件是 ______。 34． 線索二元樹的左線索指向其 ______，右線索指向其 ______。 35． 先根次序周游樹林正好等同于按 ______周游對應(yīng)的二叉樹；后根次序周游樹林正好等同于 ______周游對應(yīng)的二叉樹。 36． 在一棵存儲(chǔ)結(jié)構(gòu)為三叉鏈表的二叉樹中，若有一個(gè)結(jié)點(diǎn)是它的雙親的左子女，且它的雙親有右子女，則這個(gè)結(jié)點(diǎn)在后 序遍歷中的后繼結(jié)點(diǎn)是 ______。 37． 如果關(guān)鍵碼按值排序，而后用二分法依次檢索這些關(guān)鍵碼，并把檢索中遇到的在二叉樹中沒有出現(xiàn)的關(guān)鍵碼依次插入到二叉排序樹中，則對這樣的二叉排序樹檢索時(shí)，平均比較次數(shù)為 __________。 38． 可以唯一的標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字稱為 __________。 39． 由一棵二叉樹的前序序列和 可唯一確定這棵二叉樹。 40． 若對一棵二叉樹從 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)卷人 得分 六、簡答題（ 4小題，共 8分） 1． 在多關(guān)鍵字排序時(shí)， LSD 和 MSD 兩種方法的特點(diǎn)是什么？ 2． 以歸并算法為例，比較內(nèi)排序和外排序的不同，說明外排序如何提高操作效率。 3． 一個(gè)長度為 n 的序列，若去掉其中少數(shù) k 個(gè)記錄后，序列是按關(guān)鍵字有序的，則稱為近似有序序列。試對這種序列討論各種簡單排序方法的時(shí)間復(fù)雜度。 4． 索引順序存取方法（ ISAM）中，主文件已按關(guān)鍵字排序， 為何還需要主關(guān)鍵字索引？ 評(píng)卷人 得分 七、名詞解釋（ 5小題，共 20分） 1． 內(nèi)部排序 2． 棧。 3． 伙伴空間 4． 串 5． 文件
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1