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

数据结构(第4版）习题及实验参考答案数据结构复习资料完整版1数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head-next==NULLC、head-next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head-next==NULLC、head-next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p-next==NULLB、p==NULLC、p-next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案数据结构复习资料完整版29、在一个单链表中，若删除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.base0B、ST.top=ST.base==0C、ST.top=ST.basenD、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.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、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;数据结构(第4版）习题及实验参考答案数据结构复习资料完整版3C、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、BCDEFB、BCDEFGC、BCPQRSTD、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、3B、4C、5D、63、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（E），其叶结点数为（G）；树的最小高度为（B），其叶结点数为（G）；若采用链表存储结构，则有（I）个空链域。A、n/2B、[log2n]+1C、log2nD、nE、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1J、n1K、n2L、n1+14、在一棵二叉树上第5层的结点数最多为（B）。（假设根结点的层数为0）A、8B、16C、15D、325、深度为5的二叉树至多有（C）个结点。A、16B、32C、31D、106、在一非空二叉树的中序遍历序列中，根结点的右边（A）A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点7、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前趋为（D），后序遍历中结点B的直接后继是（E）。数据结构(第4版）习题及实验参考答案数据结构复习资料完整版4A、BB、DC、AD、IE、FF、C8、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（D）A、acbedB、decabC、deabcD、cedba9、在树形结构中，树根结点没有___前趋________结点，其余每个结点有且只有_______1______个前趋结点；叶子结点没有______后继___________结点，其余每个结点的后继结点可以__任意多个____。10、有一棵树如图所示，回答下面的问题：这棵树的根结点是____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。进一步可确定所有子树的根结点，因而也就确定了整个二叉树。对应的二叉树如图所示：⑵由前序遍历和后序遍历序列不能惟一确定一棵二叉树。如图所示为4棵不同的二叉树，它们的前序遍历序列都是ABC，而后序遍历序列都是CBA。K1K7K6K5K2K3K4ADGFECB数据结构(第4版）习题及实验参考答案数据结构复习资料完整版512、设二叉树bt的存储结构如下：12345678910left00237580101datajhfdbacegiright0009400000其中bt为树根结点指针，left，right分别为结点的左右孩子指针域，data为结点的数据域，请完成下列各题：⑴画出二叉树bt的逻辑结构⑵写出按前序、中序和后序遍历二叉树bt所得到的结点序列。答：⑴二叉树bt的逻辑结构如图所示：⑵前序遍历：abcedfhgij中序遍历：ecbhfdjiga后序遍历：echfjigdba13、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为T，试写出求二叉树的叶子数目的算法。intCountLeaf(BiTreeT){//返回指针T所指二叉树中所有叶子结点个数if(!T)return0;if(!T-lchild&&!T-rchild)return1;ACBCBAACBACBajighfdecb数据结构(第4版）习题及实验参考答案数据结构复习资料完整版6else{m=CountLeaf(T-lchild);n=CountLeaf(T-rchild);return(m+n);}//else}//CountLeaf14、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为T，试写出求二叉树的深度的算法。intDepth(BiTreeT){//返回二叉树的深度if(!T)depthval=0;else{depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);}returndepthval;}图1、一个有n个顶点的无向图最多有（C）条边。A、nB、n(n-1)C、n(n-1)/2D、2n2、具有6个顶点的无向图至少应有（A