上海交通大学：《数据结构考研试题》2000年试题答案

2000年试题答案: next:01112212321 nextval:01102201320 2. l/(1-αx)推导参见严蔚敏《数据结构》(C语言版)p261 Logm21(N+1)2+1 推导参见严蔚敏《数据结构》(C语言版)p.241 最好情况下的最坏情况下的平均情况下的额外空间的 时间复杂性 时间复杂性 时间复杂性 需求 快速排序 O (n log n) 堆排序 O(n log n) O (n log n) o(n log n) O(1) 直接插入排序 O(n2) O(m2) O(1) 简单选择排序 O(n2) n2) O(n2) 6. o (n log n) 证明参见严蔚敏《数据结构》(C语言版)p292 成功:(n+1)log(n+1)/n)-1 证明参见严蔚敏《数据结构》(C语言版)p.22l 不成功:[logn]+1

2000 年试题答案： 1． O (m+n) next: 0 1 1 1 2 2 1 2 3 2 1 nextval: 0 1 1 0 2 2 0 1 3 2 0 2． 1/(1-) 推导参见严蔚敏《数据结构》（C 语言版）p.261 3． A B C D E I F G H 4． Log [m/2] (N+1)/2 + 1 推导参见严蔚敏《数据结构》（C 语言版）p.241 5． 最好情况下的 时间复杂性 最坏情况下的 时间复杂性 平均情况下的 时间复杂性 额外空间的 需求 快速排序 O (n log n) O (n2 ) O (n log n) O ( log n) 堆排序 O (n log n) O (n log n) O (n log n) O (1) 直接插入排序 O (n) O (n2 ) O (n2 ) O (1) 简单选择排序 O (n2 ) O (n2 ) O (n2 ) O (1) 6． O (n log n) 证明参见严蔚敏《数据结构》（C 语言版）p.292 7． 成功：（（n+1）log2（n+1）/n ） -1 证明参见严蔚敏《数据结构》（C 语言版）p.221 不成功：[log2n]+1

o(n log2n) )平均情况下:2m 说明参见严蔚敏《数据结构》(C语言版)p304 2)最长:n 最短:1 BiThrNode* postorder succ(BiThr Tree r, BiThrNode*p) fif(p==r) return(NULL); else (q parent(p); if( p==q-rchild)return(@); if(p==q->lchild)&&(q->rtag==l))return(q) if(p==q->lchild)&&(q->rtag==0)) (q=q->rchild while(q->ltag==0ll q->rtag==0) while(q->ltag==0)q=q->lchild return(q) BiThrNode* parent( Bi*p) q-p while(q->ltag==0)q=q->lchild else i q=q->rchild while(q-lchild =pq=q->lchild return(q) 11 void DeleteBST(BiTree &T, Keytype x) f f->lchild=T; p=T; while(p) if(p->data f ->lchild=p->rchild g-p, p=p->rchild;

8 O (n log2n) 9. 1） 平均情况下：2m 说明参见严蔚敏《数据结构》（C 语言版）p.304 2） 最长：n 最短：1 10. BiThrNode * postorder_succ (BiThrTree r, BiThrNode *p) {if (p= = r) return (NULL); else {q= parent(p); if ( p= = q->rchild) return (q); if ((p= =q->lchild)&&(q->rtag= =1)) return (q); if ((p= =q->lchild)&&(q->rtag= =0)) {q=q->rchild; while (q->ltag= =0|| q->rtag= =0) { while(q->ltag= =0) q=q->lchild; if (q->rtag= =0) q=q->rchild; } return (q); } } } BiThrNode * parent ( BiThrNode *p) { q=p; while(q->ltag= =0) q=q->lchild; q=q->lchild; if (q->rchild= =p) return(q); else { q=q->rchild; while(q->lchild!=p) q=q->lchild; return(q); } } 11． void DeleteBST（BiTree &T， Keytype x） { f->lchild=T; p=T; while (!p) if (p->datalchild=p->rchild; q=p; p=p->rchild;

delete(q及q的左子树);∥要用非递归的遍历具体实现 else( f-p int sini(BiTree p, BiTree q) i if(p&&q) return(1) else if (p&&!q)l(p&&q)return( else return(sini(p->lchild, q->lchild)&& sini(p->rchild, q->rchild))

delete(q 及 q 的左子树) ； // 要用非递归的遍历具体实现 } else { f=p; p=p->lchild; } } 12． int sini (BiTree p, BiTree q) { if (p&&q) return (1); else if ((p&&!q)||(!p&&q)) return (0); else return (sini (p->lchild,q->lchild)&& sini (p->rchild,q->rchild)); }