数据结构1: 线性表
1.单选题 [GESP202309【6级】/GESP样题【7级】] 有些算法或数据结构在C/C++语言中使用指针实现，一个典型的例子就是链表。因此，链表这一数据结构在C/C++语言中只能使用指针来实现。 {{ select(1) }}
- 正确
- 错误
2.单选题 [NOIP普及组2015/NOIP提高组2015] 线性表若采用链表存储结构，要求内存中可用存储单元地址（ ） {{ select(2) }}
- 必须连续
- 部分地址必须连续
- 一定不连续
- 连续不连续均可
3.单选题 [CSP-J2019/CSP-J2020/NOIP普及组2014/NOIP普及组2015] 链表不具有的特点是（） {{ select(3) }}
- 插入删除不需要移动元素
- 不必事先估计存储空间
- 所需空间与线性表长度成正比
- 可随机访问任一元素
4.单选题 [CSP-J2022] 链表和数组的区别包括（ ）。 {{ select(4) }}
- 数组不能排序，链表可以
- 链表比数组能存储更多的信息
- 数组大小固定，链表大小可动态调整
- 以上均正确
5.单选题 [GESP202406【5级】] 链表的存储空间物理上可以连续，也可以不连续。 {{ select(5) }}
- 正确
- 错误
6.单选题 [GESP202406【5级】] 数组和链表都是线性表，链表的优点是插入删除不需要移动元素，并且能随机查找。 {{ select(6) }}
- 正确
- 错误
7.单选题 [GESP样题【5级】] 在任何场景下，链表都是比数组更优秀的数据结构。 {{ select(7) }}
- 正确
- 错误
8.单选题 [GESP202406【5级】] 如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。 {{ select(8) }}
- 正确
- 错误
9.单选题 [GESP202406【5级】] 如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结，则该双向链表构成循环链表。 {{ select(9) }}
- 正确
- 错误
10.单选题 [GESP202309【5级】] 在C++中，通过恰当的实现，可以将链表首尾相接，形成循环链表。 {{ select(10) }}
- 正确
- 错误
11.单选题 [GESP样题【5级】] 下列关于链表说法，正确的是（ ）。 {{ select(11) }}
- 不能用数组来实现链表
- 在链表头部插入元素的时间复杂度是O(1)
- 循环链表使得任意一个结点都可以很方便地访问其前驱与后继
- 从双向链表的任意一个节点出发，并不一定能够访问到所有其他节点
12.单选题 [GESP样题【7级】/GESP202309【5级】] 在C++中，可以使⽤二分法查找链表中的元素。 {{ select(12) }}
- 正确
- 错误
13.单选题 [GESP样题【6级】] 将N个数据按照从小到大顺序存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)。 {{ select(13) }}
- 正确
- 错误
14.单选题 [NOIP提高组2014] 对长度位 n 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为 ( ). {{ select(14) }}
- n/2
- (n+1)/2
- (n-1)/2
- n/4
15.单选题 [GESP202406【8级】] 使用单链表和使用双向链表，查找元素的时间复杂度相同。 {{ select(15) }}
- 正确
- 错误
16.单选题 [GESP202406【6级】] n个节点的双向循环链表，在其中查找某个节点的平均时间复杂度是O(logn)。 {{ select(16) }}
- 正确
- 错误
17.单选题 [GESP202309【6级】] N个节点的双向循环链，在其中查找某个节点的平均时间复杂度是（ ）。 {{ select(17) }}
- O(1)
- O(N)
- 0(logN)
- O(N2)
18.单选题 [NOIP普及组2011] 在含有 n 个元素的双向链表中查询是否存在关键字为 k的元素，最坏情况下运行的时间复杂度是( )。 {{ select(18) }}
- O(1)
- O(log n)
- O(n)
- O(n log n)
19.单选题 [GESP202406【5级】] 小杨采用如下双链表结构保存他喜欢的歌曲列表：
{{ select(19) }}
- O(1)
- O(n)
- O(logn)
- O(n2)
20.单选题 [GESP202403【5级】] 单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。 {{ select(20) }}
- 正确
- 错误
21.单选题 [GESP202403【6级】] 删除单向链表中的节点，只需知道待删除节点的地址即可，无需访问前一个节点。 {{ select(21) }}
- 正确
- 错误
22.单选题 [CSP-J2023] 假设有一个链表的节点定义如下struct Node { int data; Node* next;} 现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？ {{ select(22) }}
- Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
- Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
- Node* newNode = new Node; newNode->data = 42; head->next = newNode;
- Node* newNode = new Node; newNode->data = 42; newNode->next = head;
23.单选题 [NOIP提高组2014] 有以下结构体说明和变量定义，如图所示，指针 p、q、r 分别指向一个链表中的三个续 结点。 struct node { int data; node *next; }*p,*q,*r; 现要将 q 和 r 所指的结点先后位置交换，同时要保持链表的连续，以下程序段中错误的是（ ）。 {{ select(23) }}
- q->next = r->next; p-> next = r; r->next = q;
- p->next = r; q->next = r->next; r->next = q;
- q->next = r->next; r->next = q; p->next = r;
- r->next = q; q->next = r->next; p->next = r;
24.单选题 [NOIP普及组2010/NOIP提高组2010] 双向链表中有两个指针域 llink 和 rlink ，分别指向该结点的前驱及后继。 设 p 指向 链表中的一个结点，它的左右结点均非空。现要求删除结点 p ，则下面语句序列中错误的是 （ ）。 {{ select(24) }}
- p->rlink->llink = p->rlink; p->llink->rlink = p->llink; delete p;
- p->llink->rlink = p->rlink; p->rlink->llink = p->llink; delete p;
- p->rlink->llink = p->llink; p->rlink->llink->rlink = p->rlink; delete p;
- p->llink->rlink = p->rlink; p->llink->rlink->llink = p->llink; delete p;
25.单选题 [NOIP提高组2015] 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的 一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ）。 {{ select(25) }}
- p->llink = q; q->rlink = p; p->llink->rlink = q;q->llink = p->llink;
- q->llink = p->llink; p->llink->rlink = q; q->rlink = p;p->llink = q->rlink;
- q->rlink = p; p->rlink = q;p->llink->rlink = q; q->rlink = p;
- p->llink->rlink = q; q->rlink = p;q->llink = p->llink; p->llink = q;
26.不定项选择题 [NOIP提高组2009] 在带尾指针（链表指针 clist 指向尾结点）的非空循环单链表中每个结点都以 next 字段的指针指向下一个节点。假定其中已经有 2 个以上的结点。下面哪些说法是正确的： {{ multiselect(26) }}
- 如果 p 指向一个待插入的新结点，在头部插入一个元素的语句序列为：p->next = clist->next; clist->next = p;
- 如果 p 指向一个待插入的新结点，在尾部插入一个元素的语句序列为：p->next = clist；clist->next = p;
- 在头部删除一个结点的语句序列为：p = clist->next; clist->next = clist->next->next; deletep;
- 在尾部删除一个结点的语句序列为。p = clist; clist = clist ->next; delete p;
27.单选题 [CSP-J2022] 以下哪组操作能完成在双向循环链表结点p之后插入结点s的效果（其中，next域为结点的直接后继，prev域为结点的直接前驱）：（ ）。 {{ select(27) }}
- p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
- p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
- s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
- s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
28.单选题 [GESP202406【5级】] 小杨采用如下双链表结构保存他喜欢的歌曲列表： struct dl_node { string song; dl_node* next; dl_node* prev; }; 小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填写的代码为（ ）。 void insert(dl_node* head, string my_song) { p = new dl_node; p->song = my_song; p->prev = nullptr; p->next = head; if (head != nullptr) { ________________________________ // 在此处填入代码 } head = p; } {{ select(28) }}
- head->next->prev = p;
- head->next = p;
- head->prev = p;
- 触发异常，不能对空指针进行操作
29.单选题 [GESP202312【5级】] 同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。 {{ select(29) }}
- 正确
- 错误
30.单选题 [GESP202312【6级】] 同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。 {{ select(30) }}
- 正确
- 错误