C.关键字的取值范围                                   D.关键字的数据类型

14.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（　　　）

A.分块查找                                                 B.顺序查找

C.二分查找                                                 D.散列查找

15.可有效提高次关键字查找效率的文件是（　　　）

A.顺序文件                                                 B.倒排文件

C.散列文件                                                 D.VSAM文件

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

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

16.数据的存储结构是其逻辑结构___________。

17.输入线性表的n个元素建立带头结点的单链表，其时间复杂度为___________。

18.假设循环队列的元素存储空间大小为m，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置，则在少用一个元素空间的前提下，表示“队满”的条件是___________。

19.给定串的联接操作函数：

char *strcat(char *to, char *from);

//将串from联接到串to的末尾，并返回联接后的串

   若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是___________。

20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储        地址为100,则元素A[4][5]的存储地址为___________。

21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___________。

22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为___________。

23.在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n²)的排序算法有___________。

24.假设散列表的表长为11,散列函数为H(key)=key%7,若用线性探测处理冲突,则探查地址序列hi的计算公式为___________ 。

25.VSAM文件由___________，___________和数据集三部分组成。

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

26.已知广义表的图形表示如图所示,

(1)    写出该广义表L;

(2)    分别写出该广义表的深度和长度。

(1)     

(2)     

27.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF，

(1)    画出该二叉树的二叉链表存储表示;

(2)    写出该二叉树的后序序列。

   (1)

   (2)

28.已知有向图的邻接表如图所示,

(1)    写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;

(2)    画出该有向图的逆邻接表。

(1)

(2)

29.依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完成下列操作：

1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;

  2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足