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

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

2、下图所示： 012312342123748112364112617451821135从顶点V3出发的深度优先搜索的顶点序列是3214，相应的生成树如下：最小生成树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) 插入13的二叉排序树

3、147199124162518134、 解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：H(31)=31 MOD 11=9 H(25)=25 MOD 11=3 H(18)=18 MOD 11=7H(19)=19 MOD 11=8 H(42)=42 MOD 11=9 冲突 H(42)=(9+1) MOD 11=10H(67)=67 MOD 11=1 H(15)=15 MOD 11=4 H(33)=33 MOD 11=0H(17)=17 MOD 11=6 H(36)=36 MOD 11=3 冲突 H(36)=(3+1) MOD 11=4 冲突H(36)=(4+1) MOD 11=5 H

4、(46)=46 MOD 11=2得到的散列表结构如下：散列地址关键字0 1 2 3 4 5 6 7 8 9 1033 67 46 25 15 36 17 18 19 31 42成功查找的平均查找长度：ASL=(19+12+13)/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第三趟归并完毕，排序结束。四、算法填空（每空

5、2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的入队操作算法。(Q.rear+1)%Max_Queue_Size=Q.frontQ.rear=(Q.rear+1)%Max_Queue_Size ;2、 二叉树先序遍历的非递归算法。P=p-Lchildp=stacktop-p!=NULL 3、统计图中顶点的入度。P=G-adjlistk.firstarcP=p-nextarc4、冒泡排序算法。flag=TRUEL-Rk.keyL-Rk+1.keyL-Rk+1=L-R0五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型

6、定义及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 数据域，保存结点的值 */struct LNode *next; /* 指针域 */LNode; /* 结点的类型 */void Dynomic_search(LNode *L , ElemType k) 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)malloc(sizeof(LNode) ; ptr-data=k ; ptr