2022年《數(shù)據(jù)結(jié)構(gòu)》期末考AB卷

1、優(yōu)秀學(xué)習(xí)資料歡迎下載武夷學(xué)院期末考試試卷（ 09 級(jí) 計(jì) 算 機(jī) 科 學(xué) 與 技 術(shù) 專 業(yè) 2010 2011 學(xué)年度第 1 學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)a 卷考試形式閉卷考核類型考試本試卷共五 大題，卷面滿分 100 分，答題時(shí)間 120 分鐘。一、選擇題：（本大題共10 小題，每小題2 分，共 20 分）1某內(nèi)排序方法的穩(wěn)定性是指()。 a該排序算法不允許有相同的關(guān)鍵字記錄 b該排序算法允許有相同的關(guān)鍵字記錄 c平均時(shí)間為0（n log n）的排序方法d以上都不對(duì)2下面程序段的時(shí)間復(fù)雜度為()。for(i=2;i=n;+i) for(j=2;jnext=head；b. p-next=null

2、；c.p =null ；d. p-next-next =head ；4設(shè)棧 s 和隊(duì)列 q 的初始狀態(tài)為空，元素 b 1 ，b 2，b 3 ， b 4 ， b 5 和 b 6 依次通過棧 s，一個(gè)元素出棧后即進(jìn)隊(duì)列q，若 6 個(gè)元素出隊(duì)的序列是b 2 ，b 4 ，b 3 ，b 6 ，b 5 ，題號(hào)一二三四五六七八總分復(fù)核人得分得分評(píng)卷人密封裝訂線系別專業(yè)（班級(jí)）姓名學(xué)號(hào)精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - -

3、- - 第 1 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載b 1 ， ，則棧 s 的容量至少應(yīng)該是()。a. 3 b. 4 c. 5 d.其它5表頭和表尾均為空表的廣義表是()。a.()b.() c.()d.()，() 6. 下列二叉排序樹中，滿足平衡二叉樹定義的是()。ab.c. d.7二維數(shù)組a 的成員是4 個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i 的范圍從1到 8，列下標(biāo) j 的范圍從1到 10，若 a 按行優(yōu)先方式存儲(chǔ)，起始地址為sa，那么元素a85 的起始地址為()。asa+292 bsa+296 csa+300 dsa+304 8當(dāng)在一個(gè)有序

4、的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度()。a 必定快b不一定c 在大部分情況下要快d 取決于表遞增還是遞減9下列關(guān)鍵字序列中，構(gòu)成小根堆的是()。a84 ，46，62，41，28，58，15，37b84， 62，58，46， 41，37，28，15 c15 ，28，46， 37，84，41，58，62d15 ，28，46，37， 84，58，62， 41 10對(duì)一組數(shù)據(jù)（46,79,56,38,40,84）排序，則采用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。a38,40,46,56,79,84 b40,38,46,79,56,

5、84 c40,38,46,56,79,84 d40,38,46,84,56,79 二、填空題：（本大題共10 小題，每小題2 分，共 20 分） 01樹的先根遍歷序列與其對(duì)應(yīng)二叉樹的_先根 _遍歷序列相同。2在折半查找中，要求被查找的元素必須采用_有序的順序 _存儲(chǔ)結(jié)構(gòu)。3若某二叉樹有20 個(gè)葉子節(jié)點(diǎn)，有30 個(gè)節(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總的節(jié)點(diǎn)數(shù)是得分評(píng)卷人精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - -

6、 第 2 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載_。4(a+b)*c+e*f的后綴表達(dá)式為_ab+c*ef*+ _。5線性表l=（a1,a2, ,an）含有 n 個(gè)元素，用數(shù)組表示，假定在表中任何位置上插入元素的概率相同，則在表中插入一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_n/2_。6一個(gè)連通圖的生成樹是它的一個(gè)_極小連通 _子圖。7冒泡排序在最壞的情況下需要進(jìn)行元素的比較次數(shù)是_n(n-1)/2_ _。8高度為8 的完全二叉樹至少有_64_個(gè)葉子結(jié)點(diǎn)。9n 個(gè)頂點(diǎn)的有向完全圖，有_n(n-1)_條弧。10已知一棵完全二叉樹的第6 層（設(shè)根為第1 層）有 8 個(gè)葉結(jié)

7、點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最少是 _39_。三、判斷題：（本大題共10 小題，每小題1 分，共 10 分）1可以隨機(jī)訪問任一元素是鏈表(順序表 )不具有的特點(diǎn)。 （?）2如果二叉樹用二叉鏈表表示，則判斷某個(gè)結(jié)點(diǎn)是不是樹葉的條件是該結(jié)點(diǎn)左、右兩個(gè)指針域的值都為空。 （ ）3結(jié)點(diǎn)的平衡因子是指該結(jié)點(diǎn)的右子樹高度減去該結(jié)點(diǎn)的左子樹高樹。（ ）4快速排序是一種穩(wěn)定的排序方法。（ ）5完全二叉樹的某結(jié)點(diǎn)若無右孩子，則它必是葉結(jié)點(diǎn)。（ ）6圖的深度優(yōu)先搜索序列是唯一的。（ ?）7無向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣也可能是對(duì)稱的。（ ?）8直接插入排序的關(guān)鍵碼比較次數(shù)與初始排列無關(guān)。（ ）9 廣義表

8、的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)單元素值。（ ）10 若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（ ）四、應(yīng)用題：（本大題共5小題，每小題6 分，共 30 分）1某二叉樹的中序遍歷序列為adebcgfhij ，后序遍歷序列為adcbgeihjf ；(1)還原該二叉樹；解：得分評(píng)卷人得分評(píng)卷人f j e 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁，共 11 頁 - - - -

9、- - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載 (2)寫出該二叉樹的前序遍歷序列。fedagbcjhi2已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為：依此鄰接表從頂點(diǎn)c 出發(fā)進(jìn)行遍歷。（ 1）寫出依次從頂點(diǎn)c 出發(fā)進(jìn)行的深度優(yōu)先遍歷序列。cdbafe（ 2）寫出依次從頂點(diǎn)c 出發(fā)進(jìn)行的廣度優(yōu)先遍歷序列。cdabfe3已知一組元素的排序碼為( 46, 74, 16, 53, 14, 26, 40, 38, 86, 65, 27, 34 ) ，使之按關(guān)鍵字遞增次序排序時(shí)，寫出按最左元素作為劃分基準(zhǔn)的快速排序，第一趟排序后的結(jié)果。(34 ,27 ,16 ,38 ,14 ,26 ,40 )46 (86 ,

10、65 ,53 ,74) 4求廣義表l = ( ( a, ( b , ( ), ( c ) ), ( d, ( e ) ) ), ( f, g , ( h ) ) )的長(zhǎng)度 (2)和深度 (3)，并利用廣義表的求表頭操作和求表尾操作，將原子d 分離出來。gethead(l)=(a,(b,(),(c),(d,(e)=d gettail(d)=(b,(),(c),(d,(e)=e gettail(e)=(d,(e)=f gethead(f)=(d,(e)=g gethead(g)=(d) 綜上得： gethead(gethead(gettail(gettail(gethead(l) 5設(shè)某帶權(quán)無向圖

11、如圖，畫出用kruskal 算法生成最小生成樹每一步的結(jié)果。g d a b i h c 2 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載6 依次輸入序列（62，68，30，61，25，14，53，47，90，84）中元素，生成一棵二叉排序樹（1）畫出生成后的二叉排序樹（ 2）畫出刪除結(jié)點(diǎn)30 后的二叉排序62 47 53 90

12、 14 61 68 25 84 30 62 25 90 68 14 84 47 61 53 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載五、算法設(shè)計(jì)線性表含有n 個(gè)元素，用數(shù)組表示在表中插入一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是？武夷學(xué)院期末考試試卷（ 09 級(jí) 計(jì) 算 機(jī) 科 學(xué) 與 技 術(shù) 專 業(yè) 2010 2011 學(xué)年度第

13、1 學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)b 卷考試形式閉卷考核類型考試本試卷共五 大題，卷面滿分 100 分，答題時(shí)間 120 分鐘。一、選擇題：（本大題共10 小題，每小題2 分，共 20 分）1數(shù)據(jù)結(jié)構(gòu)是(d)。a一種數(shù)據(jù)類型b一組性質(zhì)相同的數(shù)據(jù)元素的集合c數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)d相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2下面程序段的時(shí)間復(fù)雜度為()。s=0；for(i=1 ；in；i+) for(j=1 ；jnext=s-next ； s-next=p；b. s-next=p；q-next=s-next ；c.p-next=s-next ；s-next=q；d.s-next=q ；p-next=s-ne

14、xt ；4已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data21，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8 和 3，題號(hào)一二三四五六七八總分復(fù)核人得分得分評(píng)卷人密封裝訂線系別專業(yè)（班級(jí)）姓名學(xué)號(hào)精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載則該隊(duì)列的當(dāng)前長(zhǎng)度為(a) 。a5b6c16d 17 5通常將鏈串的結(jié)點(diǎn)大小設(shè)置為大于1 是為了 (c)。

15、a.提高串匹配效率b.提高存儲(chǔ)密度c.便于插入操作d.便于刪除操作6 若進(jìn)棧序列為1， 2， 3， 4， 5， 6， 且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為(b)。a3，2，6，1，4，5b3， 4，2，1，6，5c1，2， 5，3，4，6 d5， 6，4，2，3，17下列二叉排序樹中，滿足平衡二叉樹定義的是( b)。ab.c. d. 8. 二維數(shù)組a 的成員是4 個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i 的范圍從0到 4，列下標(biāo)j 的范圍從0 到 5，若 a 按行優(yōu)先方式存儲(chǔ)，元素a35 的起始地址與當(dāng)a 按列優(yōu)先方式存儲(chǔ)時(shí)的()元素的起始地址一致。aa24 ba34 c

16、a35 da44 9下列四個(gè)序列中，哪一個(gè)是堆()。a75,65,30,15,25,45,20,10 b75,65,45,10,30,25,20,15 c75,45,65,30,15,25,20,10d75,45,65,10,25,30,20,15 10若數(shù)據(jù)元素序列11， 12，13，7，8，9，23， 4，5 是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是( b)。a起泡排序b.插入排序c.選擇排序d.二路歸并排序二、填空題：（本大題共10 小題，每小題2 分，共 20 分）1樹的后根遍歷序列與其對(duì)應(yīng)二叉樹的_中根 _遍歷序列相同。2已知一棵完全二叉樹的第6 層（設(shè)根為

17、第1 層）有 8 個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是 _111_。3n 個(gè)權(quán)構(gòu)成一棵huffman 樹，其節(jié)點(diǎn)總數(shù)為_n-1_。4(a+b)*c+e*f的前綴表達(dá)式為_+*+abc*ef_ 。得分評(píng)卷人精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載5線性表l=（a1,a2, ,an）含有 n 個(gè)元素，用數(shù)組表示，假定刪除表中

18、任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_(n-1)/2_ 。6一個(gè)非連通圖的連通分量是它的一個(gè)_極大連通 _子圖。7冒泡排序在最好的情況下需要進(jìn)行元素的比較次數(shù)是_n-1_。8若一棵二叉樹具有41 個(gè)結(jié)點(diǎn)， 這些結(jié)點(diǎn)的度要么是0 要么是 2，則該二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)是_21_；9n 個(gè)頂點(diǎn)的連通無向圖，其邊的條數(shù)至多為_n(n-1)/2_ 。10廣義表 ()， ()的深度是 _2_。三、判斷題：（本大題共10 小題，每小題1 分，共 10 分）1 線性結(jié)構(gòu)的基本特征是每個(gè)結(jié)點(diǎn)至多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 （對(duì) ）2如果樹用二叉鏈表表示，則判斷某個(gè)結(jié)點(diǎn)是不是樹葉的條件

19、是該結(jié)點(diǎn)左、右兩個(gè)指針域的值都為空。（錯(cuò) ）3直接插入排序是一種穩(wěn)定的排序方法。（對(duì)）4對(duì)于一個(gè)連通網(wǎng)，其最小生成樹是唯一的。（錯(cuò)）5完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。（ 對(duì)）6圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是唯一的。（錯(cuò)）7無向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一定不對(duì)稱。（錯(cuò) ）8直接插入排序的關(guān)鍵碼比較次數(shù)與初始排列有關(guān)。（對(duì)）9廣義表 (2),(2) 的表尾是 (2)。 （對(duì)）10樹中結(jié)點(diǎn)的度是指從根到該結(jié)點(diǎn)所經(jīng)過分支的條數(shù)。（ 錯(cuò)）四、應(yīng)用題：（本大題共5小題，每小題6 分，共 30 分）1.某二叉樹的中序遍歷序列為dfebagc，先序遍歷序列為abdefc

20、g；(1)還原該二叉樹；得分評(píng)卷人得分評(píng)卷人a b c d e g f 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載 (2)寫出該二叉樹的后序遍歷序列。fedbgca2已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為：依此鄰接表從頂點(diǎn)c 出發(fā)進(jìn)行遍歷。（ 1）寫出依次從頂點(diǎn)b 出發(fā)進(jìn)行的深度優(yōu)先遍歷序列。bacdfe（ 2）寫

21、出依次從頂點(diǎn)b 出發(fā)進(jìn)行的廣度優(yōu)先遍歷序列。bafedc3對(duì)一組關(guān)鍵字：26，85，37，10，62，18，29，15 采用快速排序方法進(jìn)行排序，用第一個(gè)關(guān)鍵字作樞軸，請(qǐng)寫出每趟排序結(jié)果。（只寫每趟結(jié)果）解：第一趟： （15 18 10）26 （62 37 29 85）第二趟：（10）15（ 18）26（29 37）62（85）第三趟： 10 15 18 26 29 （37） 62 85 4利用廣義表的head 和 tail 操作，可從廣義表l=(a，b)，(c，d)中分解得到原子c，其操作表達(dá)式為head(head(tail(l) ；分別寫出從下列廣義表中分解得到b 的操作表達(dá)式。(1)l1

22、=( （a.，b） ，c，d)； head（tail（head（l1） ） ）(2)l2=(a) ， (b)，(c)， d)。 head（head(tail(l2) ）5設(shè)某帶權(quán)無向圖如右圖，畫出用prim 算法，從頂點(diǎn)a 開始生成最小生成樹的每一步結(jié)果。6對(duì)長(zhǎng)度為12 的有序表（升序） ，給出折半查找的判定樹，給出等概率情況下的平均查找長(zhǎng)度。五、算法設(shè)計(jì)：（本大題共小題，每小題分，共分）精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁，共 11 頁 - - - - - - - - -精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁，共 11 頁 - - - - - - - - -優(yōu)秀學(xué)習(xí)資料歡迎下載1假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示非遞減有序表，單鏈表的類型定義如下：typedef struct node int da