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

《算法与数据结构》模拟试题4(参考答案) 一、填空题（每小题2分，共18分） 1、 线性结构 树形结构 图（或网）状结构 2、 表的一端 表的另一端 3、 数据元素是一个字符 4、 200 5、 2h-1 6、 n 2e 7、 以顺序方式存储 结点按关键字有序 8、 索引 散列 9、 归并 内、外存之间的数据交换 二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分） 题号 1 2 3 4 5 6 7 8 9 答案 A C B C D B C D A 三、分析题（每题6分，共30分） 1、 解：依题意对应的Huffman树如下图所示。 WPL=(2+3)×4+(4+6+7)×3+(8+9)×2=105 2、 解：该网的邻接链表如下图所示： 从顶点V3出发的深度优先有哪些信誉好的足球投注网站的顶点序列是3→2→1→4，相应的生成树如下： 3、 解：将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示；最后再插入13之后的二叉排序树T2。 4、 解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下： H(31)=31 MOD 11=9 H(25)=25 MOD 11=3 H(18)=18 MOD 11=7 H(19)=19 MOD 11=8 H(42)=42 MOD 11=9 冲突 H(42)=(9+1) MOD 11=10 H(67)=67 MOD 11=1 H(15)=15 MOD 11=4 H(33)=33 MOD 11=0 H(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(46)=46 MOD 11=2 得到的散列表结构如下： 成功查找的平均查找长度：ASL=(1×9+1×2+1×3)/11=14/11 5、 解：做非递减排序时的每一趟结果如下： 第三趟归并完毕，排序结束。 四、算法填空（每空2分，共20分） 请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。 1、 循环队列Q的入队操作算法。 (Q.rear+1)%Max_Queue_Size==Q.front Q.rear=(Q.rear+1)%Max_Queue_Size ; 2、 p!=NULL 3、统计图中顶点的入度。 P=G-adjlist[k].firstarc P=p-nextarc 4、冒泡排序算法。 flag=TRUE L-R[k].keyL-R[k+1].key L-R[k+1]=L-R[0] 五、编写算法（要求给出相应的数据结构说明，14分） 解：结点类型定义及算法如下： #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!=NULLq-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)。 1 16 4 12 25 16 4 13 9 12 图(a) 生成的二叉排序树 19 7 14 0 1 3 2 18 1 7