一、试给出下列有关并查集(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分） 五、设一个散列表包含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; } 现采用输入广义表表示建立二叉树。具体规定如下： 树的根结点作为由子树构成的表的表名放在表的最前面； (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) 存取栈顶元素的函数 下面给出了建立二叉树的算法，其中有5个语句缺失。请阅读此算法并把缺失的语句补上。 （每空3分） void CreateBinTree(BinTreeNode *& BT, char ls) { Stack<BinTreeNode *> 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采用从left, right和mid = (( left + right ) / 2( 中取中间值，并交换到right位置的办法。数组a存放待排序的一组记录，数据类型为Type，left和right是待排序子区间的最左端点和最右端点。 void quicksort (Type a[ ], int left, int right) { Type temp; if (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; } if ( a[i] > 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分） 改写quicksort算法，不用栈消去第二个递归调用 quicksort (a, i+1, right); （5分） (3) 继续改写quicksort算法，用栈消去剩下的递归调用。 （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条边未访问过，一旦访问了第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 << euler[start].city << ‘ -> ’; //输出顶点数据 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 << “输入顶点数 ：” ; cin >> n; nodelist euler= new vertex[n]; //创建邻接表数组 for ( int i = 0; i < n; i++) { //输入顶点数据, 指针置空 cin >> euler[i].city; euler[i].first = NULL; } cout << “输入各条边！” << endl; //输入各边数据 count = 0; //边计数 cin >> 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 < count; i++) visited[i] = 0; for ( i = 0; i < n; i++ ) { //判断各个顶点的度是否偶数 count = 0; p = euler[start].first; //找第一条关联的边 while ( p != NULL ) { //有 count++; p = p->link; //查下一条关联的边; } //计算该顶点的度 if ( count % 2 != 0 ) { cout << “顶点的度不为偶数, 此题无解！” << endl; exit(1); } } dfs ( euler, 0, n, visited ); //从0号顶点开始 delete [ ] visited; } 三、解答 输入的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次 20 30 40 50 60 70 80} 一般地，n个数据全部有序时，每一趟数据比较 (n/2( 次，移动n次，共 (log2n( 趟，总数据比较次数与移动次数为O(nlog2n)次。 (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次 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次 20 30 40 50 60 70 80} 一般地，n个数据随机输入时，每一趟数据比较n-1次，移动n次，共 (log2n( 趟，总数据比较次数与移动次数为O(nlog2n)次。 四、解答 有N个结点的AVL树的高度不超过 假设为表示k需要m位，则有 20 + 21 + … + 2m < k 2m+1 –1 < k ( m < log2(k+1) – 1 （5分） (2) 若每一个结点中的高度计数器有m = 8，有 9 < log2(k+1)，那么这样的AVL树可以有h = 29 -1层，最少有Fh+3-1个关键码？ （5分） 五、解答： 设散列表大小hashSize = 13，其下标从0到12，采用线性探查法解决冲突。则对于以下关键码： 10 100 32 45 58 126 3 29 200 400 0 散列函数 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 一次冲突的有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 ( ; ; ) { 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; } if ( a[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<stkNode> 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 } } } （5分）