自考本科数据结构导论真题答案

第一题:C数据的逻辑结构分为：线性结构和非线性结构数据的存储结构分为：顺序存储结构和链式存储结构第二题：B第四题：C我个人可以利用二路归并的排序方法，利用特殊情况L1(low1,high1),L2(low2,high2),且low2>hign1。第七题：A若A是一个m*n的二维数组，数组下标从零开始，以列为主序存储，则address(A[i,j])=adderss(A[0,0])+(j*n+i)*L其中L为一个元素所占的存储空间则在此题目中address(A[5,5])=1000+(5*6+5)*5=1000+175=1175若以行为主序存储，则adderss(A[i,j])=adderss(A[0,0])+(i*m+j)*L在此题目中address(A[5,5])=1000+(5*6+5)*5=1000+175=1175即在此题目中以行为主序存储和以列为主序存储，最终结果相同。第九题：B完全二叉树是指除最后一层外，每一层上的结点数都达到最大值，在最后一层上指缺少右边的若干结点。根据定义可以先求出深度为H-1的满二叉树的结点个数为2^（H-1）-1,则继而可以得到深度为H的满二叉树的结点最少为2^(H-1)。第十题：D无向图的极大连通子图就叫做连通分量。问题关键在于n个结点的无向图有很多种，所以连通分量数不能确定。第十一题：D第十二题：D二叉排序树的定义为：左子树上的所有结点值均小于根节点的值，右子数上的值均不小于根结点的值。又因为中序遍历的循序是：先访问左结点，再访问根结点，最后访问右结点。根据以上两个原则可以得到.对一棵二叉排序树采用中根遍历进行输出的数据一定是递增序列。第二十二题：一棵具有n个结点的树，所有非终端结点的度均为k，则此二叉树为K叉树，这棵树只右度为K和度为0的结点，设度为K的结点数为a，度为0的结点数为b，则n=a+b。又设二叉树的所有分支为m,则m=k*a,同样可以得到n=m+1。综上可以得到b=[(n-1)*(k-1)/k-1]。以上是我自己对以上题目的解答，如果有什么不妥之处请与我联系继续探讨。