數(shù)據(jù)結(jié)構(gòu)期末考試試題答案詳解

1、數(shù)據(jù)結(jié)構(gòu)試題（100分）（供2005級(jí)信息管理與信息系統(tǒng)本科專業(yè)使用）學(xué)號(hào)： 姓名： 座號(hào)： 系別： 年級(jí)： 專業(yè)： 題號(hào)一二三四五六七八總計(jì)得分 總分合計(jì)人： 復(fù)核人： 說明：本試卷分為兩部分，第I卷（選擇題和判斷題）必須在“答題卡”上按規(guī)定要求填、涂；第II卷直接在試卷上作答。不按規(guī)定答題、填涂，一律無效。第I卷得分評(píng)卷人一、試題類型：?jiǎn)雾?xiàng)選擇題（每小題2分，共40分）（類型說明：在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)選出正確選項(xiàng)并在“答題卡”的相應(yīng)位置上涂黑。多涂、少涂、錯(cuò)誤均無分。）1. 算法分析的兩個(gè)主要方面是： （ ）（A) 空間復(fù)雜性和時(shí)間復(fù)雜性 （B) 正確性

2、和簡(jiǎn)明性（C) 可讀性和文檔性 （D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性2. 計(jì)算機(jī)算法指的是： （ ）（A) 計(jì)算方法 （B) 排序方法 （C) 解決問題的有限運(yùn)算序列 （D) 調(diào)度方法3 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱為：（ ）（A）存儲(chǔ)結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲(chǔ)結(jié)構(gòu) （D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是 。 （ ）（A）110 （B）108 （C）100 （D）1205. 鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間： （ ）（A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針（B）只有一

3、部分，存放結(jié)點(diǎn)值（C） 只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針（D） 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)6. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址: （ ）（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以7. 棧中元素的進(jìn)出原則是： （ ） （）先進(jìn)先出 （）后進(jìn)先出 （）?？談t進(jìn) （）棧滿則出8. 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為： （ ） （） i （） n=i （） n-i+1 （） 不確定9. 串是一種特殊的線性表，其特殊性體現(xiàn)在： （ ）

4、（）可以順序存儲(chǔ) （）數(shù)據(jù)元素是一個(gè)字符 （）可以鏈?zhǔn)酱鎯?chǔ) （）數(shù)據(jù)元素可以是多個(gè)字符10. 設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號(hào)i開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結(jié)果串是： （ ） （）BCDEF （）BCDEFG （）BCPQRST （）BCDEFEF11. 假設(shè)有60行70列的二維數(shù)組a160, 170以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第

5、58列的元素a32,58的存儲(chǔ)地址為 。（無第0行第0列元素） （ ） （）16902 （）16904 （）14454 （）答案A, B, C均不對(duì)12二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。 （ ）（）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); （）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 13. 具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。 （ ）() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1

6、9;14把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。 （ ）（）唯一的 （）有多種（）有多種，但根結(jié)點(diǎn)都沒有左孩子 （）有多種，但根結(jié)點(diǎn)都沒有右孩子15. 已知圖的鄰接表如下所示，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ ）（A） 0 1 3 2 （B） 2 0 3 1 （C） 1 3 2 0 （D） 0 1 2 316. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ ）（A）0 3 2 1 （B） 1 2 3 0 （C）3 2 1 0 （D） 3 0 1 217折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，

7、則它將依次與表中 比較大小，查找結(jié)果是失敗。 （ ）（A）20，70，30，50 （B）30，88，70，50 （C）20，50 （D）30，88，5018鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。 （ ）（A）順序 （B）鏈?zhǔn)?（C）星式 （D）網(wǎng)狀19不含任何結(jié)點(diǎn)的空樹 。 （ ）（）不是一棵樹; （）不是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹20在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。 （ ） A1/2 B. 1 C. 2 D. 4 得分評(píng)卷人二、試題類型：判斷題（每小題1分，共10分）（類型說明：判斷正確答案，選項(xiàng)并在“答題卡”的相應(yīng)位置填涂，認(rèn)為正

