B．2n-1

CD．n-1

2. 一个有n个顶点的无向连通图，它所包含的连通分量个数为（ ）。

A．0 B．1 C．n D．n+1

3. 数据文件的基本操作中最重要的操作是（ ）。

A．插入 B．删除 C．修改 D．检索

4. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。 A．(2,5,12,16)26(60,32,72) B．(5,16,2,12)28(60,32,72) C．(2,16,12,5)28(60,32,72) D．(5,16,2,12)28(32,60,72)

5. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。 A．堆排序 B．快速排序 C．插入排序 D．归并排序 6．算法分析的目的是（ ）。

A．找出数据结构的合理性 B．研究算法中的输入和输出的关系

．

2n

C．分析算法的效率以求改进 D．分析算法的易懂性和文档性

7. 二叉树的第I层上最多含有结点数为（ ）

A．2I B． 2I-1-1 C． 2I-1 D．2I -1

8．循环队列存储在数组A中，长度为m，则入队时的操作为（ ）。

A. rear=rear+1 B. rear=(rear+1) mod (m-1) C.

rear=(rear+1)

mod

m

D.

rear=(rear+1)mod(m+1)

9. 广义表满足Head(A)=Tail(A)，则A为（ ）。 A．（） B．（（）） C．（（），（）） D．（（），（），（））

10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A．3 B．4 C．5 D．6 二、填空题

1. 在一个循环队列中，队首指针指向队首元素的_________。

2. 数组中每一个数据通常称为 ， 用下标区分，其中下标的个数由数组的 决定。 3. 一个图的 表示法是唯一的，而 表示法是不唯一的。

4. 在一个10阶的B-树上，每个数根结点中所含的关

键字数目最多允许

个，最少允许 个

5. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后的得到结果为 。

10.高度为1的平衡二叉树的结点数至少有________个，高度为2的平衡二叉树的结点数至少有________个。 三 判断

1. 顺序存储结构属于静态结构，链式结构属于动态结构。 （ ）

2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。 （ ）

3. 带权无向图的最小生成树必是唯一的。（ ） 4. B-树和B+树都可用于文件的索引结构。（ ） 5. 在用堆排序算法排序时，如果要进行增序排序，则需要采用\大根堆\。（ ） 四、应用题

1. 模式串p=\的next函数值序列为多少？

2. 设二维数组A[5][6]的每个元素占4个字节，已知LOC（a0,0）=1000，A共占多少个字节？A的终端结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？

3. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。

（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。