《2023年数据结构c语言描述二叉树应用习题及超详细解析答案.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构c语言描述二叉树应用习题及超详细解析答案.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构c 语言描述二叉树应用习题及答案 一、单选题（共有题目 7 题,共计 35.0 分）1.从二叉搜索树中查找一个元素时，其时间复杂度大致为()。A.O(n)B.O(1)C.O(Log2n)D.O(n 2)你的答案:C 标准答案:C 解答过程：2.向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。A.O（1）B.O（Log2n)C.O(n)D.O(nLog2n)你的答案:B 标准答案:B 解答过程：3.向堆中插入一个元素的时间复杂度是（）。A.O(1)B.O(Log2n)C.O(n)D.O(nLog2n)你的答案:B 标准答案:B 解答过程：4.利用 n 个值作为叶子结点的权生成的哈
2、夫曼树中共包含（）结点。A.n B.n+1 C.2n D.2n-1 你的答案:D 标准答案:D 解答过程：5.利用 3、6、8、12 为 4 个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（）。A.18 B.16 C.12 D.30 你的答案:A 标准答案:A 解答过程：6.对二叉搜索树进行中序遍历得到的结点序列一定是一个有序序列。A.对 B.错 你的答案:A 标准答案:A 解答过程：7.建立一个具有 n 个结点的二叉搜索树算法的时间复杂度为（）。A.O（n）B.O（nLOG2n）C.O（LOG2n）D.O（n 2）你的答案:B 标准答案:B 解答过程：二、填空题（
3、共有题目 8 题,共计 40.0 分）1.二叉搜索树又名_。你的答案:二叉排序树 标准答案:二叉排序树;解答过程：2.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_。你的答案:有序序列 标准答案:有序序列;解答过程：3.堆是一棵_二叉树。你的答案:完全 标准答案:完全;解答过程：4.在一个小根堆中，堆顶结点的值是所有结点中的_；在一个大根堆中，堆顶结点的值是所有结点中的_。你的答案:最小值 最大值 标准答案:最小值 最大值;解答过程：5.在任何一棵哈夫曼树中，单支结点的个数为_。你的答案:0 标准答案:0;零;无;解答过程：6.不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个
4、数必为_个。你的答案:奇数 标准答案:奇数;单数;解答过程：7.有 7 个带权结点，其权值分别为 3、7、8、2、6、10、14，若依它们为叶子结点构造一棵哈夫曼树，给出其广义表，并计算出其带权路径长度 WPL _。你的答案:131 标准答案:131;解答过程：8.对二叉搜索树进行_遍历后得到的结点序列为一个有序序列。你的答案:中序 标准答案:中序;解答过程：三、问答题（共有题目 4 题,共计 20.0 分）1.已知一组元素为（13，9，45，31，21，60），试画出按元素排列顺序输入生成的一棵二叉搜索树的图示。你的答案:标准答案:参见教材！解答过程：2.现有一组元素为（11，9，37，32
5、，21，50，44，60），试画出按元素排列顺序输入生成的一个大根堆的图示。你的答案:标准答案:参见教材 解答过程：3.权值分别为 3、7、8、2、6、10、14 的 7 个结点，试以它们为叶子结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），该哈夫曼树的带权路径长度 WPL 是多少_？你的答案:WPL=131 标准答案:131 解答过程：4.已知一组元素为（12，10，38，33，22，51，45，61）1.试画出从空树起，逐次输入各个数据而生成的二叉搜索树。2.试画出从空堆起，插入每个结点所得到的各个大根堆的图示。你的答案:标准答案:只要正确即可得分。解答过程：四、程序填空题（共有题目 1 题,共计 5.0 分）1.下面是在一棵二叉搜索树上进行查找的非递归算法，请根据程序填空：ElemType*Find1(struct BTreeNode*BST,ElemType x)while(BST!=NULL)if(_)return&(BST-data);else if(xdata)_;else BST=BST-right;_;你的答案:x=BST-NULL BST=BST-left BST=BST-right 标准答案:x=BST-data BST=BST-left return NULL;解答过程：