数据结构书面作业练习题69.docx
- 文档编号:10658178
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:24
- 大小:486.14KB
数据结构书面作业练习题69.docx
《数据结构书面作业练习题69.docx》由会员分享,可在线阅读,更多相关《数据结构书面作业练习题69.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构书面作业练习题69
习题六
树和二叉树
6.1单项选择题
(A)
(B)(C)
图8.74棵二叉树
2.如图8.8所示的
(A)(B)(C)
图8.84棵二叉树
3.在线索化二叉树中,t所指结点没有左子树的充要条件是B
A.t—>left=NULLB.t—>ltag=1
C.t—>ltag=1且t—>left=NULLD.以上都不对
4.二叉树按某种顺序线索化后,任一结点均有指向其前驱和后续的线索,这种说法
A.正确B.错误
5.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法_A__。
A.正确B.错误
6.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法___B_。
A.正确B.错误
7.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数
至少为__B__。
A.2hB.2h-1C.2h+1D.h+1a
8.如图8.9所示二叉树的中序遍历序列___B_。
A.abcdgefB.dfebagcC.dbaefcgD.defbagc
9.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列
是D。
A.acbedB.decabC.deabcD.cedba
10.设a,b为一棵二叉树上的两个结点,在中序遍历时,a在b前的条件是B。
A.a在b的右方B.a在b的左方
C.a是b的祖先D.a是b的子孙
13.
小于其
二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、右孩子的值。
这种说法_B_。
A.正确B.错误
14.按照二叉树的定义,具有3个结点的二叉树有_C_种。
A.3B.4C.5D.6
15.一棵二叉树如图8.10所示,其中序遍历的序列为_B_。
A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh
图8.10一棵二叉树
16.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里,我们把由树转化得到的二叉树叫做这棵数对应的二叉树。
结论A是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
17.
深度为5的二叉树至多有___C_个结点。
18.
20.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_
A.不发生改变B.发生改变C.不能确定D.以上都不对
21.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用
__C__存储结构。
A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构
24.具有五层结点的二叉平衡树至少有___B_个结点。
F(n)=F(n-1)+F(n-2)+1,1是根节点,
F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量
A.10B.12C.15D.17
25.设n,m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是__C__。
A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙
6.2填空题(将正确的答案填在相应的空中)
1.有一棵树如图8.12所示,回答下面的问题:
⑴这棵树的根结点是—K1_;
⑵这棵树的叶子结点是—K2,K5,K7,K4_;
⑶结点k3的度是_2_;
⑷这棵树的度是—3_;
⑸这棵树的深度是_4_;
⑹结点k3的子女是__K5,K6—;
⑺结点k3的父结点是K1;
2.指出树和二叉树的三个主要差别_树的结点个数至少为1,而二叉树的结点个数可以为
0;树中结点的最大度数没有限制,而二叉树结点的最大度数为2;树的结点无左、右
之分,而二叉树的结点有左、右之分。
3.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是_利
用二叉树的已有算法解决树的有关问题。
4.一棵二叉树的结点数据采用顺序存储结构,存储于数组t中,如图8.13所示,则该
叉树的链接表示形式为。
图8.13一棵二叉树的顺序存储数组t
6.在一棵二叉树中,度为零的结点的个数为no,度为2的结点的个数为n2,则有
no=_n2+1
7.
一棵二叉树的第i(i>1)层最多有_2i-1___个结点;一棵有n(n>0)个结点的满二叉树共有—2[log2n+1]-1—个叶子和—2[log2n+1]-1_个非终端结点。
9.现有按中序遍历二叉树的结果为abc,问有__5—种不同形态的二叉树可以得到这一遍
历结果,这些二叉树分别是
10.
5_种不同的形态,它们分别是—参
根据二叉树的定义,具有三个结点的二叉树有照楼上。
11.由如图8.17所示的二叉树,回答以下问题:
⑴其中序遍历序列为_dgbaechif_;
⑵其前序遍历序列为___
abdgcefhi_;
⑶
其后序遍历序列为
gdbeihfca;
⑷
该二
叉树的中序线索
F二叉树为
⑸该二叉树的后序线索二叉树为
⑹该二叉树对应的森林是
a
色
b
d
c
e
g
图8.20一棵树
12.已知一棵树如图8.20
所示,转化为一棵二叉树,表示为
图8.17一棵二叉树
37
13
7,10,12,18}为结点权值所构造的Huffman
树为
12
其带权路径长度为__165
6.3算法设计题:
1•试编写算法,对一棵以孩子-兄弟链表表示的树统计叶子的个数。
2.一棵度为2的树与一棵二叉树有何区别?
3.一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?
4.证明:
一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系
n0=(k_1)n1+1
5•请对下图所示二叉树进行后序线索化,为每个空指针建立相应的前驱或后继线索。
6.画出和下列已知序列对应的树T:
树的先根次序访问序列为GFKDAIEBCHJ树的后根次序访问序列为DIAEKFCJHBFG
7.假设用于通讯的电文仅有八个字母组成,字母在电文中出现的频率分别为
0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。
试为这八个字母设计哈夫曼编码。
使用0-7的二进制表示形式是另一种编码方案。
对于上述实例,比较两种方案的优缺点。
8.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。
请画出该树。
9.编写按层次顺序(同一层自左至右)遍历二叉树的算法。
习题七图
7.1单项选择题
1.在一个图中,所有顶点的度数之和等于所有边数的_A___倍。
A.1/2B.1C.2D.4
2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的__B__倍。
A.1/2B.1C.2D.4
3.一个有n个顶点的无向图最多有__C__条边。
A.nB.n(n-1)C.n(n-1)/2D.2n
4.具有4个顶点的无向完全图有__A__条边。
A.6B.12C.16D.20
5.具有6个顶点的无向图至少应有__A__条边才能确保是一个连通图。
A.5B.6C.7D.8
6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要___C_条边。
A.nB.n+1C.n-1D.n/2
7.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是__D
22
A.nB.(n-1)2C.n-1D.n2
8.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为
①A—;所有邻接表中的接点总数是一②C—。
1A.nB.n+1C.n-1D.n+e
2A.e/2B.eC.2eD.n+e
9.已知一个图如图9.5所示,若从顶点a出发按深度搜索法进行遍历,则可能得到的一
种顶点序列为_D①__;按宽度搜索法进行遍历,
1A.a,b,e,c,d,fB.e,c,f,e,b,d
2
则可能得到的一种顶点序列为―②-
C.a,e,b,c,f,dD.a,e,d,f,c,b
C.a,e,b,c,f,dD.a,c,f,d,e,b
图9.6一个有向图的邻接表存储结构
A.a,b,c,e,d,fB.a,b,c,e,f,d
⑴根据有向图的深度优先遍历算法,从顶点v1出发,所得到的顶点序列是_C_。
A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5
C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2
⑵根据有向图的宽度优先遍历算法,从顶点v1出发,所得到的顶点序列是_B_。
A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5
C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2
11.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_A_。
A.先序遍历B.中序遍历C.后序遍历D.按层遍历
12.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_D_。
A.先序遍历B.中序遍历C.后序遍历D.按层遍历
13.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用—D_。
A.求关键路径的方法B.求最短路径的Dijkstra方法
C.宽度优先遍历算法D.深度优先遍历算法
7.2填空题(将正确的答案填在相应饿空中)
1.n个顶点的连通图至少_n-1条边。
2.在无权图G的邻接矩阵A中,若(vi,vj)或vvi,vj>属于图G的边集合,则对应元素A[i][j]等于_1_,否则等于—0_。
3.在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于__1_。
4.已知图G的邻接表如图9.7所示,其从顶点v1出发的深度有限搜索序列为,其
从顶点v1出发的宽度优先搜索序列为。
图9.7图G的邻接表
5.已知一个有向图的邻接矩阵表示,计算第
6.已知一个图的邻接矩阵表示,删除所有从第
7.3
1•已知如图所示的有向图,请给出该图的
(1)每个顶点的入/出度;
(2)邻接距阵;
(3)邻接表;
(4)逆邻接表;
(5)强连通分量。
2•请用克鲁斯卡尔普里姆两种算法分别构造最小生成树:
(1)
3•试列出下图中全部的拓扌卜排序序列。
V8,V9,其邻接矩
阵如下:
⑴请画出该AOE图。
(2)计算完成整个计划需要的时间。
(3)求出该AOE网的关键路径。
V1
V2
V3
V4
V5
V6
V7
V8
V9
V1
OG
6
4
5
O
O
O
O
O
V2
OG
O
O
O
1
O
O
O
O
V3
O
O
O
O
1
O
O
O
O
V4
OG
O
O
O
O
2
O
O
O
V5
O
O
O
O
O
O
9
7
O
V6
O
O
O
O
O
O
O
4
O
V7
O
O
O
O
O
O
O
O
2
V8
O
O
O
O
O
O
O
O
4
V9
O
O
O
O
O
O
O
O
O
习题八查找
8.1单项选择题
1•顺序查找法适合于存储结构为_B—的线性表。
A.散列存储B.顺序存储或链接存储
C.压缩存储D.索引存储
2.对线性表进行二分查找时,要求线性表必须_C_。
A.以顺序方式存储B.以链接方式存储
C.以顺序方式存储,且结点按关键字有序排序
D.以链接方式存储,且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为_C_
A.nB.n/2C.(n+1)/2D.(n-1)/2
4.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为_D.
A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)
5.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当分查找值82为的结点时,___C_次比较后查找成功。
A.1B.2C.4D.8
6.设哈希表长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.9
7.有一个长度为12的有序表,
按二分查找法对该表进行查找,在表内各元素等概率情况
查找成功所需的平均比较次数为__B__。
D.43/12
A.35/12B.37/12C.39/12
8.2填空题(将正确的答案填在相应的空中)
1.顺序查找法的平均查找长度为____;二分查找法的平均查找长度为____;分块查找法(以二分查找确定块)的平均查找长度为;哈希表查找法采用链接法处理冲突时的平
均查找长度为。
4.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为_1___,
则比较二次查找成功的结点数为_2___,则比较三次查找成功的结点数为__4__,则比较四次查找成功的结点数为__8__,则比较五次查找成功的结点数为__5__,平均查找长度为
_3.7___。
5.对于长度为n的线性表,若进行顺序查找,则时间复杂度为_O(n)___;若采用二分法查找,则时间复杂度为__O(log2n)
6.在散列存储中,装填因子a的值越大,则__存取元素时发生冲突的可能性越大__;的值越小,则。
8.3综合练习题:
选取哈稀函数H(k)=(3k)MOD11。
用开放定址法处理冲突,di=i(i=1,2,3,…).
试在0-10的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)造哈希表,并求等概率情况下查找成功时的平均查找长度。
习题九排序
9.1单项选择题
1.
在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是___D_。
3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是___A_。
4.一组记录的关键字为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为。
7.排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为__C__。
A.希尔排序B.起泡排序C.插入排序D.选择排序
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_。
10.
下述几种排序方法中,平均查找长度最小的是_C
11.下述几种排序方法中,要求内存量最大的是___D_。
D.归并排序
A.插入排序B.选择排序C.快速排序
12.快速排序方法在_C___情况下最不利于发挥其长处。
A.要排序的数据量太大B.要排序的数据中含有多个相同值
C.要排序的数据已基本有序D.要排序的数据个数为奇数
9.2填空题(将正确的答案填在相应的空中)
1.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较__3次__。
2.在堆排序,快速排序和归并排序中,若只从存储空间考虑,则应首先选取__堆__方法,
其次选取__快速__方法,最后选取___归并_方法;若只从排序结果的稳定性考虑,则应选取__归并__方法;若只从平均情况下排序最快考虑,则应选取__快速__方法;若只从最坏
情况下排序最快并且要节省内存考虑,则应选取___堆_方法。
3.在堆排序和快速排序中,若原始记录接近正序或反序,则选用_堆排序___,若原始记
录无序,则最好选用__快速__。
4.对n个元素的序列进行起泡排序时,最少的比较次数是_n-1___。
9.3综合题
1.以关键字序列(503,087,512,061,908,170,897,275,653,426),为例,手工执行以下排序算法,写出每一趟排序结束时的关键字状态:
(1)直接插入排序;
(2)希尔排序(增量d[1]=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).
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 书面 作业 练习题 69