数据结构c语言描述二叉树应用习题及答案.doc

一、单选题（共有题目7题,共计35.0分） 1.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。A. O(n)B. O(1)C. O(Log2n)D. O(n 2)你的答案: C 标准答案: C 该题分数:5.0你的得分:5.0解答过程：2. 向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。A. O（1）B. O（Log2n)C. O(n)D. O(nLog2n)你的答案: B 标准答案: B 该题分数:5.0你的得分:5.0解答过程：3. 向堆中插入一个元素的时间复杂度是（ ）。A. O(1)B. O(Log2n)C. O(n)D. O(nLog2n)你的答案: B 标准答案: B 该题分数:5.0你的得分:5.0解答过程：4. 利用n个值作为叶子结点的权生成的哈夫曼树中共包含（ ）结点。A. nB. n+1C. 2nD. 2n-1你的答案: D 标准答案: D 该题分数:5.0你的得分:5.0解答过程：5. 利用3、6、8、12为4个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（ ）。A. 18B. 16C. 12D. 30你的答案: A 标准答案: A 该题分数:5.0你的得分:5.0解答过程：6. 对二叉搜索树进行中序遍历得到的结点序列一定是一个有序序列。A. 对B. 错你的答案: A 标准答案: A 该题分数:5.0你的得分:5.0解答过程：7. 建立一个具有n个结点的二叉搜索树算法的时间复杂度为（ ）。A. O（n）B. O（nLOG2n）C. O（LOG2n）D. O（n 2）你的答案: B 标准答案: B 该题分数:5.0你的得分:5.0解答过程：二、填空题（共有题目8题,共计40.0分） 1.二叉搜索树又名_。你的答案: 二叉排序树 标准答案: 二叉排序树; 该题分数:5.0你的得分:5.0解答过程：2. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_。你的答案: 有序序列 标准答案: 有序序列; 该题分数:5.0你的得分:5.0解答过程：3. 堆是一棵_二叉树。你的答案: 完全 标准答案: 完全; 该题分数:5.0你的得分:5.0解答过程：4. 在一个小根堆中，堆顶结点的值是所有结点中的_；在一个大根堆中，堆顶结点的值是所有结点中的_。你的答案: 最小值最大值 标准答案: 最小值最大值; 该题分数:5.0你的得分:5.0解答过程：5. 在任何一棵哈夫曼树中，单支结点的个数为_。你的答案: 0 标准答案: 0;零;无; 该题分数:5.0你的得分:5.0解答过程：6. 不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个数必为_个。你的答案: 奇数 标准答案: 奇数;单数; 该题分数:5.0你的得分:5.0解答过程：7. 有7个带权结点，其权值分别为3、7、8、2、6、10、14，若依它们为叶子结点构造一棵哈夫曼树，给出其广义表，并计算出其带权路径长度WPL_。你的答案: 131 标准答案: 131; 该题分数:5.0你的得分:5.0解答过程：8. 对二叉搜索树进行_遍历后得到的结点序列为一个有序序列。你的答案: 中序 标准答案: 中序; 该题分数:5.0你的得分:5.0解答过程：三、问答题（共有题目4题,共计20.0分） 1.已知一组元素为（13，9，45，31，21，60），试画出按元素排列顺序输入生成的一棵二叉搜索树的图示。你的答案: 标准答案: 参见教材！该题分数:5.0你的得分:4.5解答过程：2. 现有一组元素为（11，9，37，32，21，50，44，60），试画出按元素排列顺序输入生成的一个大根堆的图示。你的答案: 标准答案: 参见教材该题分数:5.0你的得分:5.0解答过程：3. 权值分别为3、7、8、2、6、10、14的7个结点，试以它们为叶子结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），该哈夫曼树的带权路径长度WPL是多少_？你的答案: WPL=131标准答案: 131该题分数:5.0你的得分:5.0解答过程：4. 已知一组元素为（12，10，38，33，22，51，45，61）1.试画出从空树起，逐次输入各个数据而生成的二叉搜索树。2.试画出从空堆起，插入每个结点所得到的各个大根堆的图示。你的答案: 标准答案: 只要正确即可得分。该题分数:5.0你的得分:5.0解答过程：四、程序填空题（共有题目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;_