大數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課后習(xí)題及問題詳解

1、實(shí)用標(biāo)準(zhǔn)文案第一章1. 數(shù)據(jù)結(jié)構(gòu)研究的主要容包括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法。2. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小標(biāo)示單位。3. 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為集合、樹形、線性、圖狀。4. 常見的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有四種類型：順序、鏈?zhǔn)?、索引、散列?. 可以從正確性、可讀性、健壯性、高效性四方面評(píng)價(jià)算法的質(zhì)量。6. 在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是問題規(guī)模的函數(shù)。7. 常見時(shí)間復(fù)雜度有：常數(shù)階 O（1）、線性階 O（n）、對數(shù)階 O（log2 n）、平方階 O（ n2）和指 數(shù)階 O（2? ）。通常認(rèn)為， 具有常數(shù)階量級(jí)的算法是好算法， 而具有指數(shù)階量級(jí)的算法是差

2、算法。8. 時(shí)間復(fù)雜度排序由大到?。?n+2）！2?2（n+2）4 次方nlog2 n100000.問答題：1. 什么叫數(shù)據(jù)元素？ 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個(gè)集合的個(gè)體，也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。2. 什么叫數(shù)據(jù)邏輯結(jié)構(gòu)？什么叫數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)？文檔大全實(shí)用標(biāo)準(zhǔn)文案數(shù)據(jù)邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間存在的固有的邏輯結(jié)構(gòu)。 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)的表示。3. 什么叫抽象數(shù)據(jù)類型？ 抽象數(shù)據(jù)類型是指數(shù)據(jù)元素集合以及定義在該集合上的一組操作。4. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？ 順序、鏈?zhǔn)?、索引、散列?. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)之間存在著怎樣的關(guān)系？ 相輔

3、相成，不可分割。6. 什么叫算法？算法的性質(zhì)有哪些？ 算法：求解問題的一系列步驟的集合。 可行性、有容性、確定性、有輸入、有輸出。7. 評(píng)價(jià)一個(gè)算法的好壞應(yīng)該從哪幾方面入手？ 正確性、可讀性、健壯性、高效性。第二章文檔大全實(shí)用標(biāo)準(zhǔn)文案1. 線性表中，第一個(gè)元素沒有直接前驅(qū)，最后一個(gè)元素沒有直接后繼。2. 線性表常用的兩種存儲(chǔ)結(jié)構(gòu)分別是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3. 在長度為 n 的順序表中，插入一個(gè)新元素平均需要移動(dòng)表中的n/2 個(gè)元素，刪除一個(gè)元素平均需要移動(dòng)（ n-1 ）/2 個(gè)元素。4. 在長度為 n 的順序表的表頭插入一個(gè)新元素的時(shí)間復(fù)雜度為O（n），在表尾插入一個(gè)新元素的時(shí)間復(fù)雜度

4、為 O（ 1）。5. 已知順序表中每個(gè)元素占用 3 個(gè)存儲(chǔ)單位，第 13 個(gè)元素的存儲(chǔ)結(jié)構(gòu)為 336，則順序表的首地 址為 300.6. 線性表的順序存儲(chǔ)結(jié)構(gòu)通過物理相鄰位置來反映數(shù)據(jù)元素之間的邏輯關(guān)系。7. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系。8. 在長度為 n 的順序表中，若刪除 i 位置處的元素，則 i 的可能取值圍為 1i n9. 已知一指針 p指向非空不帶頭單鏈表的某一個(gè)結(jié)點(diǎn)，若 p 滿足條件“ p-next ！=NULL”，則 p 指向單鏈表的不是最后一個(gè)結(jié)點(diǎn)。10. 雙向鏈表的每個(gè)結(jié)點(diǎn)均包含 2 個(gè)指針域，一個(gè)是指向前驅(qū)，一個(gè)是指向后繼。文檔大全實(shí)用標(biāo)準(zhǔn)文案

