当前位置:文档之家› 数据结构测验122答案

数据结构测验122答案

数据结构测验二一、单项选择题:1.任何一棵二叉树T,如果其终端结点数为no ,度为2的结点数为n2,则()。

A.no =n2+1 B. n2=n+1 C.n=2n2+1 D.n2=2n+12.设X是一棵树,x’是对应于X的二叉树,则X的后根遍历和x’的()遍历相同。

A.先序B.中序C.后序D.层次序3.深度为K的二叉树至多有()个结点。

A. 2kB. 2k–1C. 2k-1D. 2k-1 -1 4.将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子编号为()。

A.98 B.99 C.50 D.485.结点先序为XYZ的不同二叉树,那么它有()不同形态。

A.3 B.4 C.5 D.66.某二叉树的先序和后序序列正好相反,则该二叉树一定是()的二叉树。

A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子7.树最适合用来表示()。

A.有序数据元素 B.无序数据元素C.元素之间无联系的数据D.元素之间有分支层次关系的数据8.二叉树在线索化后,仍不能有效求解的问题是()。

A.前序线索二叉树中求前序后继 B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋 D.后序线索二叉树中求后序后继9.判断线索二叉树中某结点p有左孩子的条件是()。

A.p!=null B.p->lchild!=nullC.p->ltag==Thread D.p->ltag==Link10.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。

A.发生改变 B.不发生改变C.不能确定 D.以上都不对11、任何一个无向连通图的最小生成树()。

A. 只有一棵B. 一棵或多棵C. 一定有多棵D. 可能不存在12.在一个无向图图中,所有顶点的度数之和等于图的边数的()倍。

A.l/2 B. 1 C.2 D. 4 13.有8个结点的无向图最多有()条边。

A.14 B.28 C.56 D.112 14.用邻接表表示图进行深度优先遍历时,通常采用()来实现算法的。

A.栈B.队列C.树D.图15、深度优先遍历类似于二叉树的()。

A. 先序遍历B. 中序遍历C. 后序遍历D. 层次遍历16、对于一个具有n个顶点的有向图,采用邻接矩阵表示该矩阵的大小是()。

A. nB. (n-1)2C. n-1D. n2二、判断题(认为正确在答题处写T,不正确写)1.n(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 F_ICEH G中序:D_KFIA 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 ∞ 32 ∞∞3 ∞四、算法设计题目(先写出物理结构):1.写出二叉树的存储结构,并写出判断二叉树中结点p是否是结点q的祖先的算法。

2.写出图的深度优先遍历的算法答题纸学号: 姓名:题号 1 2 3 4 5 6 7 8 答题 A B B A C B D D 题号 9 10 11 12 13 14 15 16 答题DBBCBAAD题号 1 2 3 4 5 6 7 8 9 10 答题 ×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=15623549671321183927662.一棵二叉树的先序、中序和后序序列分别如下,其中一部分未给出,试求出空格处的内容,并画出二叉树的中序前驱线索。

(8) 先序:A B D F K ICEH J G中序:D B KFIA H EJC G 后序:D K I FBHJ E G C A3.已知图G 如下所示,画出G 的邻接矩阵和邻接表(4)。

∞ 1 3 4 1 ∞ 5 2 3 5 ∞ 6 4 2 6 ∞4.假定无向图G 有7个结点和7条边,并依次输入这7条边为(A ,B ),(A ,D ),(A ,E ),(G ,C ),(B ,E ),(C ,F ),(D ,E )。

试从顶点A 出发,分别写出按深度优先搜索和广度优先搜索进行遍历的生成树。

(6)a cdb345261深度优先搜索广度优先搜索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 ∞ 32 ∞∞3 ∞7.最短工期是97最早开工时间是:四、算法设计题目:(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 visited[MAX]; // 访问标志数组Status (* VisitFunc))(int v); // 函数指针变量void DFSTraverse(Graph G, Status(* Visit)(int v))// 对图G作深度优先遍历{VisitFunc = Visit;//使用全局变量VisitFunc,使DFS不必设函数指针参数for(v=0; v<G.vexnum; ++v)visited[v] = FALSE ;// 访问标志数组初始化for(v=0; v<G.vexnum; ++v )if(!visited[v]) DFS (G,v ); //对尚未访问的顶点调用DFS}void DFS(Graph G, int v)//从第v个顶点出发递归地深度优先遍历图G{visited[v]=TRUE;VistFunc(v); //访问第v个顶点for(w=FirstAdjVex(G,v);w>=0; w=NextAdjVex(G,v,w))if(!visited[w]) DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS }。

相关主题