【计算机类职业资格】数据结构与算法练习试卷5及答案解析.doc

1、数据结构与算法练习试卷 5 及答案解析(总分：24.00，做题时间：90 分钟)一、填空题(总题数：12，分数：24.00)1.填空题（每空）请将每一个空的正确答案写在答题卡上。（分数：2.00）_2.设只包含根节点的二叉树的高度为 0，则高度为 k 的二叉树的最小节点数为 1。（分数：2.00）填空项 1:_3.在完全二叉树的顺序存储中，若节点 i 有左子女，则其左子女是节点 1。（分数：2.00）填空项 1:_4.二叉树是节点的有限集合，这个有限集合或者为 1，或者由一个根节点及两棵不相交的，分别称作为根的左子树和右子树的二叉树组成。（分数：2.00）填空项 1:_5.m 阶 B 树的根节

2、点若不是叶节点，那么它至多有 m 棵子树，至少有 1 棵子树。（分数：2.00）填空项 1:_6.对于关键码序列 18，30，35，10，46，38，5，40 进行堆排序(假定堆的根节点为最小关键码)，在初始建堆过程中需进行的关键码交换次数为 1。（分数：2.00）填空项 1:_7.在有 n 个节点的二叉树的 llink-rlink 法存储表示中，n 个节点所含有的 2n 个指针中，必有 1 个为空指针。（分数：2.00）填空项 1:_8.对于给出的一组权 w=5，6，8，12，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 1。（分数：2.00）填空项 1:_9.对 n 个记录的文件进行

3、快速排序，最坏情况下的执行时间为 1。（分数：2.00）填空项 1:_10.散列法存储中处理碰撞的方法主要有两类：拉链法和 1。（分数：2.00）填空项 1:_11.某二叉树节点的对称序序列为 A、B、C、D、E、F、G，后序序列为 B、D、C、A、 F、G、E。则该二叉树对应的树林包括 1 棵树。（分数：2.00）填空项 1:_12.对线性表进行二分法检索，其前提条件是：线性表以 1 方式存储，并且按关键码值排好序。（分数：2.00）填空项 1:_数据结构与算法练习试卷 5 答案解析(总分：24.00，做题时间：90 分钟)一、填空题(总题数：12，分数：24.00)1.填空题（每空）请将每

4、一个空的正确答案写在答题卡上。（分数：2.00）_解析：2.设只包含根节点的二叉树的高度为 0，则高度为 k 的二叉树的最小节点数为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：k+1）解析：3.在完全二叉树的顺序存储中，若节点 i 有左子女，则其左子女是节点 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：2i）解析：4.二叉树是节点的有限集合，这个有限集合或者为 1，或者由一个根节点及两棵不相交的，分别称作为根的左子树和右子树的二叉树组成。（分数：2.00）填空项 1:_ （正确答案：正确答案：空集）解析：5.m 阶 B 树的根节点若不是叶节点，那么它至多有 m

5、 棵子树，至少有 1 棵子树。（分数：2.00）填空项 1:_ （正确答案：正确答案：2）解析：6.对于关键码序列 18，30，35，10，46，38，5，40 进行堆排序(假定堆的根节点为最小关键码)，在初始建堆过程中需进行的关键码交换次数为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：3）解析：7.在有 n 个节点的二叉树的 llink-rlink 法存储表示中，n 个节点所含有的 2n 个指针中，必有 1 个为空指针。（分数：2.00）填空项 1:_ （正确答案：正确答案：n+1）解析：8.对于给出的一组权 w=5，6，8，12，通过霍夫曼算法求出的扩充二叉树的带权外部路

6、径长度为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：61）解析：9.对 n 个记录的文件进行快速排序，最坏情况下的执行时间为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：O(n 2 )）解析：10.散列法存储中处理碰撞的方法主要有两类：拉链法和 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：开放定址法）解析：11.某二叉树节点的对称序序列为 A、B、C、D、E、F、G，后序序列为 B、D、C、A、 F、G、E。则该二叉树对应的树林包括 1 棵树。（分数：2.00）填空项 1:_ （正确答案：正确答案：2）解析：12.对线性表进行二分法检索，其前提条件是：线性表以 1 方式存储，并且按关键码值排好序。（分数：2.00）填空项 1:_ （正确答案：正确答案：顺序）解析：