考试科目：《数据结构》第五章至第七章(总分100分） 时间:90分钟 ______________学习中心（教学点) 批次： 层次:
专业： 学号: 身份证号： 姓名: 得分：
一、选择题（每题3分,共30分)
1、m阶Ｂ树中的一个分支结点最多含（C）个关键字.
Ａ、m—1 Ｂ、m Ｃ、m+1 Ｄ、[m/2]—1 Ｅ、[m/2］ Ｆ、[m/2］+1
2、设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（B)次探测。
Ａ、k-1 Ｂ、k Ｃ、k+1 Ｄ、k(k—1）/2
3、设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为(A）. Ａ、50 Ｂ、25 Ｃ、10 Ｄ、7
4、设哈希表地址范围为0~19，哈希函数H(key）=key％17,使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录,则再放入关键字值为72的记录时，其存放地址应为（）.
Ａ、2 Ｂ、3 Ｃ、4 Ｄ、7 Ｅ、8 Ｆ、以上都不对 5、直接插入排序在最好情况下的时间复杂度为（D）。 Ａ、O（logn) Ｂ、O(n） Ｃ、O(n＊logn） Ｄ、O（n2)
6、将两个各有n个元素的有序表归并成一个有序表,最少进行（B）次比较. Ａ、n Ｂ、2n-1 Ｃ、2n Ｄ、n—1
7、设有一组关键字值(46,79,56，38，40，84），则用快速排序的方法，以第一个记录为基准得到的一次划分结果为（D）。
Ａ、38,40,46，56,79，84 Ｂ、40,38，46，79,56,84 Ｃ、40，38，46，56,79,84 Ｄ、40,38，46,84,56,79 8、外部排序是指(B）。 Ａ、在外存上进行的排序方法 Ｂ、不需要使用内存的排序方法
Ｃ、数据量很大，需要人工干预的排序方法
Ｄ、排序前后数据在外存，排序时数据调入内存的排序方法 9、下述文件中适合于磁带存储的是（C）。
1
Ａ、顺序文件 Ｂ、索引文件 Ｃ、散列文件 Ｄ、多关键字文件 10、ISAM文件和VSAM文件属于(A)。
Ａ、索引非顺序文件 Ｂ、索引顺序文件 Ｃ、顺序文件 Ｄ、散列文件
二、(10分）
设用堆排序法对给定关键字序列（８５，６１，１５,３３，２４，９６，７６,４３）按升序进行排序,试画出初始堆。
答：9 6， 8 5，4 3， 2 4，1 5，7 6，3 3 三、(10分）
画出对长度为１７的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。
9
13 4
2 15 6 11
1 3 5 7 16 10 12 14
平均查找长度:
2
8 17 59 17
四、(15分)
设内存有大小为５个记录的区域可供内部排序之用,文件的关键字序列为：(18，32，56，40,23，11，8，99，58，36,21,7,4,15,19，87,73,52，82，63），要求用置换－选择排序求初始归并段。 初始归并段1：18，23，32，40,56，58，99；
初始归并段2：7，8，11，15，19，21，36,52，63，73，82，87 初始归并段3：4
五、(15分）
设哈希函数H(key)=(3＊key）％11,用开放定址法处理冲突,di=i*(（7*key)%10+1),i=1，2，3…。试在０～１0的散列地址空间中对关键字序列(２２,４１，５３,４６，３０，１３，０１，６７)造哈希表，并求等概率下查找成功时的平均查找长度。 L 0 1 2 3 4 5 6 7 8 9 10
22 67 41 30 53 13 46 01 平均查找长度=（1+1+1+2+2+1+6+3）/8=
17 8六、（20分）
3
设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于ｘ的数据元素。 Viod OutputNLT（BiTree T，KeyType X){ if （!T） return;
if （！LT（T—〉data。key，x)）｛ //根结点及右子树中所有结点的关键字值俊不小于x
Output(T-〉rchild); //按关键字值从大到小的顺序输出右子树中所有结点 Printf（T—>data）； //输出p所指结点 OutputNLT(T->lchild，x）; //处理左子树 ｝
else OutputNLT（T-〉lchild,x）； ｝//OutputNLT
Void Output（BiTree T){ Output(T—>rchild)； printf(T—>data）; Output(T->lchild); ｝
4
因篇幅问题不能全部显示，请点此查看更多更全内容