8、確的涂“A”錯(cuò)誤的涂“B ”。多涂、少涂、錯(cuò)誤均無分。）21. 二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。 （ ）22. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 （ ）23. 二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （ ）24. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。 （ ）25. 二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。 （ ）26. 隊(duì)列是一種先進(jìn)后出型結(jié)構(gòu)。 （ ）27. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。 （ ）28. 棧是一種對(duì)所有插入、刪除操

9、作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。 （ ）29. 線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。 （ ）30. 線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。（ ）第II卷得分評(píng)卷人三、試題類型：填空題（每空1分，共10分）（類型說明：請(qǐng)將正確答案填于試題預(yù)留的橫線上。）31. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 。不允許插入和刪除運(yùn)算的一端稱為 。32. 向一個(gè)長度為n的向量的第i個(gè)元素(1in+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) 個(gè)元素。33. 向一個(gè)長度為n的向量中刪除第i個(gè)元素(1in)時(shí)，需向前移動(dòng) 個(gè)元素。34. 假設(shè)有二維數(shù)組A6&

10、#215;8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為 ；末尾元素A57的第一個(gè)字節(jié)地址為 ；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為 。35. 設(shè)S=“A;/document/Mary.doc”，則strlen(s)= , “/”的字符定位的位置為 。得分評(píng)卷人四、試題類型：簡(jiǎn)答題（每小題5分，共30分）（類型說明： ）36. 已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為Loc(a11)，請(qǐng)寫出求Loc(aij)的計(jì)算公式

11、。37. 用三元組表表示下列稀疏矩陣： 38. 試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。 39. 把如圖所示的樹轉(zhuǎn)化成二叉樹。40. 已知如圖所示的有向圖，請(qǐng)給出該圖的鄰接表。41. 請(qǐng)對(duì)下圖的無向帶權(quán)圖，求其最小生成樹；得分評(píng)卷人五、試題類型：分析題（每小題5分，共5分）（類型說明： ）42. 已知一組關(guān)鍵字序列： 49 38 65 97 13 27按照快速排序方法對(duì)此序列進(jìn)行排序，寫出每趟排序的結(jié)果。得分評(píng)卷人六、試題類型：編程題（每小題5分，共5分）（類型說明： ）43. 設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有

12、序性。順序表的存儲(chǔ)結(jié)構(gòu)如下：typedef struct ElemType *elem; /指向存放線性表中數(shù)據(jù)元素的基地址 int length; /線性表的當(dāng)前長度 int listsize; /當(dāng)前分配的存儲(chǔ)容量 SqList；Status InsertSqList(SqList &va,int x)/把x插入遞增有序表va中  if(va.length+1>va.listsize) return ERROR; 數(shù)據(jù)結(jié)構(gòu)A卷信管本科專業(yè)標(biāo)準(zhǔn)答案及評(píng)分標(biāo)準(zhǔn)（按試題順序排列）一、單項(xiàng)選擇題（每小題2分，共40分）1、A 2、C 3、C 4、 B 5、A 6、

13、D 7、B 8、C 9、B 10、D 11、A 12、C 13、C 14、A 15、D 16、A 17、A 18、B 19、C 20、C 二、判斷題（每小題1分，共10分）21. A 22. B 23. B 24. A 25. B 26. B 27. B 28. A 29. B 30. B 三、填空題（每空1分，共10分） 31. 棧頂 棧底 32. n-i+1 33. n-i 34. 288 B 1282 1072 1276 35. 20 3四、簡(jiǎn)答題（每小題5分，共30分） 36. Loc(aij)= Loc(a11) + (i-1)*m+(j-1) * K66416-2259435653