5、11. 若 p 指針指向不帶頭雙向循環(huán)鏈表的某個(gè)結(jié)點(diǎn)，則判斷該鏈表只有一個(gè)結(jié)點(diǎn)的條件是p-prior=p-next 。12. 若對線性表進(jìn)行的主要操作是查詢操作，則該線性表應(yīng)該采用順序存儲(chǔ)結(jié)構(gòu)；若需要頻繁進(jìn) 行插入和刪除操作，則該線性表應(yīng)該采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。13. 線性表所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的表長。表長為0 的線性表稱為空表。14. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)主要有單鏈表、循環(huán)鏈表、雙鏈表。15. 在靜態(tài)鏈表中，結(jié)點(diǎn)之間的邏輯關(guān)系通過游標(biāo)來表示。第三章1. 能夠?qū)崿F(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)是堆棧。2. 允許在一端插入， 在另一端刪除的線性表稱為隊(duì)列。 插入的一端為隊(duì)尾， 刪除的一端為隊(duì)頭。3.

6、 在一個(gè)循環(huán)隊(duì)列 Q中，判斷隊(duì)空的條件為 Q.front = Q.rear ，判斷隊(duì)滿的條件為 (Q.rear+1 ) %QUEUESIZE=Q.front。4. 判別循環(huán)隊(duì)列隊(duì)空和隊(duì)滿的放法有： 設(shè)置一個(gè)標(biāo)志位， 設(shè)置一個(gè)計(jì)數(shù)器和少用一個(gè)儲(chǔ)存空間。5. 已知用求數(shù)組 sq50 存放循環(huán)隊(duì)列的元素，且頭指針和尾指針分別為19 和 2，則該隊(duì)列的當(dāng)文檔大全實(shí)用標(biāo)準(zhǔn)文案前長度為 33。6. 若用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈隊(duì)列，且鏈隊(duì)頭指針為 front ，則隊(duì)列為空的條件為是 front-next=NULL 。7. 已知鏈隊(duì)列 Q的頭、尾指針分別是 front 和 rear ，則出隊(duì)操作是 p =

7、 Q-front ； Q-front=Q-front-next ； free(p) 。8. 棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。9. 對于棧和隊(duì)列，無論它們采用的是順序儲(chǔ)存結(jié)構(gòu)還是鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)，進(jìn)行插入和刪除操作的 時(shí)間復(fù)雜度都是 O(1) 。10. 表達(dá)式 d/(b c) + a 的后綴表達(dá)式為 dbc /a+ 。第六章1. 除根結(jié)點(diǎn)以外，樹中每個(gè)結(jié)點(diǎn)有 1 個(gè)前驅(qū)， 0 個(gè)或多個(gè)后繼。2. 如圖 6-40 所示的樹有 3 個(gè)葉結(jié)點(diǎn)，有 3 個(gè)分支結(jié)點(diǎn)，度為 3，A的結(jié)點(diǎn)的兄弟是 B和 C。3. 樹的儲(chǔ)存結(jié)構(gòu)主要有雙親儲(chǔ)存結(jié)構(gòu)、孩子儲(chǔ)存結(jié)構(gòu)和孩子兄弟儲(chǔ)存結(jié)構(gòu)。4. 若用一棵完全二叉樹的

8、結(jié)點(diǎn)個(gè)數(shù)為 10，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)為5。文檔大全實(shí)用標(biāo)準(zhǔn)文案5. 已知采用二叉樹鏈表作為儲(chǔ)存結(jié)構(gòu)的一棵二叉樹共有 10個(gè)結(jié)點(diǎn)，則二叉樹鏈表中共有 20 個(gè) 指針域。6. 一棵具有 10 個(gè)結(jié)點(diǎn)的二叉樹共有 5 和葉結(jié)點(diǎn)，則該二叉樹有 4個(gè)度為 2 的結(jié)點(diǎn)。 1 個(gè)度為 1 的結(jié)點(diǎn)。7. 一棵具有 31 個(gè)結(jié)點(diǎn)的滿二叉樹。它的高度是 5，共有 16 個(gè)葉結(jié)點(diǎn)。8. 若二叉樹的中序遍歷序列和后序遍歷序列相同，則該二叉樹一定滿足任何子結(jié)點(diǎn)都沒有右子 樹。9. 一棵二叉樹的中序遍歷序列為 CAEFDR，B 則它的前序遍歷序列為 RACEB。D10. 根據(jù)遍歷方法不同， 線索二叉樹分為前序線索

