習題2

2.1 選擇題

（1）線性表是具有n個________的有限序列（n≠0）。

A.表元素 B.字符

C.數據元素 D.數據項

（2）順序表的存儲結構是一種________的存儲結構。

A.隨機存取 B.順序存取

C.索引存取 D.HASH存取

（3）在一個長度為n的順序表中，向第i個元素（1≤i≤n+1）之前插入一個新元素時，需要向后移動________個元素。

A.n-i B.n-i+1

C.n-i-1 D.i

（4）鏈表是一種采用________存儲結構存儲的線性表。

A.順序 B.鏈式

C.星式 D.網狀

（5）下面關于線性表的敘述錯誤的是________。

A.線性表采用順序存儲方式，必須占用一片連續的存儲空間

B.線性表采用鏈式存儲方式，不必占用一片連續的存儲空間

C.線性表采用鏈式存儲方式，便于插入和刪除操作的實現

D.線性表采用順序存儲方式，便于插入和刪除操作的實現

（6）設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用________存儲方式最節省運算時間。

A.單向鏈表 B.單向循環鏈表

C.雙向鏈表 D.雙向循環鏈表

（7）設指針q指向單鏈表中的結點A，指針p指向單鏈表中結點A的后繼結點B，指針s指向被插入的結點X，則在結點A和結點B之間插入結點X的操作序列為________。

A.s->next=p->next；p->next=-s； B.q->next=s； s->next=p；

C.p->next=s->next；s->next=p； D.p->next=s；s->next=q；

（8）設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B的操作為________。

A.p->next=p->next->next B.p=p->next

C.p=p->next->next D.p->next=p

（9）在一個以h為頭的單循環鏈表中，p指針指向鏈尾的條件是________。

A.p->next=h B.p->next=NULL

C.p->next->next=h D.p->data=-1

（10）對于只在首尾兩端進行插入操作的線性表，宜采用的存儲結構為________。

A.順序表 B.用頭指針表示的單循環鏈表

C.單鏈表 D.用尾指針表示的單循環鏈表

2.2 填空題

（1）線性表是n個元素的_____________________________。

（2）線性表的存儲結構有_____________________________。

（3）設線性表中有n個數據元素，則在順序存儲結構上實現順序查找的平均時間復雜度為___________，在鏈式存儲結構上實現順序查找的平均時間復雜度為___________。

（4）設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中_______個數據元素；刪除第i個位置上的數據元素需要移動表中_______個元素。

（5）若頻繁地對線性表進行插入與刪除操作，該線性表應采用______________存儲結構。

（6）鏈式存儲結構中的結點包含________________域和_______________域。

（7）在雙向鏈表中，每個結點有兩個指針域，一個指向_________，另一個指向_________。

（8）對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。

（9）設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點B，則在結點A的后面插入結點B的操作序列為______________________________________。

（10）設指針變量p指向單鏈表中的結點A，則刪除結點A后繼結點（假設存在）的語句序列為：

s=p->next；p->next=___________; free(s);

2.3 將一順序表A中的元素逆置。例如，原來順序表A中元素是100，90，80，70，60，50，40，逆置以后為40，50，60，70，80，90，100。要求算法所用的輔助空間要盡可能地少。用非形式算法描述，并編寫C語言程序。

2.4 編寫一算法輸出已知順序表A中元素的最大值和次最大值。用非形式算法描述，并編寫C語言程序。

2.5 設一順序表中元素值遞增有序。寫一算法，將元素x插到表中適當的位置，并保持順序表的有序性。

2.6 設有兩個按元素值遞增有序的順序表A和B（單鏈表A和B），編一程序將A表和B表歸并成一個新的遞增有序的順序表C（單鏈表C）（值相同的元素均保留在C表中）。

2.7 設有兩個線性表A和B，皆是單鏈表存儲結構。同一個表中的元素各不相同，且遞增有序。寫一算法，構成一個新的線性表C，使C為A和B的交集，且C中元素也遞增有序。