1. 下面给出的四种排序法中（　）排序法是不稳定的排序法。

A 插入

B 冒泡

C 二路归并

D 堆

正确答案 : D

2. 具有 n 个顶点的有向强连通图最少有（）条弧。

An-1

Bn

Cn(n-1)

Dn(n-1)/2

正确答案 : B

3. 在待排元素序列基本有序的前提下，效率最高的排序方法是（　）。

A 插入

B 选择

C 快速

D 归并

正确答案 : A

4. 对线性表，在下列哪种情况下应当采用链表表示？（ ）

A 经常需要随机地存取元素

B 经常需要进行插入和删除操作

C 表中元素需要占据一片连续的存储空间

D 表中元素的个数不变

正确答案 : B

5. 一棵高为 k 的二叉树最少有（）个结点。

Ak-1

Bk

Ck+1

D2k-1

E2k-1

正确答案 : B

6. 从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）

AO （ n ）

BO （ 1 ）

CO （ log2n ）

DO （ n2 ）

正确答案 : C

7. 下列叙述中错误的是（）。

A 树的度与该树中结点的度的最大值相等

B 二叉树就是度为 2 的有序树

C 有 5 个叶子结点的二叉树中必有 4 个度为 2 的结点

D 满二叉树一定是完全二叉树

正确答案 : B

8. 设广义表 L=((a,()),b,(c,d,e)) ，则 Head(Tail(Tail(L))) 的值为（　）。

Ab

Bc

C(c)

D(c,d,e)

正确答案 : D

9. 由树转换而得的二叉树，根结点（）。

A 没有左子树

B 没有右子树

C 左右子树都有

D 视树的形态而定

正确答案 : B

10. 设在一不带头结点的链队列中， front 和 rear 分别为其队头和队尾指针，则删除一个结点

的操作是（）。

Arear=front->next

Brear=rear->next

Cfront=front->next

Dfront=rear->next

正确答案 : C

11. 在一个可存放 n 个数据元素的顺序栈中，假设以高地址端为栈底，以 top 为栈顶指针，当

向栈中压入一个数据元素时， top 的变化是（）。

A 不变

Btop=n

Ctop++

Dtop--

正确答案 : D

12. 一棵二叉树中第６层上最多有（）个结点。

A ２

B31

C32

D64

正确答案 : C

13. 直接插入排序在最好情况下的时间复杂度为（）。

AO(logn)

BO(n)