9、二叉樹， 后序線索二叉樹， 中序線索二叉樹。11. 樹的后根遍歷序列與其對應(yīng)二叉樹的中序遍歷序列相同。12. 若二叉樹的右子樹為空，則與其對應(yīng)的森林有1 課樹。13. 在哈夫曼樹中，權(quán)值較大的葉結(jié)點(diǎn)一定離根結(jié)點(diǎn)較近。14. 哈夫曼樹不存在度為 1 的結(jié)點(diǎn)。文檔大全實(shí)用標(biāo)準(zhǔn)文案第七章1. 有向圖的極通子圖稱為強(qiáng)連通分量。2. 一個(gè)具有 n 個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為 1/2n(n-1); 一個(gè)具有 n 個(gè)頂點(diǎn)的完全有向圖的弧 數(shù)為 n(n-1)3. 在有向圖中，頂點(diǎn)的度等于頂點(diǎn)的入度與出度之和。4. 一個(gè)有 16 個(gè)頂點(diǎn)的無向圖，至少應(yīng)該有 15 條邊才能確保它是連通圖。5. 一個(gè)有 10 個(gè)頂

10、點(diǎn)的有向圖，它最多能有 90 條邊。6. 在有 10 個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度的最大值可以達(dá)到 18.7. 迪杰斯特拉算法是按路徑長度遞增的次序產(chǎn)生最短路徑的算法。8. 圖的存儲(chǔ)結(jié)構(gòu)主要有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表四種。9. 圖的遍歷方法主要有深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種。10構(gòu)造圖的最小生成樹的方法主要有普里姆算法和克魯斯卡爾算法兩種。11. 用圖中的頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的先后關(guān)系，這樣的有向圖稱為AOV網(wǎng)。12. 時(shí)間 Vk的最早發(fā)生時(shí)間是從源點(diǎn)到頂點(diǎn) Vk 的最大路徑長度。文檔大全實(shí)用標(biāo)準(zhǔn)文案13. 在 AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)之間具有最大路徑長度的路

11、徑稱為關(guān)鍵路徑。14. 一個(gè)有 n 個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，則求圖中邊數(shù)的方法是矩陣中1 的個(gè)數(shù)除以 2。求任一頂點(diǎn)的度的方法是計(jì)算該行中1 的個(gè)數(shù)。15. Prim 算法適用于求稠密圖的最小生成樹， Kruskal 算法適用于求稀疏圖的最小生成樹。第八章1. 動(dòng)態(tài)查找表和靜態(tài)查找表的主要區(qū)別在于：動(dòng)態(tài)查找表有插入和刪除操作2. 順序查找在查找成功情況下的平均查找長度為（n+1） / 2 ；在查找失敗情況下的平均查找長度為 n+1.3. 折半查找只能使用順序存儲(chǔ)結(jié)構(gòu)。4. 已知一個(gè)有序表為 10,23,35,46,48,55,59,64,72,83,88,99 ，當(dāng)用折半查找

12、方法查找值為 46 和 83 的元素時(shí)，分別需要比較 3 次和 4 次才能查找成功；若采用順序查找是，分別需要比較 4 次和 10 次才能查找成功。5. 索引順序表上的查找分兩個(gè)階段，它們是確定待查元素所在的塊和在塊查找待查的元素。文檔大全實(shí)用標(biāo)準(zhǔn)文案6. 在一棵 m階 B樹種， 若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 m-1；若在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并，則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 （m/2）-1 。7. 二叉排序樹查找成功是的平均查找長度一般為log 2n。8. 哈希函數(shù)的構(gòu)造方法主要有直接定址法、除留余數(shù)法、數(shù)字分析法、平方取中法和折

