C. 435                            D. 438

9. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是(      )

A. (e,f)                           B. ((e,f))

C. (f)                            D. ( )

10. 下列图示的顺序存储结构表示的二叉树是(      )

11. n个顶点的强连通图中至少含有(      )

A. n-1条有向边                           B. n条有向边

C. n(n-1)/2条有向边                        D. n(n-1)条有向边

12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为(      )

A. (19，23，56，34，78，67，88，92)         B. (23，56，78，66，88，92，19，34)

C. (19，23，34，56，67，78，88，92)         D. (19，23，67，56，34，78，92，88)

13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为

(      ) 

A. 4                B. 5

C. 8                D. 9

14. 由同一关键字集合构造的各棵二叉排序树(      )

A. 其形态不一定相同，但平均查找长度相同

B. 其形态不一定相同，平均查找长度也不一定相同

C. 其形态均相同，但平均查找长度不一定相同

D. 其形态均相同，平均查找长度也都相同

15. ISAM文件和VSAM文件的区别之一是(      )

A. 前者是索引顺序文件，后者是索引非顺序文件

B. 前者只能进行顺序存取，后者只能进行随机存取

C. 前者建立静态索引结构，后者建立动态索引结构

D. 前者的存储介质是磁盘，后者的存储介质不是磁盘

二、填空题(本大题共10小题，每空2分，共20分)

16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

17. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。

18. 栈下溢是指在____________时进行出栈操作。

19. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。

20. 去除广义表LS=(a₁,a₂,a₃,……，a_n)中第1个元素，由其余元素构成的广义表称为LS的____________。

21. 已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。

22. 在有向图中，以顶点v为终点的边的数目称为v的____________。

23. 当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。

24. 产生冲突现象的两个关键字称为该散列函数的____________。

25. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。

三、解答题(本大题共4小题，每小题5分，共20分)

26. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。

(1)写出队满的条件表达式；

(2)写出队空的条件表达式；

(3)设m=40,rear=13,quelen=19,求队头元素的位置；

(4)写出一般情况下队头元素位置的表达式。

(1)

(2)

(3)

(4)

27. 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。

28. 画出下图所示有向图的所有强连通分量。

29. 对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。

(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；

(2)对所举序列进行快速排序，