《數(shù)據(jù)結(jié)構(gòu)》1至5章期末復(fù)習(xí)題

1、第一章 一、單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。A.數(shù)據(jù)元素的組織形式 B.數(shù)據(jù)類型 C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) D.數(shù)據(jù)定義2. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（ ）。A.存儲(chǔ)結(jié)構(gòu) B.邏輯結(jié)構(gòu) C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D.順序存儲(chǔ)結(jié)構(gòu)3. 樹(shù)形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ ）。A.一對(duì)一關(guān)系B.多對(duì)多關(guān)系 C.多對(duì)一關(guān)系D.一對(duì)多關(guān)系4. 設(shè)語(yǔ)句x+的時(shí)間是單位時(shí)間，則以下語(yǔ)句的時(shí)間復(fù)雜度為（ ）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+;A.O(1)B.O( )C.O(n)D.O( )5. 算法分析的目的是（1），算法分析的兩個(gè)主要方面是（

2、2）。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中的輸入和輸出關(guān)系C.分析算法的效率以求改進(jìn) D.分析算法的易懂性和文檔性（2） A.空間復(fù)雜度和時(shí)間復(fù)雜度 B.正確性和簡(jiǎn)明性 C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6. 計(jì)算機(jī)算法指的是（1），它具備輸入，輸出和（2）等五個(gè)特性。（1） A.計(jì)算方法 B.排序方法 C.解決問(wèn)題的有限運(yùn)算序列 D.調(diào)度方法（2） A.可行性，可移植性和可擴(kuò)充性 B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性 D.易讀性，穩(wěn)定性和安全性7. 數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要（ ）。A.低 B.高 C

3、.相同D.不好說(shuō)8. 數(shù)據(jù)結(jié)構(gòu)作為一門(mén)獨(dú)立的課程出現(xiàn)是在（ ）年。A.1946B.1953C.1964D.19689. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點(diǎn)（ ）。A.正確 B.錯(cuò)誤 C.前半句對(duì)，后半句錯(cuò)D.前半句錯(cuò)，后半句對(duì)10. 計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（ ）。A.數(shù)據(jù) B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.數(shù)據(jù)庫(kù)二、填空題 1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是_和_。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是_、_、_和_。3. 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是_的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是_的。4. 一個(gè)算法的效率可分為_(kāi)效率和_效率。5. 在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)

4、點(diǎn)沒(méi)有_結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的有且只有_個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有_結(jié)點(diǎn)；其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_。6. 在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_。7. 線性結(jié)構(gòu)中元素之間存在_關(guān)系；樹(shù)型結(jié)構(gòu)中元素之間存在_關(guān)系；圖型結(jié)構(gòu)中元素之間存在_關(guān)系。8. 下面程序段的時(shí)間復(fù)雜度是_。for(i=0;iN;I+)for(j=0;jN;J+)Aij=0;9. 下面程序段的時(shí)間復(fù)雜度是_。i=s=0;while(sN) i+; s+=i;10. 下面程序段的時(shí)間復(fù)雜度是_。s=0;for(i=0;iN;I+)for(j=0;jN;J+)s+=Bij;sum=s;11. 下面程序段的時(shí)間復(fù)雜度

5、是_。i=1;while(i=n)i=i*3;12. 衡量算法正確性的標(biāo)準(zhǔn)通常是_。13. 算法時(shí)間復(fù)雜度的分析通常有兩種方法，即_和_的方法，通常我們對(duì)算法求時(shí)間復(fù)雜度時(shí)，采用后一種方法。三、求下列程序段的時(shí)間復(fù)雜度。1. x=0;for(i=1;iN;I+)for(j=i+1;j=n;j+)x+;2. x=0;for(i=1;iN;I+)for(j=1;j=n-i;j+) x+;3. int i,j,k;for(i=0;iN;I+)for(j=0;j=n;j+) cij=0;for(k=0;kN;K+) cij=aik*bkj4. i=n-1;while(i=0)&Ai!=k)j-;ret

