数据结构复习题(优化版).doc

【计算机科学与技术系-大一学期期末复习资料】（优化版） 如果发现什么错误，请联系下“纠结的晴朗”Thanks！第六章第4题改正了一次，答案是（B）-第一章-1.算法的计算量的大小称为计算的（ B ）。 A. 效率 B. 复杂性 C. 现实性 D. 难度 2.一个算法应该是（ B ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 3下面说法错误的是（ A ） （1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A. (1)B. (1)(2) C. (1)(4) D. (3) 4.在数据结构中，从逻辑上可以将之分为( D )。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 5.计算算法的时间复杂度是属于一种( B )。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6.可以用( D )定义一个完整的数据结构: A. 数据元素 B. 数据对象 C. 数据关系 D. 抽象数据类型 7.算法分析的目的是_C_。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 8.设计一个“好”的算法应考虑达到的目标有_BCD_。 A. 是可行的 B. 是健壮的 C. 无二义性 D. 可读性好 -第二章-1.线性表是具有n个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 E信息项2.若线性表最常用到操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用到存储方式( D )。 原来文件的答案是A，但如果就本题给出的条件，D更合适A.单链表 B.双向链表 C.单循环链表 D.顺序表 3.某线性表中最常用到操作是在最后一个元素之后插入一个元素或删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 4.设一个链表最常用到操作是在末尾插入结点或删除尾结点，则选用( A )最节省时间。 A. 带头结点的双循环链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 单链表 5.静态链表中指针表示的是( C ) A.下一元素的地址 B.内存储器的地址 C.下一元素在数组中的位置 D.左链或右链指向的元素的地址 6.下述哪一条是顺序存储结构的优点？（ C ） A插入运算方便 B可方便地用于各种逻辑结构的存储表示 C存储密度大 D删除运算方便 7.下面关于线性表的叙述中，错误的是哪一个？（ B ） A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作 C线性表采用链接存储，不必占用一片连续的存储单元 D线性表采用链接存储，便于插入和删除操作。 8.若某线性表最常用到操作是存取任一指定序号的元素或在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 9.链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必疏锷估计存储空间 D所需空间与线性长度成正比 10.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ） A.(1)(2) B.(1) C.(1)(2)(3) D.(2) 11. 对于顺序存储的线性表，访问结点或增加、删除结点的时间复杂度为（C ）。 A. O(n) O(n)B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 12.单链表中，增加一个头结点的目的是为了( C ）。 A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现 D. 说明单链表是线性表的链式存储 13.对于双向循环链表在p指针所指的结点之后插入s指针所指结点的操作应为（ D ）。 A p-right=s ; s-left=p; p-right-left=s ; s-right=p-right; B p-right=s ; p-right-left=s ; s-left=p; s-right=p-right; C s-left=p; s-right=p-right; p-right=s ; p-right-left=s ; ; D s-left=p; s-right=p-right; p-right-left=s ; p-right=s ; 14.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ） Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL -第三章-第四章- 1.下面关于串的的叙述中，哪一个是不正确的？（B） A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储 2.串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？（A） A. 数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 3.串的长度是指（ B ） A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数 4.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ D ）。 A2n-1 B C( n*n/2)+(n/2) D( n*n/2)+(n/2)-1 E(n*n /2)-(n/2)-1 F.其他情况 这题的解答思路是：( n - 1 ) + (n - 1) + ( n - 2) + . + 1= ( n*n - n )/2 + ( n - 1)=( n*n/2)+(n/2)-1-第五章-1.数组是同类型值的集合。（F ） /数组中元素是有线性关系的，集合没有2.从逻辑结构上看，n维数组的每个元素均属于n个向量。（ T ） 3.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ F ） -第六章-1.n(n0)个结点的树的高度：最低是多少？最高是多少？ 最低是： 1或者2 最高是：n2.n(n0)个结点的二叉树的高度：最低是多少？最高是多少？ 最低是： 大于或等于log （n+1)的最小整数 最高是：n 3.有关二叉树下列说法正确的是（ B ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 4. 一棵124个叶结点的完全二叉树，最多有( E )个结点。 A.247 B.248 C.249 D.250E.251 解题思路：因为是完全二叉树 N0+N1+N2=N N0=124 N2=N0-1 N1只能等于1或者0 题目问最多所以N1=1 那就应该是124+123+1=248 5.已知一棵完全二叉树中共有626个结点， 叶子结点的个数应为( C )。 A. 311 /看课本P103页有公式B. 312 C. 313 D. 314 E. 其它 解题思路：设二叉树的边（分支）数为B，n为结点个数，n0, n1, n2分别是度为0、1、2的结点个数，那么 n=n0 + n1 + n2 ; B =n - 1 ; B= n1 + 2 *n2 n0=n2+1; 组合公式，可得 n - 1 = n1 + 2*n2 ; 因为完全二叉树度为1的结点只能是1个或者没有，而总结点数是626，n2必须是整数，所以求的n2=312 , 再又公式求答案。6.一个具有1025个结点的二叉树的高h为（ C ） A11 B10 C11至1025之间 D10至1024之间 7.一棵树高为K的完全二叉树至少有（ C ）个结点 A. 1 B. 1 C. 2 ( K- 1 ) D. 8.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_12_个叶子结点。 9.已知二叉树的先序序列ABDFCEHG中序序列DBFAHECG请构造该二叉树。 A / B C / / D F E G / H 10.已知二叉树的后序序列DMFBHELGCA 中序序列DBMFAHECGL请构造该二叉树。 A / B C / / D F E G / / M H L11.一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。 先序序列为：A B C D E F G H I J K A中序序列为：C B E D F A H J K I G / 后序序列为：C E F D B K J I H G A B G / / C D H / E F I / J K 12.试找出满足下列条件的二叉树 ( 先序：MLR ； 中序：LMR ；后序：LRM )1）先序序列与后序序列相同 只有一个根结点的二叉树。（ 即，先M(LR) = 后(L)M(R) ，括号内代表不要的部分 ）2）中序序列与后序序列相同 没有右子树的二叉树。（ 即，中LM(R) = 后L(R)M ）3）先序序列与中序序列相同 没有左子树的二叉树。（ 即，先M(L)R = 中(L)MR ）4）中序序列与层次遍历序列相同 没有左子树的二叉树13.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）。 ACABDEFG BABCDEFG CDACEFBG DADCFEGB -14.一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( C )。 A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶子结点 D. 其中度为2的结点最多为一个解题思路：先序：MLR ； 后序：LRM ，相反即是：前ML(R)，后L(R)M ；或者，前 M(L)R，后(L)RM. 15.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( B )的二叉树 A空或只有一个结点 B. 高度等于其结点数 C任一结点无左孩子 D. 任一结点无右孩子 16.二叉树在线索化后，仍不能有效求解的问题是（D ）。 A. 先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 17.引入二叉线索树的目的是（ A ） A加快查找结点的前驱或后继的速度B为了能曰筑叉树中方便的进行插入与删除 C为了能方便的找到双亲 D使二叉树的遍历结果唯一 18. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C ) A. X的双亲 B. X的右子树中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点 19.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( B )。 A. 0 B. 1 C. 2 D. 不确定 20.将树转换成二叉树 树转换成的二叉树其右子树一定为空 21.森林转为二叉树 22.已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK解：森林的前序序列和后序序列对应其转换的二叉树的前序序列和中序序列，应先据此构造二叉树，再构造出森林 解：构造森林的二叉树 ： A / B K / / C F L / D G M N / / E H O I J 转化为森林： A K / | / B E G L N / | / | / / C D E H I J M O 23.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是 （ D )。 AM1 BM1+M2 CM3 DM2+M3 24.设F是一个森林，B是由F变换得到二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ C ）个。 An-1 Bn Cn+1 Dn+2没有右子结点的数目= |双亲结点度=1| + |双亲结点度1| +1(根结点) 25.设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是( D )。 A. 在树T中，X是其双亲的第一个孩子 B. 在树T中，X一定无右边兄弟 C. 在树T中，X一定是叶子结点 D. 在树T中，X一定有左边兄弟 26. 设树形T在后根次序下的结点排列和各结点相应的次数如： 后根次序： 次 数： 请画出的树形结构图。 27.给定权值7，6，3，32，5，26，12，9，构造相应的哈夫曼树，并计算其带权路径长度。为使结果答案唯一，请用左结点的值小于等于右结点的值来构造哈夫曼树。 -第七章-1.图中有关路径的定义是（ A ）。 A由顶点和相粱芝点序偶构成的边所形成的序列 B由不同顶点所形成的序列 C由不同边所形成的序列 D上述定义都不是 2.设无向图的顶点个数为n，则该图最多有（ B ）条边。 An-1 Bn(n-1)/2 Cn(n+1)/2 D0 E 3.一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A0 B1 Cn-1 Dn 4.要连通具有n个顶点的有向图，至少需要（b）条边。 An-l Bn Cn+l D2n 5.G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。 6.用邻接表存储图所用到空间大小 A 。 A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的平方有关 7.图G是n个顶点的无向完全图，则下列说法正确的有：BCD A. G的邻接多重表需要n(n-1)个边结点和n个顶点结点； B. G的连通分量个数最少； C. G为连通图； D. G所有顶点的度的总和为n(n-1); 8.在有向图的邻接表存储结构中，顶点v在链表中出现的次数是( B )。 A. 顶点v的度 B. 顶点v的出度 C. 顶点v的入度 D. 依附踊芝点v的边数 8.图的遍历举例 (1)假定以邻接表存储，邻接点按编号升序排列。遍历序列如下： 深度优先搜索： V1-V2-V4-V8-V5-V6-v3-v7 广度优先搜索 V1-V2-V3-V4-v5-v6-v7-v8 (2)已知邻接矩阵求遍历序列 深度优先搜索： V1-V2-V3-V4-V5 宽度优先搜索： V1-V2-V3-V4-V5 (3)已知邻接表求遍历序列 深度优先遍历：V1-V2-V3-V6-V5-V4 宽度优先遍历：V1-V2-V5-V4-V3-V6 9.深度优先(广度优先)生成树 10.最小生成树 11.试画出从顶点v1开始利用Prim算法得督的最小生成树 12.利用Kruskal算法求最小生成树 13.用DAG图描述表达式(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 14.AOV-网的拓扑排序 15.写出有向图的所有拓扑排序，并指出应用教材中的算法求得到是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。 16.求最短路径 17.求最短路径Floyd算法 18.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ D ） a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A5个 B4个 C3个 D2个 19.下面哪一方法可以判断出一个有向图是否有环（回路）：（AB） A. 深度优先遍历 B. 拓扑排序C. 求最短路径 D. 求关键路径 20.在有向图G的拓扑序列中，若顶点Vi曰芝点Vj之前，则下列情形不可能出现的是（ D ）。 AG中有弧 BG中有一条从Vi到Vj的路径 CG中没有弧 DG中有一条从Vj到Vi的路径 21.关键路径是AOE网中( B ) A. 从始点到终点的最短路径 B. 从始点到终点的最长路径 C. 从始点到终点的边数最多的路径 D. 从始点到终点的边数最少的路径 22.下列关于AOE网的叙述中，不正确的是（ B ）。 A关键活动不按期完成就会影响整个工程的完成时间 B任何一个关键活动提前完成，那么整个工程将会提前完成 C所有的关键活动提前完成，那么整个工程将会提前完成 D某些关键活动若提前完成，那么整个工程将会提前完成 23.下列有关图的说法错误的是（ C ） A. 在有向图中，出度为0的结点4称为叶子。 B. 用邻接矩阵表示图，容易判断晌意两个结点之间是否有边相连，并求得各结点的度。 C. 按深度方向遍历图和先根次序遍历树类似，得督的结果是唯一的。 D. 若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点Vi必在结点Vj之前的话，则称为一个拓扑序列。 -第八章-1.地址为 大小为 的存储块的伙伴地址是什么？buddy(16647)=1664- =1536 2.地址为 大小为 的存储块的伙伴地址是什么？buddy(28166)=2816+ =2880 3.已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。 （1） 画出可利用空间表的初始状态。 （2） 画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得督的存储块的起始地址。 （3） 画出在回收3个占用块之后可利用空间表的状态。 第九章 1.画出含有12个元素的有序表的判定树 （1）求查找成功时的平均查找长度（2）求查找失败时的平均查找长度 2.若查找每个纪录的概率均等，则在具有n个纪录的连续顺序文件中采用顺序查找法查找一个纪录，其平均查找长度ASL为( C )。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 3.对线性表进行二分查找（就是折半查找）时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储且数据元素有序 C.以链接方式存储 D.以链接方式存储且数据元素有序 4.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ) A. 必定快 B. 不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 5.在有序表A120中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是_1，3，6，8，11，13，16，19_ 6.分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成_30_块最好：若分成25块，其平均查找长度为_31.5（块内顺序查找）_。 7.设关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下： 8.二叉排序树上删除10 或40或45或5