《数据结构测验12》由会员分享，可在线阅读，更多相关《数据结构测验12（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构测验二一、单项选择题：1 任何一棵二叉树T,如果其终端结点数为n，度为2的结点数为n，则 o2（ ）。=n+1o 22 .设X是一棵树,B. n =n +1C. n =2n +1D. n =2n +12 0 0 2 2 0x是对应于X的二叉树，则X的后根遍历和x的（）遍历相同。A. 先序B.中序C.后序D.层次序3. 深度为K的二叉树至多有（）个结点。A.2kB.2k - 1C.2k-1D.2k-1 -14. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行 编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。A. 98B. 99C. 50D. 485. 结点
2、先序为XYZ的不同二叉树，那么它有（）不同形态。A. 3B. 4C. 5D. 66. 某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个结点C. 任一结点无左孩子7. 树最适合用来表示（）A.有序数据元素C. 元素之间无联系的数据8. 二叉树在线索化后，仍不能B. 高度等于其结点数D. 任一结点无右孩子B. 无序数据元素D.元素之间有分支层次关系的数据A.前序线索二叉树中求前序后继 B.中序线索二叉树中求中序后继C. 中序线索二叉树中求中序前趋 D.后序线索二叉树中求后序后继 9判断线索二叉树中某结点p有左孩子的条件是（）。A. p!=nullB. p-lchil
3、d!二nullC. p-ltag二二ThreadD. p-ltag二二Link10. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序 （）。A.发生改变B.不发生改变C.不能确定D.以上都不对11、任何一个无向连通图的最小生成树（）。A.只有一棵B. 一棵或多棵C.一定有多棵D.可能不存在12. 在一个无向图图中，所有顶点的度数之和等于图的边数的（）倍。A. l / 2B. 1C. 2D. 413. 有8个结点的无向图最多有（）条边。A.14B. 28C. 56D.11214. 用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法的。A.栈B.队列C.树D.图15. 深度优先
4、遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历16. 对于一个具有n个顶点的有向图，采用邻接矩阵表示该矩阵的大小是（）。A. nB. （n-1）2C. n-1D. n2二、判断题（认为正确在答题处写T,不正确写）1. n （n2）个结点的二叉树中至少有一个度为2的结点。2. 在任何一棵完全二叉树中，终端结点或者与分支结点一样多，或者只比 分支结点多一个。3. 二叉树的遍历只是为了在应用中找到一种线性次序4.5.6.二叉树的先序遍历序列“cctv”并不能唯一确定这棵树哈夫曼树中不存在度为1的结点如果表示某个图的邻接矩阵是不对称矩阵，则该图一定是有向图7. 连通分量是无向
5、图的极小连通子图8. 连通图的广度优先搜索中一般要采用队列来存储刚访问过的顶点9. 最小生成树是指边数最少的生成树。10任何有向无环图的结点都可以排成拓扑排序，拓扑序列不唯三、简答题：1. 已知权值：4， 2， 3， 7， 6， 18， 27 请画出相应的哈夫曼树并计算其带 权路径长度WPL （要求左孩子的权小于同一双亲右孩子的权）。2. 一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试 求出空格处的内容，并画出二叉树的中序前驱线索。先序：_B_F_ICEH_G中序：D_KFIA_EJC_后序：_K_FBHJ_G_A3已知图 G 如下所示，画出 G 的邻接矩阵和邻接表。4. 假定
6、无向图G有6个结点和7条边，并依次输入这8条边为(A, B), (A, D),(A，E), (G, C), (B, E), (C, F), (D, E)。试从顶点 A 出发，分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。5. 图 G= (V, E), V= 0, 1, 2, 3, 4, 5, E= 0, 1,0, 21, 4 2 5 5 4 4 3 5 3。写出图 G 中顶点的所有拓扑排 序。6. 设无向图 G 的邻接矩阵如下所示 画出用 Prim 算法得的最小生成树。(从 顶点 0 开始 写出计算过程)(s 1222 1OO3oooo2 3005o2o5o32oo3o 丄四、算法设
7、计题目(先写出物理结构)：1. 写出二叉树的存储结构 并写出判断二叉树中结点 p 是否是结点 q 的祖 先的算法。2. 写出图的深度优先遍历的算法答题纸学号:姓名:一、单项选择题：1.5x16=24题号12345678答题ABBACBDD题号910111213141516答题DBBCBAAD二、判断题（认为正确在答题处写T,不正确写）1x10=10题号12345678910答题xTxTTTxTxT三、简答题：1已知权值：4, 2, 3, 7, 6, 18, 27 请画出相应的哈夫曼树并计算其带权路径长度WPL （要求左孩子的权小于同一双亲右孩子的权）。（6）WPL=27*1+18*2+(4+6
8、+7)*4+(2+3)*5=27+36+68+25=1562一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试先序：中序：后序：DBKFIAHEJCGDKIFBHJEGCA求出空格处的内容，ABDFKICEHJG3s 1 3 41 s 5 23 5 s 64 2 6s4.假定无向图G有7个结点和7条边，并依次输入这7条边为（A, B）,（A, D），（A，E），（G，C），（B, E），（C，F），（D，E）。试从顶点 A 出发,分别写出按深度优先搜索和广度优先搜索进行遍历的生成树。 （6）4.假定无向图G有6个结点和7条边，并依次输入这7条边为（A, B）,(A,D),(A，E)
9、,(G,C),(B,D),(C,F),(D,G)。试从顶点 A 出发,分别写出按深度优先搜索和广度优先搜索进行遍历的生成树。5, E=0, 1,0, 21,42, 5,5, 4,4, 3,5, 3。写出图G中顶点的所有拓扑排 序。 (6)0 1 2 5 4 30 2 1 5 4 30 2 5 1 4 3 6.设无向图G的邻接矩阵如下所示，画出用Prim算法得的最小生成树。（从顶点 0 开始，写出计算过程）（10）(812221OO3oooo2300 5 o2 o 5 o 32 OO O 3 o /1234Uv-ukadjvex000001,2,3,41lowcost1222adjvex0000
10、,12,3,42lowcost0222adjvex000,1,23,43lowcost0022adjvex00,1,2,344lowcost0002adjvex lowcost00000,1,2,3,4 7. 最短工期是 97 最早开工时间是v1v2v4v6v5v3v7v80615051897597四、算法设计题目：（10*2）1.写出二叉树的存储结构，并写出判断二叉树中结点p是否是结点q的祖 先的算法。/二叉树的二叉链表存储表示typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild; / 左右孩子指针 BiT
11、Node, *BiTree;方法一：BiTree find(BiTree T，TElemType p) if(T| T-data=p) return T;s= find(T-lchild,p);if(s)return s;else return find(T-lchild,p);int panduan(BiTree T, TElemType p, TElemType q) if(T) s=find(T,p);if( s) t=find(s,q);if(t) return OK;return ERROR;2写出图的深度优先遍历的算法(10 分)int visitedMAX; / 访问标志数组Status (* VisitFunc)(int v); / 函数指针变量void DFSTraverse(Graph G, Status(* Visit)(int v)/ 对图 G 作深度优先遍历VisitFunc = Visit;/使用全局变量VisitFunc,使DFS不必设函数指针参数for(v=0; vG.vexnum; +v)visitedv = FALSE ;/ 访问标志数组初始化for(v=0; v=0; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w);对v的尚未访问的邻接顶点w递归调用DFS
