數(shù)據(jù)結(jié)構(gòu)自測題及答案

1、-作者xxxx-日期xxxx數(shù)據(jù)結(jié)構(gòu)自測題及答案【精品文檔】第一章概論 自測題答案 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的 操作對象 以及它們之間的 關(guān)系 和運算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運算 這三個方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。5. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。6 在線性結(jié)構(gòu)中，第

2、一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個 。8. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個 。9數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序 、 鏈式 、 索引 和 散列 。10. 數(shù)據(jù)的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個算法的效率可分為 時間 效率和 空間 效率。二、單項選擇題（ B ）

3、1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對一關(guān)系（ C ）2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ C ）3. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進 D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個主要方面是：A) 空間復(fù)雜性和時間復(fù)雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（ C ）5. 計算機算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的

4、有限運算序列 D) 調(diào)度方法（ B ）6. 計算機算法必須具備輸入、輸出和 等5個特性。A) 可行性、可移植性和可擴充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性三、簡答題2.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。3. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。答：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。四、分析下面各程序段的時間復(fù)雜度2. s=0; for i=0; in; i+

5、)for(j=0; jn; j+) s+=Bij;sum=s;答：O（n2）1. for (i=0; in; i+)for (j=0; jm; j+)Aij=0;答：O（m*n）3. x=0;for(i=1; in; i+) for (j=1; j=n-i; j+)x+;解：因為x+共執(zhí)行了n-1+n-2+1= n(n-1)/2，所以執(zhí)行時間為O（n2）4. i=1; while(i=n) i=i*3;答：O（log3n）五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點？ 1. D=d1,d2,d3,d4

6、R=(d1,d2),(d2,d3),(d3,d4) 答： d1d2d3d4 d1無直接前驅(qū)，是首結(jié)點 d4無直接后繼是尾結(jié)點2。D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答： 此圖為樹形結(jié)構(gòu) d1無直接前驅(qū)，是根結(jié)點 d2,d5,d7,d9無直接后繼是葉子結(jié)點3D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)答： 此圖為圖形結(jié)

7、構(gòu) d1，d2無直接前驅(qū)，是開始結(jié)點 d6,d7無直接后繼是終端結(jié)點 (2) (3)第2章 自測卷答案 一、填空1.在順序表中插入或刪除一個元素，需要平均移動 表中一半元素，具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。2. 線性表中結(jié)點的集合是 有限 的，結(jié)點間的關(guān)系是 一對一 的。3. 向一個長度為n的向量的第i個元素(1in+1)之前插入一個元素時，需向后移動 n-i+1 個元素。4. 向一個長度為n的向量中刪除第i個元素(1in)時，需向前移動 n-i 個元素。5. 在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數(shù)據(jù)結(jié)構(gòu)。6.順序表中邏輯

8、上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。7.在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。8 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為O（n）。二、判斷正誤（在正確的說法后面打勾，反之打叉）（ ）1. 鏈表的每個結(jié)點中都恰好包含一個指針。 答：錯誤。鏈表中的結(jié)點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。（ ）2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示意圖有

9、序。（ ）3. 鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。（ ）4. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。（ ）5. 順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。 錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（ ）6. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算效率較低

10、，在表長為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù)的數(shù)據(jù)元素。（ ）7. 線性表在物理存儲空間中也一定是連續(xù)的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續(xù)存放。（ ）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（ ）9. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。（后一節(jié)介紹）（ ）10. 線性表的邏輯順序與存儲順序總

11、是一致的。錯，理由同7。鏈式存儲就無需一致。三、單項選擇題（ C ）1數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲結(jié)構(gòu) （D）鏈式存儲結(jié)構(gòu)（ B ）2.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 （A）110 （B）108 （C）100 （D）120（ A ）3. 在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作是：（A） 訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in） （B） 在第i個結(jié)點后插入一個新結(jié)點（1in）（C） 刪除第i個結(jié)點（1in）（D） 將n個結(jié)點從

12、小到大排序（ B ）4. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 個元素（A）8 （B）63.5 （C）63 （D）7（ A ）5. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：（A） 分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針（B） 只有一部分，存放結(jié)點值（C） 只有一部分，存儲表示結(jié)點間關(guān)系的指針（D） 分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（ B ）6. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表；（A）順序 （B）鏈式 （C）星式 （D）網(wǎng)狀（ D ）7. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址:（A）必須是連續(xù)的