13、疊移位 法。9. 在哈希函數(shù) h（ key ） =key%m中， m值最好取小于等于表長的素?cái)?shù)。10. 常用的處理沖突的方法有：開放定址法和鏈地址法。問答題1. 順序查找時(shí)間為 O（n），折半查找時(shí)間為 O（ log2n ）, 哈希法為 O（ 1），為什么有高效率的查 找方法而低效率的方法不被放棄？ 不同的查找方法使用的圍不同，高效率的查找方法并不是在所有情況下都比其他查找方法效率 要高，而且也不是在所有情況下都可以采用。2. 為什么有序的單鏈表不能進(jìn)行折半查找？文檔大全實(shí)用標(biāo)準(zhǔn)文案因?yàn)殒湵頍o法進(jìn)行隨機(jī)訪問，若要訪問鏈表中的結(jié)點(diǎn)，必須從頭指針開始依次遍歷鏈表，從而 浪費(fèi)大量時(shí)間。另外，也不好設(shè)

14、定查找結(jié)束的條件。3. 在查找算法中，監(jiān)視哨的作用是什么？ 監(jiān)視哨的作用是免去查找過程中每次都要檢測整個(gè)表是否查找完畢，提高了查找效率。第九章1. 根據(jù)在排序過程中使用的存儲(chǔ)器將排序方法分為部排序和外部排序。2. 常用的插入排序有直接排序、折半排序和希爾排序。3. 對于直接插入排序和直接選擇排序，若待排序序列基本有序，則選用直接插入排序較好；若 待排序序列為逆序，則選用直接選擇排序較好。4. 直接插入排序在最好情況下的時(shí)間復(fù)雜度為O（n），在最壞的情況下的時(shí)間復(fù)雜度為 O（ n2）。5. 若堆中某一數(shù)據(jù)元素在數(shù)組中的下標(biāo)為30，則它的左孩子的下標(biāo)為 61，右孩子的下標(biāo)為 626. 對于堆排序和

15、快速排序，若帶排序列基本有序，則選用堆排序較好；若待排序序列無序，則 選用快速排序較好。文檔大全實(shí)用標(biāo)準(zhǔn)文案7. 常用的選擇排序方法有直接選擇排序和堆排序。8. 設(shè)有字母序列 P,D,F,Z,E,P,N,B,X,M,G,W ，請寫出按二路歸并排序方法對該序列進(jìn)行一趟 掃描后的結(jié)果是 D P F Z E P B N M X G W 。9. 若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的比較和數(shù)據(jù)元素 的移動(dòng)。10. 基數(shù)排序所用隊(duì)列可以是順序隊(duì)列，也可以是鏈隊(duì)列。 問答題1. 已知關(guān)鍵字序列 15,20,80,50,10,40 ，請給出冒泡排序的每一趟結(jié)果。 答：第一趟： 1

16、5 20 50 10 40 80第二趟： 15 20 10 40 50 80第三趟： 15 10 20 40 50 80第四趟： 10 15 20 40 50 802. 已知關(guān)鍵字序列 52,43,78,99,85,30,40 ，請給出快速排序的第一趟和第二趟的結(jié)果。 答：第一趟： 40 43 30 52 85 99 78文檔大全實(shí)用標(biāo)準(zhǔn)文案第二趟：30 40 43 52 78 85 993. 已知關(guān)鍵字序列 50,80,75,30,20,90,45,65,5,9 ，增量序列為 5,3,1 。請給出希爾排序的每 一趟結(jié)果。答：第一趟：50 45 65 5 9 90 80 75 30 20第二趟

