数据结构期末复习总结超详细1.doc

数据结构复习要点带答案 算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）算法指的是（ ）。A 对特定问题求解步骤的一种描述，是指令的有限序列算法分析的目的是（分析算法的效率以求改进），算法分析的两个主要方面是（空间性能和时间性能）。设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。【分析】数据结构指的是数据元素以及数据元素之间的关系。设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1-3所示，它是一种图结构。（栈）可作为实现递归函数调用的一种数据结构。【分析】递归函数的调用和返回正好符合后进先出性。栈的特点是先进后出，即：进去的早，出来的晚！ 54321进栈，5在栈底，1在栈顶！ 出一次栈，则栈顶的1先出来，2成为新的栈顶。 ABCD入栈，D成为新的栈顶。 全部出栈：D C B A 2 3 4 5 综上，所有元素退栈顺序为：1 D C B A 2 3 4 5Void SeqStack::Push(T x) { if ( top==StackSize-1) throw “上溢”; top++; data[top]=x; } 出栈的指针的操作：templateclass T T SeqStack::Pop() { if ( top== -1) throw “下溢”; x=data[top--]; return x; }顺序栈基本操作时间复杂度为O（1）. 设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。【解答】操作步骤为： 将所有元素出栈并入队； 依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈； 将奇数结点出栈并入队； 将偶数结点出队并入栈； 将所有元素出栈并入队； 将所有元素出队并入栈即为所求。在添加元素前，队列头指针等于队列尾指针，则队列为空在添加元素前，队列头指针 ！= 队列尾指针，但是当想要添加时，将队列尾指针加1试试，与队列头指针相等了，则队列满。此处是指，（队列尾指针 + 1 == 队列头指针）这样的判断 入队指针的操作： 若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（n-i+1 ）设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐行存于数组B[3n-2]中，使得B[k]=aij求： 用i, j表示k的下标变换公式； 用k表示i, j的下标变换公式。【解答】 要求i, j表示k的下标变换公式，就是要求在k之前已经存储了多少个非零元素，这些非零元素的个数就是k的值。元素aij求所在的行为i，列为j，则在其前面的非零元素的个数是；k=2 + 3(i－1)+( j－i + 1)= 2i+ j。 因为k和i, j之间是一一对应的关系，k+1是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即 1一个n×n的对称矩阵，按行优先或列优先进行压缩存储，则其存储容量为（　　n(n+1)/2 ）设n行n列的下三角矩阵A（行列下标均从1开始）已压缩到一维数组S[1]~S[n(n+1)/2]中，若按行优先存储，则A[i][j]在数组S中的存储位置是（i×(i-1)/2+j ）。一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示 对应的三元组顺序表如图4-5所示，十字链表如图4-6所示 已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中，编写算法计算对称矩阵的乘积。【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法 二叉链表：一棵二叉树的第i（i≥1）层最多有（2i-1 ）个结点；一棵有n（n