A. 兄弟 B. 父子 C. 祖先 D. 子孙
80. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。 A 1 B 2 C 3 D 4
81. 已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为( )。假定树根结点的高度为0。
A. 3 B. 4 C. 5 D. 6
82. 已知一棵树的边集表示为{
83. 利用n个值作为叶结点的权生成的霍夫曼树中共包含有( )个结点。 A. n B. n+1 C. 2*n D. 2*n-1
84. 利用3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为( )。
A 55 B 29 C 58 D 38
85. 一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为( )。
A 1 B 2 C 3 D 4
86. 向具有n个结点的堆中插入一个新元素的时间复杂度为( )。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n)
87. 若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度为( )。
A. n B. n+1 C. (n-1)/2 D. (n+1)/2
88. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索任一元素的平均搜索长度为( )。 A. 5.5 B. 5 C. 39/8 D. 19/4
89. 对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，则搜索任一元素的平均搜索长度为( )。 A. 5/3 B. 2 C. 7/3 D. 4/3
90. 对长度为n的单链有序表，若搜索每个元素的概率相等，则搜索任一元素的搜索成功的平均搜索长度为( )。
A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4
9
91. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值向上取整。
A. log2(n+1) B. log2n C. n/2 D. (n+1)/2
92. 对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值的向下取整加1。
A. log2(n+1) B. log2n C. n/2 D. (n+1)/2
93. 对于长度为9的顺序存储的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( )除以9。
A. 20 B. 18 C. 25 D. 22
94. 对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索第15个元素的搜索长度为( )。
A. 3 B. 4 C. 5 D. 6
95. 对具有n个元素的有序表进行折半搜索，则搜索任一元素的时间复杂度为( )。 A. O(n) B. O(n) C. O(1) D. O(log2n)
96. 在一棵高度为h的具有n个元素的二叉搜索树中，搜索一个元素的最大搜索长度为( )。
A. n B. log2n C. (h+1)/2 D. h+1
97. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为( )。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
98. 向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为( )。 A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n)
99. 在一棵AVL树中，每个结点的平衡因子的取值范围是( )。 A. -1?1 B. -2?2 C. 1?2 D. 0?1
100. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为( )种旋转类型。
A. 2 B. 3 C. 4 D. 5
101. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关( )个指针域的值。
A. 2 B. 3 C. 4 D. 5
2
10
102. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关( )个指针域的值。
A. 2 B. 3 C. 4 D. 5
103. 设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1?V2，E1?E2，则称 ( )。 A．G1是G2的子图 B．G2是G1的子图 C．G1是G2的连通分量 D．G2是G1的连通分量
104. 有向图的一个顶点的度数等于该顶点的 ( )。
A．入度 B．出度 C．入度与出度之和 D．（入度+出度）／２
105. 一个连通图的生成树是包含图中所有顶点的一个 ( )。
A．极小子图 B．连通子图 C．极小连通子图 D．无环子图
106. n个顶点的连通图中至少含有 ( )。
A．n-1条边 B．n条边 C．n(n-1)/2条边 D．n(n-1)条边
107. n个顶点的强连通图中至少含有 ( )。
A．n-1条有向边 B．n条有向边 C．n(n-1)/2条有向边 D．n(n-1)条有向边
108. 在一个带权连通图G中，权值最小的边一定包含在G的( ) 中。 A．最小生成树 B．生成树
C．广度优先生成树 D．深度优先生成树
109. 对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。 A．e-1 B．e C．2(e-1) D．2e
110. 具有n个顶点的有向无环图最多可包含 ( ) 条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)
111. 一个有n个顶点和n条边的无向图一定是 ( )。 A．连通的 B．不连通的 C．无环的 D．有环的
112. 在n个顶点的有向无环图的邻接矩阵中至少有 ( ) 个零元素。 A．n B．n(n-1)/2 C．n(n+1)/2 D．n(n-1)
113. 对于有向图，其邻接矩阵表示比邻接表表示更易于 ( )。 A．查找一条边 B．求一个顶点的邻接点 C．进行图的深度优先遍历 D．进行图的广度优先遍历
114. 在一个有向图的邻接矩阵表示中，删除一条边
11
115. 与邻接矩阵相比，邻接表更适合于存储 ( )。 A．无向图 B．连通图 C．稀疏图 D．稠密图
116. 设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度 所耗费的时间是 ( )。
A．O(n) B．O(e) C．O(n+e) D．O(n)
117. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是 ( )。 A．栈 B．队列 C．二叉树 D．树
118. 设无向图的顶点个数为n，则该图最多有（ ）条边。
A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)
119. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。
A. 3
120. 若采用邻接矩阵存储具有n个顶点的无向图，则该邻接矩阵是一个 ( )。
A. 上三角矩阵
121. 图的深度优先搜索类似于树的（ ）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次
122. 图的广度优先搜索类似于树的（ ）次序遍历。
A. 先根
123. 在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（ ）
辅助结构，判断一条边的两个端点是否在同一个连通分量上。
A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合
124. 采用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ ）数。
A. 非零
125. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。
A. O(nlog2e)
126. 若待排序对象序列在排序前已基本按排序码递增顺序排列，则采用( )方法比较次数最少。
A. 直接插入排序 B. 快速排序 C. 归并排序
D. 直接选择排序
B. O(n+e)
C. O(n)
e
2
B. 2 C. 1 D. 1/2
B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵
B. 中根 C. 后根 D. 层次
B. 非整 C. 非负 D. 非正
D. O(n)
2
12
