數(shù)據(jù)結構與算法習題與答案

1、第四章習題 (P111-113 )一、 復習題1、試述數(shù)據(jù)和數(shù)據(jù)結構的概念及其區(qū)別。 數(shù)據(jù)是對客觀事物的符號表示，是信息的載體；數(shù)據(jù)結構那么是指互相之間存在著一種或多種關系 的數(shù)據(jù)元素的集合。 ( P93)2、列出算法的五個重要特征并對其進行說明。 算法具有以下五個重要的特征：有窮性：一個算法必須保證執(zhí)行有限步之后結束。確切性：算法 的每一步驟必須有確切的定義。 輸入：一個算法有 0 個或多個輸入， 以刻畫運算對象的初始情況， 所謂 0 個輸入是指算法本身定除了初始條件。輸出：一個算法有一個或多個輸出，以反映對輸入 數(shù)據(jù)加工后的結果。沒有輸出的算法沒有實際意義?？尚行裕核惴ㄔ敲瓷夏軌蚓_地運

2、行，而且 人們用筆和紙做有限次運算后即可完成。 ( P95)3、算法的優(yōu)劣用什么來衡量？試述如何設計出優(yōu)秀的算法。時間復雜度 空間復雜度( P97-98 )4、線性和非線性結構各包含哪些種類的數(shù)據(jù)結構？線性結構和非線性結構各有什么特點？ 線性結構用于描述一對一的相互關系，即結構中元素之間只有最根本的聯(lián)系，線性結構的特點是 邏輯結構簡單。所謂非線性結構是指，在該結構中至少存在一個數(shù)據(jù)元素，有兩個或兩個以上的 直接前驅(或直接后繼)元素。樹型和圖型結構就是其中十分重要的非線性結構，可以用來描述 客觀世界中廣泛存在的層次結構和網(wǎng)狀結構的關系。(P99-105 )5、簡述樹與二叉樹的區(qū)別；簡述樹與圖的

3、區(qū)別。 樹用來描述層次結構，是一對多或多對一的關系；二叉樹( Binary Tree )是個有限元素的集合， 該集合或者為空、或者由一個稱為根 (root) 的元素及兩個不相交的、被分別稱為左子樹和右子樹 的二叉樹組成。二叉樹是有序的，即假設將其左、右子樹顛倒，就成為另一棵不同的二叉樹。圖也 稱做網(wǎng)，是一種比樹形結構更復雜的非線性結構。在圖中，任意兩個節(jié)點之間都可能相關，即節(jié) 點之間的鄰接關系可以是任意的，圖表示的多對多的關系。( P102-P104)6、請舉出遍歷算法在實際中使用的例子。 提示：根據(jù)實際生活中需要逐個訪問處理的情況舉例。7、編寫一個算法，統(tǒng)計在一個輸入字符串中各個不同字符出現(xiàn)

4、的頻度。用適當?shù)臏y試數(shù)據(jù)來驗 證這個算法。提示：根據(jù)查找算法和串中求子串的算法，查找輸入串中以單個字符形式的子串。8、假設對有 n 個元素的有序順序表和無序順序表進行順序搜索，試就以下三種情況分別討論兩者 在等搜索概率時的平均搜索長度是否相同 ?(1) 搜索失敗；(2) 搜索成功，且表中只有一個關鍵碼等于給定值k 的對象；(3) 搜索成功，且表中有假設干個關鍵碼等于給定值k 的對象，要求一次搜索找出所有對象。提示：根據(jù) P106-109 頁的查找和排序算法分別進行分析9、順序表的插入和刪除要求仍然保持各個元素原來的次序。設在等概率情形下，對有127 個元素的順序表進行插入，平均需要移動多少個元

5、素?刪除一個元素，又平均需要移動多少個元素?提示：根據(jù) P99 線性表的定義進行分析。題義是進行插入和刪除后仍然保持線性表的結構特性。10、遞歸的含義是什么？遞歸是指算法在過程中調用自身作為子算法的一種設計方法。 P109-110 練習題一填空題1、鏈表通常是由一個個節(jié)點構成的，每個節(jié)點的機構是由 域和 域構成。數(shù)據(jù)域 指針域 P99 2、樹內節(jié)點度的最大值，即樹中下級節(jié)點最多的節(jié)點的下級節(jié)點個數(shù)可被稱為度的最大值 P1023、數(shù)組在存儲和處理時是以第一個元素為起點，沿著行或者列的方向逐個進行。如果是先沿著 列的方向進行，一列完成再進行下一列，那么稱為 ；如果先沿著行的方向進行，一行進行完畢再

6、進行下一行，那么稱為 。列序為主或列序優(yōu)先 行序為主或行序優(yōu)先 P102二選擇題1、數(shù)據(jù)結構是指互相之間存在著一種或多種關系的數(shù)據(jù)元素的集合，根本的數(shù)據(jù)結構通常是A、集合結構B、線性結構C、樹型結構D圖形結構A B C DP93-94 2、算法的根本結構有 。A、順序結構B、分支結構C、循環(huán)結構D跳躍結構A B C P96-97 3、算法的實現(xiàn)方式有 A、子程序B、函數(shù)A B C DP98C、模塊D 、過程4、以下屬于非線性結構的有 。A 、樹B 、圖C 、 網(wǎng)D、串A B C( P102-105 )5、排序的方法有 _ 。A 、插入排序B、選擇排序C 、冒泡排序 D 、快速排序A B C D