13、（B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以（ B ）8 線性表在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。（）需經(jīng)常修改中的結(jié)點值 （）需不斷對進行刪除插入 （）中含有大量的結(jié)點 （）中結(jié)點結(jié)構(gòu)復(fù)雜（ C ）9 單鏈表的存儲密度（）大于1； （）等于1； （）小于1； （）不能確定（ B ）10 設(shè)a1、a2、a3為3個結(jié)點，整數(shù)P0，3，4代表地址，則如下的鏈式存儲結(jié)構(gòu)稱為P034P0a13a24A30（）循環(huán)鏈表 （）單鏈表 （）雙向循環(huán)鏈表 （）雙向鏈表四、簡答題1.試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？答： 順序存儲時，相鄰數(shù)據(jù)元素

14、的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大（1？），存儲空間利用率高。缺點：插入或刪除元素時不方便。鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度?。╰op0 ST-top=0 ST-topm0 ST-top=m0（ A ）4.判定一個隊列QU（最多元素為m0）為滿隊列的條件是 QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-fr

15、ont = = QU-rear+1解：隊滿條件是元素個數(shù)為m0。由于約定滿隊時隊首指針與隊尾指針相差1，所以不必再減1了，應(yīng)當(dāng)選A。當(dāng)然，更正確的答案應(yīng)該取模，即：QU-front = = (QU-rear+1)% m0（ D ）5數(shù)組用來表示一個循環(huán)隊列，為當(dāng)前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個數(shù)據(jù)元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進棧或進隊

16、操作時，按a1、a2、a3、a4次序每次進入一個元素。假設(shè)?；蜿牭某跏紶顟B(tài)都是空?，F(xiàn)要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是 C ，第二次出隊得到的元素是 D 。經(jīng)操作后，最后在棧中或隊中的元素還有 E 個。供選擇的答案：AD：a1 a2 a3 a4E： 1 2 3 0答：ABCDE2, 4, 1, 2, 27. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄

17、內(nèi)。棧是一種線性表，它的特點是 A 。設(shè)用一維數(shù)組A1,n來表示一個棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值 B ；從棧中彈出（POP）一個元素時，變量T的值 C 。設(shè)?？諘r，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進先出 后進先出 進優(yōu)于出 出優(yōu)于進 隨機進出B，C： 加1 減1 不變 清0 加2 減2D： a,b b,c c,ab,a c,b a,cE： n+1 n+2 n n-1 n-2答案：ABCDE=2,

18、2, 1, 6, 4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8.從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在做進棧運算時，應(yīng)先判別棧是否 A ；在做退棧運算時，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時，才產(chǎn)生上溢。供選擇的答案：A，B：空 滿 上溢 下溢C： n-1 n

19、 n+1 n/2D： 長度 深度 棧頂 棧底E：兩個棧的棧頂同時到達?？臻g的中心點 其中一個棧的棧頂?shù)竭_?？臻g的中心點 兩個棧的棧頂在達?？臻g的某一位置相遇 兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底答案：ABCDE2, 1, 2, 4, 3四、簡答題（每小題4分，共20分）1.說明線性表、棧與隊的異同點。劉答：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端

20、進行刪除運算，因而是先進先出表FIFO。 用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2.設(shè)有編號為1，2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。 全進之后再出情況，只有1種：4，3，2，1 進3個之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,3,1,4 進1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4

21、,33.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和ababab則不是回文。假設(shè)一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j-）從表尾開始打印輸出；堆棧是后進先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實現(xiàn)。（但堆棧是先減后壓還是）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈首開始入棧，全部

22、壓入后再依次輸出。4.順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三： 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空； 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法，即隊頭指針、隊尾指針中有一個指向?qū)嵲兀硪粋€指向空閑元素。判斷循環(huán)隊列隊空標(biāo)志是： f=rear 隊滿標(biāo)志是：f=(r+1)%N5.設(shè)循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出

23、隊運算后，有 front=11，rear=19; front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=32五、閱讀理解（每小題5分，共20分。至少要寫出思路）1. 按照四則運算加、減、乘、除和冪運算（）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程(不要求)：2. 寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。答：輸出為“stack”。3. 寫出下列程序段的輸出結(jié)果（隊列中的元素類型QE

24、lem Type為char）。答：輸出為“char”。4. 簡述以下算法的功能（棧和隊列的元素類型均為int）。答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進行逆置。第45章 串和數(shù)組 自測卷答案 一、填空題（每空1分，共20分）1. 不包含任何字符（長度為0）的串 稱為空串； 由一個或多個空格（僅由空格符）組成的串 稱為空白串。（對應(yīng)嚴題集，簡答題：簡述空串和空格串的區(qū)別）2. 設(shè)S=“”，則strlen(s)= 20 , “/”的字符定位的位置為 3 。4. 子串的定位運算稱為串的模式匹配； 被匹配的主串 稱為目標(biāo)串， 子串 稱為模式。5. 設(shè)目標(biāo)T=”abccdcdccbaa”

