一、選擇題
1. 下面說法錯誤的是 c 。
（1）演算法原地工作的含義是指不需要任何額外的輔助空間。
（2）在相同的規模n下，複雜度o（n）的撒在時間上總是優於複雜度o(2n)的演算法。
（3）所謂時間複雜度是指最壞情況下，估算演算法執行時間的乙個上界。
（4）同乙個演算法，實現語言的級別越高，執行效率越低。
a、（1） b、（1）（2） c、（1）（4） d、（3）
2. 乙個遞迴演算法必須包括 b 。
a、遞迴部分 b、終止條件和遞迴部分
c、迭代部分 d、終止條件和迭代部分
3. 資料的 c 包括查詢、插入、刪除、更新、排序等操作型別。
a、儲存結構 b、邏輯結構
c、基本運算 d、演算法描述
4. 在資料結構中，從邏輯上可以把資料結構分成 c 。
a、動態結構和靜態結構 b、緊湊結構和非緊湊結構
c、線性結構和非線性結構 d、內部結構和外部結構
5. 與資料元素本身的形式、內容、相對位置、個數無關的是資料的 c 。
a、儲存結構 b、儲存實現
c、邏輯結構 d、運算實現
6. 通常要求同一邏輯結構中的所有資料元素具有相同的特性，這意味著 b 。
a、資料具有同一特點
b、不僅資料元素所包含的資料項的個數要相同，而且對應資料項的型別要一致
c、每個資料元素都一樣
d、資料元素所包含的資料項的個數要相等
7. 以下說法正確的是 d 。
a、資料元素是資料的最小單位
b、資料項是資料的基本單位
c、資料結構是帶有結構的各資料項的集合
d、一些表面上很不相同的資料可以有相同的邏輯結構
8. 以下說法錯誤的是 a 。
a、程式設計的實質是資料處理
b、資料的邏輯結構是資料的組織形式，基本運算規定了資料的基本操作方式
c、運算實現是完成運算功能的演算法或這些演算法的設計
d、資料處理方式總是與資料的某種相應表示形式相聯絡，反之亦然
9. 下列程式段的時間複雜度為 b 。
x=n;
y=0;
while (x>=(y+1)*(y+1))
y=y+1;
a、o(n) b、o(n1/2) c、o(1) d、o(n2)
10. 下列敘述中有關好的程式設計風格的正確描述是 c 。
a、程式中的注釋是可有可無的
b、對遞迴定義的資料結構不要使用遞迴過程
c、過程應是自封閉的，盡量少使用全程變數
d、多採用一些技巧以提高程式的執行效率
二、填空題
1. 乙個演算法有5個特性： 有窮性 、 確定性 、 可行性、有零個或多個輸入、有乙個或多個輸出。
2. 演算法的時間複雜度是指該演算法所求解問題規模（或頻度）的函式。
3. 演算法的可行性是指每一條指令都應在有限的時間內完成 。
4、線性結構的特徵：邏輯上滿足有且僅有乙個開始結點和乙個終端結點，且其餘結點有且僅有唯一的乙個直接前趨和乙個直接後繼 。
5. 資料的儲存結構被分為順序 、 鏈結 、 索引和雜湊 4種。
6. 儲存結構是邏輯結構的儲存實現，其基本目標是建立資料的機內表示 。
7.資料表示任務是逐步完成的，即資料表示形式的變化過程是： 機外表示 →
邏輯結構 → 儲存結構 。
8. 資料處理任務也是逐步完成的，即轉化過程是： 處理要求 → 基本運算 → → 演算法 。
9. 從邏輯關係上講資料結構主要分為兩大類，它們是線性結構和非線性結構 。
10. 資料結構的基本任務是資料結構的設計和實現 。
三、給出下列演算法的時間複雜度。
1、sum(int n)
return (sum);
} t（n）=o（n2）
2、j=1;
while(j<=n)
o(log2n)
習題二一、選擇題
1.線性表是具有n個 c 的有限序列。
a、表元素 b、字元 c、資料元素
d、資料項 e、資訊項
2.線性表的靜態鍊錶儲存結構與順序儲存結構相比優點是 c 。
a、所有的操作演算法實現簡單 b、便於隨機儲存
c、便於插入和刪除 d、便於利用零散的儲存器空間
3.若長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素演算法的時間複雜度為 c 。
a、o(log2n) b、o(1)
c、o(n) d、o(n2)
4.（1）靜態鍊錶既有順序儲存的特點，又有動態鍊錶的優點。所以，它訪問表中第i個元素的時間與i無關；
（2）靜態鍊錶中能容納元素個數的最大數在定義時就確定了，以後不能增加；
（3）靜態鍊錶與動態鍊錶在元素的插入、刪除上類似，不需做元素的移動。
以上錯誤的是 b 。
a、（1）、（2） b、（1） c、（1）、（2）、（3） d、（2）
5.將圖2-6所示的s所指結點加到p所指結點之後，其語句應為 d 。
a、s－＞next=p+1;p－＞next=s;
b、(*p).next=s;(*s).next=(*p).next;
c、s－＞next=p－＞next;p－＞next=s－＞next;
d、s－＞next=p－＞next;p－＞next=s;p
圖2-6 插入結點示意
6.在雙向鍊錶儲存結構中，刪除p所指的結點時須修改指標 a 。
a、p－＞next－＞prior=p－＞prior;p－＞prior－＞next=p－＞next;
b、p－＞next=p－＞next－＞next;p－＞next－＞prior=p;
c、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior;
d、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;
7.在雙向迴圈鍊錶中，在p指標所指的結點後插入q所指向的新結點，其修改指標的操作是 c 。
a、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q;
b、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next;
c、q－＞prior=p;q－＞next=p－＞next;
p－＞next－＞prior=q;p－＞next=q;
d、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q;
8.將兩個各有n個元素的有序表歸併成乙個有序表，其最少的比較次數是 a 。
a、 n b.2n－1 c.2n
9.在乙個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入乙個新元素時須向後移動 b 個元素。
a、n－i b、n－i+1 c、n－i－1 d、i
10.線性表l=(a1，a2,……an)，下列說法正確的是 d 。
a、每個元素有有乙個直接前驅和乙個直接後繼
b、線性表中至少有乙個元素
c、表中諸元素的排列必須是由小到大或由大到小。
d、除第乙個和最後乙個元素外，其餘每個元素都有乙個且僅有乙個直接前驅和直接後繼。
11.對單鏈表表示法，以下說法錯誤的是 c 。
a、資料域用於儲存線性表的乙個資料元素
b、指標域（或鏈域）用於存放乙個指向本結點所含資料元素的直接後繼所在結點的指標
c、所有資料通過指標的鏈結而組織成單鏈表
d、null稱為空指標，它不指向任何結點只起標誌作用
12.若指定有n個元素的向量，則建立乙個有序單向鍊錶的時間複雜性的量級是 c 。
a、o(1) b、o(n) c、o(n2) d、o(nlog2n)
13.以下說法正確的是 d 。
a、順序儲存方式的優點是儲存密度大且插入、刪除運算率高
b、鍊錶的每個結點中都恰好包含乙個指標
c、線性表的順序儲存結構優於鏈式儲存結構
d、順序儲存結構屬於靜態結構而鏈式結構屬於動態結構
14.以下說法錯誤的是 a 。
a、對迴圈鍊錶來說，從表中任一結點出發都能通過前後移操作掃瞄整個迴圈鍊錶
b、對單鏈表來說，只有從頭結點開始才能掃瞄表中全部結點
c、雙鏈表的特點是找結點的前趨和後繼都很容易
d、對雙鏈中來說，結點*p的儲存位置既存放在其前趨結點的後繼指標域中，也存放在它的後繼結點的前趨指標中
15.以下說法錯誤的是 d 。
a、求表長、定位這兩種運算在採用順序儲存結構時實現的效率不比採用鏈式儲存結構時實現的效率低
b、序儲存的線性表可以隨機訪問
c、由於順序儲存要求連續的儲存區域，所以在儲存管理上不夠靈活
d、線性表的鏈式儲存結構優於順序儲存結構
二、判斷題
1.線性表採用鍊錶儲存時，結點和結點內部的儲存空間可以是不連續的。（ 錯 ）
2.在具有頭結點的鏈式儲存結構中，頭指標指向鍊錶中的第乙個資料結點。（ 錯 ）
3.順序儲存的線性表可以隨機訪問。（ 對 ）
資料結構練習題
習題3 棧和佇列 一 基本內容 棧和佇列的結構特點 在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。二 學習要點 1.掌握棧和佇列的特點。2 熟練掌握棧型別的兩種實現方法，即兩種儲存結構表示時的基本操作實現演算法，特別應注意棧滿和棧空的條件以及它們的描述方法。3 熟練掌握迴...
資料結構練習題
習題5 陣列和廣義表 一 基本內容 陣列定義及表示方式 特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現 廣義表的邏輯結構和儲存結構。二 學習要點 1.了解陣列的兩種儲存表示方法，並掌握陣列在以行為主的儲存結構中的位址計算方法。2 掌握對特殊矩陣進行壓縮儲存時的下標變換公式。3 了解稀疏矩陣的兩種壓縮儲...
資料結構練習題
a.n b.n 1 2 c.n 1 9 對於乙個具有n個頂點和e條邊的無向圖，若採用鄰接表表示，則表頭向量的大小為 所有鄰接表中的接點總數是 b.n 1 c.n 1 d.n e a.e 2 b.e d.n e 10 已知乙個圖如圖7.1所示，若從頂點a出發按深度搜尋法進行遍歷，則可能得到的一種頂點序...