搜索
1《算法与数据结构》模拟试题4(参考答案)一、填空题（每小题2分，共18分）1、线性结构树形结构图（或网）状结构2、表的一端表的另一端3、数据元素是一个字符4、2005、2h-16、n2e7、以顺序方式存储结点按关键字有序8、索引散列9、归并内、外存之间的数据交换二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ACBCDBCDA三、分析题（每题6分，共30分）1、解：依题意对应的Huffman树如下图所示。WPL=(2+3)×4+(4+6+7)×3+(8+9)×2=1053989177235469132222、解：该网的邻接链表如下图所示：从顶点V3出发的深度优先搜索的顶点序列是3→2→1→4，相应的生成树如下：3、解：将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示；最后再插入13之后的二叉排序树T2。012312342123748∧11236411∧261745从顶点V1出发广度优先搜索生成树∧1821135∧最小生成树1243567从顶点V3出发深度优先搜索生成树12438126图(a)生成的二叉排序树14719913416251218图(b)删除13的二叉排序树14719912416251834、解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：H(31)=31MOD11=9H(25)=25MOD11=3H(18)=18MOD11=7H(19)=19MOD11=8H(42)=42MOD11=9冲突H(42)=(9+1)MOD11=10H(67)=67MOD11=1H(15)=15MOD11=4H(33)=33MOD11=0H(17)=17MOD11=6H(36)=36MOD11=3冲突H(36)=(3+1)MOD11=4冲突H(36)=(4+1)MOD11=5H(46)=46MOD11=2得到的散列表结构如下：成功查找的平均查找长度：ASL=(1×9+1×2+1×3)/11=14/115、解：做非递减排序时的每一趟结果如下：第三趟归并完毕，排序结束。初始关键字：35，29，22，16，17，9，38，27，13，45第一趟：9，29，22，13，17，35，38，27，16，45第二趟：9，17，16，13，27，22，38，29，35，45第三趟：9，13，16，17，22，27，29，35，38，45图(c)插入13的二叉排序树14719912416251813散列地址关键字01234567891033674625153617181931424四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、循环队列Q的入队操作算法。(Q.rear+1)%Max_Queue_Size==Q.frontQ.rear=(Q.rear+1)%Max_Queue_Size;2、二叉树先序遍历的非递归算法。P=p-Lchildp=stack[top--]p!=NULL3、统计图中顶点的入度。P=G-adjlist[k].firstarcP=p-nextarc4、冒泡排序算法。flag=TRUEL-R[k].keyL-R[k+1].keyL-R[k+1]=L-R[0]五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#defineintElemTypetypedefstructLnode{ElemTypedata;/*数据域，保存结点的值*/structLNode*next;/*指针域*/}LNode;/*结点的类型*/voidDynomic_search(LNode*L,ElemTypek){LNode*ptr,*p=L,*q=L-next;5while(q!=NULL&&q-data!=k){p=q;q=q-next;}if(q-data==k){p-next=q-next;free(q);}/*若存在结点，则删除*/else{ptr=(*LNode)malloc(sizeof(LNode));ptr-data=k;ptr-next=L-next;L-next=ptr;}/*若结点不存在，插入新结点作为第一个结点*/}算法分析：设链表的长度为n，算法的时间主要耗费在移动指针q上，故时间复杂度为O(n)。