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

《《数据结构》1至5章期末复习题.pdf》由会员分享，可在线阅读，更多相关《《数据结构》1至5章期末复习题.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 一、单项选择题 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.找出数

2、据结构的合理性 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.不好说

3、8.数据结构作为一门独立的课程出现是在（）年。A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10.计算机内部数据处理的基本单位是（）。A.数据 B.数据元素 C.数据项 D.数据库 二、填空题 1.数据结构按逻辑结构可分为两大类，分别是_和_。2.数据的逻辑结构有四种基本形态，分别是_、_、_和_。3.线性结构反映结点间的逻辑关系是_的，非线性结构反映结点间的逻辑关系是_的。4.一个算法的效率可分为_效率和_效率。5.在树型结构中，树根结点没有_结点，其余每

4、个结点的有且只有_个前趋驱结点；叶子结点没有 _结点；其余每个结点的后续结点可以 _。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

5、=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.fac

6、t(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

7、一定是 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”

8、，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.字符串采

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 的字符串，其字符顺序存放在一个

10、一维数组的第 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.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（）存储

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.

12、二叉树中每个结点的度不能超过 2，所以二叉树是一种特殊的树。（）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）3.线索二叉树是一种逻辑结构。（）4.哈夫曼树的总结点个数（多于 1时）不能为偶数。（）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（）7.根据任意一种遍历序列即可唯一确定对应的二叉树。（）8.满二叉树也是完全二叉树。（）9.哈夫曼树一定是完全二叉树。（）10.树的子树是无序的。（）三、填空题 1.假定一棵树的广义表表示为 A（B（E），C（F（H，I，J），G），D），则该树的度为_，树的深度为_，终端结

13、点的个数为_，单分支结点的个数为_，双分支结点的个数为_，三分支结点的个数为_，C 结点的双亲结点为_，其孩子结点为_和_结点。2.设 F是一个森林，B是由 F转换得到的二叉树，F中有 n个非终端结点，则 B中右指针域为空的结点有_个。3.对于一个有 n个结点的二叉树，当它为一棵_二叉树时具有最小高度，即为_，当它为一棵单支树具有_高度，即为_。4.由带权为 3，9，6，2，5的 5个叶子结点构成一棵哈夫曼树，则带权路径长度为_。5.在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。6.对于一棵具有 n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_个，其中_个用于链接孩

14、子结点，_个空闲着。7.在一棵二叉树中，度为 0的结点个数为 n0，度为 2的结点个数为 n2，则 n0=_。8.一棵深度为 k 的满二叉树的结点总数为_，一棵深度为 k 的完全二叉树的结点总数的最小值为_，最大值为_。9.由三个结点构成的二叉树，共有_种不同的形态。10.设高度为 h的二叉树中只有度为 0和度为 2的结点，则此类二叉树中所包含的结点数至少为_。11.一棵含有 n个结点的 k 叉树，_形态达到最大深度，_形态达到最小深度。12.对于一棵具有 n个结点的二叉树，若一个结点的编号为 i(1i n)，则它的左孩子结点的编号为_，右孩子结点的编号为_，双亲结点的编号为_。13.对于一棵

15、具有 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）哪个

16、是根结点？（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层上的结点都是叶子结点，其余各层上每个结点都

17、有 k 棵非空子树，如果按层次自上至下，从左到右顺序从 1开始对全部结点编号，回答下列问题：（1）各层的结点数目是多少？（2）编号为 n的结点的父结点如果存在，编号是多少？（3）编号为 n的结点的第 i 个孩子结点如果存在，编号是多少？（4）编号为 n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6.找出所有满足下列条件的二叉树：（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；（2）它们在后序遍历和中序遍历时，得到的遍历序列相同；（3）它们在先序遍历和后序遍历时，得到的遍历序列相同；7.假设一棵二叉树的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请写出该二

18、叉树的后序遍历序列。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有双亲，输出其双亲的值。