6、urn (i);5. fact(n) if(n=1) return (1); else return (n*fact(n-1);第三章 一、單項(xiàng)選擇題1. 空串與空格字符組成的串的區(qū)別在于（ ）。A.沒(méi)有區(qū)別 B.兩串的長(zhǎng)度不相等 C.兩串的長(zhǎng)度相等 D.兩串包含的字符不相同2. 一個(gè)子串在包含它的主串中的位置是指（ ）。A.子串的最后那個(gè)字符在主串中的位置B.子串的最后那個(gè)字符在主串中首次出現(xiàn)的位置C.子串的第一個(gè)字符在主串中的位置 D.子串的第一個(gè)字符在主串中首次出現(xiàn)的位置3. 下面的說(shuō)法中，只有（ ）是正確的。A.字符串的長(zhǎng)度是指串中包含的字母的個(gè)數(shù)B.字符串的長(zhǎng)度是指串中包含的不同字符

7、的個(gè)數(shù)C.若T包含在S中，則T一定是S的一個(gè)子串 D.一個(gè)字符串不能說(shuō)是其自身的一個(gè)子串4. 兩個(gè)字符串相等的條件是（ ）。A.兩串的長(zhǎng)度相等 B.兩串包含的字符相同C.兩串的長(zhǎng)度相等，并且兩串包含的字符相同D.兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中從第i個(gè)字符開(kāi)始的連續(xù)k個(gè)字符組成的子串的操作，則對(duì)于S=“BeijingNanjing”，SUBSTR（S，4，5）=（ ）。A. “ijing” B. “jing” C. “ingNa”D. “ingN”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對(duì)于S=“BeijingNanjing

8、”，T=“jing”，INDEX（S，T）=（ ）。A.2 B.3 C.4 D.57. 若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對(duì)于S=“BeijingNanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。A. “NanjingShanghai” B. “NanjingNanjing”C. “ShanghaiNanjing” D. “ShanghaiNanjing”8. 在長(zhǎng)度為n的字符串S的第i個(gè)位置插入另外一個(gè)字符串，i的合法值應(yīng)該是（ ）。A.i0 B. in C.1in D.1in+

9、19. 字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（ ）。A.鏈表的長(zhǎng)度為1 B.鏈表中只存放1個(gè)字符C.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中不僅只存放了一個(gè)字符D.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只存放了一個(gè)字符二、填空題1. 計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長(zhǎng)度的方法：一種是_，第二種是_。2. 兩個(gè)字符串相等的充要條件是_和_。3. 設(shè)字符串S1= “ABCDEF”，S2= “PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值為_(kāi)。4. 串是指_。5. 空串是指_，空格串是指_。三、算法設(shè)計(jì)題1. 設(shè)有一個(gè)長(zhǎng)度為s的字符串，其字符順序

10、存放在一個(gè)一維數(shù)組的第1至第s個(gè)單元中（每個(gè)單元存放一個(gè)字符）?，F(xiàn)要求從此串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串，mS，tlc=NULL B. p-ltag=1 C. p-ltag=1 且p-lc=NULL D. 以上都不對(duì)9. 設(shè)n , m 為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（ ）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孫10. 如果F是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的（ ）。A. 中序B. 前序C. 后序D. 層次序11. 欲實(shí)現(xiàn)任意二叉樹(shù)的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹(shù)采用（ ）存

11、儲(chǔ)結(jié)構(gòu)。 A. 三叉鏈表B. 廣義表C. 二叉鏈表 D. 順序12. 下面敘述正確的是（ ）。A. 二叉樹(shù)是特殊的樹(shù)B. 二叉樹(shù)等價(jià)于度為2的樹(shù)C. 完全二叉樹(shù)必為滿二叉樹(shù)D. 二叉樹(shù)的左右子樹(shù)有次序之分13. 任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對(duì)14. 已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（ ）。A. 1 B. 2C. 3D. 415. 根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹(shù)，該二叉樹(shù)（ ）。A. 是完全二叉樹(shù) B. 不是完全二叉樹(shù) C. 是滿二叉樹(shù)D. 不

12、是滿二叉樹(shù)二、判斷題1. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度不能超過(guò)2，所以二叉樹(shù)是一種特殊的樹(shù)。（）2. 二叉樹(shù)的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。（）3. 線索二叉樹(shù)是一種邏輯結(jié)構(gòu)。（）4. 哈夫曼樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。（）5. 由二叉樹(shù)的先序序列和后序序列可以唯一確定一顆二叉樹(shù)。（）6. 樹(shù)的后序遍歷與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同。（）7. 根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹(shù)。 （）8. 滿二叉樹(shù)也是完全二叉樹(shù)。 （）9. 哈夫曼樹(shù)一定是完全二叉樹(shù)。（）10. 樹(shù)的子樹(shù)是無(wú)序的。 （）三、填空題1. 假定一棵樹(shù)的廣義表表示為A（B（E），C（F（H，I，J），G）

13、，D），則該樹(shù)的度為_(kāi)，樹(shù)的深度為_(kāi)，終端結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，單分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，雙分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，三分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_(kāi)，其孩子結(jié)點(diǎn)為_(kāi)和_結(jié)點(diǎn)。2. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_個(gè)。3. 對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵_二叉樹(shù)時(shí)具有最小高度，即為_(kāi)，當(dāng)它為一棵單支樹(shù)具有_高度，即為_(kāi)。4. 由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，則帶權(quán)路徑長(zhǎng)度為_(kāi)。5. 在一棵二叉排序樹(shù)上按_遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。6. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指

14、針域的總數(shù)為_(kāi)個(gè)，其中_個(gè)用于鏈接孩子結(jié)點(diǎn)，_個(gè)空閑著。7. 在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=_。8. 一棵深度為k的滿二叉樹(shù)的結(jié)點(diǎn)總數(shù)為_(kāi)，一棵深度為k的完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)的最小值為_(kāi)，最大值為_(kāi)。9. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有_種不同的形態(tài)。10. 設(shè)高度為h的二叉樹(shù)中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為_(kāi)。11. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，_形態(tài)達(dá)到最大深度，_形態(tài)達(dá)到最小深度。12. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若一個(gè)結(jié)點(diǎn)的編號(hào)為i(1in)，則它的左孩子結(jié)點(diǎn)的編號(hào)為_(kāi)，右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)，雙親結(jié)點(diǎn)的編號(hào)為_(kāi)。1