7、 (P106-108 )6、遞歸方法一般用來解決哪些類型的問題？A、數(shù)據(jù)的定義是按遞歸定義的B問題解法按遞歸算法實現(xiàn)C、數(shù)據(jù)的結構形式是按遞歸定義的D問題的復雜程度超過一般算法能夠解決的A B C D P1097、 下面表達正確的選項是 。A、算法的執(zhí)行效率與數(shù)據(jù)的存儲結構無關B、算法的空間復雜度是指算法程序中指令或語句的條數(shù)C、算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止D、以上三種描述都不對C P958、 以下數(shù)據(jù)結構中不屬于線性數(shù)據(jù)結構的是 。A、隊列B、線性表C、二叉樹D棧C P99-104 9、算法的時間復雜度是指 。A、執(zhí)行算法程序所需要的時間B、算法程序的長度C、算法執(zhí)行過

8、程中所需要的根本運算次數(shù)D、算法程序中的指令條數(shù)A P9810、 以下表達中正確的選項是 。A、線性表是線性結構B棧與隊列是非線性結構C、線性鏈表是非線性結構D二叉樹是線性結構A P9911、設一棵完全二叉樹共有699 個結點，那么在該二叉樹中的葉子結點數(shù)為 A、 349B、 350C、 255D、 351B P10412、算法的空間復雜度是指 A、算法程序的長度C、算法程序所占的存儲空間D P98B算法程序中的指令條數(shù)D、 算法執(zhí)行過程中所需要的存儲空間13、 用樹形結構來表示實體之間聯(lián)系的模型稱為 。A、關系模型B、層次模型C、網(wǎng)狀模型D數(shù)據(jù)模型B P102 14、算法一般都可以用哪幾種控

9、制結構組合而成 。A、循環(huán)、分支、遞歸B順序、循環(huán)、嵌套C、循環(huán)、遞歸、選擇D順序、選擇、循環(huán)D P9715、數(shù)據(jù)的存儲結構是指 。B、數(shù)據(jù)的邏輯結構在計算機中的表示D存儲在外存中的數(shù)據(jù)A、數(shù)據(jù)所占的存儲空間量C、數(shù)據(jù)在計算機中的順序存儲方式B P9416、 在以下選項中，哪個不是一個算法一般應該具有的根本特征 。A、確定性B、可行性C、無窮性D擁有足夠的情報CD P9517、 在計算機中，算法是指 。A、查詢方法B、加工方法C、解題方案的準確而完整的描述D排序方法C P9518、數(shù)據(jù)處理的最小單位是 A、數(shù)據(jù)B、數(shù)據(jù)元素C P9319、 算法分析的目的是 。A、找出數(shù)據(jù)結構的合理性 C、分析

10、算法的易懂性和可靠性D P9820、用鏈表表示線性表的優(yōu)點是 A、便于插入和刪除操作C、花費的存儲空間較順序存儲少A B D P99-100 21、棧和隊列的共同點是 A、都是先進后出C、只允許在端點處插入和刪除元素C P100-101 C、數(shù)據(jù)項D、數(shù)據(jù)結構B找出算法中輸入和輸出之間的關系D分析算法的效率以求改良B數(shù)據(jù)元素的物理順序與邏輯順序相同D便于隨機存取B都是先進先出D沒有共同點三討論題1、試比擬快速排序和氣泡排序方法。起泡排序首先將第一個記錄的關鍵字與第二個記錄的關鍵字進行比擬，假設與需要的順序不 符，那么將兩個記錄交換，然后比擬第二個記錄和第三個記錄的關鍵字。依次類推，直至第n-1

11、 個記錄和第 n 個記錄的關鍵字進行過比擬為止。起泡排序在排序過程中需進行n-1 趟排序，并作等數(shù)量級的記錄移動?？焖倥判蚴菍ζ鹋菖判虻囊环N改良。其根本思想是：通過一趟排序將待排記 錄分割成獨立的兩局部，其中一局部記錄的關鍵字均比另一局部記錄的關鍵字小，那么可分別對這 兩局部記錄進行排序，以到達整個序列有序。在所有同數(shù)量級的此類先進的 排序方法中，就平均時間而言，快速排序是目前被認為是最實用的一種排序方法。 P107-108 2、試述遞歸方法的優(yōu)缺點。遞歸策略只需少量的程序就可描述遞歸是指算法在過程中調用自身作為子算法的一種設計方法。出解題過程所需要的屢次重復計算，大大地減少了程序的代碼量。由

12、于遞歸引起一系列的函數(shù)調 用，并且可能會有一系列的重復計算，遞歸算法的執(zhí)行效率相對較低。在遞歸調用的過程當中系 統(tǒng)為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出。 P1093、某石油公司方案建造一條由東向西的主輸油管道。該管道要穿過一個有n 口油井的油田。從每口油井都要有一條輸油管道沿最短路徑 或南或北 與主管道相連。 如果給定 n 口油井的位置， 即它們的 x 坐標和 y 坐標，應如何確定主管道的最優(yōu)位置，即使各油井到主管道之間的輸油管道 長度總和的最小位置？ 提示：選擇適宜的數(shù)據(jù)結構對問題進行描述 解題提示：可以使用微積分中的求最大、最小值的算法4、 考慮對數(shù)組 A中的n個數(shù)的排序：開始時先找出A的最小元素并放在另一個數(shù)組B的第一個位置上。然后找出 A中次最小元素并放在 B的第二個位置上，