A) 空或只有一个结点 C) 任一结点无左孩子
B) 高度等于其节点数 D) 任一结点无右孩子
(51) 含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ）
A)3
B)4
C)5
D)6
(52) 除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ ）
A)1/2倍
B)1倍
C) 2倍
D) 3倍
(53) 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为
（ ） A)24
B)25
C)98
D)99
(54) 可以惟一地转化成一棵一般树的二叉树的特点是（ ）
A)根结点无左孩子
B)根结点无右孩子
C)根结点有两个孩子 D)根结点没有孩子
(55) 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为
（ ）。 A) 2h
B) 2h-1
C) 2h+1
D) h+1
(56) 在一棵度为3的树中，度为3的节点个数为2，度为2的节点个数为1，则度为0的节点个
数为（ ）。
A) 4
B) 5
C) 6
D) 7
(57) 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n,森林F
中第一棵 A)m-n
子树的结点个数是（ ）。 B)m-n-1
C) n+1
D) 条件不足，无法确定
(58) 将一株有100个节点的完全二叉树从上到下，从左到右依次进行编号，根节点的编号为1，
则编号为49的节点的 左孩子编号为（）。 A) 98
B) 89
C) 50
D) 没有孩子
(59) 下列图示的顺序存储结构表示的二叉树是(A )
(60) 树最适合用来表示（ ）。
A) 有序数据元素
C) 元素之间具有分支层次关系的数据
B) 无序数据元素
D) 元素之间无联系的数据
(61) 在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。
A) 只有右子树上的所有结点 C) 只有左子树的上的部分结点
B) 只有右子树上的部分结点 D) 只有左子树上的所有结点
(62) 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中相对次序（ ）。
A) 不发生改变 B) 发生改变
C) 不能确定 D) 以上都不对
(63) 在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。
A) 不确定
B) 2n
C) 2n+1
D) 2n-1
(64) 权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是（ ）。
A) 18
B) 28
C) 19
D) 29
(65) 对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（ ）。
A) n=m+1
B) m+1=2n
C) m=k-1
D) n=2k+1
(66) 在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）。
A) e
B) 2e
C) n2-e
D) n2-2e
(67) 若采用邻接矩阵翻存储一个n个顶点的无向图，则该邻接矩阵是一个（ ）。
A) 上三角矩阵 B) 稀疏矩阵
C) 对角矩阵 D) 对称矩阵
(68) 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A) 1/2
B) 1
C) 2
D) 4
(69) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
A) 1/2
B) 1
C) 2
D) 4
(70) 对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ ）。
A) O（n）
B) O(e)
C) O(n+e)
D) O(n)
2
(71) 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）。
A) 深度优先搜索算法
B) 广度优先搜索算法 D) 拓扑排序算法
C) 求最小生成树的prim算法
(72) n个顶点的连通图至少中含有( )。
A) n-1
B) n
C) n+1
D) 0
(73) n个顶点的完全有向图中含有( )。
A) n-1条有向边 B) n条有向边
C) n(n-1)/2条有向边 D) n(n-1)条有向边
(74) 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除预某个顶点vi相关的所有弧
的时间复杂度是（ ）。
A) O(n)
B) O(e)
C) O(n+e)
D) O(n*e)
(75) 在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个（ ）。
A) 顶点序列
B) 边序列
C) 权值总和 D) 边的条数
(76) 无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f), (f,d),(e,d)}，对该图进行
深度优先遍历，得到的顶点序列正确的是（ ）。 A) a,b,e,c,d,f
B) a,c,f,e,b,d
C) a,e,b,c,f,d
D) a,e,d,f,c,b
(77) 下面哪一方法可以判断出一个有向图是否有环（回路）。
A) 求节点的度
B) 拓扑排序
C) 求最短路径 D) 求关键路径
(78) 图的广度优先搜索类似于树的（ ）次序遍历。
A) 先根
B) 中根
C) 后根
D) 层次
(79) 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
A) O(n)
B) O(n+e)
C) O(n2)
D) O(n3)
(80) 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A) 从源点到汇点的最长路径 C) 最长回路
B) 从源点到汇点的最短路径 D) 最短回路
B) V1,V3,V2,V6,V4,V5,V7 D) V1,V2,V5,V3,V4,V6,V7
(82) 有n个结点的有向完全图的弧数是（ ）。
A) n2
B) 2n
C) n(n-1)
D) 2n(n+1)
(83) 设图的邻接链表如题12图所示，则该图的边的数目是（ ）。
83题图
A) 4
B) 5
C) 10
D) 20
(84) 在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。
A) 1/2
B) 1 C) 2 D) 4
(85) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
A) 1/2 B) 1 C) 2 D) 4
(86) 有8个结点的无向图最多有（ ）条边。
A) 14
B) 28 C) 56 D) 112
(87) 有8个结点的无向连通图最少有（ ）条边。
A) 5
B) 6 C) 7 D) 8
(88) 有8个结点的有向完全图有（ ）条边。
A) 14
B) 28 C) 56 D) 112
(89) 用邻接表表示图进行广度优先遍历时，通常是采用（ ）来实现算法的。
A) 栈
B) 队列 C) 树 D) 图
(90) 用邻接表表示图进行深度优先遍历时，通常是采用（ ）来实现算法的。
A) 栈
B) 队列 C) 树 D) 图
(91) 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）。
?0?1??1?1??1??0??1100100110001001100110101101000011011??1?0??0?0??1?0??
A) 0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C) 0 4 2 3 1 6 5 D) 0 3 6 1 5 4 2
建议：0 1 3 4 2 5 6
(92) 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是
（ ）。
A) 0 2 4 3 1 5 6 B) 0 1 3 5 6 4 2 C) 0 4 2 3 1 6 5
D) 0 1 3 4 2 5 6
(93) 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
（ ）。
A) 0 2 4 3 6 5 1 B) 0 1 3 6 4 2 5 C) 0 4 2 3 1 5 6
（建议：0 1 2 3 4 5 6）
(94) 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
（ ）。
A) 0 2 4 3 1 6 5 B) 0 1 3 5 6 4 2 C) 0 1 2 3 4 6 5
D) 0 1 2 3 4 5 6 D) 0 1 3 4 2 5 6
(95) 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ ）。
A) 1 3 2
B) 0 2 3 1
C) 0 3 2 1 D) 0 1 2 3
(96) 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ ）。
A) 0 3 2 1
(97) 深度优先遍历类似于二叉树的（ ）。
A) 先序遍历
B) 中序遍历
C) 后序遍历
D) 层次遍历
B) 0 1 2 3
C) 0 1 3 2
D) 0 3 1 2
(98) 广度优先遍历类似于二叉树的（ ）。
A) 先序遍历
B) 中序遍历
C) 后序遍历
D) 层次遍历
(99) 任何一个无向连通图的最小生成树（ ）。
A) 只有一棵
B) 一棵或多棵 C) 一定有多棵 D) 可能不存在
（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）
(100) 在分析折半查找的性能时常常加入失败节点，即外节点，从而形成扩充的二叉树。若设失败
节点i所在层次为Li，那么查找失败到达失败点时所做的数据比较次数是（ ）。 A) Li+1
B) Li+2
C) Li-1
D) Li
(101) 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ ）
个元素。
A) 8
B) 63.5
C) 63
D) 7
(102) 由同一组关键字集合构造的各棵二叉排序树( )。
A) 其形态不一定相同，但平均查找长度相同 B) 其形态不一定相同，平均查找长度也不一定相同 C) 其形态均相同，但平均查找长度不一定相同 D) 其形态均相同，平均查找长度也都相同 (103) 衡量查找算法效率的主要标准是（ ）。
A) 元素的个数
B) 所需的存储量 C) 平均查找长度 D) 算法难易程度
(104) 适合对动态查找表进行高效率查找的组织结构是（ ）。