要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共20小题，共计40分）
1某算法的空间复杂度为O1，则
。
A该算法执行不需要任何辅助空间
B该算法执行所需辅助空间大小与问题规模
无关
C该算法执行不需要任何空间
D该算法执行所需全部空间大小与问题规模
无关
2在长度为
的顺序表中插入一个元素，对应算法的时间复杂度为
。
AO1
BOlog2

CO

DO
2
3设线性表中有
个元素，以下运算中，
在单链表上实现要比在顺序表上实现
效率更高。
A删除指定位置元素的后一个元素
B在最后一个元素的后面插入一个新元素
C顺序输出前k个元素
D交换第i个元素和第
i1个元素的值（i1，2，…，
）
4以下数据结构中元素之间为非线性关系的是
。
A栈
B队列
C线性表
D以上都不是
5若一个栈用数组data1
存储，初始栈顶指针top为
1，则以下元素x进栈的正
确操作是
。
AtopdatatopxCtopdatatopx
BdatatopxtopDdatatopxtop
6若某循环队列有队首指针fro
t和队尾指针rear，在队不满时进队操作仅会改
变
。
Afro
t
Brear
Cfro
t和rearD以上都不队
7设循环队列中数组的下标是0～N1，其队头、队尾指针分别为f和r（f指向队首元
素的前一位置，r指向队尾元素），则其元素个数为
。
Arf
Brf1
Crf％N1DrfN％N
8设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中的叶子结点个数是。
A5
B6
C7
D8
9一棵哈夫曼树中共有199个结点，它用于多少个字符的编码
。
A99
B100
C101
D199
10设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为a、b、c、d，将森林
fF转换为一颗二叉树B，则二叉树B根结点的左子树上的结点个数是
Aa1
Ba
Cabc
。Dbcd
11下列关于图的叙述中，正确的是
。
Ⅰ回路是简单路径
Ⅱ存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ若有向图中存在拓扑序列，则该图不存在回路
A仅Ⅱ
B仅Ⅰ、Ⅱ
C仅Ⅲ
D仅Ⅰ、Ⅲ
12以下关于有向图的说法中，正确的是
。
A强连通图是任何顶点到其他所有顶点都有边
B完全有向图一定是强连通图
C有向图中任一顶点的入度等于出度
D有向图边集的子集和顶点集的子集可构成原有向图的子图
13无向图的邻接矩阵是一个
。
A对称矩阵
B零矩阵
C上三角矩阵
D对角矩阵
14如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图
一定是
。
A完全图
B连通图
C有回r