2012数据结构补考试卷B（answer）.docVIP

中国矿业大学2011-2012学年 《数据结构》试卷（B卷）（考试时间：100分钟） 专业： 班级： 序号： 姓名： 题 号 一 二 三 总分 题 分 40 50 10 得 分 阅卷人 注意：所有答案都必须写在答题纸上！！！ 一．填空（每空2分，共40分） 1. 联系 , 图（或图结构）。 2. 通常程序在调用另一个程序时，都需要使用一个 栈 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_1270 , 1210_。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6次匹配成功。 5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），判断队空和队满的条件分别分：___ Q.front==Q.rear, Q.front==（Q.rear+1）% MS __。 6. O（1） O（n） _。 7. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。 8. 深度为k 的二叉树的结点总数，最多为_2k-1__个。最少为_k__个。 9二叉树中元素按照顺序存储方式存放在如下一维数组中，则结点G所在层次为 3 。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 10. 有n个结点的无向完全图和有向完全图的边数分别为___ n(n-1)/2 , n(n-1) ____。 11. 图的深度优先遍历算法类似于树的 先序 。 12. 要从序列{1，3，5，7，9，11，13}中查找11，若采用折半查找法，则在 2 次比较后，才找到该数据。 13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下______最快，其时间复杂度为_________。快速排序 , O(n lg n) 二简答题：（每题10分，共50分） 1. 假设9个字母为：A B C D E F G H，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。 116 68 48 34 34 28 20 18 16 15 13 9 9 7 8 5 4 2. 拓朴排序为： 4 3 6 5 7 2 1 3. (1) 判断n是否是素数（或质数） （2）O（） 4．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）请画出存放状态； 0 1 2 3 4 5 6 7 8 9 10 11 12 102 54 3 4 5 30 7 72 87 95 24 63 24,63,102共计比较了3次 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 5设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则 写出希尔（shell）排序的过程，初始步长为4 Shell P, A, C, S, Q, D, F, Y, R, H, M, C, A, , F D, M, H, P, S, Q, Y, R, A C D F H M P Q R S Y 三 程序题 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。 见课本 Int search(array ST, Key key) Low =1; high<=high; While(low<high){ Mid=(low+high