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(n1/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. 常見的演算法時間複雜度用大ｏ記號表示為：常數階( )、對數階( )、線性階 ( )、平方階( )和指數階( )。
【解答】ｏ(1)，ｏ(log2n)，ｏ(n)，ｏ(n2)，ｏ(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;
【解答】ｏ(log2n)
1. 填空
⑴ 在順序表中，等概率情況下，插入和刪除乙個元素平均需移動（ ）個元素，具體移動元素的個數與（ ）和（ ）有關。
【解答】表長的一半，表長，該元素在表中的位置
⑵ 順序表中第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的儲存位址是（ ）。
【解答】108
【分析】第5個元素的儲存位址=第1個元素的儲存位址＋(5－1)×2=108
⑶ 設單鏈表中指標p 指向結點a，若要刪除a的後繼結點（假設a存在後繼結點），則需修改指標的操作為（ ）。
【解答】p->next=(p->next)->next
⑷ 單鏈表中設定頭結點的作用是（ ）。
【解答】為了運算方便
【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。
⑸ 非空的單迴圈鍊錶由頭指標head指示，則其尾結點（由指標p所指）滿足（ ）。
【解答】p->next=head
【分析】如圖2-8所示。
資料結構課後習題答案
5 選擇題 ccbdca 6 試分析下面各程式段的時間複雜度。1 o 1 2 o m n 3 o n2 4 o log3n 5 因為x 共執行了n 1 n 2 1 n n 1 2，所以執行時間為o n2 6 o 1 選擇題 babadbcabdcddac 2 演算法設計題 6 設計乙個演算法，通過一...
資料結構課後習題答案總結
第一章第1章作業 1.1,1.2,1.6 1 3 1.8 1.1 簡述下列概念 資料 資料元素 資料型別 資料結構 邏輯結構 儲存結構 線性結構 非線性結構。資料 指能夠被計算機識別 儲存和加工處理的資訊載體。資料元素 就是資料的基本單位，在某些情況下，資料元素也稱為元素 結點 頂點 記錄。資料元素...
資料結構課後習題
1.1 簡述資料與資料元素的關係與區別 資料元素 data element 是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。有時，乙個資料元素可由若干個資料項組成 1.2 資料結構和資料型別有什麼區別 資料結構是指計算機處理的資料元素的組織形式和相互關係，而資料型別是某種程式語言已實現...