資料結構C語言版部分習題及答案

第二章習題與解答

一判斷題

1．線性表的邏輯順序與儲存順序總是一致的。

2．順序儲存的線性表可以按序號隨機訪問。

3．順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。

4．線性表中的元素可以是各種各樣的，但同一線性表中的資料元素具有相同的特性，因此是屬於同一資料物件。

5．**性表的順序儲存結構中，邏輯上相鄰的兩個元素在物理位置上並不一定緊鄰。

6．**性表的鏈式儲存結構中，邏輯上相鄰的元素在物理位置上不一定相鄰。

7．線性表的鏈式儲存結構優於順序儲存結構。

8．**性表的順序儲存結構中，插入和刪除時，移動元素的個數與該元素的位置有關。

9．線性表的鏈式儲存結構是用一組任意的儲存單元來儲存線性表中資料元素的。

10．在單鏈表中，要取得某個元素，只要知道該元素的指標即可，因此，單鏈表是隨機訪問的儲存結構。

二單選題 (請從下列a，b，c，d選項中選擇一項)

1．線性表是( ) 。

(a) 乙個有限序列，可以為空； (b) 乙個有限序列，不能為空；

2．對順序儲存的線性表，設其長度為n，在任何位置上插入或刪除操作都是等概率的。插入乙個元素時平均要移動表中的（）個元素。

a) n/2 (b) n+1/2 (c) n -1/2 (d) n

3．線性表採用鏈式儲存時，其位址( ) 。

(a) 必須是連續的； (b) 部分位址必須是連續的；

4．用鍊錶表示線性表的優點是（）。

(a)便於隨機訪問

(b)花費的儲存空間較順序儲存少

(c)便於插入和刪除

(d)資料元素的物理順序與邏輯順序相同

5．某煉表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除最後乙個元素，則採用( )儲存方式最節省運算時間。

(a)單鏈表

(b)雙鏈表

(c)單迴圈鍊錶

(d)帶頭結點的雙迴圈鍊錶

6．迴圈鍊錶的主要優點是( ) 。

(a)不在需要頭指標了

(b)已知某個結點的位置後，能夠容易找到他的直接前趨

(c)在進行插入、刪除運算時，能更好的保證鍊錶不斷開

(d)從表中的任意結點出發都能掃瞄到整個鍊錶

7．下面關於線性表的敘述錯誤的是( )。

(a) 線性表採用順序儲存，必須占用一片位址連續的單元；

(b) 線性表採用順序儲存，便於進行插入和刪除操作；

(d) 線性表採用鏈式儲存，不便於進行插入和刪除操作；

8．單鏈表中，增加乙個頭結點的目的是為了（　）。

(a) 使單鏈表至少有乙個結點 (b)標識表結點中首結點的位置

（c）方便運算的實現d) 說明單鏈表是線性表的鏈式儲存

9．若某線性表中最常用的操作是在最後乙個元素之後插入乙個元素和刪除第乙個元素，則採用（）儲存方式最節省運算時間。

(a) 單鏈表 (b) 僅有頭指標的單迴圈鍊錶

10．若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則採用（）儲存方式最節省運算時間（）。

(a) 單鏈表 (b) 順序表

三填空題

1．帶頭結點的單鏈表h為空的條件是

1．非空單迴圈鍊錶l中*p是尾結點的條件是

3．在乙個單鏈表中p所指結點之後插入乙個由指標f所指結點，應執行s->next和p->next的操作。

4．在乙個單鏈表中p所指結點之前插入乙個由指標f所指結點，可執行以下操作：

s->next

p->next=s;

t=p->data;

p->data

s->data

5．在順序表中做插入操作時首先檢查

四演算法設計題

1．設線性表存放在向量a[arrsize]的前elenum個分量中，且遞增有序。試寫一演算法，將x 插入到線性表的適當位置上，以保持線性表的有序性。並且分析演算法的時間複雜度。

