2012数据结构补考试卷B（new）.doc

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