排序方法是（）
A．选择排序B．希尔排序C．归并排序D．快速排序
14．适于对动态查找表进行高效率查找的组织结构是（）
A．有序表
B．分块有序表C．三叉排序树D．线性链表
15．不定长文件是指（）
A．文件的长度不固定
B．记录的长度不固定
C．字段的长度不固定
D．关键字项的长度不固定
第二部分非选择题（共70分）
二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不
写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。
16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的
无关，是独立于计算
机的。
17．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head
可用p表示为head
。
18．栈顶的位置是随着
操作而变化的。
19．在串S“structure”中，以t为首字符的子串有
个。
20．假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B0存储
f矩阵中第1个元素a11则B31中存放的元素是
21．已知一棵完全二叉树中共有768结点，则该树中共有
22．已知一个图的广度优先生成树如右图所示，则与此相
应的广度优先遍历序列为
。
。个叶子结点。
23．在单链表上难以实现的排序方法有
和
。
24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字
比较次数为
。
25．多重表文件和倒排文件都归属于
文件。
三、解答题（本大题共4小题，每小题5分，共20分）
26．画出下列广义表的共享结构图形表示
P（（（z）xy）xyxz）
27．请画出与下列二叉树对应的森林。
28．已知一个无向图的顶点集为abcde其邻接矩阵如下所示
abc
0100110010
de
0001101101
10110
1画出该图的图形；（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
29．已知一个散列表如下图所示：
35
20
33
48
59
0123456789101112其散列函数为hkeykey13处理冲突的方法为双重散列法，探查序列为：
hihkeyih1keymi01…，m－1其中
h1keykey111回答下列问题：
（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？（2）该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题（本大题共4小题，每小题5分，共20分）
f30．下列算法的功能是比较两个链串的大小，其返回值为：
1
comstrs1s2

0

1
当s1s2当s1s2当s1s2
请在空白处填入适当的内容。
i
tcomstrLi
kStri
gs1Li
kStri
gr