问南广播电视大季现教中心 数据结构（本）形成性考核作业答案 数茄结构（本）作业4 (本部分作业覆莹数材第器9章的内容) 一、单灵选年是 (1)D (2)C (3)B (4)C (5) (6) A (7) (8)D (9)B (10)D (11)C (12)C (13)A (14)C (15)D (18)B (17)B (18)D (19)D (20)A (21)D (22)D (23)A (24)A (25)C (26)C (27)B (28)A (29)B (30)C 二、填空题 (1) 哈希表查找法 (2) 数据项的值记录 (3) 主关健字 (4) 数学期里值 第1顶共5项 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第1页 共5页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 数据结构（本）形成性考核作业答案 数据结构（本）作业 4 （本部分作业覆盖教材第 8-9 章的内容） 一、单项选择题 （1） D （2） C （3） B （4） C （5） D （6） A （7） C （8） D （9） B （10） D （11） C （12） C （13） A （14） C （15） D （16） B （17） B （18） D （19） D （20） A （21） D （22） D （23） A （24） A （25） C （26） C （27） B （28） A （29） B （30） C 二、填空题 （1） 哈希表查找法 （2） 数据项的值 记录 （3） 主关键字 （4） 数学期望值
河南厂播电现大学现数中心 (5) 顺序 (6) 二分查找升序或降序持刘 (7) 顺序存储结构 (8) 需引顺序查找 顺序查找 (9》 均小于根结点的值均大于根结点的植二叉排序树 (10)自变量函数值 (11)9,14,16,17 (12)内部排序外部排序 (13)交换排序 (14)3 (15)48 (16)堆排序快速排序 (17)主关键字 (18)关健字相等的记录 (19)m1j (20)堆尾堆项向下 三、综合题 1、己知序列(D,83,100,65,10,32,7,9),请写出对此序列果用插入排序法进行 升序排序时各墙的结果。 答： 里始序列：(70》，83,100,65,10,32,7,9 第1墙：(70,83)，100,65,10,32,7,9 第2墙：(70,83,100)，65,1032,7,9 第3趟：(65,70,83,100)，10,32,7,9 第4趟：(10,65,70,83,100)，32,7,9 第5墙：(10,32,65,70,83,100)，7,9 第6墙：(7,10,32.65,70,83.100).，9 第7趟：(7,9,10,32,65,70,83,100) 2. 己知序列(10,18,4.3,6,12,1,9.15.8)，请写出对此序列采用归并排序法进 行升序排序时各墙的结果。 答： 原始序列：10,18,4,3,6,12：1,9,15,8 第1墙：10,183,46,121,9[8,15可 第2墙：3,4,10,18,1Ⅱ1,6,9,12[8,15可 第3墙：3,4,10,18，Ⅱ1,6,89,2.1可 第4墙：1：3,4.6,8,9,10.12,15,18 3、 己知序列(256.301.751,129.937,863,742,694,076,438)请给出采用冒泡 排序法对该序列作升序持列时的每一培结果。 答： 原始序列：256,301,751,129,937,863,742,694,076,438 第1墙：256,301,129.751,863,742,694.076,438,957 第2墙：256,129,301,751,742,694,076.438,863,957 第3墙： 129,256,301,742,694,076,438.751,863,937 第4墙： 129,256,301,694,076,438,742,751,863,937 第2风共5项 版权所有河南电大现教中心范额，邮箱5@加m
河南广播电视大学现教中心 第2页 共5页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （5） 顺序 （6） 二分查找 升序或降序排列 （7） 顺序存储结构 （8） 索引顺序查找 顺序查找 （9） 均小于根结点的值 均大于根结点的值 二叉排序树 （10） 自变量 函数值 （11） 9， 14， 16 ，17 （12） 内部排序 外部排序 （13） 交换排序 （14） 3 （15） 4 8 （16） 堆排序 快速排序 （17） 主关键字 （18） 关键字相等的记录 （19） n-1 n-j （20） 堆尾 堆顶 向下 三、综合题 1、 已知序列（70，83，100，65，10，32，7，9），请写出对此序列采用插入排序法进行 升序排序时各趟的结果。 答： 原始序列：（70），83，100，65，10，32，7，9 第 1 趟： （70，83），100，65，10，32，7，9 第 2 趟：（70，83，100），65，10，32，7，9 第 3 趟：（65，70，83，100），10，32，7，9 第 4 趟：（10，65，70，83，100），32，7，9 第 5 趟：（10，32，65，70，83，100），7，9 第 6 趟：（7，10，32，65，70，83，100），9 第 7 趟：（7，9，10，32，65，70，83，100） 2、 已知序列（10，18，4，3，6，12，1，9，15，8），请写出对此序列采用归并排序法进 行升序排序时各趟的结果。 答： 原始序列：10，18，4，3，6，12，1，9，15，8 第 1 趟： [10，18][ 3，4][6，12][1，9][ 8，15] 第 2 趟： [3，4，10，18，][ 1，6，9，12][ 8，15] 第 3 趟： [3，4，10，18，][ 1，6，8，9，12，15] 第 4 趟： [1，3，4，6，8，9，10，12，15，18] 3、 已知序列（256，301，751，129，937，863，742，694，076，438）请给出采用冒泡 排序法对该序列作升序排列时的每一趟结果。 答： 原始序列：256，301，751，129，937，863，742，694，076，438 第 1 趟： 256，301，129，751，863，742，694，076，438，937 第 2 趟： 256，129，301，751，742，694，076，438，863，937 第 3 趟： 129，256，301，742，694，076，438，751，863，937 第 4 趟： 129，256，301，694，076，438，742，751，863，937
河南广播电视大学现黄中心 第5墙：129,256.301,076,438,694.742.751,863,937 第6墙： 129,256.076.301,438,694.742.751.863,937 第7通： 129,076,256,301,438,694,742.751,863,937 第8墙：076,129.256.301,438,694.742.751,863,937 第9趟：076,129,256,301,438,694,742,751,863,937 4、己知序列(503,87,512,61,908,170,97,275,653,462)请给出采用快速排 序法对该序列作升序排列时的每一墙结果， 答： 原始序列：503,87,512.61,908,170,897,275,653,462 第1趟：【462,87,275,61,170503897,908,653,512] 第2墙：1170,87.273,61]462,503引897,908,653,512] 第3墙：187,6111702751462,503897,908,653,512] 第4墙： 6118711702751462,5031897,908,653.512 第5墙： 61·87,170,[275462,503897,908.653,512] 第6插：61,87,170,275,462,503897,908,653,512] 第7墙：61,87,170.275.462,503512.653]897908) 第8插：61,87,170.275,462,503,512，【6538979081 第9趟：61,87,170,275,462,503,653,897908 第10桶：61,87,170,275,462,503,653,897.908 5、设一组记录的关键字序列为(49,3,59.41,43,47)，采用堆排序算法完成以下操 作：（要求小根堆，并画出中间过程） (1)以二叉树描述6个元素的初始堆 (2)以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆 答： (1)建堆 第一次周整2位置的结点，即59，依次为83,9 49 49 49 调整59 请极83 83 59 83 47 41 47 41 43 47 41 43 59 83 43 59 酒整49 41 不构成小根 41 雄，雕线调整 49 47 43 47 83 43 59 83 49 59 (2)堆排序 41 输41 59 43 3导9交换 43 59桥41的位型 47◆59 47 ◆49 5 834941 3 4941 8350 4 有线小制坤 第3项共5页 版权所有河南电大观教中心范隔，配箱@up恤m
河南广播电视大学现教中心 第3页 共5页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第 5 趟： 129，256，301，076，438，694，742，751，863，937 第 6 趟： 129，256，076，301，438，694，742，751，863，937 第 7 趟： 129，076，256，301，438，694，742，751，863，937 第 8 趟： 076，129，256，301，438，694，742，751，863，937 第 9 趟： 076，129，256，301，438，694，742，751，863，937 4、 已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排 序法对该序列作升序排列时的每一趟结果。 答： 原始序列：503，87，512，61，908，170，897，275，653，462 第 1 趟： [462，87，275，61，170]503[897，908，653，512] 第 2 趟： [170，87，275，61] 462，503[897，908，653，512] 第 3 趟： [87，61]170[275] 462，503[897，908，653，512] 第 4 趟： 61 [87]170[275] 462，503[897，908，653，512] 第 5 趟： 61 ，87，170，[275] 462，503[897，908，653，512] 第 6 趟： 61 ，87，170，275，462，503[897，908，653，512] 第 7 趟： 61 ，87，170，275，462，503[512，653]897[908] 第 8 趟： 61 ，87，170，275，462，503，512，[653] 897[908] 第 9 趟： 61 ，87，170，275，462，503，653，897[908] 第 10 趟： 61 ，87，170，275，462，503，653，897，908 5、 设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操 作：（要求小根堆，并画出中间过程） （1）以二叉树描述 6 个元素的初始堆 （2）以二叉树描述逐次取走堆顶元素后，经调整得到的 5 个元素、4 个元素的堆 答： （1）建堆 49 83 59 41 43 47 调整59 第一次调整n/2位置的结点，即59，依次为83、49 49 83 47 41 43 59 调整83 49 41 47 83 43 59 调整49 41 49 47 83 43 59 41 43 47 83 49 59 不构成小根 堆，继续调整 （2）堆排序 41 43 47 83 49 59 59 43 47 83 49 43 59 47 83 49 43 49 47 83 59 输出41 59补41的位置 59与43交换 59与49交换 构成小根堆 41 41 41
可南广播电视大学现黄中心 编出43 43 弹与的交操 49 不片线小根 47 49 47◆% 834143 414 83 4引45利城小根堆 6 答： (1)原序列16152053647 15162053764n-1墙 15162075364 次 15167205364 15716205364 71516205364 (2)折华查找判定树 0 ⑦@ 心西@ (3)平均直找长度=(1*1+22+33)6=146 7、答 (1)二叉排序树： ⑤ ② ⊙ ⊙⑥⑧ (2)中序遍历：2,3,4,5,6,7,14,16.18 四、程序填空愿 1、(1)>=0 (2) (3) (4)temp 2.(1)j小m1 (2)-nj (3)-+] (4)ali+l]-temp (5)当某墙冒泡中没有出现交换则己排好序结束循环。 五、算法设计题 1. 编写折半查找算法。 新半查找算法如下： int Binary_Search (NODE all,int n,int k) 第4顶共5页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第4页 共5页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 43 49 47 83 59 输出43 59补43的位置 59 49 47 83 59与49交换 49 59 47 41 41 43 83 构成小根堆 47 59 49 83 不构成小根 堆，继续调整 41 43 41 43 6、 答： （1）原序列 16 15 20 53 64 7 15 16 20 53 7 64 n-1 趟 15 16 20 7 53 64 n-j 次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 （2）折半查找判定树 20 64 7 53 15 16 （3）平均查找长度=（1*1+2*2+3*3）/6=14/6 7、 答： （1）二叉排序树： 6 18 2 14 4 5 3 7 16 （2） 中序遍历：2，3，4，5，6，7，14，16，18 四、程序填空题 1、 （1）j>=0 （2）a[j] （3）j-- （4）temp 2、 （1）j<=n-1 （2）i<=n-j （3）a[i]=a[i+1] （4）a[i+1]=temp （5）当某趟冒泡中没有出现交换则已排好序结束循环。 五、算法设计题 1、 编写折半查找算法。 折半查找算法如下： int Binary_Search（NODE a[],int n, int k）
河南厂播电现大学现数中心 快在0到叫门]中，用折率查找算法查找关键字等于k的记录，查找成功运回该记录 的下标，失数时运目1/ int low,mid,high low=0. high-n-1: while (lowc-high) mid《low+high)2 if (a[mid].key=k) return mid. 查找成功，返回查找到的记录的下标 else if (a[mid].key<k) low=mid+1; 仲取后半查找区间/ else high=mid-I. 中取前半查线区间 retum -1. :查找失数/ 2、编写顺序查找算法。 顺序查找算法如下： int search (NODE al],int n,int k) 俨在0~：门中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失 败时返回1/ int i=0; whe《ien&&可kg-k)仲没有查到同时查找过程没有结束，则继续查找/ + if(a可.kg-k) 查找成功/ return else return-I; :查找失版/ 大、完成：实验3一一找、队列、递归程序设计 实酸4一图的存储方式和应用 根据实最要求《见教材P)认真完成本实验，并提交实验报告。 第5项共5项 版权所有河南电大现教中心范额，邮箱5@m恒cm
河南广播电视大学现教中心 第5页 共5页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn /* 在 a[0]到 a[n-1]中，用折半查找算法查找关键字等于 k 的记录，查找成功返回该记录 的下标，失败时返回-1 */ { int low,mid,high; low=0; high=n-1; while（low<=high） { mid=（low+high）/2; if（a[mid].key==k） return mid; /*查找成功，返回查找到的记录的下标*/ else if（a[mid].key<k） low=mid+1; /*取后半查找区间*/ else high=mid-1; /*取前半查找区间*/ } return -1; /*查找失败*/ } 2、 编写顺序查找算法。 顺序查找算法如下： int search（NODE a[],int n, int k） /*在 a[0]～a[n-1]中顺序查找关键字等于 k 的记录。查找成功时返回该记录的下标，失 败时返回-1*/ { int i=0; while（i<n && a[i].key!=k） /*没有查到同时查找过程没有结束，则继续查找*/ i++; if（a[i].key=k） /*查找成功*/ return i; else return -1; /*查找失败*/ } 六、完成：实验 3――栈、队列、递归程序设计 实验 4——图的存储方式和应用 根据实验要求（见教材 P203）认真完成本实验，并提交实验报告