数据结构第六七章习题及解答.docx
- 文档编号:6783777
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:7
- 大小:18.66KB
数据结构第六七章习题及解答.docx
《数据结构第六七章习题及解答.docx》由会员分享,可在线阅读,更多相关《数据结构第六七章习题及解答.docx(7页珍藏版)》请在冰点文库上搜索。
数据结构第六七章习题及解答
Chap6
一、选择题
1.算术表达式a+b*(c+d/e)转为后缀表达式后为(B)。
A.ab+cde/*B.abcde/+*+C.abcde/*++D.abcde*/++
2.在下述结论中,正确的是(D)。
①只有一个结点的二叉树的度为0;②二叉树的度为2;③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.②③④C.②④D.①④
3.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是(A)
A.m-nB.m-n-1C.n+1D.条件不足,无法确定
4.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B)
A.9B.11C.15D.不确定
5.在一棵三元树中度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为(C)个。
A.4B.5C.6D.7
6.设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是(D)。
A.M1B.M1+M2C.M3D.M2+M3
7.设给定权值总数有n个,其哈夫曼树的结点总数为(D)。
A.不确定B.2nC.2n+1D.2n-1
8.有关二叉树下列说法正确的是(B)。
A.二叉树的度为2B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2
9.二叉树的第i层上最多含有结点数为(C)
A.2iB.2i-1-1C.2i-1D.2i-1
10.一个具有1025个结点的二叉树的高h为(C)。
A.11B.10C.11至1025之间D.10至1024之间
11.对于有n个结点的二叉树,其高度为(D)。
A.nlog2nB.log2nC.log2n|+1D.不确定
12.一棵具有n个结点的完全二叉树的树高度(深度)是(A)。
A.logn+1B.logn+1C.lognD.logn-1
13.深度为h的满m叉树的第k层有(C)个结点。
(1= A.mk-1B.mk-1C.mh-1D.mh-1 14.利用二叉链表存储树,则根结点的右指针是(C)。 A.指向最左孩子B.指向最右孩子C.空D.非空 15.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用(C)次序的遍历实现编号。 A.先序B.中序C.后序D.从根开始按层次遍历 16.一棵完全二叉树上有1001个结点,其中叶子结点的个数是(E)。 A.250B.500C.254D.505E.以上答案都不对 17.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是(B)。 A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG 18.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为(A)。 A.CBEFDAB.FEDCBAC.CBEDFAD.不定 19.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是(D)。 A.acbedB.decabC.deabcD.cedba 20.某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号,编号为1,2,…,n,且有如下性质: T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树的结点中,其最小编号等于V左子树上结点的最大编号加1。 这时是按(B)编号的。 A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次顺序 21.对于前序遍历与中序遍历结果相同的二叉树为(B)。 A.一般二叉树B.所有结点只有右子树的二叉树C.根结点无左孩子的二叉树 D.所有结点只有左子数的二叉树 22.一棵左子树为空的二叉树在先序线索化后,其中空的链域的个数是: (D)。 A.不确定B.0C.1D.2 23.一棵左右子树均不空的二叉树在先序线索化后,其中空的链域的个数是: (B)。 A.0B.1C.2D.不确定 24.若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则x的前驱为(C)。 A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点 25.引入二叉线索树的目的是(A) A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除 C.为了能方便的找到双亲D.使二叉树的遍历结果唯一 26.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足(C)。 A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树 27.n个结点的线索二叉树上含有的线索数为(C)。 A.2nB.n-lC.n+lD.n 28.由3个结点可以构造出多少种不同的二叉树? (D)。 A.2B.3C.4D.5 29.下述编码中哪一个不是前缀编码(B)。 A.(00,01,10,11)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001) 30.下面几个符号串编码集合中,不是前缀编码的是(B)。 A.{0,10,110,1111}B.{11,10,001,101,0001}C.{00,010,0110,1000}D.{b,c,aa,ac,aba,abb,abc} 二、判断题 1.完全二叉树一定存在度为1的结点。 (W) 2.对于有n个结点的二叉树,其高度为log2n。 (W) 3.深度为K的二叉树中结点总数≤2k-1。 (A) 4.二叉树的前序遍历并不能唯一确定这棵树,但是,如果我们还知道该树的根结点是那一个,则可以确定这棵二叉树。 (W) 5.用树的前序遍历和中序遍历可以导出树的后序遍历。 (W) 6.由一棵二叉树的前序序列和后序序列可以唯一确定它。 (W) 7.完全二叉树中,若一个结点没有左孩子,则它必是树叶。 (A) 8.二叉树只能用二叉链表表示。 (W) 9.一棵有n个结点的二叉树,从上到下,从左到右用自然数依次给予编号,则编号为i的结点的左儿子的编号为2i(2i (W) 10.给定一棵树,可以找到唯一的一棵二叉树与之对应。 (A) Chap7 一、选择题 1.设无向图的顶点个数为n,则该图最多有(B)条边。 A.n-1B.n(n-1)/2C.n(n+1)/2D.0E.n2 2.一个n个顶点的连通无向图,其边的个数至少为(A)。 A.n-1B.nC.n+1D.nlogn; 3.要连通具有n个顶点的有向图,至少需要(B)条边。 A.n-lB.nC.n+lD.2n 4.n个结点的完全有向图含有边的数目( D )。 A.n*nB.n(n+1)C.n/2D.n*(n-l) 5.一个有n个结点的图,最少有(B)个连通分量,最多有(D)个连通分量。 A.0B.1C.n-1D.n 6.在一个无向图中,所有顶点的度数之和等于所有边数(B)倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的(C)倍。 A.1/2B.2C.1D.4 7.下列哪一种图的邻接矩阵是对称矩阵? (B)。 A.有向图B.无向图C.AOV网D.AOE网 8.无向图G=(V,E),其中: V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是(D)。 A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b 9.下面是求连通网的最小生成树的prim算法: 集合VT,ET分别放顶点和边,初始为(C),下面步骤重复n-1次: a: (A);b: (B);最后: (A)。 (1).A.VT,ET为空B.VT为所有顶点,ET为空 C.VT为网中任意一点,ET为空D.VT为空,ET为网中所有边 (2).A.选i属于VT,j不属于VT,且(i,j)上的权最小 B.选i属于VT,j不属于VT,且(i,j)上的权最大 C.选i不属于VT,j不属于VT,且(i,j)上的权最小 D.选i不属于VT,j不属于VT,且(i,j)上的权最大 (3).A.顶点i加入VT,(i,j)加入ETB.顶点j加入VT,(i,j)加入ET C.顶点j加入VT,(i,j)从ET中删去D.顶点i,j加入VT,(i,j)加入ET (4).A.ET中为最小生成树B.不在ET中的边构成最小生成树 C.ET中有n-1条边时为生成树,否则无解D.ET中无回路时,为生成树,否则无解 10.一个有向无环图的拓扑排序序列(B)是唯一的。 A.一定B.不一定 11.在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是(D)。 A.G中有弧 C.G中没有弧 12.关键路径是事件结点网络中(A)。 A.从源点到汇点的最长路径B.从源点到汇点的最短路径 C.最长回路D.最短回路 13.下面关于求关键路径的说法不正确的是(C)。 A.求关键路径是以拓扑排序为基础的 B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D.关键活动一定位于关键路径上 二、判断题 1.树中的结点和图中的顶点就是指数据结构中的数据元素。 (A) 2.在n个结点的无向图中,若边数大于n-1,则该图必是连通图。 (W) 3.有e条边的无向图,在邻接表中有e个结点。 (W) 4.强连通图的各顶点间均可达。 (A) 5.强连通分量是无向图的极大强连通子图。 (W) 6.连通分量指的是有向图中的极大连通子图。 (W) 7.无向图的邻接矩阵可用一维数组存储。 (A) 8.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 (W) 9.有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。 (A) 10.有向图的邻接矩阵是对称的。 (W) 11.无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。 (W) 12.邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。 (W) 13.用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点个数有关,而与图的边数无关。 (A) 14.一个有向图的邻接表和逆邻接表中结点的个数可能不等。 (W) 15.需要借助于一个队列来实现DFS算法。 (W) 16.广度遍历生成树描述了从起点到各顶点的最短路径。 (W) 17.任何无向图都存在生成树。 (W) 18.不同的求最小生成树的方法最后得到的生成树是相同的.(W) 19.带权无向图的最小生成树必是唯一的。 (W) 20.最小生成树问题是构造连通网的最小代价生成树。 (A) 21.拓扑排序算法把一个无向图中的顶点排成一个有序序列。 (W) 22.拓扑排序算法仅能适用于有向无环图。 (W) 23.无环有向图才能进行拓扑排序。 (W) 24.AOV网的含义是以边表示活动的网。 (W) 25.对一个AOV网,从源点到终点的路径最长的路径称作关键路径。 (W) 26.关键路径是AOE网中从源点到终点的最长路径。 (A) 27.在表示某工程的AOE网中,加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。 (W) 28.在AOE图中,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少。 (A)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第六 习题 解答