習題二

一、選擇題

1．以下關于線性表的敘述正確的是（　）。

Ⅰ 線性表中每個數據元素都有一個前驅和一個后繼

II 線性表中所有元素必須按由小到大或由大到小的順序排列

III 線性表是由有限個相同類型的數據元素所構成的序列

IV 線性表基本操作的實現取決于采用哪一種存儲結構，存儲結構不同，實現的算法也不同

A．Ⅰ，II，III

B．II，III，IV

C．III，IV

D．III

2．設線性表有n個元素，以下操作中，（　）在順序表上實現比鏈表上實現效率更高。

A．輸出第i個（0≤i≤n-1）數據元素的值

B．交換第1個數據元素與第2個數據元素的值

C．順序輸出這n個數據元素的值

D．輸出與給定值x相等的數據元素在線性表中的序號

3．假設在順序表{a1，a2，…，an}中，每一個數據元素所占的存儲單元的數目為4，且第1個數據元素的存儲地址為100，則第7個數據元素的存儲地址是（　）。

A．106

B．107

C．124

D．128

4．設線性表有n個元素，嚴格說來，以下操作中，（　）在順序表上實現比鏈表上實現效率更高。

Ⅰ 輸出第i個（0≤i≤n-1）數據元素的值

II 交換第3個數據元素與第4個數據元素的值

III 順序輸出這n個數據元素的值

A．Ⅰ

B．Ⅰ，II

C．Ⅰ，III

D．II，III

5．在鏈表中若經常要刪除表中最后一個結點或在最后一個結點之后插入一個新結點，則宜采用（　）存儲方式。

A．順序表

B．用頭指針標識的循環單鏈表

C．用尾指針標識的循環單鏈表

D．雙向鏈表

6．在一個單鏈表中的p和q兩個結點之間插入一個新結點，假設新結點為s，則修改鏈指針的C語言語句序列是（　）。

A．s-＞next=p；q-＞next=s

B．p-＞next=s-＞next；s-＞next=p

C．q-＞next=s-＞next；s-＞next=p

D．p-＞next=s；s-＞next=q

7．在一個含有n個結點的有序單鏈表中插入一個新結點，使單鏈表仍然保持有序的算法的時間復雜度是（　）。

A．O（1）

B．O（log2n）

C．O（n）

D．O（n2）

8．要將一個順序表{a1，a2，…，an}中第i個數據元素ai（1≤i≤n）刪除，需要移動（　）個數據元素。

A．i

B．n-i-1

C．n-i

D．n-i+1

9．在帶頭結點的雙向循環鏈表中的p結點之后插入一個新結點s，其修改鏈指針的C語言語句序列是（　）。

A．p-＞next=s；s-＞prior=p；p-＞next-＞prior=s；s-＞next=p-＞prior；

B．p-＞next=s；p-＞next-＞prior=s；s-＞prior=p；s-＞next=p-＞next；

C．s-＞prior=p；s-＞next=p-＞next；p-＞next=s；p-＞next-＞prior=s；

D．s-＞next=p-＞next；s-＞prior=p；p-＞next-＞prior=s；p-＞next=s；

10．順序表的存儲密度（　），而單鏈表的存儲密度（　）。

A．小于1

B．等于1

C．大于1

D．不能確定

二、填空題

1．線性表是由n（n≥0）個數據元素所構成的__________，其中n為數據元素的個數，稱為線性表的__________，n=0的線性表稱為__________。

2．線性表中有且僅有一個開始結點和終端結點，除開始結點和終端結點之外，其他每一個數據元素有且僅有一個_____，有且僅有一個______。

3．線性表通常采用_____和______兩種存儲結構。若線性表的長度確定或變化不大，則適合采用_______存儲結構進行存儲。

4．在順序表{a1，a2，…，an}中的第i（1≤i≤n+1）個位置之前插入一個新的數據元素，會引起_______個數據元素的移動操作。

