试给出下列有关并查集( mfsets)的操作序列的运算结果 union (1, 2), union (3, 4), union(3, 5), union(1, 7), union(3, 6), union(8, 9),union(1, 8), union(3, 10), union(3, 11), union(3, 12). union(3, 13), union(14, 15), union (16, 0), union (14, 16), union (1, 3). union(1,14)。( union是合并运算,在以前的书中命名为 merge 要求 (1)对于unon(),以i作为j的双亲 (5分) (2)按i和j为根的树的高度实现 union(,,高度大者为高度小者的双亲 (5分) (3)按i和j为根的树的结点个数实现 union(,,结点个数大者为结点个数小者的双亲 (5分) 、设在4地(A,B,C,0D)之间架设有6座桥,如图所示: ⑥ 要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件什么? (5分) (2)设图中的顶点数为n,试用C或 Pascal描述与求解此问题有关的数据结构并编写一 个算法,找出满足要求的一条回路。 (10分) 三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数): 1)输入的n个数据全部有序 (5分) (2)输入的n个数据全部逆向有序 (5分) (3)随机地输入n个数据 (5分) 四、简单回答有关AVL树的问题。 (1)在有N个结点的AMⅥL树中,为结点增加一个存放结点高度的数据成员,那么每一个 结点需要增加多少个字位b? (5分) (2)若每一个结点中的高度计数器有8bts,那么这样的AⅥL树可以有多少层?最少有多 少个关键码? (5分)
1 一、试给出下列有关并查集(mfsets)的操作序列的运算结果： union(1, 2), union(3, 4), union(3, 5),union(1, 7), union(3, 6), union(8, 9), union(1, 8), union(3, 10), union(3, 11), union(3, 12), union(3, 13), union(14, 15), union(16, 0), union(14, 16), union(1, 3), union(1, 14)。（union 是合并运算，在以前的书中命名为 merge） 要求 (1) 对于 union(i, j)，以 i 作为 j 的双亲； （5 分） (2) 按 i 和 j 为根的树的高度实现 union(i, j)，高度大者为高度小者的双亲； （5 分） (3) 按 i 和 j 为根的树的结点个数实现 union(i, j)，结点个数大者为结点个数小者的双亲。 （5 分） 二、设在 4 地(A, B, C, 0D)之间架设有 6 座桥，如图所示： 要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1) 试就以上图形说明：此问题有解的条件什么？ （5 分） (2) 设图中的顶点数为 n，试用 C 或 Pascal 描述与求解此问题有关的数据结构并编写一 个算法，找出满足要求的一条回路。 （10 分） 三、针对以下情况确定非递归的归并排序的运行时间（数据比较次数与移动次数）： (1) 输入的 n 个数据全部有序； （5 分） (2) 输入的 n 个数据全部逆向有序； （5 分） (3) 随机地输入 n 个数据。 （5 分） 四、简单回答有关 AVL 树的问题。 (1) 在有 N 个结点的 AVL 树中，为结点增加一个存放结点高度的数据成员，那么每一个 结点需要增加多少个字位(bit)？ （5 分） (2) 若每一个结点中的高度计数器有 8bits，那么这样的 AVL 树可以有多少层？最少有多 少个关键码？ （5 分） A B C D ① ② ③ ④ ⑤ ⑥
五、设一个散列表包含 hash Size=13个表项,其下标从0到12,采用线性探查法解决冲突 请按以下要求,将下列关键码散列到表中。 101003245581263292004000 (1)散列函数采用除留余数法,用% hash size(取模运算)将各关键码映像到表中。请指 出每一个产生冲突的关键码可能产生多少次冲突。 (7分) (2)散列函数采用先将关键码各位数字折叠相加,再用% hash size将相加的结果映像到 表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。 (8分) 六、设一棵二叉树的结点定义为 struct BinTreeNode t Elem Type data: BinTreeNode *leftChild, *right child 现采用输入广义表表示建立二叉树。具体规定如下 (1)树的根结点作为由子树构成的表的表名放在表的最前面 (2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树,逗号不能省略 (3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结束 例如,对于如右图所示的二叉树,其广 义表表示为AB(D,E(G,)),C(,F) 此算法的基本思路是:依次从保存广义 表的字符串ls中输入每个字符。若遇到的是 字母(假定以字母作为结点的值),则表示是 结点的值,应为它建立一个新的结点,并把 该结点作为作为左子女(当k=0)或右子女(当k=1)链接到其双亲结点上。若遇到的是左括号"( 则表明子表的开始将k置为0;若遇到的是右括号)”,则表明子表结束。若遇到的是逗号”,”, 则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树,将k置为1。 在算法中使用了—个栈s,在进入子表之前,将根结点指针进栈,以便括号内的子女链接 之用。在子表处理结束时退栈。相关的栈操作如下 Make Empty(s) 置空栈 Push(s, p) 元素p进栈 Pop(s) 退栈 Top(s 存取栈顶元素的函数
2 五、设一个散列表包含 hashSize = 13 个表项，其下标从 0 到 12，采用线性探查法解决冲突。 请按以下要求，将下列关键码散列到表中。 10 100 32 45 58 126 3 29 200 400 0 (1) 散列函数采用除留余数法，用%hashSize（取模运算）将各关键码映像到表中。请指 出每一个产生冲突的关键码可能产生多少次冲突。 （7 分） (2) 散列函数采用先将关键码各位数字折叠相加，再用 %hashSize 将相加的结果映像到 表中的办法。请指出每一个产生冲突的关键码可能产生多少次冲突。 （8 分） 六、设一棵二叉树的结点定义为 struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; } 现采用输入广义表表示建立二叉树。具体规定如下： (1) 树的根结点作为由子树构成的表的表名放在表的最前面； (2) 每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。 (3) 在整个广义表表示输入的结尾加上一个特殊的符号（例如“#”）表示输入结束。 例如，对于如右图所示的二叉树，其广 义表表示为 A(B(D, E(G, ) ), C( , F) )。 此算法的基本思路是：依次从保存广义 表的字符串 ls 中输入每个字符。若遇到的是 字母 (假定以字母作为结点的值)，则表示是 结点的值，应为它建立一个新的结点，并把 该结点作为作为左子女(当 k=0)或右子女(当 k=1)链接到其双亲结点上。若遇到的是左括号”(”， 则表明子表的开始，将 k 置为 0；若遇到的是右括号”)”，则表明子表结束。若遇到的是逗号”,”， 则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将 k 置为 1。 在算法中使用了一个栈 s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接 之用。在子表处理结束时退栈。相关的栈操作如下： MakeEmpty(s) 置空栈 Push(s, p) 元素 p 进栈 Pop(s) 退栈 Top(s) 存取栈顶元素的函数 A B C D E F G
下面给出了建立二叉树的算法,其中有5个语句缺失。请阅读此算法并把缺失的语句补 (每空3分) void Create BinTree(BinTreeNode * bt, char ist Stack>ch; /从ins顺序读入一个字符 while(ch!=`#){/逐个字符处理,直到遇到‘#′为止 switch(ch)& case'(":[① break: case ) pop(s); break; case. break default: p= new Bin TreeNode; p->leftChild NULL; p->rightchild nULL if Bt== NULL) else if (k==1) top(s)->leftchild p; else top(s)->rightchild p ⑤
3 下面给出了建立二叉树的算法，其中有 5 个语句缺失。请阅读此算法并把缺失的语句补 上。 （每空 3 分） void CreateBinTree(BinTreeNode *& BT, char ls) { Stack s; MakeEmpty(s) ; BT = NULL; //置空二叉树 BinTreeNode *p; int k; instream ins(ls); //把串 ls 定义为输入字符串流对象 ins char ch; ins >> ch; //从 ins 顺序读入一个字符 while (ch != ‘#’) { //逐个字符处理，直到遇到‘#’为止 switch (ch) { case ‘(’ : push(s, p); k=1; break; case ‘)’ : pop(s); break; case ‘,’ : k=2; break; default : p = new BinTreeNode; p->data = ch; p->leftChild = NULL; p->rightChild = NULL; if ( BT == NULL ) Bt = p; else if (k==1) top(s)->leftChild = p; else top(s)->rightChild = p; } ins >> ch; } } ① ② ③ ④ ⑤
七、下面是一个用C编写的快速排序算法。为了避免最坏情况,取基准记录 pivot采用从lef, nght和md=「(|et+mght)/21中取中间值,并交换到mght位置的办法。数组a存放待排 序的一组记录,数据类型为Type,left和mght是待排序子区间的最左端点和最右端点。 void quicksort(Type a[ ], int left int right)t Type temp; f left right& Type pivot= median3(a,left, right);//三者取中子程序 It i left, j= right -1; (;;){ while(i pivot i temp=a[; a[j=a[right]: a[right]= temp; 1 quicksort(a, left, i-1) /递归排序左子区间 quicksort(a, i+l, right); /递归排序右子区间 } (1)用C或 Pascal实现三者取中子程序 median3(a,eft, right); (5分) (2)改写 quicksort算法,不用栈消去第二个递归调用 quicksort(a, i+l, right); (5分) (3)继续改写 quicksort算法,用栈消去剩下的递归调用。(5分)
4 七、下面是一个用 C 编写的快速排序算法。为了避免最坏情况，取基准记录 pivot 采用从 left, right 和 mid = ( left + right ) / 2 中取中间值，并交换到 right 位置的办法。数组 a 存放待排 序的一组记录，数据类型为 Type，left 和 right 是待排序子区间的最左端点和最右端点。 void quicksort (Type a[ ], int left, int right) { Type temp; if (left pivot ) { temp = a[i]; a[i] = a[right]; a[right] = temp; } quicksort (a, left, i-1); //递归排序左子区间 quicksort (a, i+1, right); //递归排序右子区间 } } (1) 用 C 或 Pascal 实现三者取中子程序 median3(a, left, right); （5 分） (2) 改写 quicksort 算法，不用栈消去第二个递归调用 quicksort (a, i+1, right); （5 分） (3) 继续改写 quicksort 算法，用栈消去剩下的递归调用。 （5 分）
、解答 (1)对于 union(j,以i作为j的双亲 (5分) ④③(⑩⑩@⑥① (2)按i和j为根的树的高度实现 union(.j,高度大者为高度小者的双亲 (5分) ③③⑨⑩@@③① (3)按i和j为根的树的结点个数实现 union(j,结点个数大者为结点个数小者的双亲 (5分) ⑦( 、解答:将下图改为无向图,城市为结点,桥为边: B ① ④ (1)此为欧拉问题。有解的充要条件是每一个结点的度为偶数。(5分) (2)数据结构采用邻接表,每个边结点有3个域,分别记录相关边号、邻接顶点号和链指针 edge AdiNo link 另外,设置一个边的访问标志数组 visited[],当 visited[]==0表示第i条边未访问过,一旦访问了
5 一、解答 (1) 对于 union(i, j)，以 i 作为 j 的双亲 （5 分） (2) 按 i 和 j 为根的树的高度实现 union(i, j)，高度大者为高度小者的双亲； （5 分） (3) 按 i 和 j 为根的树的结点个数实现 union(i, j)，结点个数大者为结点个数小者的双亲。 （5 分） 二、解答：将下图改为无向图，城市为结点，桥为边： (1) 此为欧拉问题。有解的充要条件是每一个结点的度为偶数。 （5 分） (2) 数据结构采用邻接表，每个边结点有 3 个域，分别记录相关边号、邻接顶点号和链指针。 另外，设置一个边的访问标志数组 visited[ ]，当 visited[i] == 0 表示第 i 条边未访问过，一旦访问了 1 2 7 8 9 4 5 6 10 11 12 13 3 14 15 16 0 3 15 16 0 1 2 7 8 9 4 5 6 10 11 12 13 14 4 5 6 10 11 12 13 3 1 2 7 8 9 15 16 0 14 A B C D ① ② ③ ④ ⑤ ⑥ A B C D ① ③ ② ④ ⑤ ⑥ EdgeNo AdjNo link
第i条边,即将 visited[改为1 2|22画2 22 o國2回2回2 回22 nodelist ①②③④⑤⑥ vst□ struct edgenode i ∥顶点结点 int edge ∥相关边号 int adjvertex; 邻接顶点号 ∥链接指针 struct vertex i 顶点 ∥顶点数据 edgenode* first: ∥出边表指针 Typedef vertex nodelist ∥接表数组 下面给出按深度优先搜索方法求解欧拉问题的递归算法。(5分) void dfs( nodelist euler, int start, int n, int visited[)i coutedgeno ∥边号 f( visited[==0)( ∥走过 d]=1; ∥作边访问标记 ds( euler,p-> adjvertex,n, visited);∥按邻接顶点递归下去 p= p->link: ∥查下一条关联的边 主程序 (5分) int count, n, i,j,k; coutn; nodelist euler= new vertex] ∥)创建邻接表数组
6 第 i 条边，即将 visited[i]改为 1。 struct edgenode { //顶点结点 int edgeno; //相关边号 int adjvertex; //邻接顶点号 edgenode * link; //链接指针 }; struct vertex { //顶点 int city; //顶点数据 edgenode * first; //出边表指针 }; Typedef vertex * nodelist; //邻接表数组 下面给出按深度优先搜索方法求解欧拉问题的递归算法。 （5 分） void dfs ( nodelist euler, int start, int n, int visited[ ] ) { cout ’; //输出顶点数据 edgenode * p = euler[start].first; //找第一条关联的边 while ( p != NULL ) { //有 int j = p->edgeno; //边号 if ( visited[j] == 0 ) { //未走过 visited[j] = 1; //作边访问标记 dfs ( euler, p->adjvertex, n, visited ); //按邻接顶点递归下去 } p = p->link; //查下一条关联的边 } } 主程序 （5 分） void main { int count, n, i, j, k; cout > n; nodelist euler= new vertex[n]; //创建邻接表数组 ① 2 ① 2 ① 2 ① 2 ① 2 ① 2 ① 2 ① 2 ① 2 ① 2 ① 2 ① 2 ∧ ∧ ∧ 1 A ∧ 2 B 3 C 4 D visited ① ② ③ ④ ⑤ ⑥ nodelist
for int i=0;i euler[i].city; euler[i]. first= NULL; cout1>>j>>k>>; ∥是边号码,k是顶点 while (il=0)i ∥为0,表示输入结束 edgenode p= new edgenode; ∥链入第j号链表 p-link =euler[]. first; euler[i] first=p; edgenode p= new edgenode; 链入第k号链表 p->edgeno=i; p->adjvertex p->link =euler[k]. first; euler[k] first=p cin>>1>>J>>k>>; int *visited=new int[ count ] ∥)创建访问标志数组 for (1=0; ilink 查下一条关联的边; ∥计算该顶点的度 f( count %21=0) cout<<“顶点的度不为偶数,此题无解!”<<end;exit(1);} dfs( euler, 0, n, visited ) ∥从0号顶点开始 delete visited } 三、解答 (1)输入的n个数据全部有序: (5分) n个数据全部有序时 10203040 第一趟比较4次,移动8次 1020}{3040}{5060}{70 第二趟比较4次,移动8次 10203040}{506070 第三趟比较4次,移动8次 1020304050607080} 一般地,n个数据全部有序时,每一趟数据比较Ln/2」次,移动n次,共「og2n]趟,总数据比较次 数与移动次数为 O(nlog2n)次
7 for ( int i = 0; i > euler[i].city; euler[i].first = NULL; } cout > i >> j >> k >>; //i 是边号码，j, k 是顶点 while ( i != 0 ) { //i 为 0, 表示输入结束 edgenode * p = new edgenode; //链入第 j 号链表 p->edgeno = i; p->adjvertex = k; p->link = euler[j].first; euler[j].first = p; edgenode * p = new edgenode; //链入第 k 号链表 p->edgeno = i; p->adjvertex = j; p->link = euler[k].first; euler[k].first = p; cin >> i >> j >> k >>; count++; } int *visited = new int[count]; //创建访问标志数组 for ( i = 0; i link; //查下一条关联的边; } //计算该顶点的度 if ( count % 2 != 0 ) { cout << “顶点的度不为偶数, 此题无解！” << endl; exit(1); } } dfs ( euler, 0, n, visited ); //从 0 号顶点开始 delete [ ] visited; } 三、解答 (1) 输入的 n 个数据全部有序： （5 分） n 个数据全部有序时，如 {10 20 30 40 50 60 70 80} {10} {20} {30} {40} {50} {60} {70} {80} 第一趟比较 4 次，移动 8 次 {10 20} {30 40} {50 60} {70 80} 第二趟比较 4 次，移动 8 次 {10 20 30 40} {50 60 70 80} 第三趟比较 4 次，移动 8 次 {10 20 30 40 50 60 70 80} 一般地，n 个数据全部有序时，每一趟数据比较 n/2 次，移动 n 次，共 log2n 趟，总数据比较次 数与移动次数为 O(nlog2n)次
(2)输入的n个数据全部逆向有序 (5分) n个数据全部逆向有序时,如 8070605040302010} {80}{70}{60}{50}{40}{30}{20}{10}第一趟比较4次,移动8次 7080}{5060}{3040}{1020} 第二趟比较4次,移动8次 50607080}{10203040} 第三趟比较4次,移动8次 般地,n个数据全部逆序时,每一趟数据比较Ln/2」次,移动n次,共「logn]趟,总数据比较次 数与移动次数为 O(nlog2n)次 (3)随机的输入n个数据 (5分) 随机输入n个数据时,如 {30}{70}{50}{80}{40}{10}{60}{20}第一趟比较4次,移动8次 3070}{5080}{1040}{2060} 第二趟比较6次,移动8次 30507080}{10204060} 三趟比较7次,移动 一般地,n个数据随机输入时,每一趟数据比较n-l次,移动n次,共「logn]趟,总数据比较次数 与移动次数为 O(nlog2n)次。 四、解答 (1)有N个结点的AVL树的高度不超过 k lo g +1) 假设为表示k需要m位,则有 20+21+…+2m<k (5分) (2)若每一个结点中的高度计数器有m=8,有9<log(k+1),那么这样的AVL树可以有h=29-1层, 最少有Fh+3-1个关键码? (5分) 五、解答 设散列表大小 hashS ize=13,其下标从0到12,采用线性探查法解决冲突。则对于以下关键码 3245581263292004000 (1)散列函数hash(key)=key% hashSize hash(10)=10%13=10 100)=100% ash(32)=32%13=6 45)=45%13=6(冲突)=7 hash(58)=58%13=6(冲突)=7(冲突)=8 hash(126)=126%13=9(沖突)=10(冲突)=11 hash(3)=3%13=3 hash(29)=29%13=3(冲突)=4 hash(200)=200%13=5 hash(400)=10(冲突)=11(冲中突)=12 hash(0)=0%13=0
8 (2) 输入的 n 个数据全部逆向有序； （5 分） n 个数据全部逆向有序时，如 {80 70 60 50 40 30 20 10} {80} {70} {60} {50} {40} {30} {20} {10} 第一趟比较 4 次，移动 8 次 {70 80} {50 60} {30 40} {10 20} 第二趟比较 4 次，移动 8 次 {50 60 70 80} {10 20 30 40} 第三趟比较 4 次，移动 8 次 {11 20 30 40 50 60 70 80} 一般地，n 个数据全部逆序时，每一趟数据比较 n/2 次，移动 n 次，共 log2n 趟，总数据比较次 数与移动次数为 O(nlog2n)次。 (3) 随机的输入 n 个数据。 （5 分） 随机输入 n 个数据时，如 {30 70 50 80 40 10 60 20} {30} {70} {50} {80} {40} {10} {60} {20} 第一趟比较 4 次，移动 8 次 {30 70} {50 80} {10 40} {20 60} 第二趟比较 6 次，移动 8 次 {30 50 70 80} {10 20 40 60} 第三趟比较 7 次，移动 8 次 {12 20 30 40 50 60 70 80} 一般地，n 个数据随机输入时，每一趟数据比较 n-1 次，移动 n 次，共 log2n 趟，总数据比较次数 与移动次数为 O(nlog2n)次。 四、解答 (1) 有 N 个结点的 AVL 树的高度不超过 假设为表示 k 需要 m 位，则有 2 0 + 21 + … + 2m < k 2 m+1 –1 < k m < log2(k+1) – 1 （5 分） (2) 若每一个结点中的高度计数器有 m = 8，有 9 < log2(k+1)，那么这样的 AVL 树可以有 h = 2 9 -1 层， 最少有 Fh+3-1 个关键码？ （5 分） 五、解答： 设散列表大小 hashSize = 13，其下标从 0 到 12，采用线性探查法解决冲突。则对于以下关键码： 10 100 32 45 58 126 3 29 200 400 0 (1) 散列函数 hash(key) = key % hashSize hash(10) = 10 % 13 = 10 hash(100) = 100 % 13 = 9 hash(32) = 32 % 13 = 6 hash(45) = 45 % 13 = 6 (冲突) = 7 hash(58) = 58 % 13 = 6 (冲突) = 7 (冲突) = 8 hash(126) = 126 % 13 = 9 (冲突) = 10 (冲突) = 11 hash(3) = 3 % 13 = 3 hash(29) = 29 %13 = 3 (冲突) =4 hash(200) = 200 % 13 = 5 hash(400) = 10 (冲突) = 11(冲突) = 12 hash(0) = 0 % 13 = 0 log (n 1) 2 3 k = 2 +
3 9101112 32920032455810010126400 一次冲突的有45,29;二次冲突的有58,126,400。 (7分) (2)散列函数采用先将关键码各位数字折叠相加,再用% ohashSize将相加的结果映像到表中的办法 关键码:101003245581263292004000 hash(10)=(1+0)%13=1,hash(100)=(1+0+0)%13=1(冲突)=2 hash(32)=(3+2)%13=5, sh(45)=(4+5)%13=9, hash(58)=(5+8)%13=0, hash(126)=(1+2+6)%13=9(冲突)=10 hash(3)=3%13=3, hash(29)=(2+9)%13=11, (冲突)=3(冲突) hash(400=(40+0)%13=4(沖突)=5(冲突)=6, 0)=0(冲突)=1(冲突)=2(冲突 =6(冲突)=7 58101003200324000 4512629 次冲突的有100,126:二次冲突的有200,400:冲突7次的有0。(8分) 六、解答①push(s,p); ke (每空3分) ③ p ch; 七解答 (1)三者取中子程序 median?(a, left right))取基准记录 pivot采用从le, right和mid=「( left+ right)/21 中取中间值,并交换到 right位置的办法 (5分) void median( Type a[], int left, int right )( int mid =( left+right+ 1)/2; int k= left f(ahigh<a[k])k=high ∥选最小记录 Type temp=ak];ak]=altl; a[ left=temp;∥最小者交换到left if( a(mid]<a[right]) f temp=a(mid]; amid]=a[right a[right] (2)消去第二个递归调用 quicksort(a,计+1, right)。采用循环的办法。(5分) void quicksort(Type a[l, int left, int right)( Type temp; int L,J; while(left right)& Type pivot=median(a, left, right); ∥三者取中子程序 i=left; j=right-1
9 一次冲突的有 45，29；二次冲突的有 58，126，400。 （7 分） (2) 散列函数采用先将关键码各位数字折叠相加，再用 %hashSize 将相加的结果映像到表中的办法。 关键码： 10 100 32 45 58 126 3 29 200 400 0 hash(10) = (1+0) % 13 = 1, hash(100) = (1+0+0) % 13 = 1 (冲突) = 2, hash(32) = (3+2) % 13 = 5, hash(45) = (4+5) % 13 = 9, hash(58) = (5+8) % 13 = 0, hash(126) = (1+2+6) % 13 = 9 (冲突) = 10, hash(3) = 3 % 13 = 3, hash(29) = (2+9) % 13 = 11, hash(200) = (2+0+0) % 13 = 2 (冲突) = 3 (冲突) = 4, hash(400) = (4+0+0) % 13 = 4 (冲突) = 5 (冲突) = 6, hash(0) = 0 (冲突) = 1 (冲突) = 2 (冲突) = … = 6 (冲突) = 7. 一次冲突的有 100，126；二次冲突的有 200，400；冲突 7 次的有 0。（8 分） 六、解答 ① push(s, p); ② k=2; （每空 3 分） ③ p->data = ch; ④ Bt = p; ⑤ ins >> ch; 七解答： (1) 三者取中子程序median3(a, left, right) 取基准记录pivot采用从left, right和mid = ( left + right ) / 2 中取中间值，并交换到 right 位置的办法。 （5 分） void median3( Type a[ ], int left, int right ) { int mid = ( left + right + 1 ) / 2; int k = left; if ( a[mid] < a[k] ) k = mid; if ( a[high] < a[k] ) k = high; //选最小记录 Type temp = a[k]; a[k] = a[left]; a[left] = temp; //最小者交换到 left if ( a[mid] < a[right] ) { temp = a[mid]; a[mid] = a[right]; a[right] = temp; } } (2) 消去第二个递归调用 quicksort (a, i+1, right)。采用循环的办法。（5 分） void quicksort (Type a[ ], int left, int right) { Type temp; int i, j; while (left < right) { Type pivot = median3 (a, left, right); //三者取中子程序 i = left; j = right-1; for ( ; ; ) { 0 1 2 3 4 5 6 7 8 9 10 11 12 0 3 29 200 32 45 58 100 10 126 400 0 1 2 3 4 5 6 7 8 9 10 11 12 58 10 100 3 200 32 400 0 45 126 29
while(ipivot)( aright]=a[j]: a[]=pivot; 3 quicksort(a, left, 1-1); ∥递弟归排序左子区间 (3)继续改写 quicksort算法,消去剩下的递归调用。 (5分) 为实现非递归算法,需要用到一个栈s,暂存右半个区间。栈结点定义如下。 struct stkNode i int I 区间左端点 int 区间右端点 void quicksort(Type a[l, int n)( stack s; stkNode w; Type temp; left=0; right=wlow =w high=n-1; push(S, w); while(left right)i Type pivot= median(a, left, right ∥三者取中子程序 int i=left, j=right-1; for(;;){ while(i<j&& a[i]< pivot)++ while (i<j&& pivot <aDj- f(1<){ temp =a[i: ajl=ai: al=temp; H++;J else break temp=ai: a[i]=a[right]; a[right]=temp: if( left <i-1)(w low= left; w high=1-1; push(s, w): 1 ∥在区间存在不止一个元素,进栈 if(i+1< right)left=i+1;∥右区间存在不止一个元素,排序右区间 lse if(!lsEmpty (s)) 则退栈,取保存的待排序区间 (w=top(s); pop(s); left=w low; right=w high 1
10 while (i pivot ) { a[right] = a[i]; a[i] = pivot; } quicksort (a, left, i -1); //递归排序左子区间 left = i+1; } } (3) 继续改写 quicksort 算法，消去剩下的递归调用。 （5 分） 为实现非递归算法，需要用到一个栈 s，暂存右半个区间。栈结点定义如下。 struct stkNode { int low; //区间左端点 int high; //区间右端点 } void quicksort (Type a[ ], int n ) { stack s; stkNode w; Type temp; left = 0; right = w.low = w.high = n-1; push ( s, w ); while (left < right) { Type pivot = median3 (a, left, right); //三者取中子程序 int i = left, j = right-1; for ( ; ; ) { while (i < j && a[i] < pivot) i++; while (i < j && pivot < a[j]) j--; if (i < j) { temp = a[i]; a[j] = a[i]; a[i] = temp; i++; j--; } else break; } temp = a[i]; a[i] = a[right]; a[right] = temp; if ( left < i-1 ) { w.low = left; w.high = i-1; push(s, w); } //左区间存在不止一个元素，进栈 if (i+1 < right) left = i+1; //右区间存在不止一个元素，排序右区间 else if ( !IsEmpty(s) ) //否则退栈，取保存的待排序区间 { w = top(s); pop(s); left = w.low; right = w.high } }