数据结构-东南大学.doc

数据结构是一门研究非数值计算的程序设计问题中的（A）以及它们之间的（B）和运算的学科。A操作对象 B计算方法 C逻辑存储 D数据映象A结构 B关系 C运算 D算法 试举例说明，如果两个数据结构的逻辑结构和存储结构相同，但基本运算（操作）不同，则这两个数据结构就是不同的。例如二叉树和二叉排序树在逻辑结构上都是二叉树，都采用二叉链表形式存储，但是对于某些运算的定义不同，例如插入操作，二叉树需指明作为哪个结点的左孩子还是右孩子插入，而二叉排序树无需指明，由二叉排序树的形状决定插入位置算法有哪些特点？为什么说一个具备了所有特点的算法，不一定就是实用的算法？ 答：特点：输入、输出、确定性、有穷性、有效性；一般地说，只有多项式时间度杂度的算法才是实用的。如何评价算法的好坏？答：正确性（四个层面）；可读性；健壮性；时空效率（复杂性）。程序段 for (i=n-1; i=1; i+) for (j=1; jAj+1) Aj与Aj+1对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（D ）A. O(n) B. O(nlog2n) C. O(n3) D. O(n2)分析以递归方式求阶乘的算法的时间复杂度。long Factorial ( long n ) if ( n = = 1 ) return 1; / 递归终止 else return n*Factorial ( n-1); / 递归 分析二分查找函数的时间复杂度。int BinarySearch(int *a, const int x, const int n) for(int left = 0, right = n 1; left : left = middle + 1; break; / x amiddlecase : right = middle 1; break; / x amiddlecase =: found x; / x = amiddle return 1; / not found 实例特性是数组a中元素的个数n。循环部分的每次迭代花费的时间为O(1)。假定循环一共执行k次迭代，在第i次迭代中需搜索的元素为 n/2i-1。所以，每次迭代搜索的元素个数的序列为：这样，循环迭代的次数一共是：log2n+1.设任意n个整数存放于数组An中，试编写程序，将所有负数排在所有正数前面（要求不附加额外的存储空间，且算法算法时间复杂度为O(n)）。int Rearrange（SeqList a; int n） i=0; j=n-1; / i,j初始指向线性表a的第1个和第n个元素。 t=a0; /暂存枢轴元素。 while(ij) while(i0) j-; /从右向左找负数。 if (ij) ai+=aj; /将负数前移。 while(ij & ai0) i+; /从左向右找正数。 if (ij) aj-=ai; /将正数后移。 ai=t; 将原第一元素放到最终位置。请设计算法，将一个向量(a1,a2,am)的内容原地逆置，成为(am,am-1,a1) 。Reverse(int X, int i, int j) while ( idata=x) printf(“%d”,t-data), return 1; else if (path(t-lchild, x) | path(t-rchild, x) printf(“%d”,t-data), return 1; else return 0;非递归算法按非递归后序遍历方式进行遍历，设一外部栈S，遍历完成后，栈中的内容即为路径。栈元素的格式定义为：struct stkNode BinTreeNode *ptr; enum tag L, R;int path( BtreeNode *p, BtreeNode *x, stack *S) stkNode *w; do while (p!=NULL) w.ptr = p; w.tag = L; S.push(w); p=p-leftChild; int continue = 1; while (continue & !S.IsEmpty ( ) S.Pop(w); p = w.ptr; switch (w.tag) case L: w.tag = R; S.push(w); continue = 0; p=p-rightChild; break; case R: if (p = x) 输出S的内容; while ( !S.IsEmpty( ) ); return 0;输出栈的内容即可得到路径：while (!S.IsEmpty( ) S.Pop(p); 输出p-ptr；试编写算法判定两棵树是否互为镜像。 int IsMirror(BtreeNode *r1, BbtreeNode *r2) if (r1=NULL&r2=NULL) return1; if (r1-data = r2-data) return (IsMirror( r1-lchild, r2-rchild)& IsMirror( r1-rchild, r2-lchild); else return 0;二叉搜索树的结点删除有几种情况，分别如何处理？请写出以下图的邻接矩阵。图中给出了7个顶点组成的无向图，从顶点1出发，对它进行深度优先遍历得到的的顶点序列是（1），而进行广度优先遍历得到的顶点序列是（2）。 （1）1534276 （2）1354276试给出是图的生成树和最小生成树的定义，且说明最小生成树是否是唯一的。 1、图的生成树是图的极小连通子图；2、图的权值最小的生成树是图的最小生成树；3、一般情况下图的最小生成树是不唯一的，当一个图的边上的权值均不相同时，图的最小生成树是唯一的。 分别用Prim算法和Kruskal算法求下图所示的无向图的最小生成树，并说明求解过程。用Prim算法求最小生成树。选择边的次序是：(0,5)、(5,4)、(4,3)、(3,2)、(2,1)、(1,6)用Kruskal算法求最小生成树。选择边的次序是： (0,5)、(3,2)、(1,6)、(2,1)、 (4,3)、(5,4)求如图所示的有向图中从v1到其他各顶点的最短路径。v1到v2的最短路径为v1v2，长度为2；v1到v3的最短路径为v1v2v3，长度为4；v1到v4的最短路径为v1v4，长度为3；v1到v5的最短路径为v1v2v3v5 ，长度为7；v1到v6的最短路径为v1v2v6 ，长度为9；v1到v7的最短路径为v1v2v3v5v7，长度为14；什么是排序算法的稳定性？如何判断一个排序算法是否是稳定的？1、若在排序过程中关键字相同的对象在排序前后的先后次序不发生变化，则排序算法是稳定的，否则是不稳定的。2、排序过程中是否发生了不相邻元素的交换。快速排序的过程是怎样的？试分析快速排序的效率。1、快速排序的过程是：任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准，按照该对象的关键码大小，将整个对象序列划分为左右两个子序列，然后对子序列递归地继续快速排序，直到划分的序列中只有一个对象为止。2、快速排序算法在初始序列基本有序时效率最低，可以表示为O(n2)，在初始序列无序（每次划分得到两个长度基本相同的子序列）时效率最高，可以表示为O(nlog2n)。 试分析归并排序的效率。1、在对两个长度均为n的有序子序列进行归并时，最少需要比较n次，最多需要比较2n-1次。2、归并排序算法的效率为O(nlog2n)，不受序列初始状态的影响。多关键字排序和基数排序之间是什么关系？多关键字排序有那些方法，需要注意那些问题？1、基数排序是多关键字排序的一种特例：将关键字拆分为若干个位，每一位作为一个关键字，且取值范围相同。2、常用的多关键字排序方法有：MSD和LSD。3、与人的直觉相反，应首先从最不重要的因素排序，然后是次不重要的，最后对最重要的因素排序，且必须采用稳定的排序方法（如直接插入排序或起泡排