数据结构书面作业练习题6-9.pdf

《数据结构书面作业练习题6-9.pdf》由会员分享，可在线阅读，更多相关《数据结构书面作业练习题6-9.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习习 题题 六六树树 和和 二二 叉叉 树树6.16.1 单项选择题单项选择题1.如图 8.7所示的 4 棵二叉树，_C_不是完全二叉树。（A）（A）（B）（B）（C）（C）（D）（D）图8.7 4棵二叉树图8.7 4棵二叉树2.如图 8.8所示的 4 棵二叉树，_B_是平衡二叉树。（A）（A）（B）（B）（C）（C）（D）（D）图8.8 4棵二叉树图8.8 4棵二叉树3.在线索化二叉树中，t所指结点没有左子树的充要条件是B_。A.t left=NULLB.t ltag=1C.t ltag=1 且 t left=NULLD.以上都不对4.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的

2、线索，这种说法 _B_。A.正确B.错误5.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。A.正确B.错误6.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B_。A.正确B.错误7.设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，那么此类二叉树中所包含的结点数至少为_B_。A.2hB.2h-1C.2h+1D.h+1a8.如图 8.9 所示二叉树的中序遍历序列_B_。A.abcdgefB.dfebagcC.dbaefcgD.defbagca ab bc cd dg ge ef f图8.9 一棵二叉树图8.9 一棵二叉树9.某二叉树的

3、后序遍历序列是dabec，中序遍历序列是 debac，它的前序遍历序列是D_。A.acbedB.decabC.deabcD.cedba10设 a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前的条件是B。Aa 在 b 的右方Ba 在 b 的左方Ca 是 b 的祖先Da 是 b 的子孙11.假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，那么叶子结点数为个。BA15B16C17D4712.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，那么其后序遍历的结点访问顺序是D_。A.bdgcefhaB.gdbecfhaC.bdg

4、aechfD.gdbehfca13.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法_B_。A.正确B.错误14.按照二叉树的定义，具有3 个结点的二叉树有_C_种。A.3B.4C.5D.615.一棵二叉树如图 8.10 所示，其中序遍历的序列为_B_。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgha ab bc cd de ef fg g图8.10 一棵二叉树图8.10 一棵二叉树h h16.树的根本遍历策略可分为先根遍历和后根遍历；二叉树的根本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到

5、的二叉树叫做这棵数对应的二叉树。结论_A_是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对17.深度为 5 的二叉树至多有_C_个结点。A.16B.32C.31D.1018.在一非空二叉树的中序遍历序列中，根结点的右边_A_。A.只有右子树上的所有结点B.只有右子树上的局部结点C.只有左子树上的局部结点D.只有左子树上的所有结点19.树最适合用来表示_C_。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据20.任何一

6、棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。A.不发生改变B.发生改变C.不能确定D.以上都不对21.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最正确方案是二叉树采用_C_存储结构。A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构22.对一个满二叉树，m 个树叶，n 个结点，深度为 h，那么_D_。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-123.如果某二叉树的前序为stuwv，中序为 uwtvs，那么该二叉树的后序为_C_。A.uwvtsB.vwutsC.wuvtsD.wutsv24.具有五层结点的二叉平衡树至少有_B_个结点。F(n)=

7、F(n-1)+F(n-2)+1,1 是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量A.10B.12C.15D.1725.设 n，m 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 前的条件是_C_。A.n 在 m 右方B.n 是 m 祖先C.n 在 m 左方D.n 是 m 子孙6.26.2填空题将正确的答案填在相应的空中填空题将正确的答案填在相应的空中1.有一棵树如图 8.12 所示，答复下面的问题：这棵树的根结点是_K1_；这棵树的叶子结点是_K2,K5,K7,K4_；结点 k3 的度是_2_；这棵树的度是_3_；这棵树的深度是_4_；结点 k3 的子女是_K5

8、,K6_；结点 k3 的父结点是_K1_；k k1 1k k2 2k k3 3k k4 4k k5 5k k6 6k k7 7图8.12 一棵树图8.12 一棵树2.指出树和二叉树的三个主要差异_树的结点个数至少为 1，而二叉树的结点个数可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分。3.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的根本目的是_利用二叉树的已有算法解决树的有关问题_。4.一棵二叉树的结点数据采用顺序存储结构，存储于数组 t 中，如图 8.13 所示，那么该二叉树的链接表示形式为_1 12 23

