2023年408計算機學科專業基礎真題解析

一、單項選擇題：1-40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是符合題目要求的。

1、下列對順序存儲的有序表（長度為n）實現給定操作的算法中平均時間復雜度為O（1）的是（  ）。

A.查找包含指定值元素的值

B.插入包含指定值元素的算法

C.刪除第i個元素的算法

D.獲取第i個值的算法

【答案】D

【考點】本題考查順序表的基本操作。

【解析】本題是針對順序有序表的基本操作。對于A，若采用順序查找則平均時間復雜度為O(n)，若采用折半查找則平均時間復雜度為O(logn)，因此A錯誤。對于B，若要在順序有序表中插入指定值的元素，首先需要查找該值待插入的位置，之后再在該位置插入值。查找操作的時間復雜度如選項A，插入操作由于需要移動待插入位置之后的所有元素，因此其時間復雜度為O(n)，綜上插入包含指定值元素的算法的平均時間復雜度為O(n)，因此B錯誤。對于C，刪除第i個元素需要將第i元素之后的所有元素向前移動一個單位，因此該刪除操作的平均時間復雜度為O(n)，因此C錯誤。對于D，順序表具有隨機存儲的特點，可以通過下標直接訪問該值，因此獲取第i個值的算法的平均時間復雜度為O(1)。故本題選D。

2、現有非空雙向鏈表L，其結點結構為

prer是指向直接前驅結點的指針，next是指向直接后繼結點的指針。若要在L中指針p所指向的結點（非尾結點）之后插入指針s指向的新結點，則在執行了語句序列：“s->next=p->next;p->next=s;”，后，還要執行（  ）。

A.s->next->prer=p;s->prer=p;

B.p->next->prer=s;s->prer=p;

C.s->prer=s->next->prer;s->next->prer=s;

D.p->next->prer=s->prer;s->next->prer=p;

【答案】C

【考點】本題考查雙向鏈表的插入操作。

【解析】對于A，s->next->prer此時指向的是s而非p，因此A錯誤。對于B，經過p->next=s這一步之后，p->next此時指向s，p->next->prer=p而非s，因此B錯誤。對于C，s->prer指向p，而s->next->prer指向s，該語句等價于s->prer=p，第二步s->next->prer指向s正確，因此C正確。對于D，s->prer指向null，s->next->prer指向s而非p，因此D錯誤。