14、 37. 38. 先序： A B D F J G K C E H I L M-2分 中序: B F J D G K A C H E L I M-2分 后序： J F K G D B H L M I E C A-1分39. 40. 41. 五、試題類型：分析題（每小題5分，共5分）42. 初始序列：49 38 65 97 13 27第一趟排序結(jié)果：27 38 13 49 97 65第二趟排序結(jié)果：13 27 38 49 65 97六、試題類型：編程題（每小題5分，共5分）43.   va.length+;  for(i=va.length-1;va.elemi>

15、;x&&i>=0;i-)     va.elemi+1=va.elemi;  va.elemi+1=x;  return OK; 數(shù)據(jù)結(jié)構(gòu)試題（100分）（供2005級(jí)信息管理與信息系統(tǒng)本科專業(yè)使用）學(xué)號(hào)： 姓名： 座號(hào)： 系別： 年級(jí)： 專業(yè)： 題號(hào)一二三四五六七八總計(jì)得分 總分合計(jì)人： 復(fù)核人： 說明：本試卷分為兩部分，第I卷（選擇題和判斷題）必須在“答題卡”上按規(guī)定要求填、涂；第II卷直接在試卷上作答。不按規(guī)定答題、填涂，一律無效。第I卷得分評(píng)卷人一、試題類型：?jiǎn)雾?xiàng)選擇題（每小題2分，共

16、40分）（類型說明：在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)選出正確選項(xiàng)并在“答題卡”的相應(yīng)位置上涂黑。多涂、少涂、錯(cuò)誤均無分。）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種 。 ( )(A) 一對(duì)多關(guān)系 (B) 多對(duì)多關(guān)系 (C) 多對(duì)一關(guān)系 (D) 一對(duì)一關(guān)系2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)。 ( )（A） 存儲(chǔ) （B） 物理 （C） 邏輯 （D） 物理和存儲(chǔ) 3. 算法分析的兩個(gè)主要方面是 。 （ ）（A） 空間復(fù)雜性和時(shí)間復(fù)雜性 （B） 正確性和簡(jiǎn)明性（C） 可讀性和文檔性 （D） 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性4. 計(jì)算機(jī)算法指的是 。 ( )（A） 計(jì)算方法

17、 （B） 排序方法 （C） 解決問題的有限運(yùn)算序列 （D） 調(diào)度方法5. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為 。 ( )（A）存儲(chǔ)結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲(chǔ)結(jié)構(gòu) （D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是500，每個(gè)元素的長度為2，則第10個(gè)元素的地址是 。 ( ) （A）510 （B）508 （C）518 （D）5207. 在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是 。 ( )（A）訪問第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） （B）在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）（C）刪除第i個(gè)結(jié)點(diǎn)（1in）（D）

18、將n個(gè)結(jié)點(diǎn)從小到大排序8. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 。( )（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以9. 線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 ( )（）需經(jīng)常修改中的結(jié)點(diǎn)值 （）需不斷對(duì)進(jìn)行刪除插入 （）中含有大量的結(jié)點(diǎn) （）中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜10. 棧中元素的進(jìn)出原則是 。 ( )() 先進(jìn)先出 () 后進(jìn)先出 () ?？談t進(jìn) () 棧滿則出11. 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為 。 ( )（） i （） n=i （） n-i+1 （） 不

19、確定12. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作 。 ( )（） 連接 （） 模式匹配 （） 求子串 （） 求串長13. 串是一種特殊的線性表，其特殊性體現(xiàn)在 。 ( )（） 可以順序存儲(chǔ) （） 數(shù)據(jù)元素是一個(gè)字符 （） 可以鏈?zhǔn)酱鎯?chǔ) （） 數(shù)據(jù)元素可以是多個(gè)字符 14. 假設(shè)有60行70列的二維數(shù)組a160, 170以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a32,58的存儲(chǔ)地址為 。（無第0行第0列元素） ( )（） 16902 () 16904 () 17262 () 答案A, B, C均不對(duì)15. 二叉樹是非線性數(shù)據(jù)結(jié)

