搜索
1《算法与数据结构》模拟试题3(参考答案)一、填空题（每小题2分，共18分）1、线性结构树形结构图（或网）状结构2、时间复杂度空间复杂度3、(直接)前驱结点(直接)后继结点4、零个字符组成的串05、3006、只有右子树上的所有结点7、先序遍历8、索引块9、操作系统数据库二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ABCBDBBCD三、分析题（每题6分，共30分）1、解：所画出的二叉树如图(a)所示。树的后序遍历序列是gdhiebfca，其后序线索化树如图(b)所示。fabcehidgNULLfabcehidg图(a)二叉树图(b)后序线索化树22、解：该网的邻接链表如下图所示：从顶点V1出发的广度优先搜索的顶点序列是1→2→3→5→4，相应的生成树如下：3、解：将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除18之后的二叉排序树T1如图(b)所示；最后再插入18之后的二叉排序树T2。0123412345293758∧1934413511∧241743从顶点V1出发广度优先搜索生成树∧2133353∧2114318∧1524389137从顶点V1出发广度优先搜索生成树从顶点V5出发的最小生成树15243334714918713419256图(a)生成的二叉排序树149197134256图(b)删除18的二叉排序树34、解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：成功查找的平均查找长度：ASL=(1×8+2×2+3×1)/11=17/115、解：做非递减排序时的每一趟结果如下：第四趟归并完毕，排序结束。14919713418256图(c)插入18后的二叉排序树012345678910∧∧∧∧33∧5625∧47∧71∧1729∧8∧42∧9569初始关键字：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]4四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、循环队列Q的队首元素出队操作算法。Q.front==Q.rearQ.front=(Q.front+1)%Max_Queue_Size;2、二叉树中序遍历的非递归算法。p=stack[top--]p=p-Rchildbool!=03、折半查找算法。Mid=(Low+High)/2return(0)4、简单选择排序算法。L-R[n].keyL-R[k].keyk!=mL-R[k]=L-R[0]五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#defineintElemTypetypedefstructLnode{ElemTypedata;/*数据域，保存结点的值*/structLNode*next;/*指针域*/}LNode;/*结点的类型*/voidDelete_LinkList_Value(LNode*L){LNode*p=L-next,*q,*ptr;5ElemTypek;while(p-next!=NULL){k=p-data;ptr=p;q=ptr-next;while(q!=NULL){if(q-data==k){ptr-next=q-next;free(q);}/*删除值相同的结点*/ptr=ptr–next;q=ptr–next;/*继续检查后续结点*/}p=p-next;/*继续检查下一结点，是否有值相同的结点*/}算法分析：设单链表长度为n，若指针p指向第i(i∈[1,n-1])个结点，则删除和指针p所指向结点值相同的结点时：比较次数为n-i，指针的移动次数为n-i，则总的比较次数为：所以，时间复杂度为：O(n2)i=1∑(n-i)=n(n-1)/2n-1