《数据结构测验12-2答案》由会员分享，可在线阅读，更多相关《数据结构测验12-2答案（11页珍藏版）》请在金锄头文库上搜索。
1、数据构造测验二一、单选题:1.任何一棵二叉树T，如果其终端结点数为no，度为2的结点数为n2,则（ ）。Ano=n2+1 B n2n01Cn02+1 Dn2=n0+1设X是一棵树,是相应于X的二叉树，则X的后根遍历和的()遍历相似。.先序 B中序 .后序 层顺序3.深度为K的二叉树至多有( )个结点。A. 2k B. 2k 1 C. k-1 D k-1 14.将一棵有00个结点的完全二叉树从上到下,从左到右依次对结点进行编号，根结点的编号为1,则编号为49的结点的左孩子编号为（）。A98 .99 C.5 D485.结点先序为XYZ的不同二叉树，那么它有(）不同形态。A3 B4 C.5 D66.
2、某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一种结点 B高度等于其结点数 .任一结点无左孩子 D任一结点无右孩子7树最适合用来表达( )。A.有序数据元素 B.无序数据元素C元素之间无联系的数据 元素之间有分支层次关系的数据.二叉树在线索化后，仍不能有效求解的问题是（)。.前序线索二叉树中求前序后继 B中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋 后序线索二叉树中求后序后继9.判断线索二叉树中某结点p有左孩子的条件是(）。A.p!null Bplild!ull C.p-tg=Tread D.p-lag=Lin10.任何一棵二叉树的叶结点在先序、中序和
3、后序遍历序列中的相对顺序（ )。A发生变化 B.不发生变化 .不能拟定 .以上都不对11、任何一种无向连通图的最小生成树（ ）。A 只有一棵 B. 一棵或多棵 C一定有多棵 D也许不存在12.在一种无向图图中,所有顶点的度数之和等于图的边数的()倍。Al2 B. 1 C.2 D. 413.有个结点的无向图最多有（)条边。A.14 B8 C56 .114用邻接表表达图进行深度优先遍历时,一般采用（）来实现算法的。A栈 B队列 .树 图、深度优先遍历类似于二叉树的（)。A. 先序遍历 B. 中序遍历 . 后序遍历 D. 层次遍历16、对于一种具有n个顶点的有向图，采用邻接矩阵表达该矩阵的大小是（
4、)。A. . (n-1）2C. n-1D.2二、判断题（觉得对的在答题处写T,不对的写)1.n（n2）个结点的二叉树中至少有一种度为2的结点。2.在任何一棵完全二叉树中，终端结点或者与分支结点同样多，或者只比分支结点多一种。3.二叉树的遍历只是为了在应用中找到一种线性顺序4二叉树的先序遍历序列“cctv”并不能唯一拟定这棵树.哈夫曼树中不存在度为1的结点6.如果表达某个图的邻接矩阵是不对称矩阵,则该图一定是有向图连通分量是无向图的极小连通子图.连通图的广度优先搜索中一般要采用队列来存储刚访问过的顶点9.最小生成树是指边数至少的生成树。10任何有向无环图的结点都可以排成拓扑排序，拓扑序列不唯一三
5、、简答题：1.已知权值:,2，3，,6,1，7请画出相应的哈夫曼树并计算其带权途径长度WP（规定左孩子的权不不小于同一双亲右孩子的权)。2一棵二叉树的先序、中序和后序序列分别如下,其中一部分未给出，试求出空格处的内容，并画出二叉树的中序前驱线索。 先序：_B FIC G 中序：D_KFI EJC_ 后序： FBJ G A3.已知图G如下所示,画出G的邻接矩阵和邻接表。4假定无向图G有6个结点和7条边，并依次输入这8条边为(A，B)，（A,D），（A,E),（G，)，（B,E）,(,F),(D，E)。试从顶点A出发,分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。5.图G=(V,E），V
6、=0,2，,4，5,E=0，0，,1,4，2，5，5，4，3，,3。写出图G中顶点的所有拓扑排序。6.设无向图的邻接矩阵如下所示，画出用ri算法得的最小生成树。(从顶点0开始,写出计算过程) 1 2 2 1 3 5 2 5 3 2 3 四、算法设计题目（先写出物理构造)：1.写出二叉树的存储构造,并写出判断二叉树中结点与否是结点的祖先的算法。写出图的深度优先遍历的算法答题纸 学号： 姓名: 一、单选题：1.1=4题号2345678答题ABDD题号90112114151答题BBAAD二、判断题(觉得对的在答题处写，不对的写）11=10题号234569答题TTTTT三、简答题：已知权值:4，2，,
7、6,18,27请画出相应的哈夫曼树并计算其带权途径长度WPL（规定左孩子的权不不小于同一双亲右孩子的权)。(6)WPL271+1+(4+67)4+(2+3)*=2+36+68+2=156一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出,试求出空格处的内容,并画出二叉树的中序前驱线索。(8) 先序：ABDKICEHJ 中序：DKFAHEJCG 后序:KFBHJEG3已知图G如下所示，画出G的邻接矩阵和邻接表(4）。 1 1 3564 6 4假定无向图有7个结点和7条边，并依次输入这7条边为(A,B），(A,D),(A,E）,（，）,(B,E),(C，F）,(D，）。试从顶点A出发，分别
8、写出按深度优先搜索和广度优先搜索进行遍历的生成树。（6)深度优先搜索 广度优先搜索4.假定无向图G有个结点和条边，并依次输入这7条边为（A，B），(A，D）,(,E)，（，C),(B，D），(C,），（D,)。试从顶点出发，分别写出按深度优先搜索和广度优先搜索进行遍历的生成树。深度优先搜索 广度优先搜索图G=(,E），V=0,1，2，3,4,5，E=0，0，,，5,5,，4,3，。写出图中顶点的所有拓扑排序。(6) 1 2 4 30 2 1 4 30 2 5 1 4 36.设无向图G的邻接矩阵如下所示，画出用Prim算法得的最小生成树。（从顶点0开始,写出计算过程）(0) 1 2 2 3 5
9、3 123U-Udjexlocst01022001,2,3，41adjexlwcost0202020,12,3,42djvexlco000200,1，23,43djvelowcot000，1，2,344advexlowcost000,1,，3,4 7.最短工期是97最早动工时间是：v1v46v3v8050589757四、算法设计题目：（10*2）写出二叉树的存储构造，并写出判断二叉树中结点与否是结点q的祖先的算法。/- - -二叉树的二叉链表存储表达- - ypedef struct BiTNode TEemType data; truc BTode *lchld， *rcld; /左右孩子指
10、针 BiNode, *iTe;措施一：BiTre fnd（BiTee ,lemTye p) if(| T-data=p） rtur ;=find(T-cld,p);if(s） retn s； elserturn fin(T-lchld,p)；intpaduan(BTree ， TEleTpe p, Tmype q)if（T） s=fnd（T,p）;i(s) t=find(s,q）;if（t) returO; etur ERROR;写出图的深度优先遍历的算法(1分)itsitAX; /访问标志数组Statu （ VisitFuc)）(in v); / 函数指针变量id DFSTrvere(Graph G, Stats(* Vii)(n v)/ 对图G作深度优先遍历VistFunc = sit; /使用全局变量itFunc，使S不必设函数指针参数 f(0;vvexnm; +v) vsiedv=ALE ;/ 访问标志数组初始化 fr（0; v=0; =xAjVex(,v,w) if(!vstedw) DF
