《Copy of 数据结构-东南大学》由会员分享，可在线阅读，更多相关《Copy of 数据结构-东南大学（2页珍藏版）》请在金锄头文库上搜索。
1、设任意 n 个整数存放于数组 An中，试编写程序，将所有负数排在所有正数前面（要求不附加额外的存储空间，且算法算法时间复杂度为 O(n)） 。int Rearrange（SeqList a; int n）i=0; j=n-1; / i,j 初始指向线性表 a 的第 1 个和第 n 个元素。t=a0; /暂存枢轴元素。while(i0) j-; /从右向左找负数。if (idata=x)printf(“%d”,t-data), return 1;else if (path(t-lchild, x) |path(t-rchild, x)printf(“%d”,t-data), return 1;e
2、lse 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
3、 = 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=NULLif (r1-data = r2-data) return (IsMirror( r1-lchild, r2-rchild)&IsMirror( r1-rchild, r2-lchild);else return 0;散列表存储的基本思想是什么？构造散列表需要解决那些问题？如何解决？1、散列表存储的基本思想是通过数据元素关键字的 Hash 函数值决定数据元素的存储地址。2、设计合适的散列函数和解决冲突。3、常用的散列函数有：直接定址法、数字分析法、除留余数法、平方取中法、折叠法等；散列表存储中解决冲突的基本方法有：线性探查，二次探查，再散列法，链地址法等。