2．已知一順序表a，其元素值非遞減有序排列，編寫乙個函式刪除順序表中多餘的值相同的元素。

3．編寫乙個函式，從一給定的順序表a中刪除值在x~y(x<=y)之間的所有元素，要求以較高的效率來實現。

提示：可以先將順序表中所有值在x~y之間的元素置成乙個特殊的值，並不立即刪除它們，然後從最後向前依次掃瞄，發現具有特殊值的元素後，移動其後面的元素將其刪除掉。

4．線性表中有n個元素，每個元素是乙個字元，現存於向量r[n]中，試寫一演算法，使r中的字元按字母字元、數字字元和其它字元的順序排列。要求利用原來的儲存空間，元素移動次數最小。（研54）

5．線性表用順序儲存，設計乙個演算法，用盡可能少的輔助儲存空間將順序表中前m個元素和後n個元素進行整體互換。即將線性表

（a1, a2, … , am, b1, b2, … , bn）改變為：

（b1, b2, … , bn , a1, a2, … , am）。

6．已知帶頭結點的單鏈表l中的結點是按整數值遞增排列的，試寫一演算法，將值為x 的結點插入到表l中，使得l仍然有序。並且分析演算法的時間複雜度。

7．假設有兩個已排序的單鏈表a和b，編寫乙個函式將他們合併成乙個鍊錶c而不改變其排序性。

8．假設長度大於1的迴圈單鏈表中，既無頭結點也無頭指標，p為指向該鍊錶中某一結點的指標，編寫乙個函式刪除該結點的前趨結點。

9．已知兩個單鏈表a和b分別表示兩個集合，其元素遞增排列，編寫乙個函式求出a和b的交集c，要求c同樣以元素遞增的單鏈表形式儲存。

10．設有乙個雙向鍊錶，每個結點中除有prior、data和next域外，還有乙個訪問頻度freq域，在鍊錶被起用之前，該域其值初始化為零。每當在鍊錶進行一次locata(l,x)運算後，令值為x的結點中的freq域增1，並調整表中結點的次序，使其按訪問頻度的遞減序列排列，以便使頻繁訪問的結點總是靠近表頭。試寫乙個演算法滿足上述要求的locata(l,x)演算法。

五上機實習題目

1． josephu 問題

josephu 問題為：設編號為1，2，… n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數，數到m 的那個人出列，它的下一位又從1開始報數，數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生乙個出隊編號的序列。

提示：用乙個不帶頭結點的迴圈鍊錶來處理josephu 問題：先構成乙個有n個結點的單迴圈鍊錶，然後由k結點起從1開始計數，計到m時，對應結點從鍊錶中刪除，然後再從被刪除結點的下乙個結點又從1開始計數，直到最後乙個結點從鍊錶中刪除演算法結束。

2．一元多項式的相加

提示：（1）一元多項式的表示問題：對於任意一元多項式：

pn(x)= p0+ p1x1+ p2x2+ … + pixi+ … + pnxn

可以抽象為乙個由「係數-指數」對構成的線性表，且線性表中各元素的指數項是遞增的：

p=( ( p0,0), ( p1,1), ( p2,2), … , ( pn,n) )

(2 ) 用乙個單鏈表表示上述線性表，結點結構為：

typedef sturct node

;struct node *creatlist(int num) /* 建立迴圈鍊錶 */

head=ptr1;

ptr1->next=head;

for(i=1;i

ptr1=ptr1->next;

ptr1->next=head;

}return head;

}main()

{ int i,n=30,m; /* 人數n為30個 */

struct node *head,*ptr;

randomize();

head=creatlist(n);

for(i=1;i<=30;i++)

{head->number=i;

資料結構C語言版部分習題及答案

資料結構C語言版部分習題及答案

資料結構 C語言版

資料結構C語言版第45章習題答案

資料結構C語言版部分習題及答案

資料結構C語言版部分習題及答案

資料結構 C語言版

資料結構C語言版第45章習題答案

相關推薦