选择题（每题 10 分，共计 100 分）

1. 下列关于线性表的叙述中，错误的是？ {{ select(1) }}

• 顺序表在内存中的存储单元地址必须连续
• 链表在内存中的存储单元地址连续不连续均可
• 顺序表插入元素不需要移动任何元素的位置
• 双向链表插入元素不需要移动任何元素的位置

2. 3.往一个初始为空的顺序表中依次插入3,5,2,4,1，且满足任意时刻顺序表中的元素从左至右都是升序的，则插入过程中总共移动了（ ）次元素。 {{ select(2) }}

• 4
• 7
• 8
• 10

3. “FIFO,LILO”形容的是哪一个数据结构？ {{ select(3) }}

• 顺序表
• 双向链表
• 栈
• 队列

4.设栈S的初始状态为空，元素 a, b, c, d, e, f, g 依次入栈S，出栈的序列为 c, d, f, e, g, b, a，则栈S的容量至少应该是？ {{ select(4) }}

• 3
• 4
• 5
• 6

5.【2020年第12题】独根树的高度为 1。具有 61 个结点的完全二叉树的高度为？ {{ select(5) }}

• 7
• 8
• 5
• 6

6. 已知包含7个节点的二叉树的前序遍历序列为1,2,4,3,5,6,7，中序遍历序列为4,2,1,5,3,7,6，则其后序遍历序列为（ ） {{ select(6) }}

• 2,3,4,5,6,7,1
• 2,4,3,5,6,7,1
• 3,5,6,7,4,1,2
• 4,2,5,7,6,3,1

7. 完全二叉树的顺序存储方案，是指将完全二叉树的节点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根节点存放在数组的1号位置，则第k号节点的右儿子节点如果存在的话，应当存放在数组的（ ）号位置。 {{ select(7) }}

• k+1
• k+2
• 2k+1
• 2k+2

8. 【2020年第8题】有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图 {{ select(8) }}

• 9
• 10
• 11
• 12

9.关于拓扑排序，下面说法正确的是？ {{ select(9) }}

• 所有连通的有向无环图都可以实现拓扑排序
• 对同一个图而言，拓扑排序的结果是唯一的
• 拓扑排序中入度为0的节点总会排在入度大于0的节点的前面
• 拓扑排序结果序列中的第二个节点一定是入度为1的点

10. 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有10个顶点，则它共有（ ）条边。

{{ select(10) }}

• 9
• 45
• 55
• 90