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

1、下列對(duì)順序存儲(chǔ)的有序表（長度為n）實(shí)現(xiàn)給定操作的算法中平均時(shí)間復(fù)雜度為O（1）的是（  ）。

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

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

C.刪除第i個(gè)元素的算法

D.獲取第i個(gè)值的算法

【答案】D

【考點(diǎn)】本題考查順序表的基本操作。

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

2、現(xiàn)有非空雙向鏈表L，其結(jié)點(diǎn)結(jié)構(gòu)為

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

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

【考點(diǎn)】本題考查雙向鏈表的插入操作。

【解析】對(duì)于A，s->next->prer此時(shí)指向的是s而非p，因此A錯(cuò)誤。對(duì)于B，經(jīng)過p->next=s這一步之后，p->next此時(shí)指向s，p->next->prer=p而非s，因此B錯(cuò)誤。對(duì)于C，s->prer指向p，而s->next->prer指向s，該語句等價(jià)于s->prer=p，第二步s->next->prer指向s正確，因此C正確。對(duì)于D，s->prer指向null，s->next->prer指向s而非p，因此D錯(cuò)誤。