-
关注“优题吧”，分配平台账号.
考研2023年暨南大学( )
若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是【 】
A、单链表
B、仅有头指针的单循环链表
C、双向链表
D、仅有尾指针的单循环链表
考研2023年计算机统考( )
现有非空双向链表 L，其结点结构为：prer|data|next。
prer 是指向前直接前驱结点的指针，next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点（ 非尾结点） 之后插入指针 s 指向的新结点， 则在执行了语句序列： “s->next=p->next;p->next=s”后，还要执行【 】
A、s->next->prev=p; s->prev=p;
B、p->next->prev=s;s->prev=p;
C、s->prev=s->next->prev; s->next->prer=s;
D、p->next->prev=s->prev; s->next->prev=p;
在双向链表中插入一个结点，需要修改4个指针，修改顺序没有强制要求。由于题中已经修改了两个指针，故只需按此思路继续修改另两个指针即可。
假设链表L中p的后继为q，如下图所示：
考虑新加入的结点s，初始四个指针的状态为：
p->next = q; q->prev = p; s->next = null; s->prev = null;
按题目要求，把s插入p之后，得目标图如下：
此时指针状态为：
p->next = s; q->prev = s; s->next = q; s->prev = p;
先按照题目要求执行前两步：
①s->next = q; 注意此时 q = p->next，即 s->next = p->next; 此时变为下图：
②p->next = s; 此时变为下图：
此时，还有两条线没有连，要得到目标图还需要连接： s->prev = p; 和 q->prev = s（注意此时 q = s->next，即 s->next->prev = s）；
A选项，等价于 q->prev = p; s->prev = p; 第一句错误。
B选项，等价于 s->prev = s; s->prev = p; 第一句错误。
C选项，等价于 s->prev = p; q->prev = s; 正确。
D选项，等价于 s->prev = s->prev; q->prev = p; 两句均错误。
考研2023年计算机统考( )
下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】
A、查找包含指定值元素的值
B、插入包含指定值元素的算法
C、删除第 i 个元素的算法
D、获取第 i 个值的算法
顺序表即顺序存储存储的线性表，其特点是：支持随机访问，但插入和删除比较麻烦。
链表即链式存储的线性表，其特点是：插入和删除比较容易，但不支持随机访问。
顺序表中只有随机访问元素时间复杂度为O(1) ，即根据元素位置（下标）访问元素时间复杂度为 O(1)。顺序存储的有序表即有序数组。
选项A，在有序数组中查找包含指定值的元素的位置最快的方法是用二分查找，时间复杂度为 O(logn) .
选项B，在有序数组中插入包含指定值的元素最快的方法是：首先用二分查找找到插入元素的位置，时间复杂度为 O(logn)；然后把位于插入元素后面的元素的位置后移一格，平均时间复杂度为 O(n). 综上，总的时间复杂度为 O(n).
选项C，删除第 i 个元素的最快的方法是：首先利用顺序表支持随机访问的性质找到第 i 个元素并删除，时间复杂度为 O(1)；然后把位于插入元素后面的元素的位置前移一格，平均时间复杂度为 O(n). 综上，总的时间复杂度为 O(n).
考试2016年秋程序员软考( )
若某线性表长度为n且采用顺序存储方式，则运算速度最快的操作是【 】。
A、查找与给定值相四配的元素的位置
B、查找并返回第i个元素的值(1≤i≤n)
C、删除第i个元素(1≤i≤n)
D、在第i个元素(1≤i≤n)之前插入一个新元素
考试2016年秋程序员软考( )
线性表采用单循环链表存储的主要特点是【 】
A、从表中任一结点出发都能遍历整个链表
B、可直接获取指定结点的直接前驱和直接后继结点
C、在进行删除操作后，能保证链表不断开
D、与单链表相比，更节省存储空间