单选题
单选题
下列陈述中正确的是 (45) 。
【正确答案】
D
【答案解析】[解析] 此题是考查数据结构的二叉树概念。选项A的描述不对，原因是二叉树的度不一定是2，例如：只有一个节点或者空树的二叉树它的度就不是2了；选项B二叉树只有一个节点时也有左右节点之分2。
单选题
假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶结点数为 (46) 个。
【正确答案】
B
【答案解析】[解析] 根据二叉树的性质3，叶结点数n0与度为2的结点数n2的关系是：n0=n2+1。
单选题
设a、b是一棵二叉树上的两个结点，在中序序列中，a在b之前的条件是 (47) 。
【正确答案】
B
【答案解析】[解析] 在中序序列中，a在b之前的条件是a在b的左子树上。显然，A是错误的；C也不正确，除非b在a的右子树上；D也是错误的，因为“a是b的子孙”包括“a在b的左子树上”或“a在b的右子树上”两种情况。
单选题
设森林F中有n个非叶结点，则由它转换得到的二叉树中右链域为空的结点个数为 (48) 。
【正确答案】
C
【答案解析】[解析] 将森林中各树的根视为兄弟，则最右边那棵树的根没有右邻兄弟；森林中凡是没有右邻兄弟的结点在转换得到的二叉树中其右链域为空。每个非叶结点必有一个最右边的孩子，n个非叶结点则有n个没有右邻兄弟的子结点，加上最右边那棵树的根，就有n+1个无右邻兄弟的结点。它们在转换得到的二叉树中右链域为空，而其他结点的右链域非空。
单选题
在n个结点的线索二叉链表中，有 (49) 个线索指针。
【正确答案】
C
【答案解析】[解析] 线索二叉树是利用空闲的子链域来存放某种遍历次序下的直接前驱结点或直接后继结点的地址的二叉树。因为二叉树的每个结点有且仅有两个链域，则n个结点的二叉树，有2n个子链域。又因为除根结点之外，其他每个结点都有且仅有一个进入支，这样就共有n -1进入支；而这n-1分支是由上一层的结点的子链域发出的，因此， 2n个子链域中有，n-1个链域是指向子结点的，其他n+1个链域空闲看着。经过线索化以后，这些原来空闲着的n+1个链域被用来指向前驱或后继，即用来存放线索。所以在n个结点的线索二叉链表中，有n +1个线索指针。
单选题
具有n个顶点e条边的无向图的邻接表，其边表结点总数为 (50) 。
【正确答案】
C
【答案解析】[解析] 无向图的邻接表中，第i个边表的结点是表示关联于顶点i的边。同一条无向边关联于两个顶点，因此同一条边在邻接表中用了两个边表结点表示。故e条边的无向图的邻接表，其边表结点总数为2e。