1樓：匿名使用者
第 1 章 緒 論
課後習題講解
1. 填空
⑴（ ）是資料的基本單位，在計算機程式中通常作為一個整體進行考慮和處理。
【解答】資料元素
⑵（ ）是資料的最小單位，（ ）是討論資料結構時涉及的最小資料單位。
【解答】資料項，資料元素
【分析】資料結構指的是資料元素以及資料元素之間的關係。
⑶ 從邏輯關係上講，資料結構主要分為（ ）、（ ）、（ ）和（ ）。
【解答】集合，線性結構，樹結構，圖結構
⑷ 資料的儲存結構主要有（ ）和（ ）兩種基本方法，不論哪種儲存結構，都要儲存兩方面的內容：（ ）和（ ）。
【解答】順序儲存結構，連結儲存結構，資料元素，資料元素之間的關係
⑸ 演算法具有五個特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）。
【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性
⑹ 演算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為演算法語言。
【解答】自然語言，程式設計語言，流程圖，偽**，偽**
⑺ 在一般情況下，一個演算法的時間複雜度是（ ）的函式。
【解答】問題規模
⑻ 設待處理問題的規模為n，若一個演算法的時間複雜度為一個常數，則表示成數量級的形式為（ ），若為n*log25n，則表示成數量級的形式為（ ）。
【解答】ο(1)，ο(nlog2n)
【分析】用大o記號表示演算法的時間複雜度，需要將低次冪去掉，將最高次冪的係數去掉。
2. 選擇題
⑴ 順序儲存結構中資料元素之間的邏輯關係是由（ ）表示的，連結儲存結構中的資料元素之間的邏輯關係是由（ ）表示的。
a 線性結構 b 非線性結構 c 儲存位置 d 指標
【解答】c，d
【分析】順序儲存結構就是用一維陣列儲存資料結構中的資料元素，其邏輯關係由儲存位置（即元素在陣列中的下標）表示；連結儲存結構中一個資料元素對應連結串列中的一個結點，元素之間的邏輯關係由結點中的指標表示。
⑵ 假設有如下遺產繼承規則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不能相互繼承。則表示該遺產繼承關係的最合適的資料結構應該是（ ）。
a 樹 b 圖 c 線性表 d 集合
【解答】b
【分析】將丈夫、妻子和子女分別作為資料元素，根據題意畫出邏輯結構圖。
⑶ 演算法指的是（ ）。
a 對特定問題求解步驟的一種描述，是指令的有限序列。
b 計算機程式 c 解決問題的計算方法 d 資料處理
【解答】a
【分析】計算機程式是對演算法的具體實現；簡單地說，演算法是解決問題的方法；資料處理是通過演算法完成的。所以，只有a是演算法的準確定義。
⑷ 下面（ ）不是演算法所必須具備的特性。
a 有窮性 b 確切性 c 高效性 d 可行性
【解答】c
【分析】高效性是好演算法應具備的特性。
⑸ 演算法分析的目的是（ ），演算法分析的兩個主要方面是（ ）。
a 找出資料結構的合理性 b 研究演算法中輸入和輸出的關係
c 分析演算法的效率以求改進 d 分析演算法的易讀性和文件性
e 空間效能和時間效能 f 正確性和簡明性
g 可讀性和文件性 h 資料複雜性和程式複雜性
【解答】c，e
3. 判斷題
⑴ 演算法的時間複雜度都要通過演算法中的基本語句的執行次數來確定。
【解答】錯。時間複雜度要通過演算法中基本語句執行次數的數量級來確定。
⑵ 每種資料結構都具備三個基本操作：插入、刪除和查詢。
【解答】錯。如陣列就沒有插入和刪除操作。此題注意是每種資料結構。
⑶ 所謂資料的邏輯結構指的是資料之間的邏輯關係。
【解答】錯。是資料之間的邏輯關係的整體。
⑷ 邏輯結構與資料元素本身的內容和形式無關。
【解答】對。因此邏輯結構是資料組織的主要方面。
⑸ 基於某種邏輯結構之上的基本操作，其實現是唯一的。
【解答】錯。基本操作的實現是基於某種儲存結構設計的，因而不是唯一的。
4. 分析以下各程式段，並用大o記號表示其執行時間。
【解答】⑴ 基本語句是k=k+10*i，共執行了n-2次，所以t(n)=o(n)。
⑵ 基本語句是k=k+10*i，共執行了n次，所以t(n)=o(n)。
⑶ 分析條件語句，每迴圈一次，i+j 整體加1，共迴圈n次，所以t(n)=o(n)。
⑷ 設迴圈體共執行t(n)次，每迴圈一次，迴圈變數y加1，最終t(n)=y，即：
(t(n)+1)2≤n，所以t(n)=o(n 1/2)。
⑸ x++是基本語句，所以
5．設有資料結構（d，r），其中d=，r=。試畫出其邏輯結構圖並指出屬於何種結構。
【解答】其邏輯結構圖如圖1-3所示，它是一種圖結構。
6. 為整數定義一個抽象資料型別，包含整數的常見運算，每個運算對應一個基本操作，每個基本操作的介面需定義前置條件、輸入、功能、輸出和後置條件。
【解答】整數的抽象資料型別定義如下：
adt integer
data
整數a：可以是正整數(1, 2, 3, … )、負整數(-1, -2, -3, …)和零
operation
constructor
前置條件：整數a不存在
輸入：一個整數b
功能：構造一個與輸入值相同的整數
輸出：無
後置條件：整數a具有輸入的值
set前置條件：存在一個整數a
輸入：一個整數b
功能：修改整數a的值，使之與輸入的整數值相同
輸出：無
後置條件：整數a的值發生改變
add前置條件：存在一個整數a
輸入：一個整數b
功能：將整數a與輸入的整數b相加
輸出：相加後的結果
後置條件：整數a的值發生改變
sub前置條件：存在一個整數a
輸入：一個整數b
功能：將整數a與輸入的整數b相減
輸出：相減的結果
後置條件：整數a的值發生改變
multi
前置條件：存在一個整數a
輸入：一個整數b
功能：將整數a與輸入的整數b相乘
輸出：相乘的結果
後置條件：整數a的值發生改變
div前置條件：存在一個整數a
輸入：一個整數b
功能：將整數a與輸入的整數b相除
輸出：若整數b為零，則丟擲除零異常，否則輸出相除的結果
後置條件：整數a的值發生改變
mod前置條件：存在一個整數a
輸入：一個整數b
功能：求當前整數與輸入整數的模，即正的餘數
輸出：若整數b為零，則丟擲除零異常，否則輸出取模的結果
後置條件：整數a的值發生改變
equal
前置條件：存在一個整數a
輸入：一個整數b
功能：判斷整數a與輸入的整數b是否相等
輸出：若相等返回1，否則返回0
後置條件：整數a的值不發生改變
endadt
7. 求多項式a(x)的演算法可根據下列兩個公式之一來設計：
⑴ a(x)=anxn+an-1xn-1+…+a1x+a0
⑵ a(x)=(…(anx+an-1)x+…+a1)x)+a0
根據演算法的時間複雜度分析比較這兩種演算法的優劣。
【解答】第二種演算法的時間效能要好些。第一種演算法需執行大量的乘法運算，而第二種演算法進行了優化，減少了不必要的乘法運算。
8. 演算法設計（要求：演算法用偽**和c++描述，並分析最壞情況下的時間複雜度）
⑴ 對一個整型陣列a[n]設計一個排序演算法。
【解答】下面是簡單選擇排序演算法的偽**描述。
下面是簡單選擇排序演算法的c++描述。
分析演算法，有兩層巢狀的for迴圈，所以， 。
⑵ 找出整型陣列a[n]中元素的最大值和次最大值。
【解答】演算法的偽**描述如下：
演算法的c++描述如下：
分析演算法，只有一層迴圈，共執行n-2次，所以，t(n)=o(n)。
學習自測及答案
1．順序儲存結構的特點是（ ），連結儲存結構的特點是（ ）。
【解答】用元素在儲存器中的相對位置來表示資料元素之間的邏輯關係，用指示元素儲存地址的指標表示資料元素之間的邏輯關係。
2. 演算法在發生非法操作時可以作出處理的特性稱為（ ）。
【解答】健壯性
3. 常見的演算法時間複雜度用大o記號表示為：常數階( )、對數階( )、線性階 ( )、平方階( )和指數階( )。
【解答】o(1)，o(log2n)，o(n)，o(n2)，o(2n)
4．將下列函式按它們在n 時的無窮大階數，從小到大排列。
n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n
【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!
5．試描述資料結構和抽象資料型別的概念與程式設計語言中資料型別概念的區別。
【解答】資料結構是指相互之間存在一定關係的資料元素的集合。而抽象資料型別是指一個資料結構以及定義在該結構上的一組操作。程式設計語言中的資料型別是一個值的集合和定義在這個值集上一組操作的總稱。
抽象資料型別可以看成是對資料型別的一種抽象。
6. 對下列用二元組表示的資料結構,試分別畫出對應的邏輯結構圖，並指出屬於何種結構。
⑴ a=(d，r)， 其中d=，r=
⑵ b=(d，r)， 其中d=，r=
⑶ c=( d，r)，其中d=，r=
⑷ d=(d，r)， 其中d=，
r= 【解答】⑴ 屬於集合，其邏輯結構圖如圖1-4(a)所示；⑵ 屬於線性結構，其邏輯結構圖如圖1-4(b)所示；⑶ 屬於樹結構，其邏輯結構圖如圖1-4(c)所示；⑷ 屬於圖結構，其邏輯結構圖如圖1-4(d)所示。
7. 求下列演算法的時間複雜度。
count=0; x=1;
while (x
return count;
【解答】o(log2n)
2樓：匿名使用者
這個**上有你所需
要的word.
資料結構c語言版清華大學出版社嚴蔚敏吳偉
本光碟是 資料結構 c語言版 一書的配書光碟，作為資料結構課程的 輔助學習工具。1.光碟執行環境 硬體 pentium 100以上多 pc機。軟體 windows 95 98 me 2000 xp 作業系統。2.盤中內容 dsdemow 資料結構演算法演示系統 windows版 測試版 dsdemo...
求測量學高井祥第四版中國礦業大學出版社出版課後習題答案，看清楚版本再給答案，財富值不是問題
根據教育部公佈的普通高等教育 十一五 國家級教材規劃選題名單，我社被納入普通高等教育 十一五 國家級規劃的教材已達33種 我社將充分利用高校出版社獨特的教育背景和出版資源的優勢，積極為高校教育服務，努力為各高校提供更多的優秀教材。我社入選普通高等教育 十一五 國家級教材規劃的33本教材如下 本科部分...
中國當代文學史洪子誠版（北京大學出版社）每個章節要點歸納
你好我剛好有洪子誠版的中國當代文學史是修訂版的。下面是這書的目錄及大致內容的介紹。上編 50 70年代的文學 第1章 文學的 轉折 1.1 複習筆記 1.2 考研真題與典型題詳解 第2章 文學環境與文學規範 2.1 複習筆記 2.2 考研真題與典型題詳解 略 第3章 矛盾和衝突 3.1 複習筆記 3...