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

　　

【正文】 順序 (依次 )進(jìn)棧，出棧序列有 種，即：21 (2 )!1 ( !)n nC nn???。 A、下面的 B， C， D 都不對(duì)。 。 A、 13 B、33 C、 18 D、 40 46． 串是一中特殊的線性表，其特殊性體現(xiàn)在。 slink=p C、 plink=slink。 x:=r[k].key。 PROC insert( head, x)。 WHILE num0 DO [ insert(head,num)。sumn。 39． 由一棵二叉樹(shù)的前序序列和 可唯一確定這棵二叉樹(shù)。 35． 先根次序周游樹(shù)林正好等同于按 ______周游對(duì)應(yīng)的二叉樹(shù)；后根次序周游樹(shù)林正好等同于 ______周游對(duì)應(yīng)的二叉樹(shù)。 23． 設(shè)有 一 個(gè) 10 階對(duì)稱矩陣 A 采用壓縮存儲(chǔ)方式 (以行為主序存儲(chǔ)： 11 1a? 1)．則 85a 的 地址為 ________。 ] ] ENDP。 8． 對(duì)于散列文件中的每個(gè)散列地址，其對(duì)應(yīng)單鏈表中的第 一 個(gè)結(jié)點(diǎn)稱為 _______，其余結(jié)點(diǎn)稱為 __________。k,m:integer)。 D、 B 樹(shù)和 B+樹(shù)都能有效地支持隨機(jī)檢索。若 F 中有 N 個(gè)非終端結(jié)點(diǎn)，則 B 中 右指針域?yàn)榭盏?結(jié)點(diǎn)有 ____________個(gè)。 。 A、 ni+1 B、 ni C、 i D、 i+1 10． 快速排序 （ ）在 情況下不利于發(fā)揮其長(zhǎng)處。 ( F ) 6． 為提高在外排序過(guò)程中，對(duì)長(zhǎng)度為 N 的初始序列進(jìn)行“置換 — 選擇”排序時(shí)，可以得到的最大初始有序段的長(zhǎng)度不超過(guò) N/2。 ( T ) 3． 一個(gè)圖的廣 度優(yōu)先搜索樹(shù)是唯一的 。（ F ） 19． 哈希表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。表左的 s 指向起始表元。q ne x t p ne x t q pri or p p ne x t q p ne x t q? ? ? ? ? ? ? ? ? 38． 若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。 A、 (1)(2) B、 (1) C、 (2) D、(1)、 (2)都錯(cuò) 56． 利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是 A、指向最左孩子 B、指向最右孩子 C、空 D、非空 57． 下面關(guān)于 B 和 B+樹(shù)的敘述中，不正確的是 A、 B 樹(shù)和 B+樹(shù)都是平衡的多叉樹(shù)。 2． 克魯斯卡爾算法的時(shí)間復(fù)雜度為 _____，它 對(duì) ______圖較為適臺(tái)。{sift} 5． 直接插入排序用監(jiān)視哨的作用是 _______。 r＾ .next:= (8)____。 19． 深度為 k（ 設(shè)根的層數(shù)為 1)的完全二叉樹(shù)至少有 _______個(gè)結(jié)點(diǎn)，至多有 ______個(gè)結(jié)點(diǎn)． k和結(jié)點(diǎn)數(shù) n 之間的關(guān)系足 _________. 20． 已知鏈隊(duì)列的頭尾指針?lè)謩e是 f 和 r，則將值 x 入隊(duì)的操作序列是 _______。 32． 在完全二叉樹(shù)中，編號(hào)為 i 和 j 的兩個(gè)結(jié)點(diǎn)處于同一層的條件是 ______。試對(duì)這種序列討論各種簡(jiǎn)單排序方法的時(shí)間復(fù)雜度。 27． 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 ___________。 11． 表達(dá)式求值是 ______應(yīng)用的一個(gè)典型例子。 IF head=NIL THEN[ head:=(1)______。 WHILE (j=m) AND NOT finished DO [IF(jm) AND ((2)__) THEN j:=j+1。 slink=q。 A、 .0 （ 1 ） B、 0 （ n ） C、 0 （ nlog2n ） D、 0 （ n2 ） 49． P 和 q 兩個(gè)指針?lè)謩e指向雙向循環(huán)鏈表 L 兩個(gè)元素， p 所指元素是 q 所指元素的后繼的條件是。 。 A、 插入 B、 冒泡 C、 二路歸并 D、 堆積 23． 在含有 n 個(gè)關(guān)鍵字的小根堆（堆頂元素最小）中，關(guān)鍵字最大的記錄有可能存儲(chǔ)在（ ）位置上。 （ T ） 13． 深度為 K 的二叉樹(shù)中結(jié)點(diǎn)總數(shù)≤ 2k1。石家莊學(xué)院 20222022 學(xué)年第 二 學(xué)期《 數(shù)據(jù)結(jié)構(gòu) 》 期末考試 試卷 試卷 第 1 頁(yè) （共 7 頁(yè)） 考核人數(shù)______ 考核班次_______________ 任課教員_________ 出題教員簽名________ 任課教研室主任簽名_______日期_______ 隊(duì)別__________ 教學(xué)班次___________ 學(xué)號(hào)___________ 姓名____________ ??????????密????????????封????????????線??????????????? 石家莊學(xué)院 《 數(shù)據(jù)結(jié)構(gòu) 》 期末考試 試卷 (A 卷 ) 題 目 一 二 三 四 五 六 七 總 分 核分人 復(fù)查人 得分 題目部分，（卷面共有 135 題， 100 分，各大題標(biāo)有題量和總分） 評(píng)卷人 得分 一、應(yīng)用題（ 4小題，共 8分） 1． 試列出 下圖 全部可能的拓?fù)渑判蛐蛄? 2． 在實(shí)現(xiàn)快速排序的非遞歸算法時(shí)，可根據(jù)基準(zhǔn)對(duì)象，將待排序排序碼序列劃分為兩個(gè)子序列。 ( F ) 12． 完 全二 叉樹(shù)的某結(jié)點(diǎn)若無(wú)左孩子，則它必是葉結(jié)點(diǎn)。 A、 (38,40,46,56,79,84) B、 (40,38,46,79,56,84) C、 (40,38,46,56,79,84) D、 (40,38,46,84,56,79) 22． 下面給出的四種排序法中 ( )排序法是不穩(wěn)定性排序法。 。 A、 線性表的邏輯順序與存儲(chǔ)順序總是一致的 B、 線性報(bào)第鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，內(nèi)存中可用的 存儲(chǔ)單元可以使連續(xù)的，也可以不連續(xù) C、 線性表弟順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D、 每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運(yùn)算 48． 在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，并使插入結(jié)點(diǎn)后的單鏈表仍然有序，則該操作的時(shí)間復(fù)雜性量級(jí)為。 D 、 plink=s。 t:=r[k]。r＾ .data:=x。 10． 隊(duì)列是特殊的線性表，其特殊性在于 ___________。 26． 對(duì)矩陣壓縮是為了 _______。 3． 一個(gè)長(zhǎng)度為 n 的序列，若去掉其中少數(shù) k 個(gè)記錄后，序列是按關(guān)鍵字有序的，則稱為近似有序序列。 33． 在順序存儲(chǔ)的二叉樹(shù)中，編號(hào)為 i 和 j 的兩個(gè)結(jié)點(diǎn)處在同一層的條件是 ______。 21． 設(shè)循環(huán)隊(duì)列存放在向量 [0:M]中，則隊(duì)頭指針 在循 環(huán)意義下的出隊(duì)操作可表示為 _______，若用