5．在表長為n的順序表中查找值為x的數據元素時，查找成功時需與元素比較的平均次數是_______。

6．在線性表的順序存儲結構中可實現快速的隨機存取，而在鏈式存儲結構中則只能進行________存取。

7．順序表中邏輯上相鄰的數據元素，其物理位置_______相鄰，而在單鏈表中邏輯上相鄰的數據元素，其物理位置________相鄰。

8．在僅設置了尾指針的循環鏈表中，訪問第一個結點的時間復雜度是________。

9．在一個單鏈表中p所指結點之前插入一個s所指結點時，可執行如下操作：

s-＞next=______；p-＞next=s；t=p-＞data；p-＞data=______；s-＞data=_______

10．在一個單鏈表中刪除p所指結點時，可執行如下操作：

q=p-＞next；p-＞data=q-＞data；p-＞next=_________；

三、判斷題

1．在順序表中邏輯上相鄰的元素，其對應的物理位置也是相鄰的。

2．線性表的順序存儲空間一旦分配，則其大小固定，不能在程序執行時進行改變。

3．所謂隨機存取，就是通過首地址和元素的位序號值可以在O（1）的時間內找到指定的元素。

4．順序存儲的線性表不支持隨機存取。

5．在順序表上進行插入或刪除操作時需要移動元素的個數與待插入或待刪除元素的位置無關。

6．單鏈表不是一種隨機存取的存儲結構。

7．順序存儲是動態的存儲結構，鏈式存儲結構是靜態的存儲結構。

8．線性表的唯一存儲形式是鏈表。

9．線性表的長度是線性表所占用的存儲空間的大小。

10．一個循環鏈表可能由給定的頭指針或尾指針唯一標識。

四、算法設計題

1．設計算法，實現對順序表就地逆置的操作。所謂逆置，就是把{a1，a2，…，an}變成{an，an-1，…，a1}；所謂就地，就是指逆置后的數據元素仍存儲在原來順序表的存儲空間中，即不為逆置后的順序表另外分配存儲空間。

2．已知順序表{a1，a2，…，an}中的數據元素類型為整型int，試設計一個在時間和空間兩方面都盡可能高效的算法，實現將順序表循環右移k位的操作。即原來順序表為{a1，a2，…，an-k，an-k+1，…，an}，循環向右移動k位后變成{an-k+1，…，an，a1，a2，…，an-k}。

3．已知順序表{a1，a2，…，an}中的數據元素類型為整型int，設計一個時間與空間上盡可能高效的算法，將其調整為左、右兩部分，左邊所有數據元素為奇數，右邊所有數據元素為偶數。

4．一個長度為L（L≥1）的升序序列S，處在第[L/2]個位置的數稱為S的中位數，其中[L/2]的運行符“[]”表示對運算結果L/2取整。例如：若序列S1=（11，13，15，17，19），則S1的中位數是15，兩個序列的中位數是含它們所有元素的升序序列的中位數。例如：若S2=（2，4，6，8，20），則S1和S2的中位數是11。現在有兩個等長升序序列A和B，試設計一個在時間和空間上都盡可能高效的算法，找出兩個序列A和B的中位數。

5．設計算法，實現對帶頭結點的單鏈表就地逆置的操作。

6．設計算法，實現刪除不帶頭結點的單鏈表中數據域值等于x的第一個結點的操作。若刪除成功，則返回被刪除結點的位序號；否則，返回0。

7．設計算法，找出已知兩個鏈表的第一個公共結點。所謂兩個鏈表有公共結點，就是指兩個鏈表從某個結點開始，它們的next都指向同一個結點，這個開始結點就是兩個鏈表的第一個公共結點。

8．設計算法，實現將一個用循環鏈表表示的稀疏多項式分解成兩個多項式的操作，并使兩個多項式中各自僅含奇次項或偶次項。要求利用原循環鏈表中的存儲空間構成這兩個鏈表。