第一章一．選擇題
1.下面屬於邏輯結構的是(c)備註：其他都是儲存結構，包括迴圈佇列
a 順序表 b雜湊表 c 有序表d 單鏈表
2.下面關於演算法說法錯誤的是（ d ）
a．演算法最終必須由電腦程式實現（不見得，有些演算法是np完全問題，電腦程式只能實現低數量的值，對於高數量的是實現不了的）
b.為解決某問題的演算法同為該問題編寫的程式含義是相同的
c. 演算法的可行性是指指令不能有二義性
d. 以上幾個都是錯誤的
3．從邏輯上可以把資料結構分為（ c ）兩大類。a沒有此種分法；不按照儲存結構劃分；d
a．動態結構、靜態結構 b．順序結構、鏈式結構
c．線性結構、非線性結構 d．初等結構、構造型結構
4.線性表的靜態鍊錶儲存結構與順序儲存結構相比優點是（ c ）。
a. 所有的操作演算法實現簡單 b. 便於隨機訪問
c. 便於插入和刪除d. 節省儲存空間
5.採用順序搜尋方法查詢長度為n的順序表時，搜尋成功的平均搜尋長度為（ d ）。
a. n b. n/2 c. (n-1)/2 d. (n+1)/2
備註：順序表的平均查詢長度等於所有長度和除以總的次數：
(1+2+3+...+n)/n = (1+n)/2；失敗的平局查詢次數：(0+1+2+...+n-1)/n=(n-1)/2
所以答案為(1+n)/2
6.資料結構的定義為(d，s)，其中d是( b )的集合。
備註：s是d上關係的集合
a. 演算法 b. 資料元素c. 資料操作 d. 邏輯結構
7.以下資料結構中，哪乙個是線性結構（ d ）？
a．廣義表 b. 二叉樹 c. 稀疏矩陣 d. 串
備註：對於資料結構課程而言，簡單地說，線性結構是乙個資料元素的有序(次序)集合。它有四個基本特徵:
1.集合中必存在唯一的乙個"第乙個元素"; 2.集合中必存在唯一的乙個"最後的元素"; 3.
除最後元素之外，其它資料元素均有唯一的"後繼"; 4.除第一元素之外，其它資料元素均有唯一的"前驅"。 資料結構中線性結構指的是資料元素之間存在著「一對一」的線性關係的資料結構。
如(a1,a2,a3,.....,an),a1為第乙個元素，an為最後乙個元素，此集合極為乙個線性結構的集合。
8.在資料結構中，從邏輯上可以把資料結構分成 ( c )備註：非線性包裹樹形和圖形結構兩種；
a. 動態結構和靜態結構 b. 緊湊結構和非緊湊結構
c. 線性結構和非線性結構 d. 內部結構和外部結構
9．下段程式段的時間複雜度是 ( d ).備註：怎麼求時間複雜度
i＝1；
while(i<=n) i=i*2；
o(n2) c. o(log3n) d. o(log2n)
10．演算法分析的目的是( c ).
a．找出資料結構的合理性b. 研究演算法中輸入輸出的關係
c. 分析演算法的效率以求改進d. 分析演算法的易懂性和文件
備註：分析演算法的目的就是要降低演算法的時間複雜度和空間複雜度，提高演算法的執行效率。
11．在下面的程式段中，對x的賦值語句的頻度為（ c ）怎樣求頻度
for i:=1 to n do
for j:=1 to n do
x:=x+1;
a． o(2n) b．o(n) c．o(n2) d．o(log2n)
12．以下資料結構中，（ a ）是非線性資料結構
a．樹 b．字串 c．隊d．棧
13．連續儲存設計時，儲存單元的位址（a ）。
a．一定連續 b．一定不連續 c．不一定連續 d．部分連續，部分不連續
二.填空題
1.資料結構是一門研究（ 非數值計算 ）的程式設計問題中計算機的操作物件以及它們之間的關係和操作等的學科。
2.根據資料元素之間關係的不同特性，通常有四類基本資料結構：集合、線性結構、（ 樹形結構 ）和圖狀結構。
3.一種抽象資料型別包括（ 資料 ）和基本操作兩個部分。
4.乙個「好」的演算法應該考慮達到以下目標：（ 正確性 ）、可讀性、健壯性、效率和低儲存量需求。
5. 乙個演算法的時間複雜度是用該演算法操作時重複使用次數的多少來度量的，乙個演算法的空間複雜度是用該演算法在執行過程中所占用的____儲存空間____的大小來度量的。
6．演算法具有如下特點：①有窮性、可執行性、②確定性、結果性、一般性。
有窮性 、 確定性 、 可行性 、輸入和輸出。
7．下面程式段的時間複雜度為。（log^3n）
i=1;
while(i<=n)
i=i*3;
8.在有n個元素的順序表中插入乙個元素，所需要移動元素的平均個數是（ n/2 ），具體移動元素的個數與（ 元素個數有關。
第二章一．選擇題
1．下述哪一條是順序儲存結構的優點？（ a）
a．儲存密度大 b．插入運算方便
c．刪除運算方便 d．可方便地用於各種邏輯結構的儲存表示
2．下面關於線性表的敘述中，錯誤的是哪乙個？（b ）
a．線性表採用順序儲存，必須占用一片連續的儲存單元。
b．線性表採用順序儲存，便於進行插入和刪除操作。(缺點，要移動大量元素)
c．線性表採用鏈結儲存，不必占用一片連續的儲存單元。
d．線性表採用鏈結儲存，便於插入和刪除操作。
3．若某線性表最常用的操作是訪問任一指定序號的元素和在最後進行插入和刪除運算，則利用（ a ）儲存方式最節省時間。
a．順序表 b．雙鏈表 c．帶頭結點的雙迴圈鍊錶 d．單迴圈鍊錶
備註：訪問任一指定序號最好是隨機訪問，則可採用順序表，而且，刪除和插入都是在最後進行的，所以不用移動大量元素即可；
4. 若長度為n的線性表採用順序儲存結構，在其第i個位置插入乙個新元素的演算法的時間複雜度為（ c ）(1<=i<=n+1)。
a. o(0) b. o(1c. o(nd. o(n2)
5．線性表（ a1,a2,…,an）以鏈結方式儲存時，訪問第i位置元素的時間複雜性為（c ）
a．o（i） b．o（1） c．o（n） d．o（i
6．非空的迴圈單鏈表head的尾結點p↑滿足（a）。
a．p↑.link=head b．p↑.link=nil c．p=nil d．p= head
7．迴圈鍊錶h的尾結點p的特點是（a ）。
a．p^.next:=h b．p^.next:= h^.next c．p:=h d．p:=h^.next
不會寫8.在乙個單鏈表中，若p所指結點不是最後結點，在p之後插入s結點，則執行(b).
a. s->next=p; p->next=s; b. s->next=p->next; p->next=s;
c. s->next=p->next; p=s; d. p->next=s; s->next=p;
9.在迴圈雙鏈表的p所指結點之後插入s所指結點的操作是( b ).
a. p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;
b. s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
c. s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
d. p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;
10．在單鏈表指標為p的結點之後插入指標為s的結點，正確的操作是：（b）。
a．p->next=s;s->next=p->next; b． s->next=p->next;p->next=s;
c．p->next=s;p->next=s->next; d． p->next=s->next;p->next=s;
11．對於乙個頭指標為head的帶頭結點的單鏈表，判定該錶為空表的條件是（ b ）
a．head==null b．head→next==null
c．head→next==head d．head!=null
二、演算法設計
1. a和b是兩個單鏈表，表中元素遞增有序。試寫一演算法將a和b歸併成乙個按元素值遞減有序的單鏈表c。編寫乙個函式，實現上述演算法。
node *mergelink(node *p, node *q) else } if (p == null) r->next = q; if (q == null) r->next = p; p = h->next; h = h->next; free(p); return h; }
2. 有乙個單鏈表l（至少有1個結點），其頭結點指標為head，編寫乙個過程將l逆置，即最後乙個結點變成第乙個結點，原來倒數第二個結點變成第二個結點，如此等等。
3. 在乙個遞增有序的線性表中，有數值相同的元素存在。若儲存方式為單鏈表，設計演算法去掉數值相同的元素，使表中不再有重複的元素。
例如：（7，10，10，21，30，42，42，42，51，70）將變作（7，10，21，30，42，51，70），分析演算法的時間複雜度。
4.有一有序單鏈表（按元素值公升序排列），表頭指標為head，單鏈表的結點型別如下：
typedefstructlnode
listnode,*linklist;
編寫乙個演算法，向該鍊錶中插入乙個值為x(x的資料型別為int型)的結點，使插入後該鍊錶仍然有序。
資料結構第2章習題
一 填空 1.在順序表中插入或刪除乙個元素，需要平均移動元素，具體移動的元素個數 與有關。2.線性表中結點的集合是的，結點間的關係是的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動個元素。4.向乙個長度為n的向量中刪除第i個元素 1 i n 時，需向前移動個元...
資料結構習題第10章
第10章內部排序 一 選擇題 1.下列排序方法中，穩定的排序方法是 a.簡單選擇排序 b.氣泡排序 c.希爾排序 d.快速排序 2.在下列排序演算法中,哪乙個演算法的時間複雜度與初始排序無關 a.直接插入排序 b.氣泡排序 c.快速排序 d.簡單選擇排序 3.排序方法中，從未排序序列中依次取出元素與...
資料結構習題 第1章
第一章概論自測題姓名班級 一 填空題 每空1分，共33分 1.乙個計算機系統包括和兩大部分。2.一台計算機中全部程式的集合，稱為這台計算機的 3.計算機軟體可以分為軟體和軟體兩大類。科學計算程式包屬於診斷程式屬於 4.一種用助憶符號來表示機器指令的操作符和運算元的語言是 5.資料結構是一門研究非數值...