还剩14页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构考试内部题库含答案解析(全考点)
1.已知一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是()・•A:
115.•B:116・•C:1895・•D:1896解析树转换为二叉树时,树的每个分支结点的所有子结点中的最右子结点无右孩子,根结点转换后也没有右孩子,因此,对应二叉树中无右孩子的结点个数二分支结点数+1=2011-116+1=1896答案D)
2、将森林F转换为对应的二叉树T,F中叶结点的个数等于(o・.A:T中叶结点的个数・•B:T中度为1的结点个数・•C:T中左孩子指针为空的结点个数・•D:T中右孩子指针为空的结点个数第一层有一个结点,其余h-1层上各有两个结点,节点总数=l+2h-l=15,h=8答案C
4.高度为h的完全二叉树最少有个结点解析高度为h的完全二叉树中,第1层~第h-1层构成一个高度为h-1的满二叉树,为1-L第h层至少有一个结点,所以最少的结点个数=-1+1=答案C
5.一棵有124个叶子结点的完全二叉树,最多有个结•C:•A:247•B:248•C:249•D:250解析在非空的二叉树当中,由度为和2的结点数的关系二一+1可知J=123;总结点数n=++,其最大值为248(的取值为1或0,当—二1时结点最多)注意,由完全二叉树总结点数的奇偶性可以确定的值,但不能根据来确定—的值答案B
6、已知一棵有2011个结点的树,其叶结点个数是116,该树对应的二叉树中无右孩子的结点个数是()・•A:115・•B:116・•C:1895•D:1896解析采用特殊值法求解二叉树中仅有前115个叶结点有右孩子结点,其余1896个结点均无右孩子结点答案D(
7、已知一棵完全二叉树的第6层设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是()・•A:39・•B:52・•C:111・•D:119解析第6层有叶结点,完全二叉树的高度可能为6或7,显然树高为7时结点最多完全二叉树与满二叉树相比,只是在最下一层的右边缺少了部分叶结点,而最后一层之上是个满二叉树,并且只有最后两层上有叶结点若第6层上有8个叶结点,则前6层为满二叉树,而第7层缺失了8*2=16个叶结点,故完全二答案C友对于任意一棵高度为5且有10个结点的二叉树,若采用顺序存储结构保存,每个结点占1个存储单元仅存放结点的数据信息,则存放该二叉树需要的存储单元数量至少是O•A:31•B:16•C:15•D:10解析二叉树采用顺序存储时,用数组下标来表示结点之间的父子关系对于一棵高度为5的二叉树,为了满足任意性,其1〜5层的所有结点都要被存储起来,即考虑为一棵高度为5的满二叉树,共需要存储单元的数量为1+2+4+8+16=31答案A
9、在下列关于二叉树遍历的说法中,正确的是()•A:若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点厕它一定是该子树的前序遍历结果序列的最后一个结点•B:若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点厕它一定是该子树的中序遍历结果序列的最后一个结点•C:若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它一定是该子树的前序遍历结果序列的最后一个结点•D:若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的中序遍历结果序列的最后一个结点解析二叉树中序遍历的最后一个结点一定是从根开始沿右子女指针走到底的结点,设用p指示若结点p不是叶子结点(其左子树非空),则前序遍历的最后一个结点在它的左子树中,A、B错;若结点p是叶子结点,则前序与中序遍历的最后一个结点就是它,C正确若中序遍历的最后一个结点p不是叶子结点,它还有一个左子女q,结点q是叶子结点,那么结点q是前序遍历的最后一个结点,但不是中序遍历的最后一个结点,D错答案C10,设n,m为一棵二叉树上的两个结点,在后序遍历时,n在m前的条件是()•A:n在m右方•B:n是m祖先•C:n在m左方•D:n是m子孙解析后序遍历的顺序是LRN,若n在N的左子树,m在N的右子树,则在后序遍历的过程中n在m之前访问;若n是m的子孙,设m在N的位置,则n无论是在m的左子树还是在右子树,在后序遍历的过程中n都在m之前访问,其他都不可以C要成立,要加上两个结点位于同一层答案D答案c
3.给定整数集合{3,5,6,9,12},与之对应的哈夫曼树是()解析解析首先,3和5构造为一棵子树,其根权值为8,然后该子树与6构造为一棵新子树,根权值为14,再后9与12构造为一棵子树,最后两棵子树共同构造为一棵哈夫曼树答案C
4.设哈夫曼编码的长度不超过4,若已对两个字符编码为1和01,则最多可对()个字符编码・•A:2・•B:3・•C:4在哈夫曼编码中,一个编码不能是任何其他编码的前缀3位编码可能是001,对应的4位编码只能是0000和00013位编码也可能是000,对应的4位编码只能是0010和oon.若全采用4位编码,则可以位0000,0001,0010和
0011.题中问的是最多,所以选co答案C
5、一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到()个不同的码字・•A:107・•B:108・•C:214・•D:215解析在哈夫曼树中只有度为0和度为2的结点,结点总数no nonnn-nnn=u+且口二,题中n=215,所以u=108答案B
6.以下对于哈夫曼树的说法中,错误的是•A:对应一组权值构造出来的哈夫曼树一般不是唯一的••B:哈夫曼树具有最小的带权路径长度••C:哈夫曼树中没有度为1的结点••D:哈夫曼树中除了度为1的结点外,还有度为2的结点和叶•结点解析哈夫曼树通常是指带权路径长度达到最小的扩充二叉树,在其构造过程中每次选根的权值最小的两棵树,一棵作为左子树,一棵作为右子树,生成新的二叉树,新的二叉树根的权值应为其左右两棵子树根结点权值的和对哪棵子树做左子树还是右子树没有限制,所以构造的哈夫曼树是不唯一的哈夫曼树只有度为0和度为2的结点,度为0的结点是外结点,带有权值,没有度为1的结点
7.并查集中最核心的两个操作
1.查找,查找两个元素是否属于同一个集合;
2.合并,如果两个元素不属于同一个集合,目所在的两个集合互不相交,则合并这两个集合假设初始长度为100~9的并查集,按1-
2、345-
6.7-
8.8-
9.1-
8、0-
5.1-9的顺序进行查找和合并操作,最终并查集共有个集合•A:1•B:2•C:3•D:4解析{}{}初始时,0~9各自成一个集合查找1-2时,合并1和2;{}{}{}{}查找3-4时,合并3和4;查找5-6时,合并5和6;{}{}{}查找7-8时,合并7和8;查找8-9时,合并7,8和{}{}{}9;查找1-8时,合并1,2和7,8,9;查找0-5时,{}{}合并0和5,6;查找1-9时,它们属于同一个集合最终{}{}{}的集合为0,5,
6、1,2,7,8,9和3,4,因此答案选Co,()(,
8、下列关于并直集的叙述中是错误的注意本题涉及图的考点)•A:并查集是用双亲表示法存储的树•B:并查集可用于实现克鲁斯卡尔算法•C:并查集可用于判断无向图的连通性•D:在长度为n的并查集中进行查找操作的时间复杂n度为解析在用并查集实现Kruskal算法求图的最小生成树时判断是否加入一条边之前,先查找这条边关联的两个顶点是否属于同一个集合(即判断加入这条边之后是否形成回路),若形成回路,则继续判断下一条边;若不形成回路,则将该边和边对应的顶点加入最小生成树T,并继续判断下一条边,直到所有顶点都已加入最小生成树TB正确用并查集判断无向图连通性的方法遍历无向图的边,每遍历到一条边,就把这条边连接的两个顶点合并到同一个集合中,处理完所有边后,只要是相互连通的顶点都会被合并到同一个子集合中,相互不连通的顶点一定在不同的子集合中C正确未做路径优化的并查集在最坏的情况下的高度为0n,此时查找操作的时间复杂度为0n,时间复杂度通常指最坏情况下的时间复杂度D错误答案D
9、下列选项给出的是从根分别到达两个叶结点路径上的权值序列,属于同一棵哈夫曼树的是.•A:24,10,5和24,10,7・•B:24,10,5和24,12,7・•C:24,10,10和24,14,11・•D:24,10,5和24,14,6解析答案D
10.对n个互不相同的符号进行哈夫曼编码若生成的哈夫曼树共有115个结点,则n的值是・•A:56・•B:57・•C:58n个符号构造成哈夫曼树的过程中,共新建了n-l个结点(双分支结点),因此哈夫曼树的结点总数为2n-l=115,n的值为58,答案选Co答案C
1.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为()•A:h・•B:2h-l・•C:2h+l・•D:h+1解析结点最少的情况为除根结点层只有一个结点外,其他h-l层均有()两个结点,结点总数为2h-l+l=2h-lo
2、设二叉树有2n各结点且mn,则不可能存在()的答案B结点•A:n个度为0•B:2m个度为0•C:2m个度为1•D:2m个度为2解析由二叉树的性质1可知—二,+1,结点总数二2n二+1_1+=+21_1+1,贝—l=2n-l—1-1,所以为奇数,说明该二叉树中不可能有2m个度为1的结点答案C
3.设二叉树只有度为0和度为2的结点具结点个数为15,则该二叉树的最大深度为()•A:4•B:5•C:8•D:9解析。