17、：5 9 30 20 45 65 50 75 90 80第三趟：5 9 20 30 45 50 65 75 80 904. 已知關(guān)鍵字序列 500,10,200,800,150,250,70,30,300 ，請給出構(gòu)建大根堆的過程。5. 已知關(guān)鍵字序列 50,3,80,10,20,60,40,90,1 ，請給出二路歸并排序的每一趟結(jié)果。答：第一趟：3 50 10 80 20 60 40 90 1第二趟：3 10 50 80 20 40 60 90 1第三趟：3 10 20 40 50 60 80 90 1第四趟：1 3 10 20 40 50 60 80 906. 已知關(guān)鍵字序列 501,41

18、7,225,418,391,565,359 ，請給出基數(shù)排序的每一趟結(jié)果。答：第一趟：501 391 225 565 417 418 359文檔大全實(shí)用標(biāo)準(zhǔn)文案第二趟： 501 417 418 225 359 565 391第三趟： 225 359 391 417 418 501 5657. 設(shè)有 10000 個(gè)無序的數(shù)據(jù)元素，可供選擇的排序方法有：歸并排序、基數(shù)排序、堆排序、希 爾排序和快速排序。 現(xiàn)在希望用最快速度挑選出前 10 個(gè)最大的數(shù)據(jù)元素， 問采用什么方法最好？ 為什么？ 答：這幾種方法速度都很快，但歸并排序、基數(shù)排序、希爾排序和快速排序都是在排序結(jié)束后 才能確定數(shù)據(jù)元素的順序，

19、無法提前知道數(shù)據(jù)元素的有序性。 只有堆排序， 每次均輸出最大 （或 最?。┑臄?shù)據(jù)元素，因此采用它比較合適。第一章1. 數(shù)據(jù)結(jié)構(gòu)研究的主要容包括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法。2. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小標(biāo)示單位。3. 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為集合、樹形、線性、圖狀。4. 常見的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有四種類型：順序、鏈?zhǔn)?、索引、散列?. 可以從正確性、可讀性、健壯性、高效性四方面評(píng)價(jià)算法的質(zhì)量。文檔大全實(shí)用標(biāo)準(zhǔn)文案6. 在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是問題規(guī)模的函數(shù)。7. 常見時(shí)間復(fù)雜度有：常數(shù)階 O（1）、線性階 O（n）、對數(shù)階 O（log2 n）、平

20、方階 O（ n2）和指 數(shù)階 O（2? ）。通常認(rèn)為， 具有常數(shù)階量級(jí)的算法是好算法， 而具有指數(shù)階量級(jí)的算法是差算法。8. 時(shí)間復(fù)雜度排序由大到?。?n+2）！2?2（n+2）4 次方nlog2 n100000. 問答題：1. 什么叫數(shù)據(jù)元素？ 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個(gè)集合的個(gè)體，也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。2. 什么叫數(shù)據(jù)邏輯結(jié)構(gòu)？什么叫數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)？ 數(shù)據(jù)邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間存在的固有的邏輯結(jié)構(gòu)。 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)的表示。3. 什么叫抽象數(shù)據(jù)類型？ 抽象數(shù)據(jù)類型是指數(shù)據(jù)元素集合以及定義在該集合上的一組操作。4. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表

21、示方法？ 順序、鏈?zhǔn)?、索引、散列。文檔大全實(shí)用標(biāo)準(zhǔn)文案5. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)之間存在著怎樣的關(guān)系？ 相輔相成，不可分割。6. 什么叫算法？算法的性質(zhì)有哪些？ 算法：求解問題的一系列步驟的集合。 可行性、有容性、確定性、有輸入、有輸出。7. 評(píng)價(jià)一個(gè)算法的好壞應(yīng)該從哪幾方面入手？ 正確性、可讀性、健壯性、高效性。第二章1. 線性表中，第一個(gè)元素沒有直接前驅(qū)，最后一個(gè)元素沒有直接后繼。2. 線性表常用的兩種存儲(chǔ)結(jié)構(gòu)分別是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3. 在長度為 n 的順序表中，插入一個(gè)新元素平均需要移動(dòng)表中的 n/2 個(gè)元素，刪除一個(gè)元素平 均需要移動(dòng)（ n-1 ）/2 個(gè)元素。4