9、 34 45 56 67 7g ge ea af fd d_。8 89 9101011111212131314141515161617171818191920202121c cj jl lh hb b图 8.13一棵二叉树的顺序存储数组 t5.深度为 k 的完全二叉树至少有_2k-1_个结点。至多有_2k-1_个结点，假设按自上而下，从左到右次序给结点编号从1 开始，那么编号最小的叶子结点的编号是_2k-2+1_。6.在一棵二叉树中，度为零的结点的个数为 n0，度为 2 的结点的个数为 n2，那么有n0=_n2+1_。7.一棵二叉树的第 ii1层最多有_2i-1_个结点；一棵有nn0个结点的满

10、二叉树共有_ 2log2n+1-1_个叶子和_2log2n+1-1_个非终端结点。8.结点最少的树为_只有一个结点的树_，结点最少的二叉树为_空二叉树_。9.现有按中序遍历二叉树的结果为 abc，问有_5_种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_。10.根据二叉树的定义，具有三个结点的二叉树有_5_种不同的形态，它们分别是_参照楼上_。11.由如图 8.17 所示的二叉树，答复以下问题：其中序遍历序列为_dgbaechif_；其前序遍历序列为_abdgcefhi _；其后序遍历序列为_gdbeihfca_；该二叉树的中序线索二叉树为_；该二叉树的后序线索二叉树为_；该二叉树对

11、应的森林是_。a ab bc cd de ef fg g图8.20 一棵树图8.20 一棵树12.一棵树如图 8.20 所示，转化为一棵二叉树，表示为_a ab bc cd de ef fg gh hi i图8.17 一棵二叉树图8.17 一棵二叉树_。13.以数据集4，5，6，7，10，12，18为结点权值所构造的 Huffman 树为_，其带权路径长度为_165_。6.36.3算法设计题算法设计题:1试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。2.一棵度为 2 的树与一棵二叉树有何区别?3.一棵含有 N 个结点的 k 叉树,可能到达的最大深度和最小深度各为多少?4.证明:一棵

12、满 k 叉树上的叶子结点数 n0和非叶子结点数 n1之间满足以下关系:n0=(k-1)n1+15.请对以下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。ABCDFEGH6.画出和以下序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBFG。7.假设用于通讯的电文仅有八个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。使用 0-7的二进制表示形式是另一种编码方案。对于上述实例，比拟两种方案的优缺点。8.假设一棵 二叉树的先序序

13、列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK。请画出该树。9.编写按层次顺序同一层自左至右遍历二叉树的算法。习习 题题 七七图图7.17.1单项选择题单项选择题1.在一个图中，所有顶点的度数之和等于所有边数的_A_倍。A.1/2B.1C.2D.42.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A.1/2B.1C.2D.43.一个有 n 个顶点的无向图最多有_C_条边。A.nB.n(n-1)C.n(n-1)/2D.2n4.具有 4 个顶点的无向完全图有_A_条边。A.6B.12C.16D.205.具有 6 个顶点的无向图至少应有_A_条边才能确保是一

14、个连通图。A.5B.6C.7D.86.在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要_C_条边。A.nB.n+1C.n-1D.n/27.对于一个具有 n 个顶点的无向图，假设采用邻接矩阵表示，那么该矩阵的大小是_D_。A.nB.(n-1)2C.n-1D.n28.对于一个具有 n 个顶点和 e 条边的无向图，假设采用邻接表表示，那么表头向量的大小为_A_；所有邻接表中的接点总数是_C_。A.nB.n+1C.n-1D.n+e A.e/2B.eC.2eD.n+e9.一个图如图 9.5 所示，假设从顶点a 出发按深度搜索法进行遍历，那么可能得到的一种顶点序列为_D_；按宽度搜索法进行遍历，那

15、么可能得到的一种顶点序列为_。A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,ba ab bc ce ed d图 9.5 一个无向图图 9.5 一个无向图f f10.一有向图的邻接表存储结构如图9.6 所示。1 13 32 22 23 34 45 54 45 52 24 4图图 9.69.6一个有向图的邻接表存储结构一个有向图的邻接表存储结构 根据有向图的深度优先遍历算法，从顶点v1 出发，所得到的顶点序列是_C_。A.v1,v2,v3

