数据结构试卷(四)
一、 选择题（每题 2 分，共 20 分）
1. 设一维数组中有 n 个数组元素，则读取第 i 个数组元素的平均时间复杂度为( C )。
A. O(n)
B. O(nlog
2
n)
C. O(1)
2
D. O(n )
2. 设一棵二叉树的深度为 k，则该二叉树中最多有( D )个结点。
A. 2k-1
k
B. 2
k-1
C. 2
k
D. 2 -1
3. 设某无向图中有 n 个顶点、e 条边，则该无向图中所有顶点的入度之和为( D )。
A. n
B. e
C. 2n
D. 2e
4. 在二叉排序树中插入一个结点的时间复杂度为( C )。
A. O(1)
B. O(n)
C. O(log
2
n)
2
D. O(n )
5. 设某有向图的邻接表中有 n 个表头结点和 m 个表结点，则该图中有( C )条有向边。
A. n
B. n-1
C. m
D. m-1
6. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( A )
趟的分配和回收才能使初始关键字序列变成有序序列。
A. 3
B. 4
C. 5
D. 8
7. 设用链表作为栈的存储结构，则退栈操作( B )。
A. 必须判别栈是否为满
B. 必须判别栈是否为空