22、. 在長度為 n 的順序表的表頭插入一個(gè)新元素的時(shí)間復(fù)雜度為O（n），在表尾插入一個(gè)新元素的時(shí)間復(fù)雜度為 O（ 1）。文檔大全實(shí)用標(biāo)準(zhǔn)文案5. 已知順序表中每個(gè)元素占用 3 個(gè)存儲(chǔ)單位，第 13 個(gè)元素的存儲(chǔ)結(jié)構(gòu)為 336，則順序表的首地 址為 300.6. 線性表的順序存儲(chǔ)結(jié)構(gòu)通過物理相鄰位置來反映數(shù)據(jù)元素之間的邏輯關(guān)系。7. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系。8. 在長度為 n 的順序表中，若刪除 i 位置處的元素，則 i 的可能取值圍為 1i n9. 已知一指針 p 指向非空不帶頭單鏈表的某一個(gè)結(jié)點(diǎn)，若 p 滿足條件“ p-next ！=NULL”，則 p 指向單

23、鏈表的不是最后一個(gè)結(jié)點(diǎn)。10. 雙向鏈表的每個(gè)結(jié)點(diǎn)均包含 2 個(gè)指針域，一個(gè)是指向前驅(qū)，一個(gè)是指向后繼。11. 若 p 指針指向不帶頭雙向循環(huán)鏈表的某個(gè)結(jié)點(diǎn)，則判斷該鏈表只有一個(gè)結(jié)點(diǎn)的條件是 p-prior=p-next 。12. 若對線性表進(jìn)行的主要操作是查詢操作，則該線性表應(yīng)該采用順序存儲(chǔ)結(jié)構(gòu)；若需要頻繁進(jìn) 行插入和刪除操作，則該線性表應(yīng)該采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。13. 線性表所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的表長。表長為0 的線性表稱為空表。14. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)主要有單鏈表、循環(huán)鏈表、雙鏈表。文檔大全實(shí)用標(biāo)準(zhǔn)文案15. 在靜態(tài)鏈表中，結(jié)點(diǎn)之間的邏輯關(guān)系通過游標(biāo)來表示。 第三章1. 能夠?qū)崿F(xiàn)遞歸

24、函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)是堆棧。2. 允許在一端插入， 在另一端刪除的線性表稱為隊(duì)列。 插入的一端為隊(duì)尾， 刪除的一端為隊(duì)頭。3. 在一個(gè)循環(huán)隊(duì)列 Q中，判斷隊(duì)空的條件為 Q.front = Q.rear ，判斷隊(duì)滿的條件為 (Q.rear+1 ) %QUEUESIZE=Q.front。4. 判別循環(huán)隊(duì)列隊(duì)空和隊(duì)滿的放法有： 設(shè)置一個(gè)標(biāo)志位， 設(shè)置一個(gè)計(jì)數(shù)器和少用一個(gè)儲(chǔ)存空間。5. 已知用求數(shù)組 sq50 存放循環(huán)隊(duì)列的元素，且頭指針和尾指針分別為19和 2，則該隊(duì)列的當(dāng)前長度為 33。6. 若用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈隊(duì)列，且鏈隊(duì)頭指針為 front ，則隊(duì)列為空的條件為是 front-ne

25、xt=NULL 。7. 已知鏈隊(duì)列 Q的頭、尾指針分別是 front 和 rear ，則出隊(duì)操作是 p = Q-front ； Q-front=Q-front-next ； free(p) 。8. 棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。文檔大全實(shí)用標(biāo)準(zhǔn)文案9. 對于棧和隊(duì)列，無論它們采用的是順序儲(chǔ)存結(jié)構(gòu)還是鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)，進(jìn)行插入和刪除操作的 時(shí)間復(fù)雜度都是 O(1) 。10. 表達(dá)式 d/(b c) + a 的后綴表達(dá)式為 dbc /a+ 。 第六章1. 除根結(jié)點(diǎn)以外，樹中每個(gè)結(jié)點(diǎn)有 1 個(gè)前驅(qū)， 0 個(gè)或多個(gè)后繼。2. 如圖 6-40 所示的樹有 3個(gè)葉結(jié)點(diǎn)，有 3 個(gè)分支結(jié)點(diǎn)，度為 3

