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

《数据结构期末复习总结超详细.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构复习要点带答案算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。算法指的是（）。A对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改进），算法分析的两个主要方面是（空间性能和时间性能）。1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n

2、)）。【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。【分析】数据结构指的是数据元素以及数据元素之间的关系。3.设有数据结构（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)}。试画出其逻辑结

3、构图并指出属于何种结构。【解答】其逻辑结构图如图1-3所示，它是一种图结构。4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。【分析】递归函数的调用和返回正好符合后进先出性。栈的特点是先进后出，即：进去的早，出来的晚！54321进栈，5在栈底，1在栈顶！出一次栈，则栈顶的1先出来，2成为新的栈顶。ABCD入栈，D成为新的栈顶。全部出栈：DCBA2345综上，所有元素退栈顺序为：1

4、DCBA23455.入栈：templateVoidSeqStack::Push(Tx){if(top==StackSize-1)throw“上溢”;top++;data[top]=x;}6.出栈的指针的操作：templateTSeqStack::Pop(){if(top==-1)throw“下溢”;x=data[top--];returnx;}顺序栈基本操作时间复杂度为O（1）.设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环

5、队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。【解答】操作步骤为：①将所有元素出栈并入队；②依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；③将奇数结点出栈并入队；④将偶数结点出队并入栈；⑤将所有元素出栈并入队；⑥将所有元素出队并入栈即为所求。1.循环队列队空队满的判断条件：①在添加元素前，队列头指针等于队列尾指针，则队列为空；②在添加元素前，队列头指针！

6、=队列尾指针，但是当想要添加时，将队列尾指针加1试试，与队列头指针相等了，则队列满。此处是指，（队列尾指针+1==队列头指针）这样的判断出队：入队指针的操作：若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（n-i+1）2.对称矩阵地址的计算：设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐行存于数组B[3n-2]中，使得B[k]=aij求：⑴用i,j表示k的下标变换公式；⑵用k表示i,j的下标变换公式。【解答】⑴要求i,j表示k的下标变换公式，

7、就是要求在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）2设n行n列的下三角矩阵A（行列下标均从1开始）已压缩到一维数组S[1]~S[

8、n(n+1)/2]中，若按行优先存储，则A[i][j]在数组S中的存储位置是（i×(i-1)/2+j）。一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示对应的三元组顺序表如图4-5所示，十字链表如图4-6所示已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中，编写算法计算对称矩阵的乘积。【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法1.二叉链表：一棵二叉树的第i（i≥