共 8 页 第 1 页 东 南 大 学 考 试 卷 （ A 卷） 课 程 名 称 数据结构 考试学期 08-09-3 得分 适 用 专 业 吴健雄学院电类 考 试 形 式 半开卷 考试时间长度 120分钟 一、选择题（每题 1 分，共 5 分） 1．下面有关链栈的描述，对常规情况正确的是 （ ） A．在链头插入，链尾删除。 B．在链尾插入，链头删除。 C．在链尾插入，链尾删除。 D．在链头插入，链头删除。 2．对线性表进行对半搜索时，要求线性表必须（ ） A．以数组方式存储 B．以数组方式存储并按关键码排序 C．以链表方式存储 D．以链表方式存储并按关键码排序 3．对包含 n 个元素的散列表进行搜索，平均搜索长度为（ ） A．O(log2n) B．O(n) C．不直接依赖于 n D．三者均不是 4．在同一个有向图中，所有结点的入度和与出度和之比为（ ） A．1 B．2 C．1/2 D．都不对 5．在具有 n 个顶点的无向图中，要连通全部顶点至少需要（ ）条边。 A．n B．n+1 C．n-1 D．n/2 二、判断题（每题 1 分，共 5 分） 1．链式存储的线性表所有存储单元的地址可连续可不连续。 （ ） 2．存储有向图的邻接矩阵是对称的，所以可以仅存矩阵上三角部分。 （ ） 3．在采用闭散列法解决冲突时，不要立刻做物理删除，否则搜索时会出错。 （ ） 4．二叉树中序遍历结果序列的最后一个结点必是前序遍历的最后一个结点。 （ ） 5．堆排序的时间复杂度是 O(n log2 n)，但需要额外存储空间。 （ ） 三、填空题（每空1 分，第 1 空、第 2 空为 2 分，共 11 分） 1．中缀表达式“(a+b)*d+e/(f+a*d)+c)”所对应的后缀表达式为 （1） 2．后缀表达式“ab&&ef>!||”所对应的中缀表达式为（2） 学号 姓名 密 封 线 自 觉 遵 守 考 场 纪 律 如 考 试 作 弊 此 答 卷 无 效 共 8 页 第2 页 3．高度为h 的二叉树最多可以有多少结点（3） 4．若对一棵完全二叉树从0 开始编号，并按此编号把它顺序存储到一维数组a 中，则a[i]元素的左孩子结点为(4) ，右孩子结点为(5) ，双亲结点为(6) 。 5．对用邻接矩阵表示的图进行任何一种遍历时，其时间复杂度为(7) 。对用邻接表表示的图进行任何一种遍历时，其时间复杂度为(8) 。 6．折半插入排序的时间复杂度为(9) 。 四、简答简述题（每题 8 分，共24 分） 1．设有一组关键码输入序列{ 55，31，12，37，46，73，63，...