26、，A的結(jié)點(diǎn)的兄弟是 B和 C。3. 樹的儲(chǔ)存結(jié)構(gòu)主要有雙親儲(chǔ)存結(jié)構(gòu)、孩子儲(chǔ)存結(jié)構(gòu)和孩子兄弟儲(chǔ)存結(jié)構(gòu)。4. 若用一棵完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為10，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)為 5。5. 已知采用二叉樹鏈表作為儲(chǔ)存結(jié)構(gòu)的一棵二叉樹共有 10個(gè)結(jié)點(diǎn)，則二叉樹鏈表中共有 20 個(gè) 指針域。6. 一棵具有 10 個(gè)結(jié)點(diǎn)的二叉樹共有 5 和葉結(jié)點(diǎn)，則該二叉樹有 4個(gè)度為 2 的結(jié)點(diǎn)。 1 個(gè)度為 1 的結(jié)點(diǎn)。7. 一棵具有 31 個(gè)結(jié)點(diǎn)的滿二叉樹。它的高度是 5，共有 16 個(gè)葉結(jié)點(diǎn)。8. 若二叉樹的中序遍歷序列和后序遍歷序列相同，則該二叉樹一定滿足任何子結(jié)點(diǎn)都沒有右子文檔大全實(shí)用標(biāo)準(zhǔn)文案樹。9. 一棵二叉

27、樹的中序遍歷序列為 CAEFDR，B 則它的前序遍歷序列為 RACEB。D10. 根據(jù)遍歷方法不同， 線索二叉樹分為前序線索二叉樹， 后序線索二叉樹， 中序線索二叉樹。11. 樹的后根遍歷序列與其對應(yīng)二叉樹的中序遍歷序列相同。12. 若二叉樹的右子樹為空，則與其對應(yīng)的森林有1 課樹。13. 在哈夫曼樹中，權(quán)值較大的葉結(jié)點(diǎn)一定離根結(jié)點(diǎn)較近。14. 哈夫曼樹不存在度為 1 的結(jié)點(diǎn)。第七章1. 有向圖的極通子圖稱為強(qiáng)連通分量。2. 一個(gè)具有 n 個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為 1/2n(n-1); 一個(gè)具有 n 個(gè)頂點(diǎn)的完全有向圖的弧 數(shù)為 n(n-1)3. 在有向圖中，頂點(diǎn)的度等于頂點(diǎn)的入度與出度之和

28、。4. 一個(gè)有 16 個(gè)頂點(diǎn)的無向圖，至少應(yīng)該有 15 條邊才能確保它是連通圖。文檔大全實(shí)用標(biāo)準(zhǔn)文案5. 一個(gè)有 10 個(gè)頂點(diǎn)的有向圖，它最多能有 90 條邊。6. 在有 10 個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度的最大值可以達(dá)到18.7. 迪杰斯特拉算法是按路徑長度遞增的次序產(chǎn)生最短路徑的算法。8. 圖的存儲(chǔ)結(jié)構(gòu)主要有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表四種。9. 圖的遍歷方法主要有深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種。10構(gòu)造圖的最小生成樹的方法主要有普里姆算法和克魯斯卡爾算法兩種。11. 用圖中的頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的先后關(guān)系，這樣的有向圖稱為AOV網(wǎng)。12. 時(shí)間 Vk的最早發(fā)生

