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

计算机学院2010-2011学年第一学期 《数据结构》试卷（B卷）（考试时间：100分钟） 专业： 班级： 序号： 姓名： 题 号 一 二 三 四 总分 题 分 20 20 50 10 得 分 阅卷人 注意：所有答案都必须写在答题纸上！！！ 一．填空（每空2分，共40分） 1.双向循环链表中，结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，则其基本操作为____ ,____。 2. 通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_______,_________。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 次匹配成功。 5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），判断队空和队满的条件分别分：_____________,________________。 6.字符串t=”a very cute child”，s=”I like coffee and cake”，请写出下列函数的结果：StrLength(s) =_____;Concat(SubString(s,3,15)，SubString(t,12,6))=_______。 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. 森林和二叉树的转换，画出和下列二叉树相应的森林 3. 使用克鲁斯卡尔算法求下图中最小生成树，请写出步骤。 b b c d e h g f k i 2 3 6 2 5 4 3 1 1 3 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）中的关键码按字母序的升序重新排列，则： （1）写出冒泡排序的过程； （2）写出希尔（shell）排序的过程，初始步长为4 三 程序题 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。 《数据结构》（B卷）答题纸 专业： 班级： 序号： 姓名： 题 号 一 二 三 总分 题 分 40 50 10 得 分 阅卷人 一．填空（每空2分，共40分） 1.____________________________________,___________________________________。 2.____________________________。 3.____________________,______________________。 4.__________________________