级数据结构与算法试卷A卷-参考答案

2013—2014学年第一学期闽江学院考试试卷《数据结构与算法》A卷参考答案及评分标准一、选择题答案（每题2分）30%123456789101112131415BACDCDBCCDDCABC二、填空题（每空2分）20%1、p->nexts2、53、1+n2+2n3+…+(k-1)nk4、n-1n+15、CDBGFEA6、2n-17、A[7]、A[3]、A[5]、A[4]8、2e三、判断题（每题1分）10%12345678×√×××√××四、应用题（5小题）32% 1、（6分）画哈夫曼树（每个叶子结点位置正确得0.5分，总5分）计算WPL正确得1分WPL=(2+4)*5+(5+7+8)*4+(9+10+15+18)*3+22*2=30+80+156+44=310100100415919262233910111518567824152、（8分）(1)二叉排序树(每个结点在正确的位置正确得0.5分，总6分)10041100415919262233910111518567824152714663562283113212560(2)查找成功时的平均查找长度：（总2分）ASL=(1*1+2*2+4*3+5*4)/12=37/12=3.083、（5分）（每行正确得0.5分，总5分）原始数据：（27），10，21，37，9，55，16，61，103，2第一趟后:（10，27），21，37，9，55，16，61，103，2第二趟后:（10，21，27），37，9，55，16，61，103，2第三趟后:（10，21，27，37），9，55，16，61，103，2第四趟后:（9，10，21，27，37），55，16，61，103，2第五趟后:（9，10，21，27，37，55），16，61，103，2第六趟后:（9，10，16，21，27，37，55），61，103，2第七趟后:（9，10，16，21，27，37，55，61），103，2第八趟后:（9，10，16，21，27，37，55，61，103），2第九趟后:（2，9，10，16，21，27，37，55，61，103）4、（5分）哈希表，每个表结点在正确的位置得0.5分，计4分；查找成功时的平均查找长度正确得1分。Key23149630121829H（key）20262541014∧129∧223930∧3∧418∧512∧66∧ASL成功=（1*6+2*1+3*1）/8=11/8=1.3625(1分)5、（8分）邻接表存储（4分）V1V210V33∧V2V110V42∧V3V13V47∧V4V22V37V55V64∧V5V45V68V74∧V6V44V58V76V81∧V7V54V66∧V83∧V8V61V73∧得分标准：每个结点的邻接点均正确得0.5分（即每行0.5分）克鲁斯卡尔算法画出最小生成树的过程（4分）：V2V1V2V1V3V4V5V6V7V8V2V1V3V4V5V6V7V817（1）（2）2V2V12V2V1V3V4V5V6V7V81723V2V1V3V4V5V6V7V817（3） （4）323323V2V1V3V4V5V6V7V8173423V2V1V3V4V5V6V7V817（5） （6）3423423V2V1V3V4V5V6V7V8417342713V2V1V3V4V5V6V7V8417（7）（8）得分标准：依次得出上面八张图，每张0.5分，计4分，其中第（4）、（5）张，第（6）、（7）张两权值相同的边顺序可调换。五、编程题（2小题，每题5分）10%1、已知二叉树以二叉链表作为存储结构，试编写按前序遍历该二叉树的递归算法。(5分)二叉链表的结点定义如下：typedefcharTElemType;typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;答案：voidPreorder(BiTreeT)1%{if(T){1%printf(“%c”,T->data);1%Preorder(T->lchild);1%Preorder(T->rchild);1%}}2、试写出折半查找算法的非递归实现算法。(5分)查找表定义如下：typedefintKeyType;typedefstruct{keyTypekey;//关键字域……//其它属性域}ElemType;typedefstruct{ElemTypeelem[maxsize+1];//0号单元留空intlength;//表的长度}SSTable;答案：intSearch_Bin(SSTableST,KeyTypekval){intlow=1，high=ST.length;1%while(low<=high)0.5%{mid=(low+high)/2;0.5%if（kval==ST.elem[mid].key)0.5%returnmid;0.5%elseif(kval<ST.elem[mid].key))0.5%h