- 1、本文档共11页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
数据结构计算机科学与技术学院基础知识题已知一棵树边的集合为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,
<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>},请画出这棵树,并回答下列问题:哪个是根结点?哪些是叶子结点?哪个是结点G的双亲?哪些是结点G的祖先?哪些是结点G的孩子?哪些是结点E的子孙?哪些是结点E的兄弟?哪些是结点F的兄弟?结点B和N的层次号分别是什么?树的深度是多少?以结点C为根的子树的深度是多少?试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。试分别推导含n个结点和含n0个叶子结点的完全三叉树的深度H。假设n和m为二叉树中两结点,用“1”、“0”或“ф”(分别表示肯定、恰恰相反或者不一定)填写下表:找出所有满足下列条件的二叉树:它们在先序遍历和中序遍历时,得到的结点访问序列相同;它们在后序遍历和中序遍历时,得到的结点访问序列相同;它们在先序遍历和后序遍历时,得到的结点访问序列相同;将下列二叉链表改为先序线索链表。分别画出和下列树对应的各个二叉树,给出的各树的先根序列、后根序列。将下列森林转换为相应的二叉树假设用于通讯的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。使用0~7的二进制表示形式是令一种编码方案。对于上述实例,比较两种方案的优缺点。假设一棵二叉树的前序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。编程题本章练习题中的二叉树和树的二叉链表的类型定义如下:structBiTNode{//二叉树结点
ElemTypedata;
BiTLinklchild,rchild;
};typedefBiTLinkBiTree;//二叉树链表//-----树的二叉链表(孩子-兄弟)存储表示-----//typedefstructCSNode{
ElemTypedata;
structCSNode*firstchild,*nextsibling;
}CSNode,*CSTree;编写递归算法,在二叉树中求位于先序序列中第k个位置的结点的值。
boolpre_Order_K(BiTreebt,intk,ElemType&x)
//已知bt为指向二叉链表(二叉树)的根指针,若k>0且不大于
//二叉树中的结点数,则以x带回该二叉树的先序序列中第k个
//数据元素并返回true,否则返回false编写递归算法,将二叉树中所有结点的左、右子树相互交换。
voidExchange(BiTree&bt)
//已知bt为指向二叉链表(二叉树)的根指针,
//本函数实现该二叉树上所有结点的左、右子树互换编写递归算法:对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。
voidReleaseX(BiTree&bt,ElemTypex)
//已知bt为指向二叉链表(二叉树)的根指针,若二叉树上存在其
//数据元素和x相同的结点,则均删除之。编写按层次顺序(同一层自左至右)遍历二叉树的算法。
voidLevelOrder(BiTreebt,charss[],int&n)
//bt为指向(以二叉链表表示的)二叉树的根的指针,按层序遍
//历二叉树,以字符数组ss[0..n-1]返回遍历所得二叉树的层序
//序列,n为二叉树中所含结点的数目,其初值为0*DataStructure注:如果离a和b最近的共同祖先p存在;且a在p的
左子树中,b在p的右子树中,则称a在b的左方
(即b在a的右方)。??????????????????????????????????????????????????????????????????????????????????????????????????????????**
您可能关注的文档
- 结构主义马克思主义.ppt
- 过程控制工程-潘永湘-第3章过程控制仪表(1).ppt
- 第十三章--小说(二.ppt
- 建筑施工企业廉洁风险识别.ppt
- 第7章财务报告.ppt
- 商务现场口译.ppt
- 运用唯物辩证法看统筹兼顾.ppt
- 1我国学校体育的发展概况.ppt
- 一手住房按揭贷款相关政策调整与规定1.ppt
- 第十四章-织构的测定.pptx
- 幼儿教师资格证(考试资料)《幼儿保健知识与能力》新版初级练习卷有答案与.docx
- (附答案)川农12月《中药化学》作业考核-.docx
- (附答案)川农12月《园林植物保护学(本科)》作业考核-.docx
- (附答案)川农12月《有机化学(专科)》作业考核-.docx
- (附答案)川农12月《植物保护学(本科)》作业考核-.docx
- (附答案)东师《教育心理学》在线作业2-1(1).docx
- (附答案)川农12月《药剂学》作业考核-.docx
- (附答案)川农12月《配方饲料制造工艺与技术(专科)》作业考核-.docx
- 幼儿教师资格证(考试资料)《幼儿保健知识与能力》新版基础知识题库带解析.docx
- 幼儿教师资格证(考试资料)《幼儿保健知识与能力》基础知识模拟押题卷.docx
文档评论(0)