2-1
为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？(1分)
A.堆栈
B.队列
C.树
D.图
作者
DS课程组
单位
浙江大学
2-2
若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：(2分)
A.1->2->3
B.2->3->4
C.4->1->2
D.答案不唯一
作者
DS课程组
单位
浙江大学
2-3
现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：(2分)
A.1, 2, 5, 6, 4, 3
B.2, 3, 4, 5, 6, 1
C.3, 4, 5, 6, 1, 2
D.6, 5, 4, 3, 2, 1
作者
考研真题
单位
浙江大学
2-4
以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n>0），空链域的个数为 __(2分)
A.n+1
B.n
C.n−1
D.无法确定
作者
魏宝刚
单位
浙江大学
2-5
有关树和二叉树的叙述错误的是（）。(2分)
A.树中的最大度数没有限制，而二叉树结点的最大度数为2；
B.树的结点无左右之分，而二叉树的结点有左右之分；
C.树的每个结点的孩子数为0到多个, 而二叉树每个结点均有两个孩子；
D.树和二叉树均为树形结构
作者
严冰
单位
浙大城市学院
2-6
一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。(2分)
A.15
B.16
C.17
D.47
作者
严冰
单位
浙大城市学院
2-7
深度为6的二叉树最多有( )个结点。(2分)
A.64
B.63
C.32
D.31
作者
DS课程组
单位
临沂大学
2-8
在完全二叉树中，若一个结点度为1，则它没有（ ）。(2分)
A.左子树
B.右子树
C.左子树和右子树
D.右子树和兄弟结点
作者
DS课程组
单位
临沂大学
2-9
在一棵度为 3 的树中，度为 2 的结点个数是 1，度为 0 的结点个数是 6，则度为 3 的结点个数是 __(2分)
A.2
B.3
C.4
D.无法确定
作者
魏宝刚
单位
浙江大学
2-10
如果某数据结构的数据元素的集合为S＝{A，B，C，D，E，F，G}，数据元素之间的关系为R＝{＜A，D＞，＜A，G＞，＜D，B＞，＜D，C＞，＜G，E＞，＜G，F＞}，则该数据结构是一种( )。(2分)
A.线性结构
B.树结构
C.图结构
D.链表结构
作者
夏仁强
单位
贵州工程应用技术学院
2-11
对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：(2分)
A.31
B.16
C.15
D.10
作者
考研真题
单位
浙江大学
2-12
下列说法中正确的是（）。(2分)
A.任何一棵二叉树中至少有一个结点的度为2
B.任何一棵二叉树中每个结点的度都为2
C.任何一棵二叉树中的度肯定等于2
D.任何一棵二叉树中的度可以小于2
作者
YJ
单位
西南石油大学
2-13
由3 个结点可以构造出多少种不同的二叉树( )(2分)
A.2
B.3
C.4
D.5
作者
YJ
单位
西南石油大学
2-14
已知一棵二叉树的树形如下图所示，其后序序列为{ e, a, c, b, d, g, f }。树中与结点a同层的结点是：(3分)
A.c
B.d
C.f
D.g
作者
考研试卷
单位
浙江大学
2-15
已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，则该二叉树形态中，父节点的右子节点为（）。(2分)
A.D
B.H
C.G
D.F
作者
佚名
单位
互联网
2-16
设 T 是非空二叉树，若 T 的先序遍历和后序遍历序列相同，则 T 的形态是 __(2分)
A.只有一个根结点
B.没有度为 1 的结点
C.所有结点只有左孩子
D.所有结点只有右孩子
作者
魏宝刚
单位
浙江大学
2-17
设 T 是非空二叉树，若 T 的后序遍历和中序遍历序列相同，则 T 的形态是 __(2分)
A.只有一个根结点
B.没有度为 1 的结点
C.所有结点只有左孩子
D.所有结点只有右孩子
作者
魏宝刚
单位
浙江大学
2-18
已知二叉树的前序遍历序列为 ABDCEFG，中序遍历序列为 DBCAFEG，则后序遍历序列为 __(2分)
A.BDACEFG
B.DCBFGEA
C.ABCDEFG
D.GFEDCBA
作者
魏宝刚
单位
浙江大学
2-19
若一棵二叉树的前序遍历序列是{ 4, 2, 1, 3, 6, 5, 7 }，中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 }，则下列哪句是错的？(3分)
A.这是一棵完全二叉树
B.所有的奇数都在叶子结点上
C.这是一棵二叉搜索树
D.2是5的父结点
作者
何钦铭
单位
浙江大学
2-20
将{ 32, 2, 15, 65, 28, 10 }依次插入初始为空的二叉搜索树。则该树的前序遍历结果是:(3分)
A.2, 10, 15, 28, 32, 65
B.32, 2, 10, 15, 28, 65
C.10, 28, 15, 2, 65, 32
D.32, 2, 15, 10, 28, 6
作者
陈越
单位
浙江大学
2-21
下列给定的关键字输入序列中，不能生成如下二叉排序树的是：(2分)
A.4, 5, 2, 1, 3
B.4, 5, 1, 2, 3
C.4, 2, 5, 3, 1
D.4, 2, 1, 3, 5
作者
考研真题
单位
浙江大学
2-22
将 9, 8, 7, 2, 3, 5, 6, 4 顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？(2分)
A.5 是根结点
B.2 和 5 是兄弟
C.有2个结点的平衡因子为-1
D.最后得到的AVL树的高度是3
作者
徐镜春
单位
浙江大学
2-23
首先将 28, 23, 54, 61, 98, 37 插入一棵初始为空的平衡二叉树（AVL树），然后马上插入下列选项中的一个键值。哪个键值将引起 RL 旋转？(2分)
A.10
B.30
C.60
D.70
作者
何钦铭
单位
浙江大学
2-24
给定平衡二叉树如下图所示，插入关键字 23 后，根中的关键字是：(2分)
A.16
B.20
C.23
D.25
作者
考研真题
单位
浙江大学
2-25
用线性时间复杂度的算法将给定序列{15, 26, 32, 8, 7, 20, 12, 13, 5, 19}调整为最小堆（小根堆），然后插入6。下列句子中错误的是：(3分)
A.5是根
B.从根到26的路径是{5, 6, 8, 26}
C.32是12的左孩子
D.7是19和15的父结点
作者
陈越
单位
浙江大学
2-26
将 { 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7 } 逐个按顺序插入到初始为空的最小堆中，然后连续执行两次删除最小元素操作（DeleteMin），再插入4，16，此后堆顶的元素是什么？(2分)
A.4
B.5
C.7
D.9
作者
何钦铭
单位
浙江大学
2-27
利用过滤法将关键字序列 { 37, 66, 48, 29, 31, 75 } 建成的最大堆为 __(2分)
A.75, 66, 48, 37, 31, 29
B.75, 37, 66, 29, 31, 48
C.75, 66, 48, 29, 31, 37
D.75, 48, 66, 37, 29, 31
作者
魏宝刚
单位
浙江大学
2-28
下列关于大根堆（至少含 2 个元素）的叙述中，正确的是：
(I). 可以将堆看成一棵完全二叉树
(II). 可以采用顺序存储方式保存堆
(III). 可以将堆看成一棵二叉排序树
(IV). 堆中的次大值一定在根的下一层
(2分)
A.仅 I、II
B.仅 II、III
C.仅 I、II、IV
D.仅 I、III、IV
作者
考研真题
单位
浙江大学
2-29
对N（N≥2）个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是：(2分)
A.树中一定没有度为1的结点
B.树中两个权值最小的结点一定是兄弟结点
C.树中任一非叶结点的权值一定不小于下一层任一结点的权值
D.该树一定是一棵完全二叉树
作者
DS课程组
单位
浙江大学
2-30
设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？(2分)
A.0
B.2
C.4
D.5
作者
DS课程组
单位
浙江大学
2-31
已知字符集{ a, b, c, d, e, f, g, h }。若各字符的哈夫曼编码依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列 0100011001001011110101 的译码结果是：(2分)
A.acgabfh
B.adbagbb
C.afbeagd
D.afeefgd
作者
考研试卷
单位
浙江大学
2-32
已知字符集{ a, b, c, d, e, f }，若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 }，则对应字符集中各字符的哈夫曼编码可能是：(3分)
A.00, 1011, 01, 1010, 11, 100
B.00, 100, 110, 000, 0010, 01
C.10, 1011, 11, 0011, 00, 010
D.0011, 10, 11, 0010, 01, 000
作者
考研真题
单位
浙江大学
2-33
对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是：(3分)
A.56
B.57
C.58
D.60
作者
考研真题
单位
浙江大学
2-34
若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是：(2分)
A.89
B.200
C.208
D.289
作者
考研真题
单位
浙江大学
2-35
对二叉搜索树进行什么遍历可以得到从小到大的排序序列？(1分)
A.前序遍历
B.后序遍历
C.中序遍历
D.层次遍历
作者
DS课程组
单位
浙江大学
2-36
已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉搜索树后，最后两层上的结点总数为：(2分)
A.1
B.2
C.3
D.4
作者
DS课程组
单位
浙江大学
2-37
下列二叉搜索树中，满足平衡二叉树定义的是：(1分)
A.
B.
C.
D.
作者
DS课程组
单位
浙江大学
2-38
将{ 6, 9, 12, 3, 4, 8 }依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：(3分)
A.4, 3, 6, 8, 12, 9
B.3, 4, 9, 8, 12, 6
C.3, 4, 6, 8, 12, 9
D.4, 3, 8, 12, 9, 6
作者
何钦铭
单位
浙江大学
2-39
下列关于无向连通图特征的叙述中，正确的是：
- 所有顶点的度之和为偶数
- 边数大于顶点个数减1
- 至少有一个顶点的度为1
(2分)
A.只有1
B.只有2
C.1和2
D.1和3
作者
DS课程组
单位
浙江大学
2-40
若无向图G =（V，E）中含7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：(3分)
A.6
B.15
C.16
D.21
作者
DS课程组
单位
浙江大学
