2012数据结构补考试卷A.doc

中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 专业： 班级： 序号： 姓名： 题 号 一 二 三 总分 题 分 40 50 10 得 分 阅卷人 注意：所有答案都必须写在答题纸上！！！ 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的 （1） 。 2. 通常程序在调用另一个程序时，都需要使用一个 （2） 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 C C G E D F B H A 则后序序列为 （12） ，中序序列为 （13） ，先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在 （19） 次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 3 假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）请画出存放状态； 4 森林和二叉树的转换，画出和下列二叉树相应的森林 5 设要将序列（46,79,56,38,40,84）中的关键码按升序重新排列，写出快速排序的过程。(每一步过程) 三 程序题(10分) 编写算法判别给定二叉树是否为完全二叉树 《数据结构》（A卷）答题纸 专业： 班级： 序号： 姓名： 题 号 一 二 三 总分 题 分 40 50 10 得 分 阅卷人 一．填空（每空2分，共40分） 1.____________________________________,___________________________________。 2.____________________________。 3.____________________, ______________________。 4._____________________________。 5._____________________________,__________________________________________。 6. _______________________,________________________________________________。 8．第8题答题处 7. _____________________________________。 9. ___________________,__________________。 10. ___________________。 11. __________________,___________________。 12. ____________