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

  1. 1、本文档共5页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《算法与数据结构》模拟试题4--答案.doc

《算法与数据结构》模拟试题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].key L- 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 2 4 3 3 2 12 ∧ 8 4 ∧ 11 4 6 3 12 1 ∧ 5 ∧ 5 4 7 1 6 2 3 11 2 8 1 6 从顶点V3出发深度优先有哪些信誉好的足球投注网站生成树 图 b 删除13的二叉排序树 最小生成树 7 12 8 3 4 2 1 6 5 25 9 18 19 3 4 2 18 1 7 14

文档评论(0)

资料 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档