算法與資料結構專項練習4

1.在一個單連結清單中，若删除P所指結點的後續結點，則執行？

正确答案: C

p=p->next;p->next=p->next->next

p->next=p->next

p->next=p->next->next

p=p->next->next

解析：

讓p的下一個結點指向下一個的結點的下一個結點，然後free掉(p->next)

2.設指針變量p指向雙向連結清單中結點A，指針變量s指向被插入的結點X，則在結點A的後面插入結點X的操作序列為（）。

正确答案: D

p->right=s； s->left=p； p->right->left=s； s->right=p->right；

s->left=p；s->right=p->right；p->right=s； p->right->left=s；

p->right=s； p->right->left=s； s->left=p； s->right=p->right；

s->left=p；s->right=p->right；p->right->left=s； p->right=s；

解析：

先修改待插入結點的前驅和後繼，再修改原來兩個結點中後一個結點的前驅以及前一個結點的後繼，可以簡單的記為前驅，後繼，前驅，後繼的修改順序

3.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動（ ）元素。

正确答案: B

8

63.5

63

7

解析：

平均要移動63.5次；

如果插在第一個位置那就要移動127個元素（即127次）；

如果插在第二個位置那就要移動126個元素（即126次）；

。

。

。

如果插在最後一個位置那不用移動移動次數為0；

就是從0~127的一個遞增數列（想倒過來遞減也行）；

是以平均要移動的次數N=(0+127)/2=63.5；

4.下面關于二分查找的叙述中正确的是：

正确答案: D

表必須有序,表可以順序方式存儲,也可以連結清單方式存儲

表必須有序且表中資料必須是整型,實型或字元型

表必須有序,而且隻能從小到大排列

表必須有序,且表隻能以順序方式存儲

解釋：

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。

https://blog.csdn.net/qq_40817827/article/details/89418006

5.在一個長度為 n （ n>1 ）的單連結清單上，設有頭和尾兩個指針，執行 操作與連結清單的長度有關。

正确答案: B

删除單連結清單中的第一個元素

删除單連結清單中的最後一個元素

在單連結清單第一個元素前插入一個新元素

在單連結清單最後一個元素後插入一個新元素

解釋：

A

頭指針是指向第一個元素（結點）的指針。

當删除單連結清單中的第一個元素時隻需要将頭指針指向第二個元素，然後釋放第一個元素儲存空間申請的記憶體。與連結清單長度無關。

ListNode *temp = head->next;
head->next = temp->next;
free(temp);
           

B

尾指針是指向最後一個元素（結點）的指針，與頭指針類似。

當删除單連結清單中的最後一個元素時 由于不是雙向連結清單，是以要從頭指針開始，一直周遊直到倒數第二個元素，将倒數第二個元素（結點）指向NULL，釋放原末端元素（結點）空間後，将尾指針等于新的末端元素（結點）。是以與連結清單長度有關。

ListNode *p = head;
while(p->next != rear) p = p->next;
p->next = NULL;
free(r);
r = p;
           

C

在單連結清單第一個元素前插入一個新元素時，隻需要把新的元素（結點）指向原來的第一個元素（結點），然後使頭指針指向新的元素（結點）。與連結清單長度無關。

new_point->next = head->next;
head->next = new_point;
           

D

在單連結清單最後一個元素後插入一個新元素時，隻需先将新結點指向NULL，然後将尾指針指向的原末端結點指向新的元素（結點），最後将尾指針指向新的元素（結點）。與連結清單長度無關。

new_point->next = NULL;
rear->next = new_point;
rear = new_point;
           

6.

（1）靜态連結清單既有順序存儲的優點,又有動态連結清單的優點。是以,它存取表中第i個元素的時間與i無關。

(2)靜态連結清單中能容納的元素個數的最大數在表定義時就确定了,以後不能增加.

(3)靜态連結清單與動态連結清單在元素的插入、删除上類似,不需做元素的移動。

以上錯誤的是()

正确答案: B

(1),(2)

(1)

(1),(2),(3)

(2)

解釋：

靜态連結清單是用數組存儲節點資料，模拟連結清單的實作，但是沒有用到指針。每個數組節點包括兩部分：data域和cursor（遊标）域。data存儲資料，cursor指明下個元素在數組中的下标。

（1）存取第i個元素時，需要從頭周遊到i-1和元素，由第i-1個節點的cursor，才能知道第i個元素存儲的位置，是以和i是相關的。

（2）使用數組對元素進行存儲，在定義時大小已經确定。

（3）插入和删除操作無需移動元素，隻需要修改cursor遊标的值即可，就像修改動态連結清單中的指針一樣。

7.串是一種特殊的線性表，其特殊性展現在（ ）。

正确答案: B

可以順序存儲

資料元素是一個字元

可以連結存儲

資料元素可以是多個字元

解釋：串是一種特殊的線性表，它的每個結點是一個字元，是以串也稱作字元串。

8.下面描述中正确的為?

正确答案: C D

線性表的邏輯順序與實體順序總是一緻的。

線性表的順序存儲表示優于鍊式存儲表示。

線性表若采用鍊式存儲表示時所有結點之間的存儲單元位址可連續可不連續。

二維數組是其數組元素為線性表的線性表。

解析：

A，鍊式存儲情況下不一緻

B，優劣要看使用情況

D，二維數組是順序存儲的線性表，元素就是線性表中的元素