《算法与数据结构》模拟试题3--答案.doc

《算法与数据结构》模拟试题3(参考答案)一、填空题(每小题2分,共18分)1、线性结构树形结构图(或网)状结构2、时间复杂度空间复杂度3、(直接)前驱结点(直接)后继结点4、零个字符组成的串05、3006、只有右子树上的所有结点7、先序遍历8、索引块9、操作系统数据库二、单项选择题(请将答案写在题目后的括号中。每题2分,共18分)题号123456789答案ABCBDBBCD三、分析题(每题6分,共30分)fabcehidgNULLfabcehidg图(a)二叉树图(b)后序线索化树1、解:所画出的二叉树如图(a)所示。树的后序遍历序列是gdhiebfca,其后序线索化树如图(b)所示。2、解:该网的邻接链表如下图所示:01234**********∧1934413511∧241743∧2133353∧2114318∧从顶点V1出发的广度优先搜索的顶点序列是1→2→3→5→4,相应的生成树如下:1524389137从顶点V1出发广度优先搜索生成树从顶点V5出发的最小生成树1524333473、解:将关键字序列(14,9,18,7,4,13,25,19,6)依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示;删除18之后的二叉排序树T1如图(b)所示;最后再插入18之后的二叉排序树T2。149197134256图(b)删除18的二叉排序树149**********图(a)生成的二叉排序树149**********图(c)插入18后的二叉排序树4、解:根据所给定的散列函数和处理冲突方法,得到的散列表结构如下:0**********∧∧∧∧33∧5625∧47∧71∧1729∧8∧42∧9569成功查找的平均查找长度:ASL=(1×8+2×2+3×1)/11=17/115、解:做非递减排序时的每一趟结果如下:初始关键字:35,29,52,60,17,9,38,27,13,45第一趟:[29,35][52,60][9,17][27,38][13,45]第二趟:[29,35,52,60][9,17,27,38][13,45]第三趟:[29,35,52,60][9,13,17,27,38,45]第四趟:[9,13,17,27,29,35,38,45,52,60]第四趟归并完毕,排序结束。四、算法填空(每空2分,共20分)请在下面各个算法的空白处填上相应的语句,以实现算法功能。每个空白处只能填一个语句。1、循环队列Q的队首元素出队操作算法。===(+1)%Max_Queue_Size;2、二叉树中序遍历的非递归算法。p=stack[top--]p=p->Rchildbool!=03、折半查找算法。Mid=(Low+High)/2return(0)4、简单选择排序算法。L->R[n].key<L->R[k].keyk!=mL->R[k]=L->R[0