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

1《算法与数据结构》模拟试题6(参考答案)一、填空题（每小题2分，共18分）1、顺序（存储）结构链式（存储）结构2、问题的规模3、操作受限后进先出(先进后出)4、2325、2h-16、ne7、顺序存储块间有序8、操作系统数据库9、归并内、外存之间的数据交换二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案DCBADCDBA三、分析题（每题6分，共30分）1、解：转换后得到的二叉树如图(a)，前序线索树如图(b)，中序线索树如图(c)。abfcgedijh图(a)转换后的二叉树图(b)前序线索树abfcgedijhNIL图(c)中序线索树NILabfcgedijh22、解：有向图如图(a)，其邻接矩阵如图(b)，正邻接链表如图(c)。3、解：将关键字序列（17，19，13，7，15，9，25）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示。图(a)有向图12342589105644图(b)有向图401231234∧534∧1948∧12210∧051634从顶点V1出发广度优先搜索生成树∧∞9∞∞8∞∞∞4∞56∞4∞∞∞∞∞∞∞210∞∞（c）邻接矩阵图(a)生成的二叉排序树T的过程1719171319177131917157131917915713191725915713191734、解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：H(31)=21MOD13=8H(25)=25MOD13=12H(28)=18MOD13=2H(19)=19MOD13=6H(42)=42MOD13=3H(57)=57MOD13=5H(15)=15MOD13=2冲突H(15)=(2+1)MOD13=3冲突H(15)=(3+1)MOD13=4H(43)=43MOD13=4冲突H(43)=(4+1)MOD13=5冲突H(43)=(5+1)MOD13=6冲突H(43)=(6+1)MOD13=7H(22)=22MOD13=9H(36)=36MOD13=10H(49)=49MOD13=10冲突H(49)=(10+1)MOD13=11H(27)=27MOD13=1H(65)=65MOD13=0得到的散列表结构如下：成功查找的平均查找长度：ASL=(1×9+2×2+2×3)/13=19/135、解：采用选择排序号方法做非递减排序的过程如下：0123456789101112散列地址关键字65272842155719433122364925图(b)删除13的二叉排序树T125157919173529221617938271345初始关键字：9292216173538271345第一趟排序：9132216173538272945第二趟排序：9131622173538272945第三趟排序：9131617223538272945第四趟排序：4第六趟排序结束。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、在以L为头结点的双向链表中删除所有值为key的结点。p-prior-next=p-nextfree(p)p=q2、设T是指向二叉树根结点的指针变量，用非递归方法统计树中叶子结点的数目。leaf_num++stack[++top]=qp!=NULL3、统计图中顶点的入度。P=G-adjlist[k].firstarcP=p-nextarc4、H-R[s…m]中记录关键字除H-R[s].key均满足堆定义，调整H-R[s]的位置使之成为小根堆。k=2*jH-R[j]=H-R[0]9131617222738352945第五趟排序：9131617222729353845第六趟排序：5五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#defineM50typedefstructnode{intkey;structnode*link;}HNode;inthash(intkey){inth;h=keyMOD13;returnh;}HNode*hash_search(HNode*t[],intkey){HNode*p;inth;h=hash(key);if(t[h]==NULL)return(NULL);p=t[h];while(p!=NULL)if(p-key==k)return(p);elsep=p-link;return(NULL);}