要求： 所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题2 分，共 20 小题，共计 40 分）1. 某算法的空间复杂度为O(1)，则。A.该算法执行不需要任何辅助空间B.该算法执行所需辅助空间大小与问题规模n 无关C.该算法执行不需要任何空间D.该算法执行所需全部空间大小与问题规模n 无关2. 在长度为 n 的顺序表中插入一个元素，对应算法的时间复杂度为。A.O(1) B.O(log 2n) C.O( n) D.O( n2) 3. 设线性表中有n 个元素，以下运算中，在单链表上实现要比在顺序表上实现效率更高。A.删除指定位置元素的后一个元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k 个元素D.交换第 i 个元素和第n- i+1 个元素的值（ i=1，2，⋯， n）4. 以下数据结构中元素之间为非线性关系的是。A.栈B.队列C.线性表D.以上都不是5. 若一个栈用数组data[1..n]存储，初始栈顶指针top 为 n+1，则以下元素x 进栈的正确操作是。A.top++;data[top]=x; B.data[top]=x;top++; C.top-- ;data[top]=x; D.data[top]=x;top -- ; 6. 若某循环队列有队首指针front 和队尾指针rear，在队不满时进队操作仅会改变。A.front B.rear C.front 和 rear D.以上都不队7. 设循环队列中数组的下标是0～N- 1，其队头、 队尾指针分别为f 和 r（f 指向队首元素的前一位置，r 指向队尾元素） ，则其元素个数为。A.r- fB.r- f- 1 C.(r- f)％N+1 D.(r- f+N)％N8. 设树 T 的度为 4，其中度为1、2、3、4 的结点个数分别为4、2、1、1，则 T 中的叶子结点个数是。A.5 B.6 C.7 D.8 9. 一棵哈夫曼树中共有199 个结点，它用于多少个字符的编码。A.99 B.100 C.101 D.199 10. 设森林 F 中有 4 棵树，第 1、2、3、4 棵树的结点个数分别为a、b、c、d，将森林F 转换为一颗二叉树B，则二叉树B 根结点的左子树上的结点个数是。A.a- 1 B.aC. a+b+cD.b+c+d11. 下列关于图的叙述中，正确的是。Ⅰ. 回路是简单路径Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路A. 仅ⅡB. 仅Ⅰ、ⅡC. 仅ⅢD. 仅Ⅰ、Ⅲ12. 以下关于有向图的说法中，正确的是。A.强连通图是任何顶点到其他所有顶点都有边B.完全有向图一定是强连通图C.有向图中任一顶点的入度等于出度D.有向图边集的子集和顶点集的子集可构成原有向图的子图13.无向图...
