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

《《算法与数据结构》模拟试题4--答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》模拟试题4(参考答案)一、填空题（每小题2分，共18分）1、线性结构树形结构图（或网）状结构2、表的一端表的另一端3、数据元素是一个字符4、2005、2h-16、n2e7、以顺序方式存储结点按关键字有序8、索引散列9、归并内、外存之间的数据交换二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ACBCDBCDA三、分析题（每题6分，共30分）1、解：依题意对应的Huffman树如下图所示。39891772354691322WPL=(2+3)×4+(4+6+7)×3+(8+9)×2=1052、解：该网的邻接链表如下图

2、所示：012312342123748∧11236411∧261745∧1821135∧从顶点V3出发的深度优先搜索的顶点序列是3→2→1→4，相应的生成树如下：最小生成树1243567从顶点V3出发深度优先搜索生成树124381263、解：将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示；最后再插入13之后的二叉排序树T2。图(a)生成的二叉排序树14719913416251218图(b)删除13的二叉排序树147199124162518图(c

3、)插入13的二叉排序树147199124162518134、解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：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得到的

4、散列表结构如下：散列地址关键字0123456789103367462515361718193142成功查找的平均查找长度：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第三趟归并完毕，排序结束。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实

5、现算法功能。每个空白处只能填一个语句。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].key>L->R[k+1].keyL->R[k+1]=L->R[0]五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定

6、义及算法如下：#defineintElemTypetypedefstructLnode{ElemTypedata;/*数据域，保存结点的值*/structLNode*next;/*指针域*/}LNode;/*结点的类型*/voidDynomic_search(LNode*L,ElemTypek){LNode*ptr,*p=L,*q=L->next;while(q!=NULL&&q->data!=k){p=q;q=q->next;}if(q->data==k){p->next=q->next;free(q);}/*若存在结点，则删除*/else{ptr=(*LNode)ma

7、lloc(sizeof(LNode));ptr->data=k;ptr->next=L->next;L->next=ptr;}/*若结点不存在，插入新结点作为第一个结点*/}算法分析：设链表的长度为n，算法的时间主要耗费在移动指针q上，故时间复杂度为O(n)。