北京师范大学数据结构教学资料12级数据结构试卷_答案

《北京师范大学数据结构教学资料12级数据结构试卷_答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、北乐师范大学2013-2014学年第1学期期末考试试卷答卷（A卷）课程名称：数据结构任课教师姓名：郑新肖永康卷面总分：100分一、选择题（每小题2分，共20分）1.C2.B3.C4.D5.C6.D7.D8.A9.B10.B二、填空题（每空2分，共20分）1.算法必须是正确的2.s->next=h->next;h->next=s;3.13304.2n0-25.链式6.五种7.CBEFDA8.2（n-l）9.410.关键字值乱序二、判断题（每小题2分，共10分）确误确误确正错正错正四、综合题（共5小题，共5

2、0分）1.（1）template或template（2分）（2）!p、p==NULL>first->link==NULL或p・>link==NULL（3分）（3）pr=p（3分）（4）p->link=pi•或first->link=pr（3分）（1）二叉排序树（3分）（2）平衡二叉树（7分，共3次平衡调整，分别2分、3分、2分）3.(2)KrusKal最小生成树产生过程(3分)4.(1)散列表(4分)散列地址01234567891011121314151617键关字3217

3、634924401030314647比较次数11631211133(2)查找关键字63,H(K)=63mod16=15,依次与31、46、47、32、17、63比较。(2分)(3)查找关键字60,H(K)=60mod16=12,散列地址12内为空，查找失败。(2分)(4)ASLsuss=23/llo(2分)5.(b)插入11(c)插入4、8、13(d)插入1012671)建立5阶B・树的过程如下(6分，每错1图扣1分扣完为止):(a)插入1、2、6、7(e)插入5、17、9、16(f)插入207R^Il

4、ll心13HI17457K9(g)插入3、12、14、18、192)删除四个关键字的过程如下(4分,(a)初始5阶B树(c)删除15后的结果•10•/1I12

5、[_I4(h)插入15每错1图扣1分):(d)删除4后的结果北京师范大学2013〜2014学年第1学期期末考试试卷答卷（B卷）课程名称：数据结构任课教师姓名：郑新肖永康卷面总分：100分一、选择题（每小题2分，共20分）1.B2.C3.B4.D5.A6.A7.D&A9.A10.C二、填空题（每空2分，共20分）1.线性结构、非线性结构2.两种、五

6、种3.0、n（n-l）4.顺序、按关键字值有序排列5.4、5三、判断题（每小题2分，共10分）1.错误2.错误3.错误4.正确5.错误四、简答题（共5道题，每道题10分，共50分）或者2627933102426（第1图7分每错1项扣1分扣完为止，第2图3分）2.0.05^^0.01这棵树的带权路径长度为：(0.01+0.05)*54-0.09*4+(0.18+0.13+0.12)*3+(0.23+0.19)*2=0.3+0.36+1.29+0.84=2.79（每非叶结点一分共7分；带权路径长度3分，如果

7、数值不对但方法正确可得2分）交换22与65得60562299651688100交换16与99得60562216659988100交换16与60得16562260659988100（只给出最终结果4分，中间过程每步3分）4.D[l]D⑵DC]D[4]D⑸D⑹03015ooOOOO1903519一028一210290230V1-V315V1-V3-V219V1-V3-V519V1-V3-V5-V421V1-V3-V5-V4-V623（每条路径或权值1分，D[i]的每次更新1分）5・釆用除留余数法构造哈希函数

8、，其除数取比哈希空间小的素数，比11小的素数为7,所以得到哈希函数为H(k)二kMOD7o位置012345678910存储633670943275482518英平均查找长度为2。或者采用除留余数法构造哈希函数，其除数可以取等于哈希空间的素数11,得到哈希函数为H(k)=kMOD11o位置012345678910存储702548369418637532其平均查找长度为2。(哈希表8分，每错一项扣一分，扣完为止；平均查找长度2分，如果数值不对但方法正确可得1分)