数据结构测验12-2答案
数据结构测验二一、单项选择题：1任何一棵二叉树T，如果其终端结点数为no，度为2的结点数为n2，则（ ）。Ano=n2+1 B n2=n0+1Cn0=2n2+1 Dn2=2n0+12设X是一棵树，x是对应于X的二叉树，则X的后根遍历和x的（）遍历相同。A先序 B中序 C后序 D层次序3深度为K的二叉树至多有（ ）个结点。A. 2k B. 2k 1 C. 2k-1 D. 2k-1 -14将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。A98 B99 C50 D485结点先序为XYZ的不同二叉树，那么它有（）不同形态。A3 B4 C5 D66某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。A空或只有一个结点 B高度等于其结点数 C任一结点无左孩子 D任一结点无右孩子7树最适合用来表示（ ）。A有序数据元素 B.无序数据元素C.元素之间无联系的数据 D.元素之间有分支层次关系的数据8二叉树在线索化后，仍不能有效求解的问题是（）。A前序线索二叉树中求前序后继 B中序线索二叉树中求中序后继C中序线索二叉树中求中序前趋 D后序线索二叉树中求后序后继9.判断线索二叉树中某结点p有左孩子的条件是（）。Ap！null Bp-lchild!=null Cp->ltag=Thread Dp-ltag=Link10任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。A发生改变 B.不发生改变 C不能确定 D以上都不对11、任何一个无向连通图的最小生成树（ ）。A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在12在一个无向图图中，所有顶点的度数之和等于图的边数的（）倍。Al2 B 1 C2 D 4 13有8个结点的无向图最多有（）条边。A14 B28 C56 D11214用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法的。A栈 B队列 C树 D图15、深度优先遍历类似于二叉树的（ ）。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历16、对于一个具有n个顶点的有向图，采用邻接矩阵表示该矩阵的大小是（ ）。A. n B. (n-1)2 C. n-1 D. n2二、判断题（认为正确在答题处写T，不正确写´）1n（n>2）个结点的二叉树中至少有一个度为2的结点。2在任何一棵完全二叉树中，终端结点或者与分支结点一样多，或者只比分支结点多一个。3二叉树的遍历只是为了在应用中找到一种线性次序4二叉树的先序遍历序列“cctv”并不能唯一确定这棵树5哈夫曼树中不存在度为1的结点6如果表示某个图的邻接矩阵是不对称矩阵，则该图一定是有向图7连通分量是无向图的极小连通子图8连通图的广度优先搜索中一般要采用队列来存储刚访问过的顶点9最小生成树是指边数最少的生成树。10任何有向无环图的结点都可以排成拓扑排序， 拓扑序列不唯一三、简答题：1已知权值：4，2，3，7，6，18，27请画出相应的哈夫曼树并计算其带权路径长度WPL（要求左孩子的权小于同一双亲右孩子的权）。2一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试求出空格处的内容，并画出二叉树的中序前驱线索。 先序：B FICEH G 中序：DKFIA EJC 后序： K FBHJ G A3已知图G如下所示，画出G的邻接矩阵和邻接表。4假定无向图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，2，1，4，2，5，5，4，4，3，5，3。写出图G中顶点的所有拓扑排序。6.设无向图G的邻接矩阵如下所示，画出用Prim算法得的最小生成树。（从顶点0开始，写出计算过程） 1 2 2 21 3 2 3 5 2 5 3 2 3 四、算法设计题目（先写出物理结构）：1写出二叉树的存储结构，并写出判断二叉树中结点p是否是结点q的祖先的算法。2写出图的深度优先遍历的算法答题纸 学号: 姓名: 一、单项选择题：1.5×16=24题号12345678答题ABBACBDD题号910111213141516答题DBBCBAAD二、判断题（认为正确在答题处写T，不正确写´）1×10=10题号12345678910答题×T×TTT×T×T三、简答题：1已知权值：4，2，3，7，6，18，27请画出相应的哈夫曼树并计算其带权路径长度WPL（要求左孩子的权小于同一双亲右孩子的权）。(6)WPL=27*1+18*2+(4+6+7)*4+(2+3)*5=27+36+68+25=1562一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试求出空格处的内容，并画出二叉树的中序前驱线索。(8) 先序：ABDFKICEHJG 中序：DBKFIAHEJCG 后序：DKIFBHJEGCA3已知图G如下所示，画出G的邻接矩阵和邻接表(4)。 1 3 4 1 5 23 5 64 2 6 4假定无向图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），（G，C），（B，D），（C，F），（D，G）。试从顶点A出发，分别写出按深度优先搜索和广度优先搜索进行遍历的生成树。深度优先搜索 广度优先搜索5图G=（V，E），V=0，1，2，3，4，5，E=0，1，0，2，1，4，2，5，5，4，4，3，5，3。写出图G中顶点的所有拓扑排序。(6)0 1 2 5 4 30 2 1 5 4 30 2 5 1 4 36.设无向图G的邻接矩阵如下所示，画出用Prim算法得的最小生成树。（从顶点0开始，写出计算过程）（10） 1 2 2 21 3 2 3 5 2 5 3 2 3 1234UV-Ukadjvexlowcost0102020201,2,3,41adjvexlowcost00202020,12,3,42adjvexlowcost0002020,1,23,43adjvexlowcost000020,1,2,344adjvexlowcost00000,1,2,3,4 7.最短工期是97最早开工时间是：v1v2v4v6v5v3v7v80615051897597四、算法设计题目：（10*2）1写出二叉树的存储结构，并写出判断二叉树中结点p是否是结点q的祖先的算法。/- - - - -二叉树的二叉链表存储表示- - - - -typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; /左右孩子指针 BiTNode, *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; v<G.vexnum; +v) visitedv = FALSE ;/ 访问标志数组初始化 for(v=0; v<G.vexnum; +v ) if(!visitedv) DFS (G,v ); /对尚未访问的顶点调用DFSvoid DFS(Graph G, int v) /从第v个顶点出发递归地深度优先遍历图G visitedv=TRUE; VistFunc(v); /访问第v个顶点 for(w=FirstAdjVex(G,v);w>=0; w=NextAdjVex(G,v,w) if(!visitedw) DFS
