数据结构第二次作业答案(C语言版)-07
更新时间:2023-05-12 00:03:01 阅读量: 实用文档 文档下载
- 数据结构第七章作业答案推荐度:
- 相关推荐
数据结构第二次作业答案(C语言版)-07
数据结构第二次作业答案
学号: 姓名: 评分: . 一. 单项选择题(20分)
( )1. 某二叉树的先序序列和后序序列正好相反,则该二叉树一定是____b____的二叉树。
a. 空或只有一个结点 b. 高度等于其结点数(空树高度为0) c. 任一结点无左孩子 d. 任一结点无右孩子
( )2. 设图的顶点数=n, 边数=e,若用邻接表表示图,那么求最短路径的Dijkstra算法的时间复杂
度为_____b____。
a.O(n*e) b.O(n2) c.O(n+e) d.O(n3)
( )3. 一棵左右子树均不为空的二叉树在后序线索化后(不带头结点的线索化),其空指针域数为
____b_____。
a、0 b、1 c、2 d、不确定 ( )4. 下面程序段的时间复杂度是____d_____。
i=1; while(i<=n) i=i*2;
a. O(n) b. O(n2) c. O(2n) d. O(log2n)
( )5. 在有n(>0)个结点且为完全二叉树的二叉排序树中查找一个键值,其平均比较次数的数量级
为_____b______。
a. O(n) b. O(log2n) c. O(nlog2n) d. O(n2)
( )6. 采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序
查找来确定结点所在的块时,每块应分为____b____个结点最佳。 a. 10 b. 25 c. 6 d. 625
( )7. 下列排序算法中时间复杂度不受数据初始状态影响,恒为O(n2)的是____c______。
a、堆排序 b、起泡排序 c、直接选择排序 d、快速排序
( )8. 已知数据表中的每个元素距其最终位置不远,则采用____b___排序算法最省时间。
a.堆排序 b.插入排序 c.快速排序 d.直接选择排序
( )9. 假设图的顶点数=n, 边数=e,那么当用邻接表表示图时,拓扑排序算法的时间复杂度为
____b_____。
a. O(n2) b. O(n+e) c. O(n*e) d. O(n3)
( )10. 一棵左子树为空的二叉树在先序线索化后(不带头结点的线索化),其中的空链域的个数
为____a_____。
a. 2 b. 1 c. 0 d. 不确定 二. 填空作图简答题(共62分): 1. 依次插入30,43,21,9,15,51并由空树构成一棵平衡二叉树, 画出该平衡二叉树形成过程及其中序线索二叉树。
1
数据结构第二次作业答案(C语言版)-07
2. 有一组关键码序列{40
,采用Shell排序方法从小到大进
行排序,假设其间隔序列为5,3,1,请写出每趟的结果。 答案:
第1趟: 40,20,10,15,50,45,95,60,75 第2趟: 15,20,10,40,50,45,95,60,75 第3趟: 10,15,20,40,45,50,60,75,95
3. 对下面的3阶B树依次插入关键码60,14,6,画出插入三个关键码后并删除关键码20后的
结果。
4. 用Prim算法求下图的最小生成树, 若从顶点0出发,请将算法中的辅助数组closedge的变化过
程填入下表。
辅助数组closedge
5
6 7 0 1 2 3 4 所选边 2
数据结构第二次作业答案(C语言版)-07
5. 假设某森林的先根遍历序列为EBADCFHGIKJ和中根遍历序列为ABCDEFGHIJK。请画出该
森林的带双亲的孩子链表示。
6. 已知9个结点的值分别为1~9,请将各结点的值填入下面二叉排序树中:
7. 用堆排序算法(“最大堆”排序算法)对关键字{70,33,79,67,46,24,30,40}进行排序,
请先建“最大堆”,然后输出一个堆顶元素, 并调整成堆:初始状态 { 40 , 33 , 24 , 67 , 46 , 79 , 30 ,70 } 所建大顶堆 {79,70,40,67,46,24,30,33}或{79,70,67,46,40,24,30,33} 输出一个堆顶元素后调整的结果{70,67,40,33,46,24,30,79}或{70,46,67,33,40,24,30,79}
3
数据结构第二次作业答案(C语言版)-07
8. 如下图已知哈希表为空,哈希函数为H(Key)= Key MOD 11, 冲突解决方法分别用线性探测
再散列和二次探测再散列。填入在依次插入关键字14,37,25,16之后的情况,并求等概率情况下所要求的平均查找长度。
(1)线性探测再散列
(2)二次探测再散列
线性探测再散列查找不成功时的平均查找长度=____21/11 _; 二次探测再散列查找成功时的平均查找长度=___6/4=3/2=1.5_;
9. 用快速排序对下列关键字进行排序(图示), 基准元素取第一个元素。 70 33 79 67 46 24 30 40 写出两趟排序的结果。 第一趟排序之后: { 40,33,67,46,24,30} 70 {79} 或 {40,33,30,67,46,24} 70 {79}; 第二趟排序之后: {30,33,24} 40 {67,46} 70,79 或 {24,33,30} 40 {46,67}70,79; 若基准元素按“三者取中”的原则取,则两趟排序的结果是:
第一趟排序之后:{40,33,46,24,30} 67 {79,70} 或 {33,40,30,24,46} 67,{70,79}; 第二趟排序之后:{30,33,24} 40 {46} 67
,70,79 或 {24,30} 33 {40,46} 67,70,79;
10. 已知一字符串bcbdebcecbdcabd,试设计其赫夫曼编码并画出相应的赫夫曼树。
a:1;b:5;c:4;d:3;e:2;
11. 求出下图中顶点A到其余个顶点的最短路径和最短路径长度。
4
数据结构第二次作业答案(C语言版)-07
AE=10; AF=17; AB=19; AG=25; AC=26; AD=27; AH=28
三. 程序填空(18分)
1. 下面是仅给出了部分操作的二叉树类的定义和实现。试在程序的每一划线部分填入一条语
句或表达式,完成计算度为1的结点个数的操作countNodes1( )。
typedef struct BinNode{ int data;
struct BinNode* leftchild, * rightchild; }BinNode, *BinTree;
void InitBinTree(BinTree &root) //初始化二叉树root {
root=Null; }
void DestroyBinTree(BinTree &root) //销毁二叉树root {
if (root == NULL) return;
DestroyBinTree(root->leftchild); DestroyBinTree (root->rightchild); free(root); }
int countNodes1(BinTree &root) //计算二叉树root中度为1的结点数 {
){ if(root-> leftchild!=NULL && root-> rightchild!=NULL)
___② else if(root-> leftchild==NULL && ____else if (root-> leftchild!=NULL && ) __}
return 0; }
5
数据结构第二次作业答案(C语言版)-07
2. 下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语句或表达式,以使该算
法在发现数据有序时能及时停止。
void BubbleSort(int datalist[], int size) //要排序的数据存放在数组datalist[]中,元素个数=size {
int exchange,i,j,temp; i=1;
exchange=1;
while(i<size && ___ {
_____⑨ for(j=size-1;j>=i; j--)
if(datalist[j-1]>datalist[j])
{
temp=datalist[j-1]; datalist[j-1]=datalist[j]; datalist[j]=temp;
____}
i++; } }
6
正在阅读:
数据结构第二次作业答案(C语言版)-0705-12
E解版《古代汉语》期中考试试卷(A)卷10-27
就业证明模板6篇02-09
安全文明施工创优方案12-30
铜陵学院是几本院校一年学费多少?宿舍条件怎么样2022分数线多少03-29
采矿专业技术工作总结(精选多篇)06-29
蓝桥杯练习题库 3算法训练题11-07
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 数据结构
- 作业
- 答案
- 语言
- 07
- 欧派衣柜设计标准
- 光缆传输接入的监理培训讲义
- 2014年中考数学试卷分类汇编:05二元一次方程组及其应用
- 第1章 线性规划与单纯形法-第5节-2007-8
- 海淀分班考试2014
- 03:我国钻机问题
- 棣莫弗定理与欧拉公式
- 第五章 人体内废物的排出 第一节 尿的形成和排出
- 水溶肥分类及识别
- 社会化模式下高校后勤人员管理技能的构建
- 采煤工作面工程管理制度汇编 2
- 【经典】蒙牛早餐奶年度推广方案
- 法学人生网络课程答案全
- 6s目视化管理带图片
- 军事拓展训练计划
- 用科学发展观引领社区统战工作新发展
- XX公司开业庆典策划方案
- 台湾网路认证(TaiCA)股份有限公司金融EDI认证作业
- 110kV变压器铁心多点接地故障分析及处理
- 工业革命时期英国工人的实际工资