第一章概論
一、填空題
1、 資料的儲存結構可用四種基本的儲存方法表示，分別是順序、 鏈式 、 索引和雜湊。
2、乙個演算法具有5個特性: 有窮性 、確定性、可行性，有零個或多個輸入、有乙個或多個輸出 。
3、 資料結構包括資料的邏輯結構 、儲存結構和運算（或基本操作）這三個方面的內容。
4、資料結構中評價演算法的兩個重要指標是時間效率和空間效率。
5、乙個資料結構在計算機中的表示稱為儲存結構 。
6、從邏輯上可以把資料結構分為線性結構、非線性結構兩大類
二、單項選擇題
1、 資料結構中，與所使用的計算機無關的是資料的（ c ）結構；
a) 儲存 b) 物理 c) 邏輯d) 物理和儲存
2、演算法分析的目的是（ c ）
a) 找出資料結構的合理性 b) 研究演算法中的輸入和輸出的關係
c) 分析演算法的效率以求改進 d) 分析演算法的易懂性和文件性
3、 計算機演算法指的是（ c ）
a) 計算方法 b) 排序方法 c) 解決問題的有限運算序列 d) 排程方法
4、 計算機演算法必須具備輸入、輸出和（ b ）等5個特性。
a) 可行性、可移植性和可擴充性 b) 可行性、確定性和有窮性
c) 確定性、有窮性和穩定性d) 易讀性、穩定性和安全性
5、從邏輯上可以把資料結構分為（ c ）兩大類。
a）動態結構、靜態結構 b）順序結構、鏈式結構
c）線性結構、非線性結構 d）初等結構、構造型結構
6、下列資料中，（c）是非線性資料結構。
a．棧 b. 佇列 c. 完全二叉樹 d. 堆
7、演算法分析的兩個主要方面是（ a ）。
a) 空間複雜性和時間複雜性 b) 正確性和簡明性
c) 可讀性和文件性d) 資料複雜性和程式複雜性
8、在下面程式段的時間複雜度（d ）
i=1;
while(i<=n)
i=i*3;
a． o(3n) b．o(n) c．o(n3) d．o(log3n)
9、在下面的程式段中，對x的賦值語句的頻度為（c ）
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x=x+1;
a． o(2n) b．o(n) c．o(n2) d．o(log2n)
10、下面關於演算法說法錯誤的是（d ）
a．演算法最終必須由電腦程式實現
b.為解決某問題的演算法同為該問題編寫的程式含義是相同的
c. 演算法的可行性是指指令不能有二義性
d. 以上幾個都是錯誤的
三、判斷題
1. 資料的邏輯結構說明資料元素之間的順序關係,它依賴於計算機的儲存結構.(× )
2. 資料的邏輯結構是指資料的各資料項之間的邏輯關係；(× )
3. 資料的物理結構是指資料在計算機內的實際儲存形式。(√ )
4．演算法的優劣與演算法描述語言無關，但與所用計算機有關。(× )
5．健壯的演算法不會因非法的輸入資料而出現莫名其妙的狀態。(√ )
6．演算法可以用不同的語言描述，如果用c 語言或pascal語言等高階語言來描述，則演算法實際上就是程式了。(× )
四、簡答題
1、當為解決某一問題而選擇資料結構時，應從哪些方面考慮？
答：通常考慮演算法所需要的儲存空間量和演算法所需要的時間量。後者又涉及到四方面：
程式執行時所需輸入的資料總量，對源程式進行編譯所需時間，計算機執行每條指令所需時間和程式中指令重複執行的次數。
第2章線性表
一、填空
1．當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素時，應採用順序儲存結構。
2．順序儲存的線性表儲存特點是用物理位置的相鄰表示元素之間的關係的，在順序表中插入或刪除乙個元素，移動的元素個數與表長和該元素在表中的位置有關。如果線性表l=（a1,a2,…,an）用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是（n-1）/2_；第i個元素（1<=i<=n）之前插入乙個元素時，需向後移動n-i+1_個元素。如果要在第1個元素前插入乙個元素，要後移 n 個元素；刪除第i個元素(1≤i≤n)時，需向前移動 n-i 個元素。
3．設單鏈表的結點結構為(data,next)，next為指標域，已知指標px指向單鏈表中data為x的結點，指標py指向data為y的新結點 , 若將結點y插入結點x之後，則需要執行以下語句:__ py->next=px->next; _ px->next=py
4．在順序表中訪問任意一結點的時間複雜度均為 o(1) ，因此，順序表也稱為隨機訪問的資料結構。
5、鏈結儲存的特點是利用__指標來表示資料元素之間的邏輯關係。在單鏈表中，除了首元結點外，任一結點的儲存位置由其直接前驅結點的鏈域的值指示，查詢結點都必須從頭結點開始，因此，鍊錶也稱為順序訪問的資料結構。在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的位址，其時間複雜度為o（n），在給定值為x的結點後插入乙個新結點的時間複雜度為 o(n)_。
7．已知指標p指向單鏈表l中的某結點，則刪除其後繼結點的語句是： u=p->next; 為空表的條件是：_ l->next==l && l->prior==l p->next=u->next;
8．帶頭結點的雙迴圈鍊錶l中只有乙個元素結點的條件是：l->next->next==l；
二、判斷正誤（在正確的說法後面打勾，反之打叉）
（ × ）1. 線性表的特點是每個元素都有乙個前驅和乙個後繼。
（ × ）2. 鍊錶的物理儲存結構具有同煉表一樣的順序。
（ × ）3. 鍊錶的刪除演算法很簡單，因為當刪除鏈中某個結點後，計算機會自動地將後續的各個單元向前移動。
（ × ）4. 取線性表的第i個元素的時間同i的大小有關.
（ × ）5. 順序表結構適宜於進行順序訪問，而鍊錶適宜於進行隨機訪問。
（ × ）6. 順序儲存方式的優點是儲存密度大，且插入、刪除運算效率高。
(√ )7．鍊錶是採用鏈式儲存結構的線性表,進行插入、刪除操作時，在鍊錶中比在順序儲存結構中效率高。
（ × ）8. 線性表在順序儲存時，邏輯上相鄰的元素未必在儲存的物理位置次序上相鄰。
（ × ）9. 順序儲存方式只能用於儲存線性結構。
（ × ）10. 線性表的邏輯順序與儲存順序總是一致的。
(× )11. 鍊錶中的頭結點僅起到標識的作用。
(√ )12. 順序儲存結構的主要缺點是不利於插入或刪除操作。
(√ ) 13．線性表採用鍊錶儲存時，結點和結點內部的儲存空間可以是不連續的。
(× )14．順序儲存方式插入和刪除時效率太低，因此它不如鏈式儲存方式好。
(× )15. 對任何資料結構鏈式儲存結構一定優於順序儲存結構。
三、單項選擇題
1．資料在計算機儲存器內表示時，實體地址與邏輯位址相同並且是連續的，稱之為（ c ）
（a）儲存結構 （b）邏輯結構 （c）順序儲存結構 （d）鏈式儲存結構
2．乙個向量第乙個元素的儲存位址是100，每個元素的長度為2，則第5個元素的位址是（ b ）
（a）110 （b）108c）100 （d）120
3. 在n個結點的順序表中，演算法的時間複雜度是o（1）的操作是（ a ）
（a） 訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）
（b） 在第i個結點後插入乙個新結點（1≤i≤n）
（c） 刪除第i個結點（1≤i≤n）
（d） 將n個結點從小到大排序
4. 向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動（ b ）個元素
（a）8 （b）63.5c）63 （d）7
5. 線性表（ a1,a2,…,an）以鏈結方式儲存時，訪問第i位置元素的時間複雜性為（c）
a．o（i） b．o（1） c．o（n） d．o（i-1）
6. 鍊錶是一種採用（ b ）儲存結構儲存的線性表；
（a）順序 （b）鏈式c）星式 （d）網狀
7. 線性表若採用鏈式儲存結構時，要求記憶體中可用儲存單元的位址（ d ）
（a）必須是連續的 （b）部分位址必須是連續的
（c）一定是不連續的 （d）連續或不連續都可以
8． 線性表ｌ在（ b ）情況下適用於使用鏈式結構實現。
（ａ）需經常修改ｌ中的結點值 （ｂ）需不斷對ｌ進行刪除插入
（ｃ）ｌ中含有大量的結點中結點結構複雜
9． 單鏈表的儲存密度（ c ）
（ａ）大於1； （ｂ）等於1； （ｃ）小於1； （ｄ）不能確定
10．對於乙個頭指標為head的帶頭結點的單鏈表，判定該錶為空表的條件是（b ）
a．head==null b．head→next==null c．head→ext==head d．head!=null
資料結構總複習題 da an
一 填空題 1.資料結構是研究資料的 邏輯結構 和 物理結構，並在這種結構上定義相關的運算，設計實現這些運算的演算法，分析演算法的效率。演算法的效率包括時間和空間兩個方面，分別稱為 時間複雜度 和 空間複雜度 2.資料的基本單位是 資料元素，資料的最小單位是 資料項。3.演算法是對特定問題求解 步驟...
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比，有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...