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

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

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

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

4、（）可以順序存儲 （）數(shù)據(jù)元素是一個字符 （）可以鏈?zhǔn)酱鎯?（）數(shù)據(jù)元素可以是多個字符10. 設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號i開始的j個字符組成的子串，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以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第

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

6、9;14把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。 （ ）（）唯一的 （）有多種（）有多種，但根結(jié)點都沒有左孩子 （）有多種，但根結(jié)點都沒有右孩子15. 已知圖的鄰接表如下所示，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)點序列是（ ）（A） 0 1 3 2 （B） 2 0 3 1 （C） 1 3 2 0 （D） 0 1 2 316. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是（ ）（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鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表。 （ ）（A）順序 （B）鏈?zhǔn)?（C）星式 （D）網(wǎng)狀19不含任何結(jié)點的空樹 。 （ ）（）不是一棵樹; （）不是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹20在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的 倍。 （ ） A1/2 B. 1 C. 2 D. 4 得分評卷人二、試題類型：判斷題（每小題1分，共10分）（類型說明：判斷正確答案，選項并在“答題卡”的相應(yīng)位置填涂，認為正

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

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

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

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

12、序性。順序表的存儲結(jié)構(gòu)如下：typedef struct ElemType *elem; /指向存放線性表中數(shù)據(jù)元素的基地址 int length; /線性表的當(dāng)前長度 int listsize; /當(dāng)前分配的存儲容量 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)答案及評分標(biāo)準(zhǔn)（按試題順序排列）一、單項選擇題（每小題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四、簡答題（每小題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級信息管理與信息系統(tǒng)本科專業(yè)使用）學(xué)號： 姓名： 座號： 系別： 年級： 專業(yè)： 題號一二三四五六七八總計得分 總分合計人： 復(fù)核人： 說明：本試卷分為兩部分，第I卷（選擇題和判斷題）必須在“答題卡”上按規(guī)定要求填、涂；第II卷直接在試卷上作答。不按規(guī)定答題、填涂，一律無效。第I卷得分評卷人一、試題類型：單項選擇題（每小題2分，共

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

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

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

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

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

21、) 順序 (B) 二分法 (C) 順序，也能二分法 (D) 隨機 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 得分評卷人二、試題類型：判斷題（每小題1分，共10分）（類型說明：判斷正確答案，選項并在“答題卡”的相應(yīng)位置填涂，認為正確的涂“A”錯誤的涂“B ”。多涂、少涂、錯誤均無分。）21.

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

23、，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。 （ ）29. 二叉樹中每個結(jié)點的兩棵子樹是有序的。 （ ）30. 二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值。 （ ）第II卷得分評卷人三、試題類型：填空題（每小題1分，共20分）（類型說明：請將正確答案填于試題預(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ù)的存儲結(jié)構(gòu)和數(shù)據(jù)的 這三個方面的內(nèi)容。33. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和 。34.

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

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

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