单选题

1. 关于哈夫曼树，下面说法正确的是（ ）。

   {{ select(1) }}

• 不可能是满二叉树
• 哈夫曼树是一种用于数据压缩的二叉树
• 权值较大的结点离根较远
• 构建哈夫曼树的时间复杂度为 ( O(\log n) )

2. 给定一组权值 ({3, 4, 7, 14, 15, 20})，计算带其权路径长度（WPL）为（ ）。

   {{ select(2) }}

• 147
• 146
• 142
• 145

3. 二叉树T，已知其先根遍历是1243576（数字为结点的编号，以下同），中根遍历是2415736，则该二叉树的后根遍历是（ ）。

   {{ select(3) }}

• [ ] A. 4257631
• [✓] B. 4275631
• [ ] C. 7425631
• [ ] D. 4276531

4. 一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ ）。

   {{ select(4) }}

• 2
• 3
• 4
• 5

5. 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（ ）号位置。

   {{ select(5) }}

• 2k
• 2k+1
• [k/2]
• [(k+1)/2]

6. 如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（ ）。

   {{ select(6) }}

• 10
• 11
• 12
• 13

7. 广度优先搜索时，需要用到的数据结构是（ ）。

   {{ select(7) }}

• 链表
• 队列
• 栈
• 散列表

8. 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素d已经出栈，则可能的入栈顺序是（ ）。

   {{ select(8) }}

• a,d,c,b
• b,a,c,d
• a,c,b,d
• d,a,b,c

9. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

   {{ select(9) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

10. 一棵具有5层的满二叉树中结点数为（ ）。

    {{ select(10) }}

• 31
• 32
• 33
• 34

11. 今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈S的栈顶元素为：

    {{ select(11) }}

• f
• c
• a
• b

12. 如果根的高度为1，具有61个结点的完全二叉树的高度为（）

    {{ select(12) }}

• 5
• 6
• 7
• 8

13. 面向对象程序设计将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（）。

    {{ select(13) }}

• 面向对象程序设计一般不采用自顶向下设计方法进行设计。
• 面向对象程序设计方法具有继承性、封装性和多态性等特点。
• 当前较为流行的面向对象的编程语言有C++、JAVA、C#等。
• 面向对象程序设计中对对象的成员属性的改变通常通过对象的成员函数实现。

14. 前序遍历序列与中序遍历序列相同的二叉树为（）。

    {{ select(14) }}

• 根结点无左子树
• 根结点无右子树
• 只有根结点的二叉树或非叶子结点只有左子树的二叉树
• 只有根结点的二叉树或非叶子结点只有右子树的二叉树

15. 下面程序是一个二叉排序树的，横线处应该填入的是（）。

• if current.right is None:
      current.right = node
      return
  

• if current.right is None:
      current.left = node
      return
  

• if current.left is None:
      current.left = node
      return
  

判断题

1. 在哈夫曼树中，从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

   {{ select(16) }}

• 对
• 错

2. 满二叉树每一层的结点个数都达到了最大值。

   {{ select(17) }}

• 对
• 错

3. 如果一棵二叉树是满二叉树，但是它不一定是完全二叉树。

   {{ select(18) }}

• 对
• 错

4. 栈中元素的插入和删除操作都在栈的顶端进行，所以方便用双向链表比单向链表更合适来实现。

   {{ select(19) }}

• 对
• 错

5. 格雷码是一种变权码，每一位码没有固定的大小。

   {{ select(20) }}

• 对
• 错

6. 格雷码的基本特点就是任意两个相邻的代码只有一位二进制数不同。

   {{ select(21) }}

• 对
• 错

7. 栈是一种只能在一端进行插入和删除操作的特殊线性表。

   {{ select(22) }}

• 对
• 错

8. 最后进入队列的元素才能最先从队列中删除。

   {{ select(23) }}

• 对
• 错

9. 当队列为满时，做出以运算产生的溢出现象，常用作程序控制转移的条件。

   {{ select(24) }}

• 对
• 错

10. 在循环队列的上下文中，rear指针通常用于指示队列尾部元素的下一个位置，而不是直接指示队列尾部的元素。因此，rear的计算通常与入队操作相关。

    {{ select(25) }}

• 对
• 错