2015年考研计算机数据结构测试题(六)答案.doc

2015年考研：计算机数据结构测试题（六）答案 　一、选择题 　　1.A 2.B 3.A 4.A 5.D 　　6.B 7.B 8.B 9.C 10.C 　　二、填空题 　　1. 1. top1+1=top2 　　2. 2. 可以随机访问到任一个顶点的简单链表 　　3. 3. i(i+1)/2+j-1 　　4. 4. FILO，FIFO 　　5. 5. ABDECF，DBEAFC，DEBFCA 　　6. 6. 8，64 　　7. 7. 出度，入度 　　8. 8. ki=k2i ki=k2i+1 p= 　　9. 9. n-i，r[j+1]=r[j] 　　10. 10. mid=(low+high)/2，r[mid].keyk 　　三、应用题 　　1. 1. DEBCA 　　2. 2. E={(1,5),(5,2),(5,3),(3,4)},W=10 　　3. 3. ASL=(1*1+2*2+3*4)/7=17/7 　　4. 4. ASL1=7/6，ASL2=4/3 　　四、算法设计题 　　1. 1. 设计判断两个二叉树是否相同的算法。 　　typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; 　　int judgebitree(bitree *bt1,bitree *bt2) 　　{ 　　if (bt1==0 bt2==0) return(1); 　　else if (bt1==0 || bt2==0 ||bt1-data!=bt2-data) return(0); 　　else return(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild)); 　　} 　　2. 2. 设计两个有序单链表的合并排序算法。 　　void mergelklist(lklist *ha,lklist *hb,lklist *hc) 　　{ 　　lklist *s=hc=0; 　　while(ha!=0 hb!=0) 　　if(ha-datadata){if(s==0) hc=s=ha; else {s-next=ha; s=ha;};ha=ha-next;} 　　else {if(s==0) hc=s=hb; else {s-next=hb; s=hb;};hb=hb-next;} 　　if(ha==0) s-next=hb; else s-next=ha; 　　} 　　实践是检验真理的唯一标准，做题时检验自身的重要途径，新东方在线小编希望每一位考生都能够把握理论基础，注重实践应用，真正做到统筹全局，整体提升。在这里预祝大家2015年考研，取得一个好成绩，加油!