数据结构考前复习3

1第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A．求子串B．联接C．匹配D．求串长10．串的长度是指（B）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数二、填空题1．空格串是指由空格字符（ASCII值32）所组成的字符串，其长度等于空格个数__。2．组成串的数据元素只能是__字符______。3．一个字符串中任意个连续的字符组成的子序列称为该串的子串。四、应用题1．名词解释：串串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。2．描述以下概念的区别：空格串与空串。空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。第六章树和二叉树一、选择题1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(D)A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE4.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）A．5B．6C．7D．85.在下述结论中，正确的是（D）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④结点的度：一个结点的子数个数称为此结点的度数的度;树中所有结点的读的最大值6.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A）A．m-nB．m-n-1C．n+1D．条件不足，无法确定8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A．9B．11C．15D．不确定10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）。A．M1B．M1+M2C．M3D．M2+M3211．具有10个叶结点的二叉树中有（B）个度为2的结点，A．8B．9C．10D．ll13.设给定权值总数有n个，其哈夫曼树的结点总数为(D)A．不确定B．2nC．2n+1D．2n-114.有n个叶子的哈夫曼树的结点总数为（D）。A．不确定B．2nC．2n+1D．2n-116.有关二叉树下列说法正确的是（B）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为217．二叉树的第I层上最多含有结点数为（C）A．2IB．2I-1-1C．2I-1D．2I-123．在一棵高度为k的满二叉树中，结点总数为（C）A．2k-1B．2kC．2k-1D．log2k+132．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（B）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定41．对于前序遍历与中序遍历结果相同的二叉树为（F）;对于前序遍历和后序遍历结果相同的二叉树为（B）。A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树F．所有结点只有右子树的二叉树42．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树57.由3个结点可以构造出多少种不同的有向树？（A）A．2B．3C．4D．563．下面几个符号串编码集合中，不是前缀编码的是（B）。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}二、判断题1.二叉树是度为2的有序树。×2.完全二叉树一定存在度为1的结点。×6.二叉树的遍历结果不是唯一的.√7.二叉树的遍历只是为了在应用中找到一种线性次序。√9.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。√10.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。×12．对一棵二叉树进行层次遍历时，应借助于一个栈。×45．霍夫曼树的结点个数不能是偶数。√48．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。×三、填空题1．二叉树由_根结点_，__左子树_，_右子树__三个基本单元组成。2．树在计算机内的表示方式有双亲链表表示法__，孩子链表表示法，孩子兄弟表示法__。33．在二叉树中，指针p所指结点为叶子结点的条件是_p-lchild==null&&p-rchlid==null_____。9．深度为H的完全二叉树至少有2H-1个结点；至多有2H-1个结点；H和结点总数N之间的关系是H=log2N+1。四、应用题41.证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC。试画出该二叉树。（1）试画出在先根次序和中根次序下结点排列顺序皆相同的所有类型的二叉树形。试画出在先根次序和后根次序下结点排列顺序皆相同的所有类型的二叉树形。由前序序列ABDGECFH和中序序列DGBEAFHC构造的二叉树如图：42.（1）给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。由中序序列DBEAFIHCG和后序序列DEBHIFGCA确定的二叉树略。第七章图一、选择题1．图中有关路径的定义是（A）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（B）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n23．一个n个顶点的连通无向图，其边的个数至少为（A）。A．n-1B．nC．n+1D．nlogn；4．要连通具有n个顶点的有向图，至少需要（B）条边。A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（D）。4abedcfA．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。A．0B．1C．n-1D．n7．在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A．1/2B．2C．1D．410．下面结构中最适于表示稀疏无向图的是（C），适于表示稀疏有向图的是（BDE）。A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表11．下列哪一种图的邻接矩阵是对称矩阵？（B）A．有向图B．无向图C．AOV网D．AOE网12．从邻接阵矩010101010A可以看出，该图共有（B）个顶点；如果是有向图该图共有（B）条弧；如果是无向图，则共有（D）条边。①．A．9B．3C．6D．1E．以上答案均不正确②．A．5B．4C．3D．2E．以上答案均不正确③．A．5B．4C．3D．2E．以上答案均不正确13．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（B）。A．nijiA1],[B．n1jj,iAC．niijA1],[D．nijiA1],[+n1ji,jA15.下列说法不正确的是（B）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b17.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（D）aebdfcacfdebaedfcbaefdcbaefdbcA．5个B．4个C．3个D．2个第17题图第18题图518.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(C)，而进行广度优先遍历得到的顶点序列是（C）。①．A．1354267B．1347652C．1534276D．1247653E．以上答案均不正确②．A．1534267B．1726453C．l354276D．1247653E．以上答案均不正确19．下面哪一方法可以判断出一个有向图是否有环（回路）：ABA．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径20.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为(B)。A.O(n)B.O(n+e)C.O(n2)D.O(n3)25．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（A）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V726．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（A）。A．存在B．不存在27．一个有向无环图的拓扑排序序列（B）是唯一的。A．一定B．不一定28.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径30.关键路径是事件结点网络中（A）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路31.下面关于求关键路径的说法不正确的是（C）。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上二、判断题1.树中的结点和图中的顶点就是指数据结构中的数据元素。（√）2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（×）4.有e条边的无向图，在邻接表中有e个结点。（×）5.有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（×）6．强连通图的各顶点间均可达。（√）7．强连通分