1 安徽大学2014-2015 学年第一学期《数据结构》期末考试试卷（A 卷） （含参考答案） 一、 单项选择题（本大题共15 小题，第小题2 分，共30 分）在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。 1. 算法必须具备输入、输出和 [ C ] A. 计算方法 B. 排序方法 C．解决问题的有限运算步骤 D. 程序设计方法 2. 有n 个节点的顺序表中，算法的时间复杂度是O(1)的操作是 [ A ] A. 访问第i 个节点（1≤i≤n） B. 在第i 个节点后插入一个新节点（1≤i≤n） C. 删除第i 个节点（1≤i≤n） D. 将n 个节点从小到大排序 3．单链表的存储密度 [ C ] A．大于 1 B. 等于 1 C．小于 1 D. 不能确定 4. 循环队列SQ 的存储空间是数组 d[m]，队头、队尾指针分别是front 和rear，则执行出队后其头指针 front 值是 [ D ] A．front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m 5. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 [ B ] A. O(1) B. O(n) C. O(n2) D. O(nlogn) 6 设二 维 数组A[0..m-1][0..n-1] 按 行 优 先 顺序存 储 ，则 元 素A[i][j] 的地 址 为 [ B ] A． LOC(A[0][0])+(i*m+j) B．LOC(A[0][0])+(i*n+j) C. LOC(A[0][0])+[(i-1)*n+j-1] D. LOC(A[0][0])+[(i-1)*m+j-1] 7．设将整数1,2,3,4,5 依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是 [ B ] A．23415 B. 54132 C．23145 D. 15432 2 8. 一个非空广义表的表头 [ D ] A．一定是子表 B. 一定是原子 C．不能是子表 D. 可以是原子，也可以是子表 9．具有n 个节点的完全二叉树的深度为 [ A ] A．lo g2(n +1) -1 B. lo g2n +1 C. lo g2n D. lo g2n 10. 若要惟一地确定一棵二叉树，只需知道该二叉树的 [ D ] A．前序序列 B. 中序序列 C．前序和后序序列 D. 中序和后序序列 11．在一个无向图中，所有顶点的度数之和等于图的边数的 倍 [ C ] A．1/2 B. 1 C. 2 D. 4 12. 拓扑排序运算只能用于 [ C ] A．带权有向图 B. 连通无向图 C．有向无环图 D. 无向图 13 ．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 [ D ] A．希...
