模拟试题 4
一、选择题（20 分）
1. n 个顶点的无向图的邻接表中结点总数最多有( )个。
(A) 2n (B) n (C) n/2 (D) n(n-1)
2. 设连通图 G 的顶点数为 n，则 G 的生成树的边数为( )。
(A) n (B) n-1 (C) 2n (D) 2n-1
3. 下列哪种排序需要的附加存储开销最小( )。
(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 计数排序
4. 若按 ( )列出二叉搜索树中所存储的元素，则恰好是集合中所有元素从小到大的排序。
(A) 先序 (B) 中序 (C) 后序 (D) 按层次
5. 在图 9.5 所示的 4 棵树中，哪一棵是完全二叉树( )。
（A） （B） （C） （D）
图 9.5
6. 下面程序段的时间复杂度为( )。
s=s0;
for(i =1 ;i<=n;i++)
{
for(j =n;j>=n-1;j--)
{
s = s+1;
}
}
(A) O(n) (B) O(nlog
2
n) (C) O(n
2
) (D) O(n
3/2
)
7. 采用链结构存储线性表时，其地址( )。
(A) 必须是连续的 （B）连续不连续都可以
（C）部分地址必须是连续的 (D) 必须是不连续的
8. 具有 2000 个结点的二叉树，其高度至少为( )。
(A) 9 (B) 10 (C) 11 (D) 12
9. 若按字典顺序排序，则图 9.6 中( )为二叉搜索树。
(A) (B) (C) (D)
