2011-2012(10)数据结构试卷A答案.doc

徐州工程学院试卷答案 2011-2012(一)数据结构A卷试卷答案1、 选择题 1、B 2、B 3、D 4、B 5、D 6、D 7、A 8、B 9、B 10、C二、填空题（共 6小题，每题3分，共计 18 分）1、有穷性 ，确定性 ，可行性 2、 O(1), O(N) 3、 b a c 4、 5、1080 6、n(n-1)/2三、简答及应用（共计44分）1、解：设二叉树上叶子结点数为n0，度为k的分支结点数为nk，则 n = n0 + nk （1）又 二叉树上分支总数：B = k*nk （2） 且n=B+1 （3）联立（1）、（2）、（3），求得： n0=n-nk=n-(n-1)/k=(nk-n+1)/k2、画出广义表(a)，b)，(d)，(e，f)的存储结构，并求其深度。（8分）10e11111110d0f0b10a.7分该广义表深度：3 .1分3解F、(1)二叉树如右图所示：CGKHAJEHDHIBH.5分(2)先序遍历序列为：FCAEBDGHKIJ .2分(3)二叉树转化为森林如下：KJGFIHCDAE.4分B4.ACEDB解：（1）该图如下所示：.2分(2)邻接矩阵如下： 0001000001010000110010010.2分(3)邻接表如下：0A1B2C3D4E2331014.4分5给定一组关键码50，38，62，20，70，16，45，画出执行快速排序的过程。（6分）pivotkey 初始关键字： 50 38 62 20 70 16 45 50 i j进行一次交换后: 45 38 62 20 70 16 50 i i j 进行二次交换后: 45 38 20 70 16 62 50 i j j 进行三次交换后: 45 38 16 20 70 62 50 i i j进行四次交换后: 45 38 16 20 70 62 50 i j j 完成一次排序后: 45 38 16 20 50 70 62 .4分 对左右两侧分别 进行快速排序： 20 38 16 45 62 70 16 20 38 排序结果为： 16 20 38 45 50 62 70.2分6、解：（1）将各元素代入哈希函数得：H0（22）=0 H0（41）=8H0（58）=3H0（47）=3(冲突) H1（47）=4 H0（30）=8 （冲突） H1(30)=9H0（36）=3 （冲突） H1（36）=4（冲突） H2（36）=2H0（69）=3（冲突） H1（69）=4（冲突）H2（69）=2（冲突）H0（69）=7H0（17）=6 （冲突） 采用线性探测的开放定址法解决冲突时的哈希表， 0 1 2 3 4 5 6 7 8 9 10 2236584717694130.6分（2）等概率情况下查找成功时的平均查找长度为：ASLsuc=（4*1+2*2+3+4）/8=15/8 .2分四、算法设计题 （共 2 小题，每题 8 分，共计 16 分）1、解：可采用将该单链表逆置方法，复杂性为O（n）的算法如下。void inverse(linklist &L)p=L; while(p-next!=NULL) p=p-next; tail=p;q=L-next；while(q!=tail)L-next=q-next; p-next=q; p=q; q=L-next; p-next=NULL; .8分2、运用栈的基本操作，试将下列递归过程改写为非递归过程。void test(int &sum)int x;scanf(x);if(x=0) sum=0;elsetest(sum); sum+=x;printf(sum);解：算法如下void test(int &sum) scanf(x); while(x!=0) push(S,x); scanf(x); sum=0;