《数据结构与算法》试卷(1A)参考答案

1、江苏技术师范学院2007-2008学年第2学期数据结构与算法试卷（1A）参考答案与评分标准、选择题（每题1.5分，共15分）题号12345678910“案BBADABADCC:、填空（每空1.5分，共15分）1、数据元素的有限集，D上关系的有限集2、n-i3、队列4、20,35、开放定址法，再哈希法，链地址法，建立一个公共溢出区6、非零元很少（t<<m*n）且分布没有规律7、简单路径或简单回路或简单环8、31（m+n2=0+n2=nc-1=31）,26-1=329、log2n三、判断题（10分，每题1分对的打如，错的打X'）题号12345678910卜案VXVVXXXVXV

2、四、简答、应用题（共40分）1设顺序表循环队列中存放元素的数组data口，容量为MAXSIZE队列中队头指针为begin，队尾指针为end,指向队列的指针为pring。采用少用一个元素空间的办法判断队列空与满。写出元素x入队列，x出队列的操作（操作中不考虑队列满与空）。（4分）解：入队歹U:pring->datapring->end=xpring->end=（pring->end+1）%MAXSIZE出队歹U:x=pring->datapring->beginpring->front=（pring->front+1）%MAXSIZE2列出先序遍历

3、能得到ABC序列的所有不同的二叉树。（5分）3已知某算法如下，试说明该算法实现的功能。（6分）#defineMax100voidunknow(intnum,intr)(intstMax,top=0;while(num!=0)(sttop+=num%r;num=num/r;while(top>0)cout<<st-top<<cout<<endl;答：将十进制数num转换成r进制的数，弁输出结果。5分)3G是一个非连通无向图，共有28条边，贝U该图至少有多少个顶点?结点数为28<=n（n-1）/2，则n取满足该式的最小值为解：设有一个顶点为独立的结点

4、，其余结点为全连通图,5对于下图所示的有向图G给出从顶点0到其余各顶点的最短路径及路径长度。（6分）1: 0-1132: 0-283: 0-2-3134: 0-2-3-4195: 0-2-3-4-5216: 0-1-6206已知某二叉树中序遍历的结果为：DGBAECHF,则具有28条边的全连通图具有8,故该图至少有9个顶点。(6分)其后半序遍历的结果为：GDBEHFCA,试画出这棵二叉树。(A；(B)D)(EJQF(G)(H)7对关键字序列(7,4,1,14,100,30,5,9,20,134),设哈希函数为H(k)=kmod13,试给出表长为13的,弁求出在等概率情况下，查找成功的平下标01

5、2345789101112K11443057201009134探查i欠121221128哈希表（用线性探测开放定址法处理冲突）均查找长度。（7分）解：H(7)=7mod13=7H(4)=4mod13=4H(1)=1mod13=1H(14)=14mod13=1冲突H1=(14+1)mod13=2H(100)=100mod13=9H(30)=30mod13=4冲突H1=(30+1)mod13=5H(5)=5mod13=5冲突H1=(5+1)mod13=6H(9)=9mod13=9冲突H1=(9+1)mod13=10H(20)=20mod13=7冲突H1=(20+1)mod13=8H(134)=13

6、4mod13=4冲突H1=(134+1)mod13=5冲突H1=(134+2)mod13=6冲突_H1(134+3)mod13=7冲突H1=(134+4)mod13=8冲突H1=H1=H1=(134+5)mod13=9冲突(134+6)mod13=10冲突(134+7)mod13=11冲突在等概率情况下：ASL=(1*4+5*2+1*8)/10=2.2五、算法设计题（20分）1.题目分析本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除弁回收空间），再插入到链表的最前面。LinkedListdelinsert(L

7、inkedListlist)/list是非空线性链表，链结点结构是(data,link),data是数据域，link是链域。/本算法将链表中数据域值最小的那个结点移到链表的最前面。(p=list->link；/p是链表的工作指针pre=list;/pre指向链表中数据域最小值结点的前驱。q=p;/q指向数据域最小值结点，初始假定是第一结点while(p->link!=null)(if(p->link->data<q->data)(pre=p;q=p->link;/找到新的最小值结点；p=p->link;/ 若最小值是第一元素结点，则不需再操作if(q!=list->link)(pre->link=q->link;/将最小值结点从链表上摘下；q->link= list->link ;q结点插到链表最前面。list->link=q;/算法结束算法讨论算法中假定list带有头结点，否则，插入操作变为q->link=list;list=q。2.解：intLeafCount_BiTree(BitreeT)/求二叉树中叶子结点的数目(if(!T)return0;/空树没有叶子elseif(!T->lchild&&a