15、3. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為_(kāi)個(gè)，其中_個(gè)用于鏈接孩子結(jié)點(diǎn)，_個(gè)空閑著。14. 哈夫曼樹(shù)是指_的二叉樹(shù)。15. 空樹(shù)是指_，最小的樹(shù)是指_。16. 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有_和_兩種。17. 三叉鏈表比二叉鏈表多一個(gè)指向_的指針域。18. 線索是指_。19. 線索鏈表中的rtag域值為_(kāi)時(shí)，表示該結(jié)點(diǎn)無(wú)右孩子，此時(shí)_域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。20. 本節(jié)中我們學(xué)習(xí)的樹(shù)的存儲(chǔ)結(jié)構(gòu)有_、_和_。四、應(yīng)用題1. 已知一棵樹(shù)邊的集合為I，m，I，n，E，i，B，e，B，d，A，b，G，j，G，k，C，g，C，f，H，l，C，h，A，c，請(qǐng)畫(huà)出這棵樹(shù)，并

16、回答下列問(wèn)題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)g的雙親？（4）哪些是結(jié)點(diǎn)g的祖先？（5）哪些是結(jié)點(diǎn)g的孩子？（6）哪些是結(jié)點(diǎn)e的孩子？（7）哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？（8）結(jié)點(diǎn)b和n的層次號(hào)分別是什么？（9）樹(shù)的深度是多少？（10）以結(jié)點(diǎn)c為根的子樹(shù)深度是多少？2. 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別。3. 試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和二叉樹(shù)的所有不同形態(tài)？4. 已知用一維數(shù)組存放的一棵完全二叉樹(shù)：ABCDEFGHIJKL，寫(xiě)出該二叉樹(shù)的先序、中序和后序遍歷序列。5. 一棵深度為H的滿k叉樹(shù)有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k

17、棵非空子樹(shù)，如果按層次自上至下，從左到右順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào)，回答下列問(wèn)題：（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是多少？（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是多少？（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？6. 找出所有滿足下列條件的二叉樹(shù)：（1）它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（2）它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（3）它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的遍歷序列相同；7. 假設(shè)一棵二叉樹(shù)的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)寫(xiě)出該二叉樹(shù)的后序遍歷序列。8. 假設(shè)一棵二叉樹(shù)的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請(qǐng)寫(xiě)出該二叉樹(shù)的后序遍歷序列。9. 給出如圖5-14所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫(huà)出該森林對(duì)應(yīng)的二叉樹(shù)。10給定一組權(quán)值（5，9，11，2，7，16），