C语言【数据结构】顺序表、链表【选择题】_在一个长度为n(n>1)的单链表上,设有头和尾两个指针,执行( )操作与链表的长度有关

目录 

1. 在长度为 n 的顺序表下标为 i 的位置前插入一个元素（1 ≤ i ≤ n+1），元素的移动次数为（B）

2.下列关于链表的说法哪个是正确的？（A）

3.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（C）

4.下列判断循环双向链表为空的语句中，正确的是（C）

5. 在长度为n(n>1)的单链表上，设有头和尾两个指针，执行（D）操作与链表的长度有关。

6.关于链表和顺序表间的区别，叙述错误的是（D）

7.在一个循环双向链表中，要在p所指的节点之前插入s所指节点，以下代码正确的执行次序是（A）  

8.将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为（A）

9.在一个长度为n的顺序表中删除第i个元素，要移动_______个元素。如果要在第i个元素前插入一个元素，要后移_________个元素，应选择（A）

10.以下属于链表的优点的是（B）

---

1. 在长度为 n 的顺序表下标为 i 的位置前插入一个元素（1 ≤ i ≤ n+1），元素的移动次数为（B）

A.n - i + 1

B.n - i

C.i

D.i - 1

解释：

        顺序表插入元素，需要移动元素，这里需要把[i, n - 1]区间的元素全部向后移动一次，故移动的次数为n - 1 - i + 1 = n - i

2.下列关于链表的说法哪个是正确的？（A）

A.插入或删除时，无需移动其他元素

B.数据在内存中一定是连续的

C.需要事先估计存储空间

D.可以随机访问表内的元素

解释：

A：链表插入删除元素只需要修改指针指向，不需要移动元素

B：链表是用指针链接前后节点，数据在内存中不一定连续

C：每次插入元素，都是先出开一个节点的空间，不需要事先估计存储空间

D：链表没有索引，不能随机访问

3.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（C）

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

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

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

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

解释：

要先把s和p的next节点链接，再更新p的next为s，否则可能会出现找不到节点的情况

4.下列判断循环双向链表为空的语句中，正确的是（C）

A.head==NULL;

B.head->next==NULL;

C.head->next==head;

D.head!=NULL;

 解释：

        双向带头循环链表中，head不是存放有效数据的节点，如果只有一个head节点，说明链表为空。

5. 在长度为n(n>1)的单链表上，设有头和尾两个指针，执行（D）操作与链表的长度有关。

A.在单链表第一个元素前插入一个新元素

B.在单链表最后一个元素后插入一个新元素

C.删除单链表中的第一个元素

D.删除单链表中的最后一个元素

 解释：

A：头插，不需要遍历链表

B：尾插，也不需要遍历链表

C：头删，不需要遍历链表

D：尾删，需要遍历单链表，找到尾节点的前一个节点，所以与长度有关

6.关于链表和顺序表间的区别，叙述错误的是（D）

A.链表和顺序表都属于线性表

B.链表不能随机访问其中的某个元素，顺序表可以

C.链表能做的事，顺序表都可以完成，只是操作方法不同，效率不同

D.链表在进行插入和删除的时候，速度总是比顺序表快

 解释：

D：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。

7.在一个循环双向链表中，要在p所指的节点之前插入s所指节点，以下代码正确的执行次序是（A）  

①p->prev->next=s;

②p->prev=s;

③s->prev=p->prev;

④s->next=p;

.........

A.④③①②

B.④③②①

C.②①④③

D.②①③④

 解释：

        要注意避免出现野指针的情况，因此一定不能是②①开头，否则会导致无法找到p节点的前一个节点，所以是④③开头。

        下一个一定是先①后②，①是让p的上一个节点的next链接上新节点s，①完成链接之后，才应该到②，②是让p的前一个节点变成s

8.将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为（A）

A.O(m)

B.O(1)

C.O(N)

D.O(m+n)

解释：

        将长度为n的链表连接在长度为m的单链表之后，只需要找到链表m的尾节点，然后把链表n连接在链表m的尾节点后面即可，因此时间复杂度为O(m)

9.在一个长度为n的顺序表中删除第i个元素，要移动_______个元素。如果要在第i个元素前插入一个元素，要后移_________个元素，应选择（A）

A. n - i, n - i + 1

B. n - i + 1, n - i

C. n - i, n - i

D. n - i + 1, n - i + 1

解释：

        要删除第i个元素，就将第i元素后面的元素依次往前覆盖，因此是n - i

        要在第i个元素前插入一个元素，这里需要把[i, n - 1]区间的元素全部向后移动一次，故移动的次数为n - 1 - i + 1 = n - i

10.以下属于链表的优点的是（B）

A.用数组可方便实现

B.插入操作效率高

C.不用为节点间的逻辑关系而增加额外的存储开销

D.可以按元素号随机访问

解释：

A：顺序表是用数组实现的，链表不适合用数组实现

B：插入效率高是链表的优点

C：链表需要增加额外的指针域

D：链表不能随机访问