20、構(gòu)，所以 。 ( )（）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); （）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);（）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用16. 具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。 ( )() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù 17. 對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較 次關(guān)鍵字。( )(A) 3 (B) 4 (C) 5 (D) 6 18. 鏈表適用于 查找。 ( )(A

21、) 順序 (B) 二分法 (C) 順序，也能二分法 (D) 隨機(jī) 19. 堆的形狀是一棵 。 ( )() 二叉排序樹 () 滿二叉樹 () 完全二叉樹 () 平衡二叉樹 20. 下列關(guān)鍵字序列中， 是堆。 ( )() 16, 72, 31, 23, 94, 53 () 94, 23, 31, 72, 16, 53 () 16, 53, 23, 94，31, 72 () 16, 23, 53, 31, 94, 72 得分評(píng)卷人二、試題類型：判斷題（每小題1分，共10分）（類型說明：判斷正確答案，選項(xiàng)并在“答題卡”的相應(yīng)位置填涂，認(rèn)為正確的涂“A”錯(cuò)誤的涂“B ”。多涂、少涂、錯(cuò)誤均無分。）21.

22、 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 ( )22. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 ( )23. 線性表的邏輯順序與存儲(chǔ)順序總是一致的。 ( )24. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。 ( )25. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。 ( )26. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n1個(gè)非空指針域。 ( )27. 對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i1個(gè)結(jié)點(diǎn)。 ( )28. 用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹

23、，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。 （ ）29. 二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。 （ ）30. 二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （ ）第II卷得分評(píng)卷人三、試題類型：填空題（每小題1分，共20分）（類型說明：請(qǐng)將正確答案填于試題預(yù)留的橫線上。）31. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是數(shù)據(jù)元素的有限集合，R是D上的 有限集合。32. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的 這三個(gè)方面的內(nèi)容。33. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和 。34.

24、 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。35. 在 中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。36. 在 中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。37. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 。38. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序 、 鏈?zhǔn)?、 索引 和 。39. 一個(gè)算法的效率可分為 效率和空間效率。40. 設(shè)要將序列（Q, H,

25、C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母序的升序重新排列，則冒泡排序一趟掃描的結(jié)果是 。41. 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是 。42. 線性有序表（a1，a2，a3，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 次。43. 假設(shè)在有序線性表a20上進(jìn)行折半查找，平均查找長度為 。44. 散列法存儲(chǔ)的基本思想是由 決定數(shù)據(jù)的存儲(chǔ)地址。45. 有8個(gè)結(jié)點(diǎn)的無向連通圖最少有 條邊。46. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。47. 在一個(gè)圖中，所有

26、頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。48. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 個(gè)元素。49. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 。50. 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。得分評(píng)卷人四、試題類型：綜合題（每小題5分，共25分）（類型說明： ）51. 請(qǐng)對(duì)下圖的無向帶權(quán)圖，寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；52. 寫出下圖AOE-網(wǎng)的關(guān)鍵路徑。53. 寫出下圖的拓?fù)渑判蛐蛄小?4. 已知某二叉樹的中序遍歷序列結(jié)點(diǎn)序列是B F J D G K A C H E L I M、后序遍歷結(jié)點(diǎn)序列J F K G D B H L M I E C A是，試寫出其先序遍歷結(jié)點(diǎn)序列并畫出此二叉樹。55. 下圖是某樹的二叉樹表示法，試畫出此樹。 A B E C K F H D L G I M J 得分評(píng)卷人五、試題類型：編程（每小題5分，共5分）（類型說明： ）56. 已知11個(gè)元素的有序表為（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)寫出折半查找的算法程序，查找關(guān)鍵字為key的數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)B卷信管本科專業(yè)標(biāo)準(zhǔn)答案及評(píng)分標(biāo)準(zhǔn)（按試題順序排列）一、單項(xiàng)選擇題（每小題2分，共