数据结构考试题9.doc

(完整word版)数据结构考试题9要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题2分，共20小题，共计40分）1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度为（ ）。x=1;while (xnext，*pb=hb-next，*q;free(hb);hc=ha; hc-next=NULL;/hc利用ha的头结点，并设置为空while (pa!=NULL & pb!=NULL)/扫描ha、hb的数据结点if (pa-datadata)/将较小结点采用头插法插入到hc中q=pa-next;pa-next=hc-next;hc-next=pa;pa=q;elseq=pb-next;pb-next=hc-next;hc-next=pb;pb=q;if (pb!=NULL) pa=pb;while (pa!=NULL)/将没有扫描完的结点采用头插法插入到hc中q=pa-next;pa-next=hc-next;hc-next=pa;pa=q;评分说明：上述算法的时间复杂度为O(m+n)。若设计的算法时间复杂度为O(m*n)，至少扣3分，若设计的算法空间复杂度不为O(1)，扣2分。2、（10分）参考算法如下：int singleodes(BTNode *b)if (b=NULL) return 0; if (b-lchild=NULL & b-rchild!=NULL) |/单分支的结点(b-lchild!=NULL & b-rchild=NULL)return singleodes(b-lchild)+ singleodes(b-rchild)+1;elsereturn singleodes(b-lchild)+ singleodes(b-rchild);）评分说明：可以采用任意一种遍历方法。判断单分支的结点为3分。