资源描述：
《数据结构-03农信信管(a)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、华南农业大学期末考试试卷（ A 卷）2004学年第二学期 考试科目： 数据结构 考试类型：（闭卷） 考试时间： 120 分钟学号姓名年级专业题号010203040506070809101112131415总分得分评阅人1．比较线性表的顺序存储结构和链式存储结构的优缺点。（5分）2．具有8个存储单元的环形（循环）队列，画出经过下列操作后环形队列的示意图。(5分)EnQueue(‘a’),EnQueue(‘b’),EnQueue(‘c’),EnQueue(‘d’),EnQueue(‘e’),DeQueue(),DeQueue(),EnQu
2、eue(‘f’),EnQueue(‘g’),DeQueue(),DeQueue(),EnQueue(‘h’),EnQueue(‘i’),EnQueue(‘j’),DeQueue(),EnQueue(‘k’)3．有一链式存储的堆栈，画出经过下列操作后堆栈的示意图。(5分)push(1),Push(2),Push(3),Pop(),Pop(),Push(4),Push(5),Push(6),Pop(),Pop(),push(7)4．已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少个叶子结点，写出求解
3、过程？（5分）5．给出一棵二叉树的中序遍历CBDAFHGIE,及前序遍历序列ABCDEFGHI。(5分)(1)画出这棵树（3分）(2)给出后序遍历序列（2分）6．有一份电文AECBECACDEDBEDCEADEBCDBDFD，试对每个字符进行二进制编码，使通信编码的总长度最短,最后给出通信编码的总长度值。（5分）7．有10个按关键字有序的记录以顺序方式存储，采用什么查找方式查找，使等概率情况下平均查找长度ASL值最小？ASL值是多少？(5分)8．画出利用逐点插入法建立序列（50，72，85，75，35，45，20，30，66）对应的二叉排序树
4、，并给出查找元素45要进行比较的次数。（5分）9．将下列9个数据(46，37，70，29，62，78，25，12，20)进行升序排序,请写出希尔(Shell)排序的每趟排序过程（其中d=4,2,1）。（5分）810．下面程序将数据(28,76,54,39,87,14)按堆排序法进行排序,请写出建大堆的过程。（5分）11．设一组关键子{59,42,44,4,92,40,12,36,81,56,38},采用哈希函数:H(key)=key%13，采用开放地址法的线性探测再散列方法解决冲突,画出在0~12的散列地址空间中对该关键字序列构造哈希表（10
5、分）12．描述PRIM算法步骤，并画出对G1图生成最小生成树的过程（10分）2EB152DA301044154FC10（G1）13．用C语言编写算法，将带头结点的单链表中指针P所指向结点删除的算法。（10分）p·header14．用C语言编写算法，求二叉排序树中关键字值最小的结点。（10分）15．用C语言编写快速排序中的分区算法，以x[lb],x[ub],和x[mid](mid＝(ub+lb)/2)三者的中间值为枢轴。（10分）8华南农业大学期末考试试卷答案（ A 卷）1．比较线性表的顺序存储结构和链式存储结构的优缺点。（5分）答：顺序存储结
6、构的优点：在线性表的顺序存储结构中，元素之间的逻辑关系是通过存储位置直接反映的。顺序存储结构中只需存放数据元素自身的信息，因此1)存储密度大、空间利用率高。另外，元素的存储位置可以用元素的下标通过简单的解析式计算出来，因此2）可以随机存取。缺点：在顺序表中，1）元素的插入和删除运算可能需要移动许多其他元素的位置；一些长度变化较大的线性表必须按最大需要的空间分配存储，因此2）最大空间估计有可能过大，而造成空间浪费，也有可能估计过小而造成溢出。链式存储结构的优点：在线性表的链式存储结构中，数据元素之间的逻辑次序是靠结点的指针域来指示的，结点空间是
7、动态申请和动态释放。所以，1）不要预先按最大的需要分配连续空间。2）线性表的插入和删除只需修改指针域，而不需移动其他元素。缺点：每个结点中的指针域需额外占用存储空间，因此1）存储密度小。另外，2）查找任一结点都要从头指针开始，顺序搜索。因此，对于需要进行大量元素插入和删除的线性表适宜选用链式存储结构，主要操作为查找定位操作的线性表适宜选用顺序存储结构。2．具有8个存储单元的环形（循环）队列，画出经过下列操作后环形队列的示意图。(5分)EnQueue(‘a’),EnQueue(‘b’),EnQueue(‘c’),EnQueue(‘d’),EnQ
8、ueue(‘e’),DeQueue(),DeQueue(),EnQueue(‘f’),EnQueue(‘g’),DeQueue(),DeQueue(),EnQueu