16、,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2 根据有向图的宽度优先遍历算法，从顶点v1 出发，所得到的顶点序列是_B_。A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v211.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_A_。A.先序遍历B.中序遍历C.后序遍历D.按层遍历12.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_D_。A.先序遍历B.中序遍历C.后序遍历D.按层遍历13.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可

17、以利用_D_。A.求关键路径的方法B.求最短路径的 Dijkstra 方法C.宽度优先遍历算法D.深度优先遍历算法7.27.2填空题将正确的答案填在相应饿空中填空题将正确的答案填在相应饿空中1.n 个顶点的连通图至少_n-1_条边。2.在无权图 G 的邻接矩阵 A 中，假设(vi,vj)或vi,vj属于图 G 的边集合，那么对应元素Aij等于_1_，否那么等于_0_。3.在无向图 G 的邻接矩阵 A 中，假设 Aij等于 1，那么 Aji 等于_1_。4.图 G 的邻接表如图 9.7 所示，其从顶点 v1 出发的深度有限搜索序列为_，其从顶点v1 出发的宽度优先搜索序列为_。V1V2V5V4v

18、2v3V5v3V6v4v5V4V6V3v6图 9.7图 G 的邻接表5.一个有向图的邻接矩阵表示，计算第i 个结点的入度的方法是_。6.一个图的邻接矩阵表示，删除所有从第i 个结点出发的边的方法是_。7.37.31如下图的有向图，请给出该图的:151每个顶点的入/出度；2邻接距阵；3邻接表；4逆邻接表；65强连通分量。2342请用克鲁斯卡尔普里姆两种算法分别构造最小生成树：1 1abcdf161611 1511 15151515151313161614141212e21212 21216472912353.3.试列出以下图中全部的拓扑排序序列。152061641325105312454.4.请

19、用图示说明从顶点 a 到其余各顶点之间的最短路径。4bd11638af9ce27.4AOE7.4AOE 网有网有 9 9 个结点：个结点：V1V1，V2V2，V3V3，V4V4，V5V5，V6V6，V7V7，V8V8，V9V9，其邻接矩阵如下：，其邻接矩阵如下：(1)请画出该 AOE 图。(2)计算完成整个方案需要的时间。(3)求出该 AOE 网的关键路径。V1V2V3V4V5V6V7V8V9V1645V21V31V42V597V64V72V84V9习习 题题 八八查查找找8.18.1单项选择题单项选择题1.顺序查找法适合于存储结构为_B_的线性表。A.散列存储B.顺序存储或链接存储C.压缩存

20、储D.索引存储2.对线性表进行二分查找时，要求线性表必须_C_。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n 的线性表时，每个元素的平均查找长度为_C_.A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找长度为n 的线性表时，每个元素的平均查找长度为_D_。AOn2B.O(nlog2n)C.O(n)D.O(log2n)5.有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值 82 为的结点时，_C_次比拟后查找成功

21、。A.1B.2C.4D.86.设哈希表长 m=14，哈希函数 H(key)=key%11。表中已有 4 个结点：H(15)=4;H(38)=5;H(61)=6;H(84)=7如用二次探测再散列处理冲突，关键字为49 的结点的地址是_D_。A.8B.3C.5D.97.有一个长度为 12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比拟次数为_B_。A.35/12B.37/12C.39/12D.43/128.28.2填空题将正确的答案填在相应的空中填空题将正确的答案填在相应的空中1.顺序查找法的平均查找长度为_ _；二分查找法的平均查找长度为_ _；分块查找法以

22、二分查找确定块的平均查找长度为_；哈希表查找法采用链接法处理冲突时的平均查找长度为_。2.二分查找的存储结构仅限于_顺序存储_，且是_有序的_。3.在散列函数 H(key)=key%p 中，p 应取_小于表长的最大素数_。4.假设在有序线性表A1.20上进行二分查找，那么比拟一次查找成功的结点数为_1_，那么比拟二次查找成功的结点数为_2_，那么比拟三次查找成功的结点数为_4_，那么比拟四次查找成功的结点数为_8_，那么比拟五次查找成功的结点数为_5_，平均查找长度为_3.7_。5.对于长度为 n 的线性表，假设进行顺序查找，那么时间复杂度为_ On_；假设采用二分法查找，那么时间复杂度为_

