2009数据结构学位考试试卷A参考答案

你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。==============================================================================命运如同手中的掌纹，无论多曲折，终掌握在自己手中==============================================================数据结构学位考试试卷A参考答案一、单项选择题(每题1分,只有一个正确答案）1、A 2、B 3、B 4、D 5、D 6、C 7、C 8、B 9、D 10、B二．判断题(正确打“√”,错误打“×”)1、× 2、√ 3、√ 4、√ 5、√ 6、√ 7、√ 8、× 9、× 10、×三．阅读算法（ （1）、S1的功能：将p指向该单链表的最后一个节点 （2）、S2的功能：将p的next指针指向第1个节点，原第1个节点的next指针置为空 （3）、(a2,……an-1,an,a1,)四．算法填空（每空2分,共10分）return1;return++c1;NodeLevel(BT->right,x)c2>=1return++c2;五．应用题（共30分）1、已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHIJ和BCDAFEHJIG，试给出该二叉树的后序遍历序列并绘出该二叉树对应的森林。(10分）AABECDFGHIJ2.已知邻接矩阵: v0 v1 v2 v3 v4 v5v0 0 ∞ 10 ∞ 30 100v1 ∞ 0 5 ∞ ∞ ∞v2 ∞ ∞ 0 50 ∞ ∞v3 ∞ ∞ ∞ ∞ ∞ 10v4 ∞ ∞ ∞ 20 ∞ 60v5 ∞ ∞ ∞ ∞ ∞ ∞(1).画出该图(2).求出顶点V0到其它顶点的最短路径(要求写出求解过程的表)(12分）V0V0V1V2V3V4V510301005501020601、v0->v2 102、v0->v2->v3 603、v0->v4 304、v0->v2->v3->v5 703．用给出的一组权值{7，19，2，6，32，3，21，10}，构造一棵哈夫曼树，并计算其带权路径长度WPL。（要求写出哈夫曼树构造过程及WPL的计算过程）(8分） 100 60 40 28 32 19 21 11 17 5 6 7 102 3 WPL=(2+3)*5+(6+7+10)*4+(32+19+21)*2=261六．编写算法（每小题10分,共20分）1、写出统计二叉树度为二的节点数intBTreeCountDegree2(BinTreeNode*BT) { if(BT==NULL)return0; if(BT->left&&BT->right) return1+BTreeCountDegree2(BT->left)+BTreeCountDegree2(BT->right); else returnBTreeCountDegree2(BT->left)+BTreeCountDegree2(BT->right);}2、现给出函数定义,请写出快速排序的算法：(10分)voidQuickSort(intA[],ints,intt){ inti=s,j=t+1; intx=A[s]; do{ doi++;while(A[i]<x); doj--;while(A[j]>x); if(i<j) { inttemp=A[i]; A[i]=A[j];A[j]=temp; } }while(i