素不存在，则把该数据元素插入到集合中。
这种方式主要适合于（
）
A静态查找表
B动态查找表
C静态查找表与动态查找表
D两种表都不适合
12．由索引集、顺序集和数据集三部分组成的文件称为（
）
AVSAM文件
B散列文件
C顺序文件
D索引文件
13．下列有关散列文件的说法中不正确的是（
）
A散列文件具有随机存放的优点
B散列文件只能按关键字存取
C散列文件需要索引区
D散列文件的记录不需要进行排序
14．一组记录的键值为（12，38，35，25，74，50，63，90），按2路归并排序方法对该序
列进行一趟归并后的结果为（
）
A1238253550746390
B1238352574506390
C1225353850746390
D1235382563507490
15．用快速排序方法对包含有
个关键字的序列进行排序，最坏情况下执行的时间复杂度为
（
）
AO

BOlog2

CO
log2

DO
2
二、填空题每空2分，共26分
1．定义在线性表上的初始化、查找、插入和删除运算中，
是引用型运算。
2．线性表a0a1a2…a
≥1中，每个元素占c个存储单元，m为a0的首地址，则按顺序
存储方式存储线性表，a
的存储地址是
。
3．在栈的顺序实现中，设栈顶指针为top，栈空的条件为
。
4．队列中允许进行插入的一端称为
。
5．深度为90的满二叉树上，第11层有个结点。
6．给定
个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有
棵二叉树，经过次
合并后才能使森林中的二叉树的数目由
棵减少到只剩下一棵最终的哈夫曼树。
7．设无向图G的顶点数为
，则G最少有
条边。
8．通常采用拉链法、线性探测法、多重散列法、二次探测法、公共溢出区法等解决散列地
址冲突问题，若要避免“堆积”现象发生应采用
。
9．对有序表25303238475462689095用二分查找法查找32，则所需的比较次数为。
10．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的关系。
11．文件的检索有顺序存取、直接存取和
三种方式。
12．第i趟在
i1i12…
1个记录中选取键值最小的记录作为有序序列的第i个记录。
这样的排序方法称为
。
2
f…………………………………………………………精品自学考试资料推荐………………………………………………
13．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用
。
三、应用题共30分1．设有字符串为3yay2，试利用栈写出将其转换为3yay2的操作步骤。假定用X代
表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一字符加入到新字符串尾的出栈操作。例r