23、Olog2n_；6.在散列存储中，装填因子a的值越大，那么_存取元素时发生冲突的可能性越大_；的值越小，那么_。8.38.3综合练习题综合练习题:选取哈稀函数 Hk=3kMOD 11。用开放定址法处理冲突，di=ii=1，2，3，.试在 0-10 的散列地址空间中对关键字序列22,41,53,46,30,13,01,67造哈希表，并求等概率情况下查找成功时的平均查找长度。习习 题题 九九排排序序9.19.1单项选择题单项选择题1.在所有排序方法中，关键字比拟的次数与记录的初始排列次序无关的是_D_。A.希尔排序B.起泡排序C.插入排序D.选择排序3.在待排序的元素序列根本有序的前提下，效率最高

24、的排序方法是_A_。A.插入排序B.选择排序C.快速排序D.归并排序4.一组记录的关键字为46，79，56，38，40，84，那么利用堆排序的方法建立的初始堆为_。A.79，46，56，38，40，80B.38，46,56，79，40，84，C.84，79，56，46，40，38D.84，56，79，40，46，385.一组记录的关键字为46，79，56，38，40，84，那么利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_C_。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，796

25、.一组记录的关键字为25，48，16，35，79，82，23，40，36，72，其中含有 5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_A_。A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，827.排序方法中，从未排序序列中依次取出元素与已排序序列 初始时为空中的元素进行比拟，将其放入已排序序列的正确位置上的方法，称为_C_。A.希尔排序B.起泡排序C.插入排序D.选择排

26、序8.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列初始时为空的一端的方法，称为_D_。A.希尔排序B.归并排序C.插入排序D.选择排序9.用某种排序方法对线性表 25，84，21，47，15，27，68，35，20进行排序时，元素序列的变化情况如下：25，84，21，47，15，27，68，35，20 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84那么所采用的排序方法是_D_。A.选择排序B.希尔排序C.归并排序D.快速排序10.下述几种排序方法中，平均查找长度最小

27、的是_C_。A.插入排序B.选择排序C.快速排序D.归并排序11.下述几种排序方法中，要求内存量最大的是_D_。A.插入排序B.选择排序C.快速排序D.归并排序12.快速排序方法在_C_情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已根本有序D.要排序的数据个数为奇数9.29.2填空题填空题 将正确的答案填在相应的空中将正确的答案填在相应的空中1.在对一组记录54，38，96，23，15，72，60，45，83进行直接插入排序时，当把第7 个记录 60 插入到有序表时，为寻找插入位置需比拟_3 次_。2.在堆排序，快速排序和归并排序中，假设只从

28、存储空间考虑，那么应首先选取 _堆_方法，其次选取_快速_方法，最后选取_归并_方法；假设只从排序结果的稳定性考虑，那么应选取_归并_方法；假设只从平均情况下排序最快考虑，那么应选取_快速_方法；假设只从最坏情况下排序最快并且要节省内存考虑，那么应选取_堆_方法。3.在堆排序和快速排序中，假设原始记录接近正序或反序，那么选用_堆排序_，假设原始记录无序，那么最好选用_快速_。4.对 n 个元素的序列进行起泡排序时，最少的比拟次数是_n-1_。9.39.3综合题综合题1.以关键字序列503,087,512,061,908,170,897,275,653,426，为例，手工执行以下排序算法，写出每一趟排序结束时的关键字状态：（1）直接插入排序；（2）希尔排序增量 d1=5；（3）快速排序；（4）堆排序；（5）归并排序；2.判别以下序列是否为堆小顶堆或大顶堆。如果不是，那么把它调整为堆要求记录交换次数最少。1(100,86,48,73,35,39,42,57,66,21);(2)(12,70,33,65,24,56,48,92,86,33)(3)(103,97,56,38,66,23,42,12,30,52,06,20)(4)(05,56,20,23,40,38,29,61,35,76,28,100).