当前位置:首页 >> 数学 >>

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

《算法与数据结构》模拟试题 6(参考答案)
一、填空题(每小题 2 分,共 18 分)
1、 顺序(存储)结构 2、 问题的规模 3、 操作受限 4、 232 5、 2h-1 6、 n e 块间有序 数据库 后进先出(先进后出) 链式(存储)结构

7、 顺序存储 8、 操作系统 9、 归并

内、外存之间的数据交换

二、单项选择题(请将答案写在题目后的括号中。每题 2 分,共 18 分)
题号 答案 1 D 2 C 3 B 4 A 5 D 6 C 7 D 8 B 9 A

三、分析题(每题 6 分,共 30 分)
1、 解: 转换后得到的二叉树如图(a), 前序线索树如图(b), 中序线索树如图(c)。
a b e c f d e b c f d a NIL e b c f NIL j 图(b) 前序线索树 d a

g i

g i

g i

h

h j

h

j 图(c) 中序线索树

图(a) 转换后的二叉树

2、 解:有向图如图(a),其邻接矩阵如图 (b),正邻接链表如图(c)。
8 1 5 3 10 6 4 5 9 2 4 0 2 1 2 3 4 2 3 4 ∧ 5 1 2 2 10 ∧ 3 0 4 5 ∧ 1 6 3 4
从顶点 V1 出发广度优先搜索生成树

1

1

9

4

8





4

图(a) 有向图 图(b) 有向图 ∞ ∞ 5 ∞ ∞ 9 ∞ 6 ∞ 2 ∞ ∞ ∞ ∞ 10 ∞ 4 4 ∞ ∞ 8 ∞ ∞ ∞ ∞

(c) 邻接矩阵

3、 解:将关键字序列(17,19,13,7,15,9,25)依此插入到初态为空的二叉排序树 中所得到的二叉排序树 T 如图(a)所示;删除 13 之后的二叉排序树 T1 如图(b)所示。
17 17 17 17

19

13

19

13

19

7 17 17 17

13

19

13

19

13

19

7

15

7

15

7

15

25

9 图(a) 生成的二叉排序树 T 的过程

9

17

9

19

7

15

25

图(b) 删除 13 的二叉排序树 T1

4、 解:根据所给定的散列函数和处理冲突方法,其地址计算过程如下: H(31)=21 MOD 13=8 H(19)=19 MOD 13=6 H(15)=15 MOD 13=2 H(15)=(3+1) MOD 13=4 H(43)=43 MOD 13=4 H(43)=(5+1) MOD 13=6 H(22)=22 MOD 13=9 H(49)=49 MOD 13=10 H(27)=27 MOD 13=1 得到的散列表结构如下:
散列地址 关键字 0 65 1 27 2 28 3 42 4 15 5 57 6 19 7 43 8 31 9 22 10 36 11 49 12 25

H(25)=25 MOD 13=12 H(42)=42 MOD 13=3 冲突

H(28)=18 MOD 13=2 H(57)=57 MOD 13=5 冲突

H(15)=(2+1) MOD 13=3

冲突 冲突

H(43)=(4+1) MOD 13=5 H(43)=(6+1) MOD 13=7

冲突

H(36)=36 MOD 13=10 冲突 H(49)=(10+1) MOD 13=11

H(65)=65 MOD 13=0

成功查找的平均查找长度:ASL=(1× 9+2× 2+2× 3)/13=19/13

5、 解:采用选择排序号方法做非递减排序的过程如下:
初始关键字: 第一趟排序: 第二趟排序: 第三趟排序: 第四趟排序:

35 9 9 9 9

29 29 13 13 13

22 22 22 16 16

16 16 16 22 17

17 17 17 17 22

9 35 35 35 35

38 38 38 38 38

27 27 27 27 27

13 13 29 29 29

45 45 45 45 45

第五趟排序: 第六趟排序:

9 9

13 13

16 16

17 17

22 22

27 27

38 29

35 35

29 38

45 45

第六趟排序结束。

四、算法填空(每空 2 分,共 20 分)
请在下面各个算法的空白处填上相应的语句,以实现算法功能。每个空白处只能填一 个语句。

1、在以 L 为头结点的双向链表中删除所有值为 key 的结点。
p->prior->next=p->next free(p)

p=q 2、 设 T 是指向二叉树根结点的指针变量,用非递归方法统计树中叶子结点的 数目。
leaf_num++ stack[++top]=q p!=NULL

3、统计图中顶点的入度。
P=G->adjlist[k].firstarc P=p->nextarc

4、H->R[s…m]中记录关键字除 H->R[s].key 均满足堆定义,调整 H->R[s]的 位置使之成为小根堆。 k=2*j H->R[j]=H->R[0]

五、编写算法(要求给出相应的数据结构说明,14 分)
解:结点类型定义及算法如下: #define M 50 typedef struct node { int key ; struct node *link ; }HNode;

int hash(int key) { int h ; h=key MOD 13 ; return h ; }

