数据结构测验12-2答案.doc

《数据结构测验12-2答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构测验二一、单项选择题：1．任何一棵二叉树T，如果其终端结点数为no，度为2的结点数为n2，则（）。A．no=n2+1B．n2=n0+1C．n0=2n2+1D．n2=2n0+12．设X是一棵树，x’是对应于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．结点先序为XYZ的不同二叉树，那么它有（）不

2、同形态。A．3B．4C．5D．66．某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子7．树最适合用来表示（）。A．有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间有分支层次关系的数据8．二叉树在线索化后，仍不能有效求解的问题是（）。A．前序线索二叉树中求前序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前趋D．后序线索二叉树中求后序后继9.判断线索二叉树中某结点p有左孩子的条件是（）。A．p！＝nullB．p-＞lchild!=nullC．p->ltag==T

3、hreadD．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、深度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍

4、历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．连通图的广度优先搜索中一般要采用队列来存储刚访

5、问过的顶点9．最小生成树是指边数最少的生成树。10．任何有向无环图的结点都可以排成拓扑排序，拓扑序列不唯一三、简答题：1．已知权值：4，2，3，7，6，18，27请画出相应的哈夫曼树并计算其带权路径长度WPL（要求左孩子的权小于同一双亲右孩子的权）。2．一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试求出空格处的内容，并画出二叉树的中序前驱线索。先序：＿BF＿ICEHG中序：D＿KFIAEJC＿后序：KFBHJGA3．已知图G如下所示，画出G的邻接矩阵和邻接表。4．假定无向图G有6个结点和7条边，并依次输入这8条边为（A，B），（A，D），（A，E），（G，C），（B，

6、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开始，写出计算过程）∞12221∞3∞∞23∞5∞2∞5∞32∞∞3∞四、算法设计题目（先写出物理结构）：1．写出二叉树的存储结构，并写出判断二叉树中结点p是否是结点q的祖先的算法。2．写出图的深度优先遍历的算法答题纸学号:姓名:一

7、、单项选择题：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