25、，模式P=“cdcc”，則第 6 次匹配成功。6. 若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為 (n-m+1)*m 。7. 假設(shè)有二維數(shù)組A68，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節(jié)地址為 1282 ；若按行存儲時，元素A14的第一個字節(jié)地址為 (8+4)6+1000=1072 ；若按列存儲時，元素A47的第一個字節(jié)地址為 (674)61000）1276 。(注：數(shù)組是從0行0列還是從1行1列計算起呢？由末單元為A57可知，是從0

26、行0列開始！)8. 00年計算機系考研題設(shè)數(shù)組a160, 170的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a32,58的存儲地址為 8950 。答：不考慮0行0列，利用列優(yōu)先公式： LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1*289509. 三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。10.求下列廣義表操作的結(jié)果：（1） GetHead【(a,b),(c,d)

27、】= (a, b) ; /頭元素不必加括號（2） GetHead【GetTail【(a,b),(c,d)】= (c,d) ;（3） GetHead【GetTail【GetHead【(a,b),(c,d)】= b ;（4） GetTail【GetHead【GetTail【(a,b),(c,d)】= （d） ;二、單選題（每小題1分，共15分）（ B ）1.串是一種特殊的線性表，其特殊性體現(xiàn)在： 可以順序存儲 數(shù)據(jù)元素是一個字符 可以鏈式存儲 數(shù)據(jù)元素可以是多個字符（ B ）2.設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作： 連接 模式匹配 求子串 求串長（ D ）3.設(shè)串s1=ABCDE

28、FG，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 BCDEFEF（ A ）4. 01年計算機系考研題假設(shè)有60行70列的二維數(shù)組a160, 170以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a32,58的存儲地址為 。（無第0行第0列元素） 16902 16904 14454 答案A,

29、B, C均不對答：此題與填空題第8小題相似。（57列60行31行）2字節(jié)10000=16902( B )5. 設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B 1, n(n-1)/2 中，對下三角部分中任一元素ai,j(ij), 在一維數(shù)組B中下標(biāo)k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。有一個二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址

30、。假設(shè)存儲數(shù)組元素A0,1的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是 A 。若按行存儲，則A3,5和A5,3的第一個字節(jié)的地址分別是 B 和 C 。若按列存儲，則A7,1和A2,4的第一個字節(jié)的地址分別是 D 和 E 。供選擇的答案：AE：28 44 76 92 108 116 132 176 184 188答案：ABCDE=8, 3, 5, 1, 67. 有一個二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是 A 個字節(jié)。假設(shè)存儲數(shù)組元素A1,0的第一個字節(jié)的地址是0，則存儲數(shù)組A的最

31、后一個元素的第一個字節(jié)的地址是 B 。若按行存儲，則A2,4的第一個字節(jié)的地址是 C 。若按列存儲，則A5,7的第一個字節(jié)的地址是 D 。供選擇的答案AD：12 66 72 96 114 120 156 234 276 282 （11）283 （12）288答案：ABCD=12, 10, 3, 9三、簡答題（每小題5分，共15分）1.已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址為Loc(a11)，請寫出求Loc(aij)的計算公式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出，此處雖是方陣，但行列公式仍不相同；按行存儲的元素地址公式是： Loc(a

32、ij)= Loc(a11) + (i-1)*m+(j-1) * K按列存儲的元素地址公式是： Loc(aij)= Loc(a11) + (j-1)*m+(i-1) * K2.遞歸算法比非遞歸算法花費更多的時間，對嗎？為什么？答：不一定。時間復(fù)雜度與樣本個數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費時間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、計算題（每題5分，共20分）1. 設(shè)s=I AM A STUDENT, t=GOOD, q=WORKER, 求Replace(s

33、,STUDENT,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)。解： Replace(s,STUDENT,q)I AM A WORKER 因為 SubString(s,6,2)A ；SubString(s,7,8) STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT所以Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)A GOOD STUDENT2. （P60 4-18）用三元組表表示下列稀疏矩陣： 解：參見填空題4. 三元素組表中的每個結(jié)點對

34、應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。所以（1）可列表為： （2）可列表為：8866416-225943565353233685467858123. （P60 4-19）下列各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。 解：（1）為64矩陣，非零元素有6個。 （2）為45矩陣，非零元素有5個0 2 0 0 12 0 0 0 3 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 1 0 0 0 00 0 0 9 00 8 0 0 60 0 7 0 0第6章 樹和二叉樹 自測卷解答 一、下面是有關(guān)二叉樹的敘述，請判

