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错误。