湖北理工数据结构第三次月考.doc

1. 不含任何结点的空树（ C ）。A是一棵树B. 是一棵二叉树C. 是一棵树也是一棵二叉树D. 既不是树也不是二叉树2. 如果结点A有3个兄弟，B是A的双亲，则B的度是（ D）A1 B. 2 C. 3D. 43.二叉树是非线性数据结构，所以（ C）。A它不能用顺序存储结构存储 B. 它不能用链式存储结构存储 C. 顺序存储结构和链式存储结构都能存储 D. 顺序存储结构和链式存储结构都不能使用4.由3 个结点可以构造出多少种不同的二叉树？（D ） 。A2 B. 3C. 4 D. 5 5. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ D ）A250B.500C. 254 D. 5016一个具有1025个结点的二叉树的高h为（ C ）。A10 B11 C11至1025之间 D10至1024之间7把一棵树转换为二叉树后，这棵二叉树的形态是（A ）。A唯一的 B. 有多种 C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子8深度为h的满m叉树的第k层有（ A）个结点。(1=k=0)个结点的完全二叉树的深度为（ C ）A 以2为底n的对数向上取整 B以2为底n的对数向下取整 C以2为底n的对数向下取整+1 D以2为底n+1的对数向上取整 11对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ C ）遍历实现编号。A. 先序 B. 中序 C. 后序 D. 从根开始按层次遍历 12若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（C ）遍历方法最合适。A前序 B中序 C后序 D按层次13在下列存储形式中，（ D ）不是树的存储形式？A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法14. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ B ）。A所有的结点均无左孩子 B. 所有的结点均无右孩子 C. 完全二叉树 D. 堆15某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（D ）的二叉树。A空或只有一个结点 B任一结点无左子树 C高度等于其结点数 D任一结点无右子树16若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ C ）。AX的双亲 B. X的右子树中最左的结点 C.X的左子树中最右结点 D. X的左子树中最右叶结点17引入二叉线索树的目的是（A ）A加快查找结点的前驱或后继的速度 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示18线索二叉树是一种（ C）结构。A逻辑B逻辑和存储。C物理。D线性。19线索二叉树中某结点R没有左孩子的充要条件是（ C ）。 AR.lchild=NULL BR.ltag=0 CR.ltag=1 DR.rchild=NULL 20设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ C）个A n-1 Bn C n+1 D n+221讨论树、森林和二叉树的关系，目的是为了（ B ）。A借助二叉树上的运算方法去实现对树的一些运算 B将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决其相关问题 C双链表 D体现一种技巧，没什么实际意义22设森林中有3棵树，3棵树的结点数依次为m、n、k，则把森林转换成二叉树后，其根结点的右子树的结点数为( D )。A. m-1 B.m C. m+n D.n+k23设森林中有3棵树，3棵树的结点数依次为m、n、k，则把森林转换成二叉树后，其根结点的左子树的结点数为（ B ）。A m-1 Bm C m+n D n+k24. 设一棵二叉树的结点数为n，分枝数为m，则二者的关系是（ B ）。A n=m B n=m+1 C n=m-1 D不确定25. 下面关于二叉树和树的叙述中正确的是（ A ）。 A因为二叉树是树的特殊形式，所以可以把树转化为二叉树来处理。 B 因为二叉树不是树的特殊形式，所以不能把树转化为二叉树来处理C虽然二叉树不是树的特殊形式，但是通常可以把树转化为二叉树来处理 D以上A，B，C都不对。26.在一个有向图中，所有顶点的入度与出度之和等于图的弧数的（ B ）倍。A二分之一 B1 C2 D.427在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B ）倍。A二分之一 B1 C2 D428具有n个顶点的无向图最多有（ D ）条边。An Bn(n-1) Cn(n+1) Dn(n-1)的二分之一29n个顶点的有向完全图用邻接矩阵表示时，该矩阵有（ B ）个非零元素An Bn(n-1) C2(n-1) Dn(n+1)30含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（C）。A. 1 B. n C. n-1 D. n的二分之一31对于一个有n个顶点的无向图，若采用邻接矩阵存储，该矩阵的大小是（ D ）。An B(n-1)的平方Cn-1 Dn的平方32 连通图的生成树（ B） A. 是唯一的B. 不是唯一的C. 唯一性不能确定D. 前面三个都 不正确33G是一个非连通无向图，共有21条边，则该图至少有（ C ）个顶点。A10 B9C8 D 734若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ A ）图。A连通 B强连通 C非连通 D有向35. 下面（A）算法适合构造一个稠密图G的最小生成树。A Prim算法B Kruskal算法 C Floyd算法 DDijkstra算法36. 用邻接表表示图进行广度优先遍历时，通常借助（ B ）来实现算法。A栈B队列C顺序表D链表37. 用邻接表表示图进行深度优先遍历时，通常借助（ A ）来实现算法。A. 栈 B. 队列 C. 顺序表 D. 链表38. 深度优先遍历类似于二叉树的（ B ）遍历。 A. 层次 B. 先序 C. 中序 D. 后序 39.广度优先遍历类似于二叉树的（ A ）遍历。A. 层次 B. 先序 C. 中序 D. 后序40. 图的DFS生成树的树高比BFS生成树的树高（ D ）。 A. 小 B. 相等 C. 小或相等 D. 大或相等41. 已知图的邻接矩阵如图一所示，则从顶点0出发按深度优先遍历的结果是（ A ）。 A. 0134256B. 0136542C. 0361542D. 0243156注：有图，图一42. 下面（ B ）方法可以判断出一个有向图是否有回路。A. 广度优先遍历 B. 拓扑排序 C. 求关键路径 D.求最短路径43. 已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ A）。A. FEDCBA B. ABCDEF C. FDECBA D. FBDCEA44. 设某有向图有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。A. n-1 B. n C. n+1 D. 2n-145. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中的弧数是（ C ）。A. n B. n-1 C. m D. m-146. 设某连通图G中的边集E（a,b），（a,e），（a,c），（b,e），（e,d），（d,f），（f,c）,是从顶点a出发可以得到的一种深度遍历序列为（ B ）。Aabedfc B. acfebd C. aebdfc D. aedfbc47. 若一个有n个顶点的无向图中没有重复的边，有一个顶点的度是n-1,则所有顶点中顶点的度的最小可能是（ B ）A. B. C. 大于 D. n-148. 若一个有n个顶点的无向图中没有重复的边，有一个顶点的度是n-1,则下面叙述中正确的是( A )。A至少有3个顶点的度是相同的 B. 至少有2个顶点的度是相同的 C. 至多有3个顶点的度是相同的 D. 至多有2个顶点的度是相同的49. 设一棵二叉树中度为0,1,2的结点的个数分别是m,n,k,则下面选择中正确的是（ A ）。A. m=k+1B.m=k-1 C.m=n+1D.m=n-150.下面的题目中涉及到的数据类型的定义都和所学的教材中的定义相同，不在此给出为,下面算法代码中50处应该是（ C ）Status PreorderTraverse(BiTree T,Status (*Visit)(TElemType e) if(50)if(Visit(T-data) if( PreOrderTraverse( 51 ,Visit ) ) if( PreOrderTraverse( 52 ,Visit ) ) return OK; else return OK;AT-lchild B. T-rchild C. T D. T=NULL51. 下面的题目中涉及到的数据类型的定义都和所学的教材中的定义相同，不在此给出为,下面算法代码中51处应该是（ A ）Status PreorderTraverse(BiTree T,Status (*Visit)(TElemType e) if(50)if(Visit(T-data) if( PreOrderTraverse( 51 ,Visit ) ) if( PreOrderTraverse( 52 ,Visit ) ) return OK; else return OK;A T-lchild B. T-rchild C. T D. T=NULL52.下面的题目中涉及到的数据类型的定义都和所学的教材中的定义相同，不在此给出为,下面算法代码中52处应该是（ B ）Status PreorderTraverse(BiTree T,Status (*Visit)(TElemType e) if(50)if(Visit(T-data) if( PreOrderTraverse( 51 ,Visit ) ) if( PreOrderTraverse( 52 ,Visit ) ) return OK; else return OK;A T-lchild B T-rchild C. TD. T=NULL53.下面的代码是应用二叉树的遍历的思想求二叉树的叶子的个数，53处应该是（D）。int LeafCount(BiTree &T） if() return(0); else if() return(1); else return();A. T-lchild B. T-rchild C. T D. T=NULL54.下面的代码是应用二叉树的遍历的思想求二叉树的叶子的个数，54处应该是（C）。int LeafCount(BiTree &T） if() return(0); else if() return(1); else return();A.T-lchild=NULLB.T-rchild=NULLC.T-lchild=NULL&T-rchild=NULLD.T55.下面的代码是应用二叉树的遍历的思想求二叉树的叶子的个数，55处应该是（A）。int LeafCount(BiTree &T） if() return(0); else if() return(1); else return();A.LeafCount(T-lchild)+leaf(T-rchild)B.LeafCount(T-lchild)A.LeafCount(T-rchild)C.LeafCount(T)56.下面的代码是应用二叉树的遍历的思想求二叉树的高度，56处应该是（B）。 int TreeDepth(BiTree &T) if()return(0); elsereturn();AT B. T=NULL C. T-lchild D. T-lchild57. max()是求二者最大一个值的函数，下面的代码是应用二叉树的遍历的思想求二叉树的高度，57处应该是（C）。 int TreeDepth(BiTree &T) if()return(0); elsereturn();A. max(TreeDepth (T-left), TreeDepth (T-right)） B. TreeDepth (T-left) C.max(TreeDepth (T-left), TreeDepth (T-right)+1 D. TreeDepth (T-right)+158. 以双向线索链表为存储结构对二叉树进行遍历的算法代码如下，58处应该是（A）。Status f(BiThrTree T,Status (*Visit) BiThrTree p; p=T-lchild; while(p!=T)while(p-Ltag=Link) ;if(!Visit(p-data) return ERROR;while(p-Rtag=Thread&) p=p-rchild;Visit(p-data);Return OK;Ap=p-lchild B. p=p-rchildC. p=T D. p=p-lchild-rchild59. 题目同题58，59处应该是（A）。Ap-rchild!=T Bp-lchild!=T Cp!=T D. p=NULL60. 题目同题58，60处应该是（C）。Ap=p-lchild Bp=p-LtagCp=p-rchild Dp=p-RTag61. 下面是关于图的深度优先搜索的算法描述,61处应该是（C）： Boolean visitedMax_Vertices_Num；/是否访问过的标志数组Status (*VisitFunc)(int v); /指向函数的指针变量void DFSearch(Matric_Graph G，status(*Visit)(int v) VisitFunc=Visit; for(v=1；v+)/访问标志数组初始化，全置为未访问过 visitedv-1=FALSE； for(v=1；v+) if() DFS(G，v)；/对尚未访问过的顶点调用DFS进行访问void DFS(Matrix_Graph G，int v)visitedv=;VisitFunc(v);/访问第v个顶点for(u=；u=0；u=)if(!visitedu) DFS(G，u);/对与v邻接的顶点进行遍历，尚未访问的就调用DFS访问A. v=G.Vexnum B. v=G.Vexnum+1 C. v=G.Vexnum 62. 题目同题61,处应该是（ D ）。A. visitedv-1 B. !visitedv-1C. visitedv D. !visitedv 63. 题目同题61,处应该是( A )。 A. TRUE B. FALSE C. 0 D. n 64. 题目同题61,处应该是(B )。A. FirstAdjVex(G,v)-1 B. FirstAdjVex(G,v) C. NextAdjVex(G,v,u)-1 D. NextAdjVex(G,v,u) 65. 题目同题61,处应该是（ D ）。 A. FirstAdjVex(G,v)-1 B. FirstAdjVex(G,v) CNextAdjVex(G,v,u)-1 D. NextAdjVex(G,v,u)66. 以下是关于由邻接表GL存储的图从第i个顶点开始的广度优先搜索的算法，66处应该是（A）。void AJ(AdjList GL,int i,int n) Queue Q;InitQueue(Q);coutiadjvex; if() coutjnext DGLj+11. 树是一种线性结构。( )2. 树至少有一个根结点。( ) 3二叉树是树的特殊形式。( )4二叉树中每个结点的两棵子树的高度差等于1。( )5若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。( ) 6二叉树中每个结点的两棵子树是有序的。( )7二叉树中每个结点有两棵非空子树或有两棵空子树。( )8. 二叉树中结点的总数是2的(k-1)次方-1，其中k是树的深度。( ) 9. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。( )10. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 ( )11. .用二叉链表法（link