35、斷正誤（每小題1分，共10分）（ ）1. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n1個非空指針域。（ ）2.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。 （ ）3.二叉樹中每個結(jié)點的兩棵子樹是有序的。 （ ）4.二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。 （ ）5.二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值。 （應(yīng)當(dāng)是二叉排序樹的特點）（ ）6.二叉樹中所有結(jié)點個數(shù)是2k-1-1，其中k是樹的深度。（應(yīng)2i-1） （ ）7.二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。 （

36、 ）8.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i1個結(jié)點。（應(yīng)2i-1）（ ）9.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。（ ）10.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。最快方法：用葉子數(shù)n/26，再求n2=n0-1=5 二、填空（每空1分，共15分）1 由個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。 2. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結(jié)點和 26-1 =32 個葉子。注：滿二叉樹沒有度為1的結(jié)點，所以分支結(jié)點數(shù)就是二度結(jié)點數(shù)。3 一棵具有個結(jié)點的完全二叉

37、樹，它的深度為 9 。（ 注：用 log2(n) +1= 8.xx +1=94. 設(shè)一棵完全二叉樹有700個結(jié)點，則共有 350 個葉子結(jié)點。答：最快方法：用葉子數(shù)n/2350 5. 設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 500 個葉子結(jié)點，有 499 個度為2的結(jié)點，有 1 個結(jié)點只有非空左子樹，有 0 個結(jié)點只有非空右子樹。答：最快方法：用葉子數(shù)n/2500 ，n2=n0-1=499。 另外，最后一結(jié)點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數(shù)0.6.一棵含有n個結(jié)點的k叉樹，可能達到的最大深度為 n

38、 ，最小深度為 2 。答：當(dāng)k=1(單叉樹)時應(yīng)該最深，深度n（層）；當(dāng)k=n-1（n-1叉樹）時應(yīng)該最淺，深度2（層），但不包括n=0或1時的特例情況。教材答案是“完全k叉樹”，未定量。)7. 二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按N L R次序），后序法（即按 L R N 次序）和中序法（也稱對稱序法，即按L N R次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 F E G H D C B 。 解：法1：先由已知條件畫圖，再后序遍歷得到

39、結(jié)果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹。例如，前序遍歷BEFCGDH中，根結(jié)點在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計算。如B在前序序列中第一，中序中在中間（可知左右子樹上有哪些元素），則在后序中必為最后。如法對B的左右子樹同樣處理，則問題得解。8.中序遍歷的遞歸算法平均空間復(fù)雜度為 O(n) 。答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹的深度k+1，包括葉子的空域也遞歸了一次。9. 用5個權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長度是 33 。解：先構(gòu)造哈夫曼樹，得到各

40、葉子的路徑長度之后便可求出WPL（453）2（12）3=33 (15)(9) (6) （注：兩個合并值先后不同會導(dǎo)致編碼不同，即哈夫曼編碼不唯一） 4 5 3 (3) （注：合并值應(yīng)排在葉子值之后）1 2（注：原題為選擇題：32 33 34 15）三、單項選擇題（每小題1分，共11分）（ C ）1 不含任何結(jié)點的空樹 。（）是一棵樹; （）是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹答：以前的標(biāo)答是B，因為那時樹的定義是n1（ C ）2二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。（）它不能用順序存儲結(jié)構(gòu)存儲; （）它不能用鏈式存儲結(jié)構(gòu)存儲; （）順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲

41、; （）順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都不能使用 （ C ）3.具有n(n0)個結(jié)點的完全二叉樹的深度為 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+1注1：x 表示不小于x的最小整數(shù)； x表示不大于x的最大整數(shù)，它們與 含義不同！注2：選（A）是錯誤的。例如當(dāng)n為2的整數(shù)冪時就會少算一層。似乎 log2(n) +1是對的？（ A ）4把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。（）唯一的 （）有多種（）有多種，但根結(jié)點都沒有左孩子 （）有多種，但根結(jié)點都沒有右孩子5.從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。樹是結(jié)點的有限集合，它A 根結(jié)點，記為T。其余的結(jié)點分成為m（m0）個 B 的集合T1，T2，Tm，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1im）。一個結(jié)點的子結(jié)點個數(shù)為該結(jié)點的 C 。供選擇的答案A： 有0個或1個 有0個或多個 有且只有1個 有1個或1個以上 B: 互不相交 允許相交 允許葉結(jié)點相交 允許樹枝結(jié)點相交C： 權(quán) 維數(shù) 次數(shù)（或度） 序答案：ABC1，1，36.從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。二叉樹 A 。在完全的二叉樹中，若一個結(jié)點沒有 B ，則它必定是葉結(jié)點。每棵