1. 元素$R_1​、R_2​、R_3​、R_4​、_R5​$入栈的顺序为$R_1​、R_2​、R_3​、R_4​、R_5​$。如果第1个出栈的是$R_3$​，那么第5个出栈的不可能是？ {{ select(1) }}

• R1
• R2
• R4
• R5
  
  

2. 双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是？ {{ select(2) }}

• 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;
  
  

3. 填空题

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

4. 在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度是？ {{ select(4) }}

• $O(1)$
• $O(log n)$
• $O(n)$
• $O(n log n)$
  
  

5. （）是一种先进先出的线性表？ {{ select(5) }}

• 栈
• 队列
• 哈希表（散列表）
• 二叉树
  
  

6. 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素d已经出栈，则可能的入栈顺序是？ {{ select(6) }}

• a, d, c, b
• b, a, c, d
• a, c, b, d
• d, a, b, c
  
  

7. 下图中所使用的数据结构是？

{{ select(7) }}

• 哈希表
• 栈
• 队列
• 二叉树
  
  

8. 链表不具备的特点是？ {{ select(8) }}

• 可随机访问任何一个元素
• 插入、删除操作不需要移动元素
• 无需事物估计存储空间大小
• 所需存储空间与存储元素个数成正比
  
  

9. 线性表若采用链表存储结构，要求内存中可用存储单元地址？ {{ select(9) }}

• 必须连续
• 部分地址必须连续
• 一定不连续
• 连续不连续均可
  
  

10. 今有一空栈 S，对下列待进栈的数据元素序列 a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈， 进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为？ {{ select(10) }}

• f
• c
• a
• b
  
  

11. 对于入栈顺序为 a,b,c,d,e,f,g 的序列，下列（ ）不可能是合法的出栈序列？ {{ select(11) }}

• a, b, c, d, e, f, g
• a, d, c, b, e, g, f
• a, d, b, c, g, f, e
• g, f, e, d, c, b, a
  
  

12. 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的？ {{ select(12) }}

• 5 4 3 6 1 2
• 4 5 3 1 2 6
• 3 4 6 5 2 1
• 2 3 4 1 5 6
  
  

13. 链表和数组的区别包括？ {{ select(13) }}

• 数组不能排序，链表可以
• 链表比数组能存储更多的信息
• 数组大小固定，链表大小可动态调整
• 以上均正确
  
  

14. 假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据？ {{ select(14) }}

• 2
• 3
• 4
• 6
  
  

15. 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）？ {{ select(15) }}

• 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;
  
  

16. 假设有一个链表的节点定义如下：

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？

{{ select(16) }}

• 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;