29、時(shí)間是從源點(diǎn)到頂點(diǎn) Vk 的最大路徑長度。13. 在 AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)之間具有最大路徑長度的路徑稱為關(guān)鍵路徑。14. 一個(gè)有 n 個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，則求圖中邊數(shù)的方法是矩陣中1 的個(gè)數(shù)除以 2。求任一頂點(diǎn)的度的方法是計(jì)算該行中1 的個(gè)數(shù)。15. Prim 算法適用于求稠密圖的最小生成樹， Kruskal 算法適用于求稀疏圖的最小生成樹。第八章文檔大全實(shí)用標(biāo)準(zhǔn)文案1. 動(dòng)態(tài)查找表和靜態(tài)查找表的主要區(qū)別在于：動(dòng)態(tài)查找表有插入和刪除操作2. 順序查找在查找成功情況下的平均查找長度為(n+1) / 2 ；在查找失敗情況下的平均查找長度為 n+1.3. 折半查找只能使用順

30、序存儲(chǔ)結(jié)構(gòu)。4. 已知一個(gè)有序表為 10,23,35,46,48,55,59,64,72,83,88,99 ，當(dāng)用折半查找方法查找值為 46 和 83 的元素時(shí)，分別需要比較 3 次和 4 次才能查找成功；若采用順序查找是，分別需要比較 4 次和 10 次才能查找成功。5. 索引順序表上的查找分兩個(gè)階段，它們是確定待查元素所在的塊和在塊查找待查的元素。6. 在一棵 m階 B樹種， 若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 m-1；若在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并，則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 (m/2)-1 。7. 二叉排序樹查找成功是的平均查找長

31、度一般為log 2n。8. 哈希函數(shù)的構(gòu)造方法主要有直接定址法、除留余數(shù)法、數(shù)字分析法、平方取中法和折疊移位 法。文檔大全實(shí)用標(biāo)準(zhǔn)文案9. 在哈希函數(shù) h（ key ） =key%m中， m值最好取小于等于表長的素?cái)?shù)。10. 常用的處理沖突的方法有：開放定址法和鏈地址法。問答題1. 順序查找時(shí)間為 O（n），折半查找時(shí)間為 O（ log2n ）, 哈希法為 O（ 1），為什么有高效率的查 找方法而低效率的方法不被放棄？ 不同的查找方法使用的圍不同，高效率的查找方法并不是在所有情況下都比其他查找方法效率 要高，而且也不是在所有情況下都可以采用。2. 為什么有序的單鏈表不能進(jìn)行折半查找？ 因?yàn)殒湵?/p>

32、無法進(jìn)行隨機(jī)訪問，若要訪問鏈表中的結(jié)點(diǎn)，必須從頭指針開始依次遍歷鏈表，從而 浪費(fèi)大量時(shí)間。另外，也不好設(shè)定查找結(jié)束的條件。3. 在查找算法中，監(jiān)視哨的作用是什么？ 監(jiān)視哨的作用是免去查找過程中每次都要檢測整個(gè)表是否查找完畢，提高了查找效率。第九章文檔大全實(shí)用標(biāo)準(zhǔn)文案1. 根據(jù)在排序過程中使用的存儲(chǔ)器將排序方法分為部排序和外部排序。2. 常用的插入排序有直接排序、折半排序和希爾排序。3. 對于直接插入排序和直接選擇排序，若待排序序列基本有序，則選用直接插入排序較好；若 待排序序列為逆序，則選用直接選擇排序較好。4. 直接插入排序在最好情況下的時(shí)間復(fù)雜度為O（n），在最壞的情況下的時(shí)間復(fù)雜度為 O（ n2）。5. 若堆中某一數(shù)據(jù)元素在數(shù)組中的下標(biāo)為30，則它的左孩子的下標(biāo)為 61，右孩子的下標(biāo)為 626. 對于堆排序和快速排序，若帶排序列基本有序，則選用堆排序較好；若待排序序列無序，則 選用快速排序較好。7. 常用的選擇排序方法有直接選擇排序和堆排序。8. 設(shè)有字母序列 P,D,F,Z,E,P,N,B,X,M,G,W ，請寫出按二路歸并排序方法對該序列進(jìn)行一趟 掃描后的結(jié)果是 D P F Z E P B N M X G W 。9. 若不考慮基數(shù)排序，則在排序過