数据结构-03农信信管(A).doc

华南农业大学期末考试试卷（A卷）2004学年第二学期 考试科目：数据结构考试类型：（闭卷）考试时间：120 分钟学号 姓名 年级专业 题号01 02 03040506070809101112131415总分得分评阅人1 比较线性表的顺序存储结构和链式存储结构的优缺点。（5分）2具有8个存储单元的环形（循环）队列，画出经过下列操作后环形队列的示意图。(5分)EnQueue(a), EnQueue(b), EnQueue(c),EnQueue(d), EnQueue(e), DeQueue(),DeQueue(),EnQueue(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的结点，问该树中有多少个叶子结点，写出求解过程？（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）对应的二叉排序树，并给出查找元素45要进行比较的次数。（5分）9将下列9个数据(46，37，70，29，62，78，25，12，20)进行升序排序,请写出希尔(Shell)排序的每趟排序过程（其中d=4,2,1）。（5分）10下面程序将数据(28,76,54,39,87,14)按堆排序法进行排序,请写出建大堆的过程。（5分）11设一组关键子59,42,44,4,92,40,12,36,81,56,38,采用哈希函数:H(key)=key%13，采用开放地址法的线性探测再散列方法解决冲突,画出在012的散列地址空间中对该关键字序列构造哈希表（10分）12描述PRIM算法步骤，并画出对G1图生成最小生成树的过程（10分）2EB152DA301044154FC10（G1）13用C语言编写算法，将带头结点的单链表中指针P所指向结点删除的算法。（10分）pheader14用C语言编写算法，求二叉排序树中关键字值最小的结点。（10分）15用C语言编写快速排序中的分区算法，以xlb,xub,和xmid(mid(ub+lb)/2)三者的中间值为枢轴。（10分）华南农业大学期末考试试卷答案（A卷）1 比较线性表的顺序存储结构和链式存储结构的优缺点。（5分）答：顺序存储结构的优点：在线性表的顺序存储结构中，元素之间的逻辑关系是通过存储位置直接反映的。顺序存储结构中只需存放数据元素自身的信息，因此1) 存储密度大、空间利用率高。另外，元素的存储位置可以用元素的下标通过简单的解析式计算出来，因此2）可以随机存取。缺点：在顺序表中，1）元素的插入和删除运算可能需要移动许多其他元素的位置；一些长度变化较大的线性表必须按最大需要的空间分配存储，因此2）最大空间估计有可能过大，而造成空间浪费，也有可能估计过小而造成溢出。 链式存储结构的优点：在线性表的链式存储结构中，数据元素之间的逻辑次序是靠结点的指针域来指示的，结点空间是动态申请和动态释放。所以，1）不要预先按最大的需要分配连续空间。2）线性表的插入和删除只需修改指针域，而不需移动其他元素。缺点：每个结点中的指针域需额外占用存储空间，因此1）存储密度小。另外，2）查找任一结点都要从头指针开始，顺序搜索。因此，对于需要进行大量元素插入和删除的线性表适宜选用链式存储结构，主要操作为查找定位操作的线性表适宜选用顺序存储结构。2具有8个存储单元的环形（循环）队列，画出经过下列操作后环形队列的示意图。(5分)EnQueue(a), EnQueue(b), EnQueue(c),EnQueue(d), EnQueue(e), DeQueue(),DeQueue(),EnQueue(f),EnQueue(g),DeQueue(),DeQueue(),EnQueue(h),EnQueue(i),EnQueue(j),DeQueue(),EnQueue(k) 答： ijkfghrearfront3有一链式存储的堆栈，画出经过下列操作后堆栈的示意图。(5分)push(1),Push(2), Push(3),Pop(),Pop(), Push(4), Push(5), Push(6),Pop(),Pop(),push(7)答：Top741 4已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少个叶子结点，写出求解过程？答：树中结点的个数为n, 叶子结点n0，因此，结点总数为 n=n0+ n1+ n2+ . + nm （1） 树中共有n-1条边，n-1=n1+ 2n2+ . + m nm （2）(1) 与（2）约简后有n0= n2+2n3+ +(m-1) nm+15给出一棵二叉树的中序遍历CBDAFHGIE,及前序遍历序列ABCDEFGHI 。(5分) (1) 画出这棵树（3分）ABCDEFGHI 答：(2) 给出后序遍历序列（2分）答：CDBHIGFEA6有一份电文AECBECACDEDBEDCEADEBCDBDFD，试对每个字符进行二进制编码，使通信编码的总长度最短, 最后给出通信编码的总长度值。（5分）答：DCBAF26158711E541346E从电文中可得各字符出现的频度为：A3，B4，C5, D7, E6，F1，以频度建立哈夫曼树：各个字符的哈夫曼编码为：A：0001，B：001， C：10， D：01， E：11， F：0000通信编码的总长度值，即WPL=3*4+4*3+5*2+7*2+6*2+1*4=64。7有10个按关键字有序的记录以顺序方式存储，采用什么查找方式查找，使等概率情况下平均查找长度ASL值最小？ ASL值是多少？答：折半查找的平均查找长度最小。4178025936 ASL=(1*1+2*2+3*4+4*3)/10=2.938画出利用逐点插入法建立序列（50，72，85，75，35，45，20，30，66）对应的二叉排序树，并给出查找元素45要进行比较的次数。（5分）5035457230575208566 答： 查找元素45需要比较3次。9将下列9个数据(46，37，70，29，62，78，25，12，20)进行升序排序,请写出希尔(Shell)排序的每趟排序过程（其中d=4,2,1）。（5分）答：初态： 46，37，70，29，62，78，25，12，20 d=4后： 20，37，25，12，46，78，70，29，62 d=2后： 20，12，25，29，46，37，62，78，70 d=1后： 12，20，25，29，37，46，62，70，78 10下面程序将数据(28,76,54,39,87,14)按堆排序法进行排序,请写出建大堆的过程。（5分）28768754391428877654391487762854391411设一组关键子59,42,44,4,92,40,12,36,81,56,38,采用哈希函数:H(key)=key%13，采用开放地址法的线性探测再散列方法解决冲突,画出在012的散列地址空间中对该关键字序列构造哈希表，并给出等概率情况下查找成功的平均查找长度（10分）答：key594244492401236815638H(key)73541112105412比较次数111112112520 1 2 3 4 5 6 7 8 9 10 11 12389240424448159563612ASL=（7*1+2*2+5+2）/11=18/1112描述PRIM算法步骤，并画出以A为初始顶点对G1图生成最小代价生成树的过程（10分）BCAE30242154（G1）F1010D154 答：2(2)EB 2(1)DA10(4)4(3)4(5)FC13用C语言编写算法，将带头结点的单链表中指针P所指向结点删除的算法。（10分）pheaderdelenode(struct node *header, struct node *p) r=header; while (r-next!=p) r=r-next; r-next=p; free(p); 14用C语言编写算法，求二叉排序树中关键字值最小的结点。（10分） struct node *findmin(struct node *root) p=root; while (p-lchild!=NULL) p=p-lchild; return(p);15用C语言编写快速排序中的分区算法，以xlb,xub,和xmid(mid(ub+lb)/2)三者的中间值为枢轴。（10分）int partition(int x,int lb,in ub) mid=(lb+ub)/2; if (xmidxlb & xmidxub)| (xmidxub) t=xlb; xlb