13．下列有关散列文件的说法中不正确的是（ ）
A.散列文件具有随机存放的优点
B.散列文件只能按关键字存取
C.散列文件需要索引区
D.散列文件的记录不需要进行排序
14．一组记录的键值为（12，38，35，25，74，50，63，90），按2路归并排序方法对该序列进行一趟归并后的结果为（ ）
A.12,38,25,35,50,74,63,90 B.12,38,35,25,74,50,63,90
C.12,25,35,38,50,74,63,90 D.12,35,38,25,63,50,74,90
15．用快速排序方法对包含有n个关键字的序列进行排序，最坏情况下执行的时间复杂度为（ ）
A.O(n) B.O(log2n)
C.O(nlog2n) D.O(n2)
二、填空题(每空2分，共26分)
1．定义在线性表上的初始化、查找、插入和删除运算中， 是引用型运算。
2．线性表(a0,a1,a2,…,an)(n≥1)中，每个元素占c个存储单元，m为a0的首地址，则按顺序存储方式存储线性表，an的存储地址是 。
3．在栈的顺序实现中，设栈顶指针为top，栈空的条件为 。
4．队列中允许进行插入的一端称为 。
5．深度为90的满二叉树上，第11层有 个结点。
6．给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过 次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。
7．设无向图G的顶点数为n，则G最少有 条边。
8．通常采用拉链法、线性探测法、多重散列法、二次探测法、公共溢出区法等解决散列地址冲突问题，若要避免“堆积”现象发生应采用 。
9．对有序表(25,30,32,38,47,54,62,68,90,95)用二分查找法查找32，则所需的比较次数为 。
10．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的 关系。
11．文件的检索有顺序存取、直接存取和 三种方式。
12．第i趟在n-i+1(i=1,2,…,n-1)个记录中选取键值最小的记录作为有序序列的第i个记录。这样的排序方法称为 。
13．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用 。
四、设计题(共14分)
1．设字符串仅由圆括号“（”和“）”，方括号“[”和“]”，花括号“{”和“}”组成，利用链栈的操作编写一个检查括号是否正确配对的算法：int Matcher(LstackTP *ls)。例如[{{（）}[ ]}（）{[ ]}]是正确的，而{（{（）[ ]}）}]）}则不正确。设链栈定义如下：（6分）
typedef struct node
{ char data;
struct node * next;
} LStackTp；
2．利用一维数组a可以对n个整数进行排序，其中一种排序算法的处理思想是：将n个整数分别作为数组a的n个元素的值，每次（即第i次）从元素a[i]到a[n]中挑出最小的一个元素a[k](i≤k≤n)，然后将a[k]与a[i]换位。这样反复n-1次完成排序。编写实现上述算法的函数:void sort(int a[],int n)。（8分） |
