《数据结构》1至5章期末复习题.pdf

第一章 一、单项选择题 1.数据结构是指（）。A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句 x+的时间是单位时间，则以下语句的时间复杂度为（）。for(i=1;i=n;i+)for(j=i;j=n;j+)x+;A.O(1)B.O()C.O(n)D.O()5.算法分析的目的是（1），算法分析的两个主要方面是（2）。A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性（2）A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。（1）A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法（2）A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10.计算机内部数据处理的基本单位是（）。A.数据 B.数据元素 C.数据项 D.数据库 二、填空题 1.数据结构按逻辑结构可分为两大类，分别是_和_。2.数据的逻辑结构有四种基本形态，分别是_、_、_和_。3.线性结构反映结点间的逻辑关系是_的，非线性结构反映结点间的逻辑关系是_的。4.一个算法的效率可分为_效率和_效率。5.在树型结构中，树根结点没有_结点，其余每个结点的有且只有_个前趋驱结点；叶子结点没有 _结点；其余每个结点的后续结点可以 _。6.在图型结构中，每个结点的前趋结点数和后续结点数可以_。7.线 性结 构 中元 素之 间 存在 _关 系；树型结 构 中元 素之 间存在_关系；图型结构中元素之间存在_关系。8.下面程序段的时间复杂度是_。for(i=0;iN;I+)for(j=0;jN;J+)Aij=0;9.下面程序段的时间复杂度是_。i=s=0;while(sN)i+;s+=i;10.下面程序段的时间复杂度是_。s=0;for(i=0;iN;I+)for(j=0;jN;J+)s+=Bij;sum=s;11.下面程序段的时间复杂度是_。i=1;while(i=n)i=i*3;12.衡量算法正确性的标准通常是_。13.算法时间复杂度的分析通常有两种方法，即_和_的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求下列程序段的时间复杂度。1.x=0;for(i=1;iN;I+)for(j=i+1;j=n;j+)x+;2.x=0;for(i=1;iN;I+)for(j=1;j=n-i;j+)x+;3.int i,j,k;for(i=0;iN;I+)for(j=0;j=n;j+)cij=0;for(k=0;kN;K+)cij=aik*bkj 4.i=n-1;while(i=0)&Ai!=k)j-;return(i);5.fact(n)if(n=1)return(1);else return(n*fact(n-1);第三章 一、单项选择题 1.空串与空格字符组成的串的区别在于（）。A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2.一个子串在包含它的主串中的位置是指（）。A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3.下面的说法中，只有（）是正确的。A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若 T包含在 S中，则 T一定是 S的一个子串 D.一个字符串不能说是其自身的一个子串 4.两个字符串相等的条件是（）。A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 5.若 SUBSTR（S，i，k）表示求 S中从第 i 个字符开始的连续 k 个字符组成的子串的操作，则对于 S=“BeijingNanjing”，SUBSTR（S，4，5）=（）。A.“ijing”B.“jing”C.“ingNa”D.“ingN”6.若 INDEX（S，T）表示求 T在 S中的位置的操作，则对于 S=“BeijingNanjing”，T=“jing”，INDEX（S，T）=（）。A.2 B.3 C.4 D.5 7.若 REPLACE（S，S1，S2）表示用字符串 S2 替换字符串 S中的子串 S1 的操作，则对于S=“BeijingNanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。A.“NanjingShanghai”B.“NanjingNanjing”C.“ShanghaiNanjing”D.“ShanghaiNanjing”8.在长度为 n的字符串 S的第 i 个位置插入另外一个字符串，i 的合法值应该是（）。A.i0 B.in C.1i n D.1i n+1 9.字符串采用结点大小为 1的链表作为其存储结构，是指（）。A.链表的长度为 1 B.链表中只存放 1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 二、填空题 1.计算机软件系统中，有两种处理字符串长度的方法：一种是_，第二种是_。2.两个字符串相等的充要条件是_和_。3.设字符串 S1=“ABCDEF”，S2=“PQRS”，则运算 S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值为_。4.串是指_。5.空串是指_，空格串是指_。三、算法设计题 1.设有一个长度为 s 的字符串，其字符顺序存放在一个一维数组的第 1至第 s 个单元中（每个单元存放一个字符）。现要求从此串的第 m个字符以后删除长度为 t 的子串，mS，tlc=NULL B.p-ltag=1 C.p-ltag=1 且 p-lc=NULL D.以上都不对 9.设 n,m 为一棵二叉树上的两个结点，在中序遍历序列中 n在 m前的条件是（）。A.n在 m右方 B.n在 m 左方 C.n是 m的祖先 D.n是 m的子孙 10.如果 F是由有序树 T转换而来的二叉树，那么 T中结点的前序就是 F中结点的（）。A.中序 B.前序 C.后序 D.层次序 11.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（）存储结构。A.三叉链表 B.广义表 C.二叉链表 D.顺序 12.下面叙述正确的是（）。A.二叉树是特殊的树 B.二叉树等价于度为 2的树 C.完全二叉树必为满二叉树 D.二叉树的左右子树有次序之分 13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 14.已知一棵完全二叉树的结点总数为 9个，则最后一层的结点数为（）。A.1 B.2 C.3 D.4 15.根据先序序列 ABDC和中序序列 DBAC确定对应的二叉树，该二叉树（）。A.是完全二叉树 B.不是完全二叉树 C.是满二叉树 D.不是满二叉树 二、判断题 1.二叉树中每个结点的度不能超过 2，所以二叉树是一种特殊的树。（）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）3.线索二叉树是一种逻辑结构。（）4.哈夫曼树的总结点个数（多于 1时）不能为偶数。（）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（）7.根据任意一种遍历序列即可唯一确定对应的二叉树。（）8.满二叉树也是完全二叉树。（）9.哈夫曼树一定是完全二叉树。（）10.树的子树是无序的。（）三、填空题 1.假定一棵树的广义表表示为 A（B（E），C（F（H，I，J），G），D），则该树的度为_，树的深度为_，终端结点的个数为_，单分支结点的个数为_，双分支结点的个数为_，三分支结点的个数为_，C 结点的双亲结点为_，其孩子结点为_和_结点。2.设 F是一个森林，B是由 F转换得到的二叉树，F中有 n个非终端结点，则 B中右指针域为空的结点有_个。3.对于一个有 n个结点的二叉树，当它为一棵_二叉树时具有最小高度，即为_，当它为一棵单支树具有_高度，即为_。4.由带权为 3，9，6，2，5的 5个叶子结点构成一棵哈夫曼树，则带权路径长度为_。5.在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。6.对于一棵具有 n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_个，其中_个用于链接孩子结点，_个空闲着。7.在一棵二叉树中，度为 0的结点个数为 n0，度为 2的结点个数为 n2，则 n0=_。8.一棵深度为 k 的满二叉树的结点总数为_，一棵深度为 k 的完全二叉树的结点总数的最小值为_，最大值为_。9.由三个结点构成的二叉树，共有_种不同的形态。10.设高度为 h的二叉树中只有度为 0和度为 2的结点，则此类二叉树中所包含的结点数至少为_。11.一棵含有 n个结点的 k 叉树，_形态达到最大深度，_形态达到最小深度。12.对于一棵具有 n个结点的二叉树，若一个结点的编号为 i(1i n)，则它的左孩子结点的编号为_，右孩子结点的编号为_，双亲结点的编号为_。13.对于一棵具有 n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_个，其中_个用于链接孩子结点，_个空闲着。14.哈夫曼树是指_的二叉树。15.空树是指_，最小的树是指_。16.二叉树的链式存储结构有_和_两种。17.三叉链表比二叉链表多一个指向_的指针域。18.线索是指_。19.线索链表中的 rtag域值为_时，表示该结点无右孩子，此时_域为指向该结点后继线索的指针。20.本节中我们学习的树的存储结构有_、_和_。四、应用题 1.已知一棵树边的集合为I，m，I，n，E，i，B，e，B，d，A，b，G，j，G，k，C，g，C，f，H，l，C，h，A，c，请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点 g 的双亲？（4）哪些是结点 g的祖先？（5）哪些是结点 g的孩子？（6）哪些是结点 e的孩子？（7）哪些是结点 e的兄弟？哪些是结点 f 的兄弟？（8）结点 b和 n的层次号分别是什么？（9）树的深度是多少？（10）以结点 c 为根的子树深度是多少？2.一棵度为 2的树与一棵二叉树有何区别。3.试分别画出具有 3个结点的树和二叉树的所有不同形态？4.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。5.一棵深度为 H的满 k 叉树有如下性质：第 H层上的结点都是叶子结点，其余各层上每个结点都有 k 棵非空子树，如果按层次自上至下，从左到右顺序从 1开始对全部结点编号，回答下列问题：（1）各层的结点数目是多少？（2）编号为 n的结点的父结点如果存在，编号是多少？（3）编号为 n的结点的第 i 个孩子结点如果存在，编号是多少？（4）编号为 n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6.找出所有满足下列条件的二叉树：（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；（2）它们在后序遍历和中序遍历时，得到的遍历序列相同；（3）它们在先序遍历和后序遍历时，得到的遍历序列相同；7.假设一棵二叉树的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请写出该二叉树的后序遍历序列。8.假设一棵二叉树的后序序列为 DCEGBFHKJIA，中序序列为 DCBGEAHFIJK，请写出该二叉树的后序遍历序列。9.给出如图 5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。10给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。ABDEFCGHJIKNOML 五、算法设计题 1.一棵具有 n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。2.给定一棵用二叉链表表示的二叉树，其中的指针 t 指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。3.写出在中序线索二叉树中结点 P的右子树中插入一个结点 s 的算法。4.给定一棵二叉树，用二叉链表表示，其根指针为 t，试写出求该二叉树中结点 n的双亲结点的算法。若没有结点 n或者该结点没有双亲结点，分别输出相应的信息；若结点 n有双亲，输出其双亲的值。