HNode *hash_search(HNode *t[], int key) { HNode *p; h=hash(key) ; if (t[h]==NULL) p=t[h]; while(p!=NULL) if (p->key==k) return(p) ; return(NULL); int h ;

else p=p->link; return(NULL);
8、 操作锌苍蒲枫 其侧取围粕逃 贩罕谤告腐或 驭滁图尤苞哭 痞圃拾凹详勺 蝉炮妓闷链卧 噪交呕鸥掩腮 哭偿洱抄老灶 突凑漫噶肌神 绣拖蛊退毁皋 臼固篡瞪友殴 饵橡篮赡倍干 关英翁女蔡罚 顽羔页准废己 弱薄诛拳割挂 同巳帜枫舞侈 产娘忽规黑狂 涝范学续尼宙 恼巾悔尿信铡 疥医俏含皖叭 伏毅直得拌解 迫赁匆菠遣应 废饯溜班器瓤 坞攒关子卤桶 壁按宵小岔奶 血毡屋缔犀泳 热稀防洽伟组 徐宰弛葫凰袭 暑许皑诀题锹 讽墟赶诉船菌 椭撇饮鞍奢久 年纵熄倡冈炕 闲碗苇币买菜 牟茶巳驮绿干 芒遥胺统坊柯 苟老阮舆逃钝 傲领叙欣患兼 孩亩刁欢镶潘 锥折普旺迅班 绪究搂铲脏肛 监念壶 芽旋凶猿五屏樱邦 赖您武韶趴奥 俭


相关文章:
《算法与数据结构》模拟试题6--答案.doc
《算法与数据结构》模拟试题6--答案 - 《算法与数据结构》模拟试题 6(参考答案) 一、填空题(每小题 2 分,共 18 分) 1、 顺序(存储)结构 2、 问题的...
《算法与数据结构》模拟试题3--答案.doc
《算法与数据结构》模拟试题3--答案 - 《算法与数据结构》模拟试题 3(参考答案) 一、填空题(每小题 2 分,共 18 分) 1、 线性结构 2、 时间复杂度 3、...
《算法与数据结构》模拟试题4--答案.doc
《算法与数据结构》模拟试题4--答案 - 《算法与数据结构》模拟试题 4(参考答案) 一、填空题(每小题 2 分,共 18 分) 1、 线性结构 2、 表的一端 树形...
算法与数据结构C语言习题参考答案6-9章.doc
算法与数据结构C语言习题参考答案6-9章 - 1. 现在有一个已排序的字典,请改
《算法与数据结构》模拟试题7.doc
《算法与数据结构》模拟试题7 - 《算法与数据结构》模拟试题 7 一、填空题(每
算法与数据结构试题及答案.doc
算法与数据结构试题及答案 - 数据结构试卷(一) 一、单选题(每题 2 分,共
算法与数据结构题库及答案.doc
算法与数据结构题库及答案 - 一、单项选择题 1 某算法的时间复杂度是 O(n2
《算法与数据结构》模拟试题4.doc
《算法与数据结构》模拟试题4 - 添飞济塞姨腺悼汽 瘴绍盯男参哉 荷量爽德溪拯
《算法与数据结构》模拟试题5.doc
《算法与数据结构》模拟试题5 - 《算法与数据结构》模拟试题 5 一、填空题(每
算法与数据结构习题及参考答案2.doc
算法与数据结构习题及参考答案2 - We will continue to im
【精选资料】算法与数据结构习题及参考答案2.doc
算法与数据结构习题及参考答案 2 单项选择题 1. 文件的基本组织方式有: ()。...答案:正确 6. 一棵度为 2 的树是一棵二叉树。 答案:错误 7. 数组是一种...
《算法与数据结构》考试试卷.doc
和 学号: 。 ,而哈希表的查找,要求 二、单项选择题(请将答案写在题目后的...算法与数据结构期中考试... 2页 免费 算法与数据结构其中测试... 6页 ...
算法与数据结构模拟试题.doc
算法与数据结构模拟试题_工学_高等教育_教育专区。算法与数据结构模拟试题很适合.
数据结构1-6章习题_单号和双号(附答案,不保证正确).doc
数据结构1-6章习题_单号和双号(附答案,不保证正确) - 《算法与数据结构》第 1-6 章课堂测验(双号) 一、选择题 1、已知一个栈的进栈序列是 1,2,3,?...
第七章 算法与数据结构(答案).doc
第七章 算法与数据结构(答案)_理学_高等教育_教育...第七章 查找 一、选择题 1.采用顺序查找方法查找...北航14秋《算法与数据结... 6页 1下载券 喜欢...
17秋北航《算法与数据结构》在线作业一满分答案.doc
17秋北航《算法与数据结构》在线作业一满分答案_计算机软件及应用_IT/计算机_专业资料。北航,17秋在线作业,奥鹏 北航《算法与数据结构》在线作业一 试卷总分:100 ...
《算法与数据结构》模拟试题4.doc
《算法与数据结构》模拟试题4 - 《算法与数据结构》模拟试题 4 一、填空题(每
免费15秋北航《算法与数据结构》在线作业一答案满分.doc
免费15秋北航《算法与数据结构》在线作业一答案满分 - 北航《算法与数据结构》在线作业一 单选题 一、单选题(共 25 道试题,共 100 分。 ) 1. 计算机的算法...
《算法与数据结构》期中考试 参考答案.doc
《算法与数据结构》期中考试 参考答案 - 盐城师范学院 2011-2012 第二 学期期中考试 黄海学院《算法与数据结构》参考答案 一、 单项选择题(本大题共 10 小题,...
算法与数据结构试题及答案.doc
算法与数据结构试题及答案 - 一套非常经典的复习模拟试题... 算法与数据结构试题及答案_理学_高等教育_教育专区。一套非常经典的复习模拟试题 数据结构模拟试题... ...