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

数据结构测验二 一、单项选择题： 1．任何一棵二叉树T，如果其终端结点数为no，度为2的结点数为n2，则（ ）。 A．no=n2+1 B． n2=n0+1 C．n0=2n2+1 D．n2=2n0+1 2．设X是一棵树，x’是对应于X的二叉树，则X的后根遍历和x’的（）遍历相同。 A．先序 B．中序 C．后序 D．层次序 3．深度为K的二叉树至多有（ ）个结点。 A. 2k B. 2k –1 C. 2k-1 D. 2k-1 -1 4．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。 A．98 B．99 C．50 D．48 5．结点先序为XYZ的不同二叉树，那么它有（）不同形态。 A．3 B．4 C．5 D．6 6．某二叉树的先序和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子 7．树最适合用来表示（ ）。 A．有序数据元素 B.无序数据元素 C.元素之间无联系的数据 D.元素之间有分支层次关系的数据 8．二叉树在线索化后，仍不能有效求解的问题是（）。 A．前序线索二叉树中求前序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继 9.判断线索二叉树中某结点p有左孩子的条件是（）。 A．p！＝null B．p-＞lchild!=null C．p-ltag==Thread D．p-＞ltag==Link 10．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。 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. n B. (n-1)2 C. n-1 D. n2 二、判断题（认为正确在答题处写T，不正确写?） 1．n（n2）个结点的二叉树中至少有一个度为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 A 3．已知图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〉}。