(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) V1,V3,V4,V6,V2,V5,V7 B) V1,V3,V2,V6,V4,V5,V7 C) V1,V3,V4,V5,V2,V6,V7 D) V1,V2,V5,V3,V4,V6,V7 (81) 关键路径是事件结点网络中（ ）。
A) 从源点到汇点的最长路径 B) 从源点到汇点的最短路径
C) 最长回路 D) 最短回路 (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出
发按深度优先遍历的结点序列是（ ）。 ?0111101??1001001? ???1000100? ??1100110?? ?1011010??? 0001101??? ?1100010??
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 D) 0 1 3 4 2 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 (95) 已知图的邻接表如下所示，根据算法，则从顶点0
出发按深度优先遍历的结点序列是（ ）。
A) 1 3 2 B) 0 2 3 1 C) 0 3 2 1 D) 0 1 2 3 (96)
A) 0 3 2 1 B) 0 1 2 3 C) 0 1 3 2 D) 0 3 1 2
(97) 深度优先遍历类似于二叉树的（ ）。
A) 先序遍历 B) 中序遍历 C) 后序遍历 D) 层
已知图的邻接表如下所示，根据算法，则从顶点0
出发按广度优先遍历的结点序列是（ ）。
次遍历 (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) 适合对动态查找表进行高效率查找的组织结构是
（ ）。
A) 有序表 B) 分块有序表 C) 二叉排序树 D) 快速排序
(3)能进行二分查找的线性表,必须以（ ）。 A) 顺序方式存储，且元素按关键字有序 B) 链式方式存储，且元素按关键字有序 C) 顺序方式存储，且元素按关键字分块有序 D) 链式方式存储，且元素按关键字分块有序