爱迪国际c++章节测试-线性表

*
1.单选题
元素𝑅1、𝑅2、𝑅3、R4、𝑅5入栈的顺序为𝑅1、𝑅2、𝑅3、𝑅4、𝑅5,如果第1个出栈的是𝑅3
，那么第5个出栈的不可能是（ ）。
A. 𝑅1
B. 𝑅2
C. 𝑅4
D. 𝑅5
​
*
2.单选题
双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是（ ）。

A. p-＞rlink-＞llink = p-＞rlink;p-＞llink-＞rlink = p-＞llink; delete p;
B. p-＞llink-＞rlink = p-＞rlink;p-＞rlink-＞llink = p-＞llink; delete p;
C.p-＞rlink-＞llink = p-＞llink;p-＞rlink-＞llink-＞rlink = p-＞rlink; delete p;
D. p-＞llink-＞rlink = p-＞rlink;p-＞llink-＞rlink-＞llink = p-＞llink; delete p;
*
3.填空题

队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素1、2、3入队，元素1出队后，此刻的队列快照是"2 3"。当元素2、3也出队后，队列快照是""，即为空。现有3个正整数元素依次入队、出队。已知它们的和为8，则共有_________种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，"5 2 1"、"4 2 2"、""都是可能的队列快照；而"7"不是可能的队列快照，因为剩下的2个正整数的和不可能是1。

*
4.单选题
在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度是（ ）。
A. O(1)
B. O(logn)
C. O(n)
D. O(nlogn)
*
5.单选题
（）是一种先进先出的线性表。
A. 栈
B. 队列
C. 哈希表（散列表）
D. 二叉树
*
6.单选题
如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素
𝑑已经出栈，则可能的入栈顺序是（ ）。

A ：a, d, c, b
B ：b, a, c, d
C: a, c, b, d
D: d, a, b, c
*
7.单选题
下图中所使用的数据结构是( )。
A. 哈希表
B. 栈
C. 队列
D. 二叉树
*
8.单选题
链表不具备的特点是( )。
A.可随机访问任何一个元素
B.插入、删除操作不需要移动元素
C.无需事先估计存储空间大小
D.所需存储空间与存储元素个数成正比
*
9.单选题
线性表若采用链表存储结构，要求内存中可用存储单元地址( )。
A. 必须连续
B. 部分地址必须连续
C. 一定不连续
D. 连续不连续均可
*
10.单选题
a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈， 进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为()。
A. f
B. c
C. a
D. b
*
11.单选题
对于入栈顺序为 a,b,c,d,e,f,g 的序列，下列（ ）不可能是合法的出栈序列。
A a, b, c, d, e, f, g
B a, d, c, b, e, g, f
C a, d, b, c, g, f, e
D g, f, e, d, c, b, a
*
12.单选题
链表不具有的特点是()
A.插入删除不需要移动元素
B.不必事先估计存储空间
C.所需空间与线性表长度成正比
D.可随机访问任一元素
*
13.单选题
链表不具有的特点是( )。
A. 可随机访问任一元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比
*
14.单选题
有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。
A 5 4 3 6 1 2
B 4 5 3 1 2 6
C 3 4 6 5 2 1
D 2 3 4 1 5 6
*
15.单选题
链表和数组的区别包括（ ）。
A 数组不能排序，链表可以
B 链表比数组能存储更多的信息
C 数组大小固定，链表大小可动态调整
D 以上均正确
*
16.单选题
假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。
A 2
B 3
C 4
D 6
*
17.单选题
以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）:（ ）。
A p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D s-＞next=p-＞next; p-＞next-＞prev=s; s-＞prev=p; p-＞next=s;
*
18.单选题
假设有一个链表的节点定义如下:现在有一个指向链表头部的指针:Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的?
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;
*
19.单选题
链表不具有的特点是( )。
A. 不必事先估计存储空间
B. 可随机访问任一元素
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比
问卷星提供技术支持
举报