1、数据结构与算法练习试卷 4及答案与解析 1 设只包含根节点的二叉树的高度为 0，则高度为 k的二叉树的最小节点数为_。 2 在完全二叉树的顺序存储中，若节点 i有左子女，则其左子女是节点 _。 3 二叉树是节点的有限集合，这个有限集合或者为 _，或者由一个根节点及两棵不相交的，分别称作为根的左子树和右子树的二叉树组成。 4 m阶 B树的根节点若不是叶节点，那么它至多有 m棵子树，至少有 _棵子树。 5 对于关键码序列 18， 30， 35， 10， 46， 38， 5， 40进行堆排序 (假 定堆的根节点为最小关键码 )，在初始建堆过程中需进行的关键码交换次数为 _。 6 在有 n个节点的二叉
2、树的 llink-rlink法存储表示中， n个节点所含有的 2n个指针中，必有 _个为空指针。 7 对于给出的一组权 w=5， 6， 8， 12，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 _。 8 对 n个记录的文件进行快速排序，最坏情况下的执行时间为 _。 9 散列法存储中处理碰撞的方法主要有两类：拉链法和 _。 10 某二叉树节点的对称序序列为 A、 B、 C、 D、 E、 F、 G，后序序列为 B、 D、C、 A、 F、 G、 E。则该二叉树对应的树林包括 _棵树。 11 对线性表进行二分法检索，其前提条件是：线性表以 _方式存储，并且按关键码值排好序。 数据结构与算法练习试
3、卷 4答案与解析 1 【正确答案】 k+1 【知识模块】 数据结构与算法 2 【正确答案】 2i 【知识模块】 数据结构与算法 3 【正确答案】 空集 【知识模块】 数据结构与算法 4 【正确答案】 2 【知 识模块】 数据结构与算法 5 【正确答案】 3 【知识模块】 数据结构与算法 6 【正确答案】 n+1 【知识模块】 数据结构与算法 7 【正确答案】 61 【知识模块】 数据结构与算法 8 【正确答案】 O(n2) 【知识模块】 数据结构与算法 9 【正确答案】 开放定址法 【知识模块】 数据结构与算法 10 【正确答案】 2 【知识模块】 数据结构与算法 11 【正确答案】 顺序 【知识模块】 数据结构与算法
