严版数据结构前7章习题答案汇总

第一章绪论一.填空题1.从逻辑关系上讲，数据结构的类型主要分为集合、线性结构、树结构和图结构2.数据的存储结构主要有顺序存储和链式存储两种基本方法，不论哪种存储结构二.选择题三.简答题3.求多项式A(x)的算法可根据下列两个公式之一来设计：根据算法的时间复杂度分析比较这两种算法的优劣。第二章线性表1.在顺序表中，等概率情况下，插入和删除一个元素平均需移动表长的一半个元素，具体移动元素的个数与表长和插入的位置有关。2.在一个长度为n的顺序表的第i(1≤i≤n+1)个元素之前插入一个元素，需向后移动 n-i+1个元素，删除第i(1≤i≤n)个元素时，需向前移动n-i个元素。3.在单循环链表中，由rear指向表尾，在表尾插入一个结点s的操作顺序是s->next=rear->next;rear->next=s;rear=s;;删除开始结点的操作顺序为q=rear->next->next;1.数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的，称之为：CA存储结构B逻辑结构C顺序存储结构D链式存储结构2.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：AA访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2sisn)B在第i个结点后插入一个新结点(1≤isn)C删除第i个结点(1si≤n)D将n个结点从小到大排序3.线性表L在B情况下适用于使用链式结构实现。A需经常修改L中的结点值B需不断对L进行删除插入CL中含有大量的结点DL中结点结构复杂4.单链表的存储密度C1.线性表的逻辑顺序和存储顺序总是一致的。F2.线性表的顺序存储结构优于链接存储结构。F4.线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。F1.分析下列情况下，采用何种存储结构更好些。(1)若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。(2)如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。(3)描述一个城市的设计和规划。1.已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。数组奇偶调整算法Adjust{while(A[j]%2=0)j--}2.线性表存放在整型数组A[arrsize]的前elenum个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复i--;}}课后作业部分第三章栈和队列课后作业部分第三章栈和队列一.填空题1.设有一个空栈，栈顶指针为1000H,现有输入序列为1.2.3.4.5,经过push,push,pop,push,pop,push,push后，输出序列是23,栈顶指针为1003H。2.栈通常采用的两种存储结构是顺序栈、链栈；其判定栈空的条件分别是3.栈可作为实现递归函数调用的一种数据结构。4.表达式a*(b+c)-d的后缀表达式是abc+*d-。1.若一个栈的输入序列是1,2,3,…,n,输出序列的第一个元素是n,则第i个输2.设栈S和队列Q的初始状态为空，元素e1.e2.e3.e4.e5.e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e2.e4.e3.e6.e5.e1,则栈S的容量至少应该是C。3.一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是C。1.设有一个栈，元素进栈的次序为A,B,C,D,E,课后作业部分第三章栈和队列课后作业部分栈顶元素为6,栈底元素为1。队头元素为5,队尾元素为9。4.简述以下算法的功能(栈的元素类型SElemType为int)。}}{}{}五.算法设计{'}}}第四章串一.填空题1.不包含任何字符(长度为0)的串称为空串；由一个或多个空格(仅由空格符)组成的串称为空白串。3.若n为主串长，m为子串长，则串的经典模式匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。二.选择题A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符A连接B模式匹配C求子串D求串长3.设串s1='ABCDEFG',s2='PQRST’,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：(D)4.若串S="software",其子串的数目是(B)。三.计算题m),删除串S中从位置i开始的连续的m个字符。若i≥strlen(S),则没有字符被删除；若i+m2strlen(S),则将S中从位置i开始直至末尾的字符均被删去。{}{}}第五章数组和广义表一.填空1.假设有二维数组A₆×8,每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为1000,则数组A的体积(存储量)为288;末尾元素Asz的第一个字节地址为1282;若按行存储时，元素A14的第一个字节地址为1072;若按列存储时，元素A47的第一个字节地址为12762.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，1.假设有60行70列的二维数组a[1..60,1..70]以列序为主序顺序存储，其基地址为10000,每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为(A)。(无第0行第0列元素)2.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组1.设有一个二维数组A[m][n],假设A[0][0]存放位置在644,A[2][2]存放位置在676,每个元素占一个空间，问A[3][3]存放在什么位置?写出计算过程。A[2][2]的地址相对A[0][0]偏移量为32,则A[3][3]相较于A[0][0]的偏移量为A[3][3]地址为48+644=6922.设A[9][9]是一个10*10对称矩阵，采用压缩存储方式存储其下三角部分，已知每个元素占用两个存储单元，其第一个元素A[0][0]的存储位置在1000,求下面问题的计算课后作业部分课后作业部分01230123若以行序为主序，则地址为1000+2(5(1+5)/2+4)=1036若以列序为主序，则地址为1000+2(4(10+7)/2+5)=1062给出存储位置为1080的元素下标。3.一个稀疏矩阵如图所示，则对应的三元组线性表是什么?其对应的十字链表是什13221333-13454.下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。课后作业部分第五章数组和广义表课后作业部分四.算法设计课后作业部分第五章数组和广义表课后作业部分分析算法，外层for循环共执行m次，内层第一个for循环执行n次，第二个for循环最坏情况下执行m次，所以，最坏情况下的时间复杂度为0(mn+mm)。课后作业部分第五章数组和广义表课后作业部分第六章树和二叉树1.树是n(n≥0)结点的有限集合。在一棵空树中有0个元素；在一棵非空树中，有且仅有一个个根结点，其余的结点分成m(m>0)个互不相交的集合，每个集合都是根结点的子树。2.一棵二叉树的第i(i≥1)层最多有2i-1个结点；一棵有n(n>0)个结点的满二叉树3.设深度为k的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是2k-1,最小值是2k-1。4.深度为k的二叉树中，所含叶子的个数最多为2k-1.5.在顺序存储的二叉树中编号为i和j的两个结点处在同一层的条件为：[1og₂i]=[10g₂]1.前序遍历和中序遍历结果相同的二叉树是(D)。A根结点无左孩子的二叉树B根结点无右孩子的二叉树C所有结点只有左子树的二叉树D所有结点只有右子树的二叉树2.序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]～A[n]中，结点A[j]若有左子树，则左子树的根结点是(D)。3.完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h,则其左分支下的子孙的最大层次为(C)。A左线索标志为0,右线索标志为1B左线索标志为1,右线索标志为0C左.