第一章緒論
一、問答題
1什麼是資料結構？
2敘述四類基本資料結構的名稱與含義。
3敘述演算法的定義與特性。
4敘述演算法的時間複雜度。
5敘述資料型別的概念。
6敘述線性結構與非線性結構的差別。
7敘述物件導向程式設計語言的特點。
8在物件導向程式設計中，類的作用是什麼？
9敘述引數傳遞的主要方式及特點。
10. 敘述抽象資料型別的概念。
二、判斷題（在各題後填寫「√」或「×」）
1線性結構只能用順序結構來存放，非線性結構只能用非順序結構來存放。（ ）
2演算法就是程式。（ ）
3在高階語言（如c或 pascal）中，指標型別是原子型別。（ ）
三、計算下列程式段中x=x+1的語句頻度
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
【解答】
i=1時： 1 = (1+1)×1/2 = (1+12)/2
i=2時： 1+2 = (1+2)×2/2 = (2+22)/2
i=3時： 1+2+3 = (1+3)×3/2 = (3+32)/2
… i=n時： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2
x=x+1的語句頻度為：
f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2
=[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2
=n(n+1)(n+2)/6
=n3/6+n2/2+n/3
區分語句頻度和演算法複雜度：
o(f(n)) = o(n3)
四、試編寫演算法，求一元多項式pn(x)=a0+a1x+a2x2+a3x3+…anxn的值pn(x0)，並確定演算法中的每一語句的執行次數和整個演算法的時間複雜度，要求時間複雜度盡可能小，規定演算法中不能使用求冪函式。注意：本題中的輸入ai(i=0,1,…,n),x和n，輸出為pn(x0)。
通常演算法的輸入和輸出可採用下列兩種方式之一：
（1）通過參數列中的參數顯式傳遞。
（2）通過全域性變數隱式傳遞。
試討論這兩種方法的優缺點，並在本題演算法中以你認為較好的一種方式實現輸入和輸出
【解答】
（1）通過參數列中的參數顯式傳遞
優點：當沒有呼叫函式時，不占用記憶體，呼叫結束後形參被釋放，實參維持，函式通用性強，移置性強。
缺點：形參鬚與實參對應，且返回值數量有限。
（2）通過全域性變數隱式傳遞
優點：減少實參與形參的個數，從而減少記憶體空間以及傳遞資料時的時間消耗
缺點：函式通用性降低，移植性差
演算法如下：通過全域性變數隱式傳遞引數
polyvalue()
printf(「%f」,p);
}演算法的時間複雜度：t(n)=o(n)
通過參數列中的參數顯式傳遞
float polyvalue(float a[ ], float x, int n)
return(p);
}演算法的時間複雜度：t(n)=o(n)
第二章線性表
2.1 描述以下三個概念的區別：頭指標，頭結點，首元素結點。
2.2 填空：
（1） 在順序表中插入或刪除乙個元素，需要平均移動＿＿一半＿＿元素，具體移動的元素個數與＿＿插入或刪除的位置＿＿有關。
（2） 在順序表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。
（3） 在帶頭結點的非空單鏈表中，頭結點的儲存位置由＿＿＿＿＿＿指示，首元素結點的儲存位置由＿＿＿＿＿＿指示，除首元素結點外，其它任一元素結點的儲存位置由＿＿其直接前趨的next域＿＿指示。
2.3 已知l是無表頭結點的單鏈表，且p結點既不是首元素結點，也不是尾元素結點。按要求從下列語句中選擇合適的語句序列。
a. 在p結點後插入s結點的語句序列是：＿（4）、（1）＿。
b. 在p結點前插入s結點的語句序列是：（7）、（11）、（8）、（4）、（1）。
c. 在表首插入s結點的語句序列是：（5）、（12）。
d. 在表尾插入s結點的語句序列是：（11）、（9）、（1）、（6）。
供選擇的語句有：
（1）p->next=s;
（2）p->next= p->next->next;
（3）p->next= s->next;
（4）s->next= p->next;
（5）s->next= l;
（6）s->next= null;
（7）q= p;
（8）while(p->next!=q) p=p->next;
（9）while(p->next!=null) p=p->next;
（10）p= q;
（11）p= l;
（12）l= s;
（13）l= p;
2.4 已知線性表l遞增有序。試寫一演算法，將x插入到l的適當位置上，以保持線性表l的有序性。
status insert_sqlist(sqlist &va,int x)//把x插入遞增有序表va中
//insert_sqlist
2.5 寫一演算法，從順序表中刪除自第i個元素開始的k個元素。
[提示]：注意檢查i和k的合法性。
（集體搬遷，「新房」、「舊房」）
< 方法1 > 以待移動元素下標m（「舊房號」）為中心，
計算應移入位置（「新房號」）：
for ( m= i－1+k; m<= l－>last; m++)
l－>elem[ m－k ] = l－>elem[ m ];
< 方法2 > 同時以待移動元素下標m和應移入位置j為中心：
< 方法2 > 以應移入位置j為中心，計算待移動元素下標：
2.6已知線性表中的元素（整數）以值遞增有序排列，並以單鏈表作儲存結構。試寫一高效演算法，刪除表中所有大於mink且小於maxk的元素（若表中存在這樣的元素），分析你的演算法的時間複雜度（注意：
mink和maxk是給定的兩個參變數，它們的值為任意的整數）。
status delete_between(linklist &l,int mink,int maxk)//刪除元素遞增排列的鍊錶l中值大於mink且小於maxk的所有元素
}//delete_between
2.7試分別以不同的儲存結構實現線性表的就地逆置演算法，即在原表的儲存空間將線性表（a1, a2..., an）逆置為（an, an-1,..., a1）。
（1） 以一維陣列作儲存結構，設線性表存於a(1:arrsize)的前elenum個分量中。
（2） 以單鏈表作儲存結構。
[方法1]:在原頭結點後重新頭插一遍
[方法2]:可設三個同步移動的指標p, q, r，將q的後繼r改為p
2.8 假設兩個按元素值遞增有序排列的線性表a和b，均以單鏈表作為儲存結構，請編寫演算法，將a表和b表歸併成乙個按元素值遞減有序的排列的線性表c，並要求利用原表（即a表和b表的）結點空間存放表c.
[提示]：參p.28 例2-1
< 方法1 >
void merge(linklist a; linklist b; linklist *c)
else
while ( pa!=null)
while ( pb!=null)
< 方法2 >
linklist merge(linklist a; linklist b)
{ ……
linklist c；
pa=a－>next; pb=b－>next;
C語言資料結構答案
助人教育qq 707223565 c語言 資料結構綜合測試 一 單項選擇題 1 下列與k n 完全等價的表示式是 c a k n b k n l c k n，n n 1 d n n 1，k n 2 已知int a 5，b 3，p b，q a 下列賦值語句中與b a 等價的語句是 a a p q b ...
資料結構 C語言描述 2章習題答案
第一章習題 2 3 1 包含改變量定義的最小範圍 2 資料抽象 資訊隱蔽 3 資料物件 物件間的關係 一組處理資料的操作 4 指標型別 5 集合結構 線性結構 樹形結構 圖狀結構 6 順序儲存 非順序儲存 7 一對 一 一對多 多對多 8 一系列的操作 9 有限性 輸入 可行性 4 1 a 2 c ...
資料結構C語言描述耿國華習題及答案
第一章習題答案 2 3 1 包含改變量定義的最小範圍 2 資料抽象 資訊隱蔽 3 資料物件 物件間的關係 一組處理資料的操作 4 指標型別 5 集合結構 線性結構 樹形結構 圖狀結構 6 順序儲存 非順序儲存 7 一對 一 一對多 多對多 8 一系列的操作 9 有限性 輸入 可行性 4 1 a 2 ...