C.基于交换的                                                D.基于选择的

13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为(      )

A.1                                                                B.2

C.3                                                                D.4

14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是(      )

15.若需高效地查询多关键字文件，可以采用的文件组织方式为(      )

A.顺序文件                                                   B.索引文件

C.散列文件                                                   D.倒排文件

二、填空题（本大题共10小题，每小题2分，共20分）

请每小题的空格中填上正确答案。错填、不填均无分。

16.下面程序段的时间复杂度为___________。

sum=1；

for（i=0；sum<n;i++）

sum+=1；

17.已知链表结点定义如下：

typedef  struct  node{

char  data［16］；

struct node   *next;

} LinkStrNode；

如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。

18.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为___________。

19.3个结点可以组成___________种不同树型的二叉树。

20.用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。

21.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。

22.影响排序效率的两个因素是关键字的___________次数和记录的移动次数。

23.对任一m阶的B树，每个结点中最多包含___________个关键字。

24.若两个关键字通过散列函数映射到同一个散列地址，这种现象称为___________。

25.如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为___________。

三、解答题（本大题共4小题，每小题5分，共20分）

26.要在［0..n-l］的向量空间中建立两个栈stackl和stack2，请回答：

(1)应该如何设计这两个栈才能