数据结构(第4版)习题及实验参考内容答案数据结构复习预习资料完整版(c语言版).doc

.数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像） 。它依赖于计算机。存储结构可分为 4 大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作） 。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机） 。4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。5、在数据结构中，从逻辑上可以把数据结构分成（ C ）A、动态结构和表态结构 B、紧凑结构和非紧凑结构C、线性结构和非线性结构 D、内部结构和外部结构6、算法的时间复杂度取决于（ A ）A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。2、表长为 n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ） ，删除一个元素需要移动的元素的个数为（ A ） 。A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/23、 “线性表的逻辑顺序与存储顺序总是一致的。 ”这个结论是（ B ）A、正确的 B、错误的 C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ）A、必须是连续的 B、部分地址必须是连续的 C 一定是不连续的 D 连续或不连续都可以5、带头结点的单链表为 空的判定条件是（ B ）A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL6、不带头结点的单链表 head 为空的判定条件是（ A ）A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL7、非空的循环单链表 head 的尾结点 P 满足（ C ）A、p->next=NULL B、p=NULL C、p->next=head D、p=head8、在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ）.A、O(1) B、O(n) C、O(n 2) D、O(nlog 2n)9、在一个单链表中，若删除 p 所指结点的后继结点，则执行（ A ）A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p->next=p->next;D、p= p->next->next;10、在一个单链表中，若在 p 所指结点之后插入 s 所指结点，则执行（ B ）A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11、在一个单链表中，已知 q 是 p 的前趋结点，若在 q 和 p 之间插入结点 s，则执行（ C ）A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12、在线性结构中，第一个结点 没有 前趋结点，其余每个结点有且只有 1 个前趋结点。栈和队列1、在栈操作中，输入序列为（A ，B，C，D） ，不可能得到的输出数列是（ D ）A、 （A，B，C，D） B、 （D，C ，B，A） C、 （A，C ，D，B ） D、 （C，A，D，B ）2、设栈 ST 用顺序存储结构表示，则栈 ST 为空的条件（ B ）A、ST.top=ST.basen D、ST.top=ST.base=n3、向一个栈顶指针为 HS 的链栈中插入一个 s 结点时，执行（ C ）A、HS->next=s; B、s->next=HS->next;HS->next=s;C、s->next=HS;HS=S; D、s->next=HS;HS=HS->next;4、从一个栈顶指针为 HS 的链栈中删除一个结点，用 x 保存被删结点的值，则执行（ C ）A、x=HS;HS=HS->next; B、HS=HS->next;x=HS->data;C、x=HS->data;HS=HS->next; D、s->next=HS;HS=HS->next;5、用单链表表示的链示队列的队头在链表的（ A ）位置。A、链头 B、链尾 C、链中6、判定一个链队列（最多元素个数为 n）为空的条件是（ A ）、.front=Q.rear B、Q.front!=Q.rearC、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n7、在链队列中，插入要所指结点需顺序执行的指令是（ B ）A、Q.front->next=s;f=s;B、Q.rear->next=s;Q.rear=s;C、s->next=Q.rear;Q.rear=s;D、s->next=Q.front;Q.front=s;.8、在一个链队列 Q 中，删除一个结点需要执行的指令是（ C ）A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;9、栈和队列的共同点（ C ）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10、栈的特点是_先进后出，队列的特点是先进先出11、线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。串和数组1、设串 s1=ABCDEFG，s2=PQRST，函数 Concat(x,y)返回 x 和 y 串的连接串，Substr(s,I,j)返回串 s 从序号 i 开始的 j 个字符组成的子串，length(s)返回串 s 的长度，则Concat(Substr(s1,2, length(s2), Substr(s1,length(s2),2)的结果串是（ D ）A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF2、串是一种特殊的线性表，其特殊性体现在（ D ）A、可以顺序存储 B、数据元素是一个字符C、可以链接存储 D、数据元素可以是多个字符3、设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作（ B ）A、连接 B、模式匹配 C、求子串联 D、求串长4、串的两种最基本的存储方式是顺序存储方式和链接存储方式。树和二叉树1、树最合适用来表示（ B ）A、有序数据元素 B、元素之间具有分支层次关系的数据C、无序数据元素 D、元素之间无联系的数据2、按照二叉树的定义，具有 3 个结点的二叉树有（ C ）种。A、3 B、4 C、5 D、63、在一棵有 n 个结点的二叉树中，若度为 2 的结点数为 n2，度为 1 的结点数为 n1，度为0 的结点数为 n0，则树的最大高度为（ E ） ，其叶结点数为（ G ） ；树的最小高度为（ B ） ，其叶结点数为（ G ） ；若采用链表存储结构，则有（ I ）个空链域。A、n/2 B、log 2n+1 C、log 2n D、n E、n 0 + n1 + n2 F、n 1 + n2 G、n 2 +1 H、1 I、n+1 J、n 1 K、n 2 L、n 1 +14、在一棵二叉树上第 5 层的结点数最多为（ B ） 。 （假设根结点的层数为 0）A、8 B、16 C、15 D、325、深度为 5 的二叉树至多有（ C ）个结点。A、16 B、32 C、31 D、106、在一非空二叉树的中序遍历序列中，根结点的右边（ A ）A、只有右子树上的所有结点 B、只有右子树上的部分结点.C、只有左子树上的部分结点 D、只有左子树上的所有结点7、一棵完全二叉树按层次遍历的序列为 ABCDEFGHI，则在先序遍历中结点 E 的直接前趋为（ D ） ，后序遍历中结点 B 的直接后继是（ E ） 。A、B B、 D C、A D、I E、F F、C8、已知某二叉树的后序遍历序列是 dabec,中序遍历序列是 debac,它的前序遍历序列是（ D ）A、acbed B、decab C、deabc D、cedba9、在树形结构中，树根结点没有_前趋_结点，其余每个结点有且只有_1_个前趋结点；叶子结点没有_后继_结点，其余每个结点的后继结点可以_任意多个_。10、有一棵树如图所示，回答下面的问题：K1K7K6K5K2 K3 K4这棵树的根结点是_K1_ ，这棵树的叶子结点是_K2 ，K5，K7，K4_；结点 k3 的度是_2_; 这棵树的度为_3_；这棵树的深度是_4_；结点 k3 的子女是_K5 ，K6_；结点 k3 的父结点是_K1_.11、已知一棵二叉树的中序遍历序列为 CDBAEGF，前序遍历序列为 ABCDEFG，试问能不能惟一确定一棵二叉树，若能请画出该二叉树。若给定前序遍历序列和后序遍历序列，能否惟一确定一棵二叉树，说明理由。答：由中序遍历序列和前序遍历序列或中序遍历序列和后序遍历序列可以惟一确定一棵二叉树。基本思想是前序（后序）定根，中序分左右。对于给定的前序和中序序列。可确定根结点为 A，以 A 为根的左子树结点为 B，C，D，右子树结点为 E，F，G。进一步可确定所有子树的根结点，因而也就确定了整个二叉树。对应的二叉树如图所示：FAD GFECB由前序遍历和后序遍历序列不能惟一确定一棵二叉树。如图所示为 4 棵不同的二叉树，它们的前序遍历序列都是 ABC，而后序遍历序列都是 CBA。.ACBCBA ACBACB12、设二叉树 bt 的存储结构如下：1 2 3 4 5 6 7 8 9 10left 0 0 2 3 7 5 8 0 10 1data j h f d b a c e g iright 0 0 0 9 4 0 0 0 0 0其中 bt 为树根结点指针，left，right 分别为结点的左右孩子指针域，data 为结点的数据域，请完成下列各题：画出二叉树 bt 的逻辑结构写出按前序、中序和后序遍历二叉树 bt 所得到的结点序列。答：二叉树 bt 的逻辑结构如图所示：12ajighfdecb前序遍历：abcedfhgij中序遍历：ecbhfdjiga后序遍历：echfjigdba13、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为 T，试写出求二叉树的叶子数目的算法。int CountLeaf (BiTree T)/返回指针 T 所指二叉树中所有叶子结点个数if (!T ) return 0;if (!T->lchild .elsem = CountLeaf( T->lchild); n = CountLeaf( T->rchild); return (m+n); /else / CountLeaf14、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为 T，试写出求二叉树的深度的算法。int Depth (BiTree T ) / 返回二叉树的深度if ( !T ) depthval = 0;else depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild );depthval = 1 + (depthLeft > depthRight ?depthLeft : depthRight); return depthval;图1、一个有 n 个顶点的无向图最多有（ C ）条边。A、n B、n(n-1) C、 n(n-1)/2 D、2n2、具有 6 个顶点的无向图至少应有（ A ）条边才能确保是一个连通图。A、5 B、6 C、7 D、83、存储稀疏图的数据结构常用的是（ C ）A、邻接矩阵 B、三元组 C、邻接表 D、十字链表4、在有向图的邻接表存储结构中，顶点 V 在表结点中出现的次数是（ C ）A、顶点 V 的度 B、顶点 V 的出度 C、顶点 V 的入度 D、依附于顶点 V的边数5、用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时，打印出相应的顶点，则输出的顶点序列是（ A ）A、逆拓扑有序的 B、拓扑有序的 C、无序的6、已知一个图如图所示，若从顶点 a 出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ D ） ，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ B ） 。A、abecdf B、acfebd C、acebfd D、acfdebA、abcedf B、abcefd C、abedfc D、acfdeb.Cacfdeb7、采用邻接表存储的图的广度优先搜索遍历算法类似于二叉树的（ D ）A、中序遍历 B、先序遍历 C、后序遍历 D、按层遍历8、已知一个图如图所示，则由该图得到的一种拓扑序列为（ A ）165432A、V1，V4，V6，V2，V5，V3 B、V1 ，V2，V3 ，V4 ，V5，V6C、V1，V4，V2，V3，V6，V5 D、V1 ，V2，V4 ，V6 ，V3，V59、在图形结构中，每个结点的前趋结点数和后续结点数可以_任意多个_。10、在 AOE 网中，从源点到汇点各活动时间总和最长的路径称为关键路径。11、给出图 G，如图所示：1111098765432.（1）给出图 G 的邻接表（画图即可）（2）在你给出的邻接表的情况下，以顶点 V4 为根，画出图 G 的深度优先生成树和广度优先生成树。（3）将你画出的广度优先生成树转换为对应的二叉树。答： （1）图的邻接表如下图所示：略（2）以顶点 V4 为根的深度优先生成树和广度优先生成树如图所示1111098765432d 1111098765432（3）广度优先生成树转换成二叉树如下图所示.11109117863452.附录 习题及实验参考答案习题 1 参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). C. (9). B. (10.) A.1.2.填空题(1). 数据 关系(2). 逻辑结构 物理结构(3). 线性数据结构 树型结构 图结构(4). 顺序存储 链式存储 索引存储 散列表（Hash）存储(5). 变量的取值范围 操作的类别(6). 数据元素间的逻辑关系 数据元素存储方式或者数据元素的物理关系(7). 关系 网状结构 树结构(8). 空间复杂度和时间复杂度(9). 空间 时间(10). (n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。1.4 语句的时间复杂度为：(1) (n 2) (2) (n 2)(3) (n 2)(4) (n-1)(5) (n 3)1.5 参考程序：main()int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y) if(X>=Z) if (Y>=Z)